{"id":230058,"date":"2023-08-21T16:05:22","date_gmt":"2023-08-21T23:05:22","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/java\/?p=230058"},"modified":"2023-08-21T16:24:55","modified_gmt":"2023-08-21T23:24:55","slug":"how-tiered-compilation-works-in-openjdk","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/java\/how-tiered-compilation-works-in-openjdk\/","title":{"rendered":"How Tiered Compilation works in OpenJDK"},"content":{"rendered":"

The OpenJDK HotSpot runtime system is a complex piece of software that employs several techniques to optimize the execution of Java programs on the fly. The system is composed of two different compilers, one interpreter and several different Garbage Collectors, among several other components. These compilers are orchestrated in a tiered compilation mechanism which tries to use the most suitable compiler for each method.\u00a0<\/span>\u00a0<\/span><\/p>\n

HotSpot has the critical goal of generating efficient machine code while keeping the runtime cost at a minimum. To achieve that it employs various strategies, such as tiered compilation, dynamic profiling, speculation, deoptimization, and various compiler optimizations, both architecturally dependent and independent. In this post, we will delve into the motivation behind tiered compilation and understand how it works.<\/span>\u00a0<\/span>\u00a0<\/span><\/p>\n

The Right Tool for The Job<\/span><\/b>\u00a0<\/span><\/p>\n

The basic idea behind tiered compilation is that most of the execution time of a program is spent on a small part of the code (i.e., a few methods). Furthermore, the cost to compile a method (i.e., CPU cycles) is the same whether it executes only once or a million times. Based on these observations the VM is designed to use a “simple compiler” for methods that do not execute “many times”, i.e., <\/span>cold methods<\/span><\/i>, and use a more “optimizing” compiler for methods that run “a lot”, i.e., <\/span>hot methods<\/span><\/i>. The rationale is as follows:<\/span>\u00a0<\/span><\/p>\n

    \n
  1. We do not want to spend too many CPU cycles compiling a method that is going to be executed only once. In other words, we do not want to spend more cycles compiling a method than executing it!<\/span>\u00a0<\/span><\/li>\n<\/ol>\n
      \n
    1. If a method executes a sufficiently high number of times the cost of compiling it <\/span>plus<\/span><\/i><\/b> the cost of running it, in an <\/span>optimized <\/span><\/i>form, will be lower than the cost of running it in an <\/span>unoptimized<\/span><\/i> form.<\/span>\u00a0<\/span><\/li>\n<\/ol>\n

      Let us use some <\/span>hypothetical<\/span><\/i><\/b> values to exemplify the points above. Consider a VM that has three different compilers: <\/span>Comp1<\/span>, <\/span>Comp2<\/span>, <\/span>Comp3<\/span>. Each of these compilers is slower than the previous one to produce code, but the actual generated code is better than the one produced by the previous compiler. <\/span>Comp1<\/span> is a fast and simple compiler that produces “slow code”. <\/span>Comp2<\/span> is slower than <\/span>Comp1, <\/span>but it produces slightly “faster code”. <\/span>Comp3<\/span> is a compiler that produces very efficient code, but it is much slower than <\/span>Comp1<\/span> and <\/span>Comp2<\/span>.<\/span>\u00a0<\/span><\/p>\n

      Based on these descriptions, suppose we have the values shown in the table below for the compilation of a random method. The <\/span>Compilation<\/span><\/i> column shows the cost, as the number of CPU cycles to compile the method. The <\/span>Cycle Count<\/span><\/i> column shows the number of cycles the code produced for the method takes to execute.<\/span>\u00a0<\/span><\/p>\n\n\n\n\n\n\n
      Compiler<\/span><\/b>\u00a0<\/span><\/td>\nCompilation<\/span><\/b>\u00a0<\/span><\/td>\nCycle Count<\/span><\/b>\u00a0<\/span><\/td>\n<\/tr>\n
      Comp1<\/span>\u00a0<\/span><\/td>\n1<\/span>\u00a0<\/span><\/td>\n50<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
      Comp2<\/span>\u00a0<\/span><\/td>\n10<\/span>\u00a0<\/span><\/td>\n30<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
      Comp3<\/span>\u00a0<\/span><\/td>\n100<\/span>\u00a0<\/span><\/td>\n10<\/span>\u00a0<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      These values mean that <\/span>Comp1<\/span> can compile the method 100x faster than <\/span>Comp3<\/span>, however the produced code will execute 5x slower. The table below shows the <\/span>total number of CPU cycles necessary to compile and execute the method<\/span><\/i> in four different scenarios: A) The method executes only once; B) The method executes one hundred times; C) The method executes 1000 times and, D) The method executes 1,000,000 times.<\/span>\u00a0<\/span><\/p>\n\n\n\n\n\n\n
      Compiler<\/span><\/b>\u00a0<\/span><\/td>\nA<\/span><\/b>\u00a0<\/span><\/td>\nB<\/span><\/b>\u00a0<\/span><\/td>\nC<\/span><\/b>\u00a0<\/span><\/td>\nD<\/span><\/b>\u00a0<\/span><\/td>\n<\/tr>\n
      Comp1<\/span>\u00a0<\/span><\/td>\n51<\/span>\u00a0<\/span><\/td>\n5,001<\/span>\u00a0<\/span><\/td>\n50,001<\/span>\u00a0<\/span><\/td>\n50,000,001<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
      Comp2<\/span>\u00a0<\/span><\/td>\n40<\/span>\u00a0<\/span><\/td>\n3,010<\/span>\u00a0<\/span><\/td>\n30,010<\/span>\u00a0<\/span><\/td>\n30,000,010<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
      Comp3<\/span>\u00a0<\/span><\/td>\n110<\/span>\u00a0<\/span><\/td>\n1,100<\/span>\u00a0<\/span><\/td>\n10,100<\/span>\u00a0<\/span><\/td>\n10,000,100<\/span>\u00a0<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      If we use <\/span>Comp1<\/span> in Scenario A, the total number of cycles to compile and execute the method would be 51 (1 to compile + 50 to execute once). If we use <\/span>Comp2<\/span> for this same scenario the total number of cycles would have been 40 (10 cycles to compile the method + 30 to execute it once). If, on the other hand, we use <\/span>Comp3<\/span> the total number of cycles would be 110 (100 to compile + 10 to execute once). Therefore, the best compiler, if the method is executed only once, is <\/span>Comp2<\/span>.<\/span>\u00a0<\/span><\/p>\n

      In scenario D, if we use <\/span>Comp1<\/span> the total number of cycles would be 50,000,001 (1 to compile the method and 50,000,000 to execute). If we use <\/span>Comp3<\/span> in this scenario, the total number of cycles would be 10,000,100 (100 cycles to compile the method and 10,000,000 to execute it 1,000,000 times).<\/span>\u00a0<\/span><\/p>\n

      As you can see, the numbers are quite different depending on the compiler that is used and\/or the number of times the method executes. In other words, the best compiler for compiling the method depends on how many times the method is going to execute. In the next section, we will look at how to “predict” (or guess) how many times a method will execute.<\/span>\u00a0<\/span><\/p>\n

      Hot Code Prediction<\/span><\/b>\u00a0<\/span><\/p>\n

      In the previous section I intentionally used terms like “a lot”, “simple”, etc. In this section I explain exactly what I mean by each of them.<\/span>\u00a0<\/span><\/p>\n

      By a \u201csimple\u201d compiler, I mean one that can produce code quickly (i.e., the compilation cost is not large) but there is no stringent requirement for the machine code produced to be the most efficient possible. On the other hand, a sophisticated compiler (sometimes called an <\/span>optimizing compiler<\/span><\/i>) is one that employs many optimizations, aiming to produce the most efficient machine code possible. As you can imagine, the compilation cost is different for the two compilers. Also, note that we do not have to settle with just the two extremes, we can employ a range of different compilers with different capabilities, or we can just use the same compiler but run a different list of optimizations for different pieces of code (like GCC or Clang with the distinct levels of optimization).<\/span>\u00a0<\/span><\/p>\n

      We saw in the previous section that the number of times a method executes is a crucial factor in deciding which compiler to use. Baked in our example was the assumption that we know how many times a method is going to execute <\/span>before<\/span><\/i> we even compile it, because we are going to use that information to decide how to compile it.<\/span>\u00a0<\/span><\/p>\n

      Now, how do we tell, before we even compile a method, whether it is going to execute “many times” or not? What is “many times”? The answer is: we cannot \u2013 sort of! The problem that we are trying to solve is a version of an important [undecidable] problem in Computer Science – <\/span>The Halting Problem<\/span><\/a>. What we do in practice is find a workaround for the problem: we assume the method is cold and compile it using the simple compiler and then execute the method a few times, let us say <\/span>N<\/span>. <\/span>If the method is executed <\/span><\/i>N<\/span> times, we assume that it will execute at least <\/span><\/i>N<\/span><\/i> more times in the future<\/span><\/i> – and therefore is a hot method. If the method does not even reach <\/span>N<\/span> executions, then it is a cold method, and we already used the right compiler for it – the simple one. In other words, we use threshold <\/span>N<\/span> to find when a method <\/span>has become<\/span><\/i> hot, and we use that as an indicator that the method will continue to be hot in the future.<\/span>\u00a0<\/span><\/p>\n

      The question then is how to choose the value of the threshold <\/span>N<\/span>. If we make <\/span>N = 1<\/span><\/i> there is a good chance our assumption (the method will execute <\/span>N<\/span> more times) will hold most of the time, however that does not help much to find methods that are hot. If we make <\/span>N = 1,000,000 <\/span><\/i>we increase our chance of finding real hot methods, <\/span>but<\/span><\/i> we also increase the probability that our assumption – that the method will execute N more times \u2013 will be false. Moreover, we executed a method compiled with the simple compiler <\/span>1,000,000 <\/span>times.<\/span>\u00a0<\/span><\/p>\n

      In practice what we do is we choose <\/span>N<\/span> based on empirical evidence. We consider, among other things, the compilation costs, the performance of the code produced by our compilers, the kind of workload that we have, how many compilers do we have, etc., and try to produce an educated guess for the threshold. There is hardly an ideal threshold that will work for every situation. For instance, there are programs where the execution is more spread throughout the source code (e.g., GUI programs) and other programs where the execution is much more limited to a small part of the source code (e.g., scientific programs or <\/span>benchmarks<\/span><\/i>). The behavior of a program might even go through phases where different portions of the code become hot at different moments.<\/span>\u00a0<\/span><\/p>\n

      In the next section we are going to take a quick look at how HotSpot deals with this problem.<\/span>\u00a0<\/span><\/p>\n

      Tiered Compilation in HotSpot<\/span><\/b>\u00a0<\/span><\/p>\n

      As we will see, the Tiered Compilation process in HotSpot is a very elaborate process, but the idea is still the same one that we discussed in the previous section: use the best tool for the job.<\/span>\u00a0<\/span><\/p>\n

      HotSpot has 2 compilers, C1 (<\/span>source<\/span> here<\/span><\/a>) and C2 (<\/span>source here<\/span><\/a>), and an interpreter. There may be multiple threads executing each compiler and the number of such threads is adjusted dynamically based on the load of the system. That means that several methods may be compiled <\/span>concurrently<\/span><\/i>. Furthermore, the execution of a method may continue uninterrupted in its current form while another version of the method is being compiled. The compiler threads act upon two priority queues, one for each compiler, containing Compilation Tasks (<\/span>source here<\/span><\/a>) that describe, among other things, which method should be compiled.<\/span>\u00a0<\/span><\/p>\n

      The two compilers in different configurations are combined with the interpreter to produce a total of five distinct optimization levels:<\/span>\u00a0<\/span><\/p>\n\n\n\n\n\n\n\n\n
      Level<\/span><\/b>\u00a0<\/span><\/td>\nCompiler<\/span><\/b>\u00a0<\/span><\/td>\n<\/tr>\n
      0<\/span>\u00a0<\/span><\/td>\nInterpreter<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
      1<\/span>\u00a0<\/span><\/td>\nC1 without profiling<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
      2<\/span>\u00a0<\/span><\/td>\nC1 with basic profiling<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
      3<\/span>\u00a0<\/span><\/td>\nC1 with full profiling<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
      4<\/span>\u00a0<\/span><\/td>\nC2 full optimizing, no profiling<\/span>\u00a0<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      Normally the execution of a method starts in the <\/span>interpreter,<\/span><\/i> which is the simplest\/cheapest mechanism that HotSpot has available to execute code. During the execution of the method via interpretation, or in compiled form, the dynamic profile of the method is collected using <\/span>instrumentation<\/span><\/i>. The method\u2019s profile is then used by several heuristics that will decide, among other things, if the method should be compiled, recompiled at a different level, which optimizations should be performed, etc.\u00a0<\/span>\u00a0<\/span><\/p>\n

      The two most fundamental pieces of information collected by HotSpot during the execution of a method are how many times the method has been executed and how many times the loops in a method have iterated. That information is used by a Compilation Policy (<\/span>source here<\/span><\/a>) to decide whether to compile a method or not, and at which level. HotSpot also has a feature called On-Stack-Replacement (OSR) that makes it possible to compile hot loops independently of their containing method. This is an interesting feature to work around cases where a hot loop is inside a method that has not itself become hot.<\/span>\u00a0<\/span><\/p>\n

      The following formula (see source <\/span>here<\/span><\/a> and <\/span>here<\/span><\/a>) is used by the Compilation Policy to decide whether to create a compilation request at level 3, for a method that is currently being interpreted. The same formula is used to decide if a request should be created to compile a method at level 4 if the method is currently executing as a level 3 compilation. A similar formula is used to control OSR compilations.<\/span>\u00a0<\/span><\/p>\n

      (Executions > TierXInvocationThreshold * Scale)<\/span><\/p><\/blockquote>\n

      OR\u00a0<\/span><\/b>\u00a0<\/span><\/p>\n

      (Executions\u00a0> TierXMinInvocationThreshold * Scale\u00a0<\/span>AND <\/span><\/b>Executions + Iterations > TierXCompileThreshold * Scale)<\/span>\u00a0<\/span><\/p><\/blockquote>\n

      Where:<\/span>\u00a0<\/span><\/p>\n