The case for unrolling the main push/pull loops #1414
Comments
|
I have tested this modification with the The "flattening" of the loops has reduced the noise of the compiler significantly, in particular when confronted with changing workloads (e.g. direction of bulk traffic from encap-heavy to decap-heavy, from ipv4 only to ipv6 only, from unfragmented to fragmented traffic). The observed effect is that there are much fewer aborted traces and much fewer implicit blacklistings of side traces. Performance has become much more stable across all workloads and "catastrophic JIT failures" have practically vanished. Those failures would result in highly suboptimal traces or even substantial interpreter fallback (>50%) when the system was exposed to a wide range of different workloads. I am confident enough to include this change in the next production release of |
The goal of this change is to simplify the loop structure of the Snabb engine to make it more likely that the compiler can find and optimize the packet-processing loops. In particular, it can help in the situation when the program starts in an idle state with no packets to process. In that case, we want to avoid that traces compiled for this initial workload have a negative impact on the creation of traces for the actual (non-idle) workload. See snabbco#1414 for an analysis with a simplified engine.
The basic loop structure of Snabb is the following (simplified)
The actual workload is processed in the
pull()andpush()methods, which, in general, contain loops of the kindThose are the loops that we would like to be compiled most efficiently, i.e. containing an actual loop in the trace itself (a "looping" trace). Let's assume that the compiler actually does find those traces (but note that this is by no means guaranteed in a complex Snabb program). Due to the design of the tracing compiler, the outer loops cannot form looping traces themselves and end up being implemented by connecting distinct "straight" traces. Those traces are considerably less optimized and the number and inner structure of them can have a significant impact on the overall performance of the program.
I would like to argue that it is beneficial to replace the explicite second-level loops over the
breathe_pull_orderandbreathe_push_orderarrays by implicit loops usinggoto:To study the impact of this, consider the following simplified model of the
breathe()loopThe program instantiates 5 pseudo-apps, each of which has a trivial
pullmethod that simply increments a counter. Those methods are called from a nested loop in the style of abreatheloop. For simplicity, we omit thepushloop, which will not change our findings in a fundamental way because thepullandpushloops are sequential (i.e. the overall loop structure is the same in a "topological" sense).The program takes two arguments. The first one is a string that selects which style of loop should be used.
stdwill use the traditional nested loops while any other value will use the "flattened" loop usinggoto. The mainrepeatloop keeps track of its iterations in the global variablecounterand the program terminates after1e8iterations, printing the time in seconds that has elapsed while the loop was being executed.The second parameter to the program is a number that determines after how many iterations of of the main loop the loops in thepullmethods should be executed. This allows us to simulate a Snabb program which is idle for a while right after starting. I believe that this is actually the case in most real-world applications.To simulate diversity in the apps being run, the actual functions that implement the
pullmethods are created vialoadstring(). This makes sure that they will be implemented by different prototypes.Let's start by studying a completely idle system with the standard loops
Using
perf topwe see 7 active tracessim-empty-std.txt
The only loop that gets compiled is the
for i = 1, napps doloop. Let's look at trace #2This looks like a good trace, but note the guard for the address of the
pullfunctionThis address is different for each pseudo-app. What happens right after the compiler has finished recording this loop iteration? Since this was a successful trace, the resulting code is optimized and compiled to a proper looping root trace and the system continues by executing the next iteration of the loop from that freshly compiled trace. However, in that very next iteration the mentioned guard fails, because the
pullmethod of the next app is different from the previous one. As a consequence, the trace is left to the interpreter via exit #0 right away and before the actual loop has even be reached.After this has happened 10 times (the default number of passes through a side exit after which it gets hot) the compiler starts recording a side trace
You can see that the address of the
pullmethod is now0x40ce8c18when it was0x40ce9090in trace #2. Normally, a side trace cannot form a loop but this case is an exception, because the exit happens so early that the code has not yet been specialized enough to prohibit the formation of a new loop. The loop that is being recorded in trace #3 looks exactly like the previous trace and, in fact, the exact same thing is happening with it, i.e. the trace is left right in the next iteration.The same game is repeated in traces #4 and #5. Sometimes it will happen that one of those traces is entered with the expected
pullmethod and execution proceeds into the actual loop but since the next iteration will always cause the same failure of the guard, it will never reach thePHIat the end of the loop. Eventually, such an exit will become hot as well, which is the case for trace #6, which is started from exit #3 of trace #3. It executes thepullmethod and returns to the loop which has been compiled in trace #2 and therefore links directly to that trace.Trace #7 is again like #2, #3, #4 and #5 and traces #8 #9 and #10 are of the same kind as #6.
The good news is that everything is running compiled. The bad thing is that none of the optimized loops are actually executed.
Let's compare this with the "flattened" loop
We can already see that the elapsed time is smaller by a factor of almost 30. The program compiles to a single trace
Essentially, the flattened loop is like an explicit unrolling which removes the guards for the individual function prototypes. The loop is super compact and contains only the actual function calls, one after the other.
In this extreme case, where non of the apps share the same
pullfunctions, this is actually the optimum. But any real-world Snabb program will probably also have a significant number of distinct apps in their networks, which makes this example relevant.Now let's look what happens if the apps get busy after a short while, e.g. 1000 iterations of the main loop. During the first 1000 iterations, the compiler will find the exact same traces as just discussed. But what happens once the
pullmethods start executing their own loops?sim-std.txt
There are 20 active traces
As expected, we see the traces #2, #3, #4, #5 and #7 from the initial phase before the innermost loops become active. The five most active traces (#11-#15) all look like this
Clearly, those are the
pullloops for each of the 5 apps and they are all compiled nicely, which is good. All remaining traces are simple "straight" traces that connect these loops with each other and with the initial traces.Compare this with the flattened loop
sim-flat.txt
We can see trace #2 from the "emtpy" phase and traces #3, #4, #5, #6 and #7 that contain the exact same looping traces for the
pullmethods. Also here, there are a handful of straight traces connecting all the loops.The difference is that in the standard scenario, there is a significantly larger part of relatively inefficient code which translates to a running time which is 20% lower than in the standard case.
As a final test, consider the case when none of the apps is idle when the program starts.
sim-full-std.txt
Here, the innermost loops are naturally compiled first and none of the side-traces observed in the "empty" scenario occur. In fact, the trace structure is essentially the same as the one in the "flat + empty" case.
How does it compare to the modified loop case?
sim-full-flat.txt
In the "full" scenario, both looping mechanisms are equivalent.
The conclusion is that we can significantly improve the performance in case the system is idle for a while when it starts up without any negative effects for the case when the system is loaded immediately. I believe the former case is actually more common in realistic scenarios.
Based on these findings I propose to apply the "flattening" of the
breathe_pull_orderandbreathe_push_orderloops incore.app.The text was updated successfully, but these errors were encountered: