{"id":32451,"date":"2021-03-25T12:58:16","date_gmt":"2021-03-25T19:58:16","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/dotnet\/?p=32451"},"modified":"2021-09-29T12:15:42","modified_gmt":"2021-09-29T19:15:42","slug":"loop-alignment-in-net-6","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/loop-alignment-in-net-6\/","title":{"rendered":"Loop alignment in .NET 6"},"content":{"rendered":"

When writing a software, developers try their best to maximize the performance they can get from the code they have baked into the product. Often, there are various tools available to the developers to find that last change they can squeeze into their code to make their software run faster. But sometimes, they might notice slowness in the product because of a totally unrelated change. Even worse, when measured the performance of a feature in a lab, it might show instable performance results that looks like the following\u00a0BubbleSort<\/strong>\u00a0graph1<\/sup>. What could possibly be introducing such flakiness in the performance?<\/p>\n

\"Instable<\/p>\n

 <\/p>\n

To understand this behavior, first we need to understand how the machine code generated by the compiler is executed by the CPU. CPU\u00a0fetch<\/em>\u00a0the machine code (also known as instruction stream) it need to execute. The instruction stream is represented as series of bytes known as opcode. Modern CPUs\u00a0fetch<\/em>\u00a0the opcodes of instructions in chunks of 16-bytes (16B), 32-bytes (32B) or 64-bytes (64B). The CISC architecture has variable length encoding, meaning the opcode representing each instruction in the instruction stream is of variable length. So, when the Fetcher fetches a single chunk, it doesn’t know at that point the start and end of an instruction. From the instruction stream chunk, CPU’s Pre-decoder identifies the boundary and lengths of instruction, while the Decoder decodes the meaning of the opcodes of those individual instructions and produce micro-operations (\u03bcops<\/code>) for each instruction. These\u00a0\u03bcops<\/code>\u00a0are fed to the Decoder Stream Buffer (DSB) which is a cache that indexes\u00a0\u03bcops<\/code>\u00a0with the address from where the actual instruction was fetched. Before doing a\u00a0fetch<\/em>, CPU first checks if the DSB contains the\u00a0\u03bcops<\/code>\u00a0of the instruction it wants to fetch. If it is already present, there is no need to do a cycle of instruction fetching, pre-decoding and decoding. Further, there also exist Loop Stream Detector (LSD) that detects if a stream of\u00a0\u03bcops<\/code>\u00a0represents a loop and if yes, it skips the front-end fetch and decode cycle and continue executing the\u00a0\u03bcops<\/code>\u00a0until a loop misprediction happens.<\/p>\n

<\/a>Code alignment<\/h2>\n

Let us suppose we are executing an application on a CPU that fetches instruction in 32B chunks. The application has a method having a hot loop inside it. Every time the application is run, the loop’s machine code is placed at different offset. Sometimes, it could get placed such that the loop body does not cross the 32B address boundary. In those cases, the instruction fetcher could fetch the machine code of the entire loop in one round. On the contrary, if the loop’s machine code is placed such that the loop body crosses the 32B boundary, the fetcher would have to fetch the loop body in multiple rounds. A developer cannot control the variation in fetching time because that is dependent on where the machine code of the loop is present. In such cases, you could see instability in the method’s performance. Sometimes, the method runs faster because the loop was aligned at fetcher favorable address while other times, it can show slowness because the loop was misaligned and fetcher spent time in fetching the loop body. Even a tiny change unrelated to the method body (like introducing a new class level variable, etc.) can affect the code layout and misalign the loop’s machine code. This is the pattern that can be seen in bubble sort benchmark above. This problem is mostly visible in CISC architectures because of variable length encoding of the instructions. The RISC architectures CPUs like Arm have fixed length encoding and hence might not see such a large variance in the performance.<\/p>\n

To solve this problem, compilers perform alignment of the hot code region to make sure the code’s performance remains stable. Code alignment is a technique in which one or more\u00a0NOP<\/code>\u00a0instructions are added by the compiler in the generated machine code just before the hot region of the code so that the hot code is shifted to an address that is\u00a0mod(16)<\/code>,\u00a0mod(32)<\/code>\u00a0or\u00a0mod(64)<\/code>. By doing that, maximum fetching of the hot code can happen in fewer cycles. Study shows that by performing such alignments, the code can benefit immensely. Additionally, the performance of such code is stable since it is not affected by the placement of code at misaligned address location. To understand the code alignment impact in details, I would highly encourage to watch the\u00a0Causes of Performance Swings due to Code Placement in IA<\/a>\u00a0talk given by Intel’s engineer Zia Ansari at 2016 LLVM Developer’s Meeting.<\/p>\n

In .NET 5, we started\u00a0aligning methods at 32B boundary<\/a>. In .NET 6, we have added a feature to\u00a0perform adaptive loop alignment<\/a>\u00a0that adds\u00a0NOP<\/code>\u00a0padding instructions in a method having loops such that the loop code starts at\u00a0mod(16)<\/code>\u00a0or\u00a0mod(32)<\/code>\u00a0memory address. In this blog, I will describe the design choices we made, various heuristics that we accounted for and the analysis and implication we studied on 100+ benchmarks that led us to believe that our current loop alignment algorithm will be beneficial in stabilizing and improving the performance of .NET code.<\/p>\n

Heuristics<\/h2>\n

When we started working on this feature, we wanted to accomplish the following things:<\/p>\n