Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

On the Algebraic Properties of Flame Graphs

arxiv.org

Post reply on HN
Print view View original

1–10 of 12 posts

Re: On the Algebraic Properties of Flame Graphs

#3

Post by m1el »

As a developer who doesn't use mathematical notation very often, I've had some difficulty reading it. From my understanding, the paper goes as follows:

2.1 Define FlameGraph

    Frame = something that identifies function/location in the code
    Stack = Vec
    FlameGraph = Map
    FlameGraphPositive = Map
2.2 Define FlameChart

    FlameChart = Vec
    # such that the start values are strictly ordered
    fn to_flamegraph(flame_chart: FlameChart) -> FlameGraphPositive {
        flame_chart
            .map(|{ start, flame_graph }| flame_graph)
            .sum() 
    }
Personally, I think a better definition of FlameChart is:

    FlameChart = Vec
    # such that sampling starts at 0 and Vec is strictly ordered by end_time
    fn to_flamegraph(flame_chart: FlameChart) -> FlameGraphPositive {
        let mut start = 0.0;
        flame_chart.map(|{ end_time, stack }| {
            let elapsed = end_time - start;
            start = end_time;
            FlameGraphPositive::from_stack(stack, elapsed)
        }).sum()
    }
3.1 Define diff

    # a,b: FlameGraphPositive
    fn diff(a, b) -> FlameGraph;
    # such that a + diff = b
    # diff: FlameGraph
    # add, sub: FlameGraphPositive
    fn to_positive(diff) -> { add, sub };
    # such that diff = add - sub
3.2 Define a naive diff metric

    # a,b: FlameGraphPositive
    fn diff_metric(a, b) -> RealPositive {
        diff(a, b).size() / (a.size() + b.size())
    }
    # diff_metric(a, b) \in [0, 1]^Real
3.3 Define a more sophisticated diff metric

Using Hotelling T^2 Test, the author defines a metric, which takes sampling variance into account, and allows to detect performance regression, even when the sampling profile is noisy. (you'd have to read the paper for the exact method)

The code for this test is here: https://github.com/P403n1x87/flamegraph-experiment/blob/04db... https://github.com/P403n1x87/flamegraph-experiment/blob/04db...

Re: On the Algebraic Properties of Flame Graphs

#4

Post by BlackFly »

I don't think this algebra is a full description of flame graphs but it feels like it captures part of what you want for the limited purpose of global performance analysis.

I feel like a flame graph cannot be an element of a vector space since vectors are commutative and the stacks of a flame graph are ordered. From a performance perspective, ignoring the ordering can simplify the algebra (apparently by turning it into a vector space) and will still correspond with your overall impression of "time spent in a frame".

Specifically,

    |A|B |A|
    |C|C |C|
is (1, C;A), (2, C;B), (1, A;C) but as (1, C;A) + (2, C;B) + (1, A;C) with vector addition we can rearrange this to (2, C;A) + (2, C;B)

or

    |A |B |
    |C |C |
which of course still captures the time spent in C;A and C;B, but it has lost some information. We think of it as a different flame graph. Of course, ignoring that information can be meaningful to a performance analysis.

Indeed the ordering can only be important to application semantics. This is clearly accentuated by the norm, which is even destroying the information of the basis elements.

Re: On the Algebraic Properties of Flame Graphs

#5

Post by m1el »

BlackFly wrote: post #4

I don't think this algebra is a full description of flame graphs but it feels like it captures part of what you want for the limited purpose of global performance analysis. I feel like a flame graph cannot be an element of a vector space since vectors are commutative and the stacks of a flame graph are ordered. From a performance perspective, ignoring the ordering can simplify the algebra (apparently by turning it in…

The information loss you're describing is going from Flame Charts to Flame Graphs. Yes, the call ordering, and multiple calls are lost if you're generating a Flame Graph.

Re: On the Algebraic Properties of Flame Graphs

#7

Post by yccs27 »

Vervious wrote: post #2

I'm confused, what are the takeaways, and why are there 83 upvotes with no discussion?

The paper looks interesting but it seems no one here understands it, so people upvote it in the hopes that someone knowledgeable will see it and summarize it in the comments.

Re: On the Algebraic Properties of Flame Graphs

#8

Post by defrost »

Oddly enough I've generated similar graphs for stack tracing and profiling in the far far distant past and had not realised they'd been named and formalised.

For anyone else who has not recognised the name, I found these origin links which may interest some:

    Abstract [2]:
 
    Flame graphs are a simple stack trace visualization that helps answer an everyday problem: how is software consuming resources, especially CPUs, and how did this change since the last software version? 

    Flame graphs have been adopted by many languages, products, and companies, including Netflix, and have become a standard tool for performance analysis.

    They were published in "The Flame Graph" article in the June 2016 issue of Communications of the ACM, by their creator, Brendan Gregg.
[1] https://www.brendangregg.com/flamegraphs.html

[2] https://www.usenix.org/conference/atc17/program/presentation...

(hour long usenix talk of [2]) https://www.youtube.com/watch?v=D53T1Ejig1Q

This paper appears to be formalising the nature of a flame graph, recognising that they rest on data from sampling profilers and as such suffer a "never the same twice" variation when repeatedly run, and thus seeking to quantify "distance" of one graph from another as well as "average" of multiple graphs (for the "one true mean reference graph" I guess).

The motivation is then to be able to reliably measure "distance" from one group of profiling runs to another, before and after changes of interest.

I dare say much more is possible, but I fear I've barely skimmed the material before bedtime :/

Re: On the Algebraic Properties of Flame Graphs

#9

Post by HelloNurse »

BlackFly wrote: post #4

I don't think this algebra is a full description of flame graphs but it feels like it captures part of what you want for the limited purpose of global performance analysis. I feel like a flame graph cannot be an element of a vector space since vectors are commutative and the stacks of a flame graph are ordered. From a performance perspective, ignoring the ordering can simplify the algebra (apparently by turning it in…

Following the terminology of the article, CA and AC are two different stacks (C calling A vs. A calling C) so they cannot be merged. Instead, the whole flame graphs form a vector space, with a dimension for each stack (with the provision that for many purposes only the positive cone makes sense). There is no meaningful operation between stacks.

Re: On the Algebraic Properties of Flame Graphs

#10

Post by vrnvu »

Vervious wrote: post #2

I'm confused, what are the takeaways, and why are there 83 upvotes with no discussion?

I upvoted it because the paper is simple and easy to follow. It defines some properties of flame graphs and makes us of them to make conclusions about performance regression, A/B testing and how to have better profiling results removing noise.
Post reply on HN