36.2 The Just-In-Time Compiler

Java’s Just-In-Time Compiler secretly optimizes your code when it runs.
  • The code you write is not necessarily the code that executes!
  • As your code runs, the “interpreter” is watching everything that happens.
    • If some segment of code is called many times, the interpreter actually studies and re-implements your code based on what it learned by watching WHILE ITS RUNNING (!!).
      • Example: Performing calculations whose results are unused.
      • See this video if you’re curious.

JIT Example

The code below creates Linked Lists, 1000 at a time.
  • Repeating this 500 times yields an interesting result.
  • First optimization: Not sure what it does.
  • Second optimization: Stops creating linked lists since we’re not actually using them.

… So Which is Better? MSD or MergeSort?

The performance of the merge sort algorithm is highly dependent on the presence of just-in-time (JIT) compilation. Specifically, when JIT is enabled, merge sort is faster in cases where the strings being sorted are equal, but slower when JIT is disabled. This suggests that merge sort is generally more effective for this specific case, given that JIT is typically enabled. However, there are numerous other scenarios to consider, including the sorting of almost equal strings, randomized strings, and real-world data from specific datasets. When assessing the effectiveness of merge sort for these alternative cases, it is important to conduct careful experimentation and profiling to determine which sorting algorithm is most suitable. The lectureCode repository provides code for running these experiments, allowing for more precise assessment of algorithm performance under various conditions. Ultimately, real-world applications will require a thorough analysis of different implementations on actual data in order to select the optimal algorithm for the task at hand.

Bottom Line: Algorithms Can Be Hard to Compare

Comparing algorithms that have the same order of growth can be a difficult task, as it requires conducting computational experiments to determine their relative performance. However, modern programming environments can introduce additional challenges to this process, as certain optimizations such as just-in-time (JIT) compilation in Java can impact the results of experiments. It is worth noting that even small optimizations to an algorithm can have a significant impact on its performance. For instance, a change to the Quicksort algorithm suggested by Vladimir Yaroslavskiy has been shown to provide notable improvements, as discussed briefly in the Quicksort lecture. Therefore, when comparing algorithms with similar growth rates, it is crucial to remain vigilant of potential optimizations and variations that may influence their performance.

JIT Compilers Are Always Evolving

The JIT (just-in-time) compiler is a highly complex and essential component of modern compilers, and is an active area of research and development in this field. However, the older JIT compiler known as C2 has become increasingly difficult to maintain and extend, with no major improvements implemented in recent years. The codebase for C2 is written in a specific dialect of C++, making it challenging for new engineers to understand and work with. As a result, the codebase is being abandoned in favor of newer and more maintainable alternatives. For individuals interested in this area of study, CS164 offers a course on compilers and there are opportunities for involvement in ongoing research. It is worth noting that the reasons for the improved performance of merge sort with the JIT are not yet fully understood, making it an interesting topic for further research.