[Feb. 22 Discussion]: Profiling

[tonyjie]

This thread is for discussing the "Efficient Path Profiling" paper by Thomas Ball and James R. Larus. Niansong (@zzzDavid) and I (@tonyjie) are the discussion leader and will try to answer all your questions!

[tonyjie]

This paper presents a simple and fast algorithm for Path Profiling. Compared to the Profiling on Basic Blocks or Edges, it is more accurate: the result of Path Profile could determine Basic Block and Edge Profile, but the converse doesn't hold. We can only use the heuristic analysis to select Path when we use Edge Profile. And that would lead to incorrect predictions.

The experiment result is: Path profiling could have comparable overhead compared with Edge profiling (31% vs. 16%), and Path profiling could provide far more information than basic block or edge profiles, which is helpful for profile-driven compilers. Related result is that the path prediction accuracy of edge profile method is 37.9% in average.

So I'm just wondering what profile-driven compilers are actually doing given the Path Profiling result. Will the compiler benefit a lot from very accurate path profiling result?

[atucker]

I don't know what profile-driven compilers are actually doing with this information, but I think a natural use-case for path profiling could be to profile the actual paths that users are taking through a company's product. For example, it seems really useful for a company to know the actual number of users who are going through each possible signup or onboarding flow. If a lot of users are going through a particular code path, then it is particularly useful for product designers to figure out how to make that interaction easier, and knowing the actual path counts could help designers know what steps could potentially be merged or reworked rather than only optimizing each path separately.

[charles-rs]

When I first read the paper, I even thought the 16% overhead is for path profiling, and later I found I was wrong. So the question is the same: do we really need a profiling method that has such huge overheads? How to balance the tradeoff between running time and accuracy? How much can a JIT compiler benefit from path profiling compared with other profiling methods?

I don't know too much about the way a JIT works, but my general understanding is you have some kind of interpreter (probably bytecode) and when some code is "hot," you compile it and use the compiled version instead. I would imagine then that the profiling would actually be inserted into the interpreter here. This could be interesting, as the interpreter is probably (definitely?) less efficient than the optimized assembly where the 36% figure comes from, so the % slowdown of the profiling would likely be lower. I would be very interested to see numbers for the overhead when a JIT is involved, such as the JVM.

An interesting question this brings up is whether or not to instrument the JITted code, that is, if you have your instrumentation in the bytecode, and then you find a nice, hot, path and you JIT it, you have already determine that this path is hot, so I could see an argument that you don't need to profile it anymore, and can continue profiling other paths and JIT them if necessary. This might run into some issues though, esp if you JIT the path A -> B -> C, and then something changes and the path A -> B -> D becomes hot, how would this be dealt with? Perhaps there is a way to extend the algorithm to deal with certain paths as "special", and have the profiling work a little differently, but I'm not sure what this would look like.

[orkosinha]

I believe JIT does deoptimize code, so maybe some instrumentation remains. I know almost nothing about JIT and it seems a bit magical, but maybe dynamic profiling is done some other way when JIT creates native code form dynamic code, or the same instrumentation remains in another form. Either way, I'm very curious about this.

Complete side note, I found this from the author's website discussing their opinion on "why profile paths?". I was a bit confused on what they meant by "concentrate/favor frequently executed paths", do they mean try to optimize this path more? Why favor it over others?

Side side note: I thought the reference to solving Y2K issues was interesting

[charles-rs]

i think one way of favoring a path is making it the "fall through" case with branches. This is good for icache/prefetching, and the branch predictor would probably learn it too?

[ayakayorihiro]

While this is more about testing rather than compilers, the paper also mentions that path profiling could potentially be used by software test coverage tools in order to aid path coverage, noting that tools use weaker criteria such as statement and edge coverage, and ought to be strengthened. More than 20 years after this paper, coverage tools still mostly use the weaker criteria of statement and edge coverage... So, one thing that I'm curious about/I'd like to look into a bit more about how this algorithm was used towards path coverage, and what were the potential drawbacks such that the status quo of weaker criteria still prevails today.

[michaelmaitland]

I'm not sure I understand whats going on in section 3.3 (Efficiently Computing Sums). The goal is to use a spanning tree to select edges to instrument and compute the appropriate increment for each instrumented edge. The algorithm chooses a maximal cost spanning tree of the graph so we can find a minimal cost set of chord edges.

I'm not sure I understand why instrumenting these chord edges works and why instrumenting the chord edges is a good choice.

Lastly, I cannot figure out why in Figure 7, the graph in the middle shows the unique cycle of spanning tree edges associated with chord B -> D. Firstly, if this is a spanning tree with chord B->D, how is B->D in the spanning tree if by definition, a chord is an edge not part of the spanning tree? Secondly, why is it the unique cycle? Couldn't we have also built the cycle A -> B -> E -> F -> A (which would in fact be the spanning graph for which B->D is not in the graph (i.e. a chord, as desired)?

[zzzDavid]

I think you are right that Section 3.2 focuses on unique path sums. The first step is to make sure each path sums to a unique encoding, but that is not "efficient" yet. By selecting a few edges for instrumentation and "pushing" all the edge values to the instrumentations decreases the times we increment the register while still ensuring that each path sums to a unique value, therefore, it is more efficient than incrementing the register at every edge.

The paper says that "this approach requires computing a weight for each edge that statically approximates the edge's execution frequency". I think the path execution frequency estimate might not need to be highly accurate, as the edge frequency estimation only determines where the instrumentations are placed. I think running a representative workload to obtain the pattern may be good enough, otherwise the edge frequency estimation becomes too costly.

[sampsyo]

Right. The confusing thing is that there are two kinds of edge weights involved: the frequencies, used to minimize the cost of instrumentation, and the sum values, used to uniquely identify paths.

You can imagine the setup working in two phases: run edge profiling first, and then use that to find the minimum instrumentation for path profiling in a second phase.

[chhzh123]

From here we know that the maximal spanning tree is to select paths that are most frequently executed, so that what's left (the chords) are the least frequently executed.

Intuitively this is true, but is there any proof in the paper? I only noticed the proof of the uniqueness of path sum. For example, what would happen if there are way too many chords in the CFG, is the overhead still low in this case? There will only N-1 edges in the spanning tree, but actually you can at most have N*N edges in the graph. In this way, path profiling seems still a heuristic method that tries to minimize the instrumentation overheads but is not the optimal one?

[tonyjie]

In Section 3.1, this paper introduces chord as follows:

If T is the set of spanning tree edges, then any graph edge not in T is a chord of the spanning tree.
In the graph of Figure 2, the unadorned graph edges comprise a spanning tree. The edges labeled by squares are chords of the spanning tree.

I think this means that all the chords need to be labeled so that we can get a unique path sums. Therefore, when we know the maximum spanning tree, the left edges in the graph are all labeled by squares.

[ayakayorihiro]

Just wanted to quickly say that I was also getting a bit tripped up on what was happening with the instrumentation (along the examples that were given in the paper), and reading this discussion really helped me understand what was happening here! So, thank you :)

[5hubh4m]

I thought this paper was pretty innovative in the way it finds a way to represent all possible paths in a CFG using an index into an array, and builds upon that to do low overhead path profiling. Since this was an old paper I went to see what other works built upon this paper; and while I can see a large number of academic publications like this and this I struggled to find any mentions of this technique being used in production JVMs or even offline profiling tools like gprof. I did see a research project that implement this in LLVM but again, no mentions of it's uses.

So I guess I'm trying to understand why this technique isn't more mainstream, given the very relevant use cases that @sampsyo mentioned here.

[tonyjie]

I think that's a great question and I'm also curious about that. I checked the paper you mentioned, and found their reasons to not use this efficient path profiling method we are discussing.

The technique adopted for profiling must have low (profile) instrumentation overheads and low profiling overheads, since these constitute a part of the running time of the program. As a consequence, sophisticated low profile overhead algorithms such as the Ball and Larus’ efficient path profiling algorithm [6] or the efficient edge profiling algorithm [5], which take significant time to identify profile points in the program, cannot be used in dynamic compilation.

So it seems that this method takes too much time to identify the profile points, which is not good for JIT compiler. (which is the opinion from that paper)

[sampsyo]

Ball-Larus used to have an implementation in-tree in LLVM, FWIW:
https://opensource.apple.com/source/llvmCore/llvmCore-3418.0.80/lib/Transforms/Instrumentation/PathProfiling.cpp.auto.html

Unfortunately, it was unmaintained and was removed in 2013:
llvm/llvm-project@ea56494

@Dan12 made a new implementation for his 6120 course project in 2019, and it was awesome:
https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/efficient-path-prof/

[JonathanDLTran]

I am also wondering why the Ball-Larus path profiling technique is not used as often. As I understand, the overhead for the Ball-Larus path profiling on the author's chosen benchmarks was 31%, almost twice the overhead of using efficient edge profiling at 16%. In the most extreme case, for the GCC benchmark, profiling overhead reached nearly 97%. It does seem like the accuracy that Ball-Larus brings may be offset by the time spent profiling. In turn, this might hurt specific applications, such as a compiler-tool profiling what paths should be better optimized.

On the other hand, there are other works that adapt the Ball-Larus technique to have less overhead, while also trading off accuracy of profiling paths. The paper Continuous Path and Edge Profiling proposes another method do sample paths rather than storing the entire path, and retains an accuracy of 94% and a 4.3% recorded maximum overhead for a series of Java Benchmarks. To me, this suggests that losing some accuracy might still be acceptable, especially with such high accuracy and low overhead. However, it might be hard to compare the two techniques, because the languages being profiled are different, and the benchmarks are also different as well.

[gsvic]

Probably this is slightly out of topic, as the paper presents a new algorithm for efficient path profiling, while my question is on the prediction accuracy and the dependency on the data. If I am not wrong, given a CFG the hot paths can differ among executions for varying input data distributions (e.g. skew) per execution. This can happen especially when branching conditions depend on the input of the program. So, my main question would be, how the prediction accuracy of such a profiler could be affected by the different inputs? And if so, how such a case would be addressed?

[alaiasolkobreslin]

I had a similar thought when I was reading this paper. My guess is that there are some cases where optimizing based on results of path profiling would not be ideal. If there is high variability of the hot paths for executions on different inputs, then it doesn't make sense to pick a hot path from one input in a CFG and optimize it. On the other hand, if you find that on most inputs the hot path is the same, then it might make sense to optimize this path.

[tonyjie]

I think Path Profiling needs to be done for every new input (distributions). The "profile" is based on the inputs, I guess.

[orkosinha]

Also had a similar thought about this, I wanted read a little bit more into path profiling. I found this Wikipedia article, and found the sentence on the Fortran compiler to be a bit funny, where the compiler randomly decides whether conditional branches (weighted by programmer input) are taken. I guess this may lead to more accurate profiling, but also potentially very harmful.

[andreyyao]

Adding on to your thought, I wonder if it's possible to replace the integer valuing of the path costs with probabilities about selection of out-edges on the conditional branches. This idea is probably wildly impractical, but one can imagine approximating the frequency of some subset of the paths by feeding some inputs(ideally with similar distribution to that of actual use-cases). Then with this information there is perhaps some way to apply it to predict the visit frequency of the paths(statically, without having to run the program again)...

[andrewb1999]

This paper, and the discussion below @tonyjie post, reminds me of some previous work I have read about on so called "hardware JITs". The idea in this line of work is to choose hot functions in code and compile the hottest functions to a custom accelerator, such as an FPGA. An algorithm similar to the one described in this paper could be applied in hardware JITs to determine which parts of the code should be compiled to hardware, rather than just compiling entire functions.

Obviously, there are a large number of challenges with this work, including long compilation times for FPGAs and overhead in transferring data to and from the accelerator, but I still think it is an interesting potential application of the path profiling method.

[tonyjie]

We wrote a Discussion Blog and @zzzDavid just sent the pull request. It is not easy to directly read the md file, so you're welcomed to visit Niansong's blog here! 😄