Slowing down programs is surprisingly useful

Most research on programming language performance asks a variation of a single question: how can we make some specific program faster? Sometimes we may even investigate how we can use less memory. This means a lot of research focuses solely on reducing the amount of resources needed to achieve some computational goal. So, why on earth might we be interested in slowing down programs then? Slowing Down Programs is Surprisingly Useful! Making programs slower can be useful to find race conditions, to simulate speedups, and to assess how accurate profilers are. To detect race conditions, we may want to use an approach similar to fuzzing. Instead of exploring a program’s implementation by varying its input, we can explore different instruction interleavings, thread or event schedules, by slowing down program parts to change timings. This approach allows us to identify concurrency bugs and is used by CHESS, WAFFLE, and NACD. The Coz profiler is an example of how slowing down programs can be used to simulate speedup. With Coz, we can estimate whether an optimization is beneficial before implementing it. Coz simulates it by slowing down all other program parts. The part we think might be optimizable stays at the same speed it was before, but is now virtually sped up, which allows us to see whether it gives enough of a benefit to justify a perhaps lengthy optimization project. And, as mentioned before, we can also use it to assess how accurate profilers are. Though, I’ll leave this for the next blog posts. :) The current approaches to slowing down programs for these use cases are rather coarse-grained though. Race detection often adapts the scheduler or uses, for example, APIs such as Thread.sleep() . Similarly, Coz pauses the execution of the other threads. Work on measuring whether profilers give actionable results, inserts bytecodes into Java programs to compute Fibonacci numbers. By using more fine-grained slowdowns, we think we could make race detection, speedup estimation, and profiler accuracy assessments more precise. Thus, we looked into inserting slowdown instructions into basic blocks. Which x86 Instructions Allow us to Consistently Slow Down Basic Blocks? Let’s assume we run on some x86 processor, and we are looking at programs from the perspective of processors. When running a benchmark like Towers, the OpenJDK’s HotSpot JVM may compile it to x86 instructions like this: 1 2 3 4 5 6 7 mov dword ptr [ rsp + 0x18 ], r8d mov dword ptr [ rsp ], ecx mov qword ptr [ rsp + 0x20 ], rsi mov ebx , dword ptr [ rsi + 0x10 ] mov r9d , edx cmp edx , 0x1 jnz 0 x... < Bl ock 55 > This is one of the basic blocks produced by HotSpot’s C2 compiler. For our purposes, it suffices to see that there are some memory accesses with the mov instructions, and we end up checking whether the edx register contains the value 1. If that’s not the case, we jump to Block 55. Otherwise, execution continues in the next basic block. A key property of a basic block is that there’s no control flow inside of it, which means once it starts executing, all of its instructions will execute. Though, how can we slow it down? x86 has many many different instructions one could try to insert into the block, which each will probably consume CPU cycles. However, modern CPUs try to execute as many instructions as possible at the same time using out-of-order execution. This means, instructions in our basic block that do not directly depend on each other might be executed at the same time. For instance, the first three mov instructions access neither the same register nor memory location. This means the order in which they are executed here does not matter. Though, which optimizations CPUs apply depends on the program and the specific CPU generation, or rather microarchitecture. To find suitable instructions to slow down basic blocks, we experimented only on an Intel Core i5-10600 CPU, which has the Comet Lake-S microarchitecture. On other microarchitectures, things can be very different. For the slowdown that we want, we can use nop or mov regX, regX instructions on Comet Lake-S. This mov would move the value from register X to itself, so basically does nothing. These two instructions give us a slowdown that is small enough to slow down most blocks accurately to a desired target speed, and the slowdown seems to affect only the specific block it is meant for. Our basic block from earlier would then perhaps end up with nop instructions interleaved after each instruction. In practice, the number of instructions we need to insert depends on how much time a basic block takes in the program. Though, for illustration, it might look like this: 1 2 3 4 5 6 7 8 9 10 11 12 13 mov dword ptr [ rsp + 0x18 ], r8d nop mov dword ptr [ rsp ], ecx nop mov qword ptr [ rsp + 0x20 ], rsi nop mov ebx , dword ptr [ rsi + 0x10 ] nop mov r9d , edx nop cmp edx , 0x1 nop jnz 0 x... < Bl ock 55 > We tried six different candidates, including a push - pop sequence, to get a better impression of how Comet Lake-S deals with them. For more details of how and what we tried, please have a look at our short paper below, which we will present at the VMIL workshop. When inserting these instructions into basic blocks, so that each individual basic block takes about twice as much time as before, we end up with a program that indeed is overall twice as slow, as one would hope. Even better, when we look at the Towers benchmark with the async-profiler for HotSpot, and compare the proportions of run time it attributes to each method, the slowed-down and the normal version match almost perfectly, as illustrated below. The same is not true for the other candidates we looked at. Figure 1: A scatter plot per slowdown instruction with the median run-time percentage for the top six Java methods of Towers. The X=Y diagonal indicates that a method’s run‐time percentage remains the same with and without slowdown. The paper has a few more details, including a more detailed analysis of the slowdown each candidate introduces, how precise the slowdown is for all basic blocks in the benchmark, and whether it makes a difference when we put the slowdown all at the beginning, interleaved, or at the end. Of course, this work is merely a stepping stone to more interesting things, which I will look at in a bit more detail in the next post. Until then, the paper is linked below, and questions, pointers, and suggestions are welcome on Mastodon, BlueSky, or Twitter. Abstract Slowing down programs has surprisingly many use cases: it helps finding race conditions, enables speedup estimation, and allows us to assess a profiler’s accuracy. Yet, slowing down a program is complicated because today’s CPUs and runtime systems can optimize execution on the fly, making it challenging to preserve a program’s performance behavior to avoid introducing bias. We evaluate six x86 instruction candidates for controlled and fine-grained slowdown including NOP, MOV, and PAUSE. We tested each candidate’s ability to achieve an overhead of 100%, to maintain the profiler-observable performance behavior, and whether slowdown placement within basic blocks influences results. On an Intel Core i5-10600, our experiments suggest that only NOP and MOV instructions are suitable. We believe these experiments can guide future research on advanced developer tooling that utilizes fine-granular slowdown at the machine-code level.