Finding the limit: examining the potential and complexity of compilation scheduling for jit-based runtime systems

This work aims to find out the full potential of compila-tion scheduling for JIT-based runtime systems. Compila-tion scheduling determines the order in which the compi-lation units (e.g., functions) in a program are to be compiled or recompiled. It decides when what versions of the units are ready to run, and hence affects performance. But it has been a largely overlooked direction in JIT-related research, with some fundamental questions left open: How significant compilation scheduling is for performance, how good the scheduling schemes employed by existing runtime systems are, and whether a great potential exists for improvement. This study proves the strong NP-completeness of the prob-lem, proposes a heuristic algorithm that yields near optimal schedules, examines the potential of two current scheduling schemes empirically, and explores the relations with JIT de-signs. It provides the first principled understanding to the complexity and potential of compilation scheduling, shed-ding some insights for JIT-based runtime system improve-ment