Grant Wallace
CS 597d
Observation 3:
 
Edge Profiling versus Path Profiling: The Showdown [1]
 
Paper’s Claim:
    Using edge profiling to choose "hot" paths (i.e. greedy, potential heuristics) works well when the edge profile is characterized by very high and low frequency edges (i.e. with a large amount of definite flow, it’s easy to guess the hot paths). Path profiling is more efficient when the frequency of the edges are similar (little definite flow, many potential hot paths).
 
    From their experimental results figure 12(b) we can see that for "go" the potential paths algorithm overestimates the "hot" paths by roughly a factor of 10. This can be seen because the actual hot paths, Aq, (with cut off 0.125%) represent 75.2% of the total flow (table 1), and the total-flow divided by potential-flow < 0.1 (figure 12(b)). The potential paths algorithm correctly picks ~90% of the "hot" paths (figure 13a), but since it overestimated by a factor of 10, it has greatly increased the computational workload of optimizing these potential "hot" paths. So we can see that for programs like "go" with low definite flow it might be more efficient to do path profiling.
 
Questions:
    In section 4.3 (2nd to last paragraph), they mention that a predictor is indirectly penalized for picking a path not in Aq. I don’t see this.
    I would be interested to see the ratios of the sizes Pq/Aq and Gq/Aq. In other words how many incorrect "hot" paths are chosen for every actual "hot" path identified? It seems this information would help directly support their claim.
 
 
    From an intuitive perspective I would express their algorithm for deciding if a given path, p, has a definite frequency as:
        1. First consider edge e with minimum frequency in the path p. Certainly the definite frequency of path p will be less than or equal to the frequency of e.
        2. Now consider all paths p’ which also contain edge e. These are the paths that can reduce the definite frequency of p.
        3. For all edges which converge with path p above e, or which diverge with path p below e, subtract those edge frequencies from the frequency of e. This will be the definite frequency of path p.
 
    A path profile uniquely identifies an edge profile. An edge profile can be induced by any path profile within a set of path profiles (i.e. an edge profile maps to a set of path profiles). So the sets of path profiles induced by different edge profiles are disjoint.
 
 
[1] Edge Profiling versus Path Profiling: The Showdown", T. Ball, P. Mataga, and M. Sagiv, Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.