Tidy up library interface for flamegraph (and collapse?)

[jonhoo]

If we want other projects, like @koute's nperf, to start using inferno to draw their flame graphs (and perhaps even to do the collapsing), we need to provide an external interface that isn't just a purely line-based textual one like the ones used internally between perf script, stackcollapse-perf, and flamegraph.pl. Specifically, we'll want an interface that is typed, and where all (most?) of the parsing is done by the caller. I'm imagining something like:

mod flamegraph {
  struct StackCount<S> {
    stack: S,
    count: usize,
  }
    
  fn from_samples<I, S, W>(o: Opts, samples: I, writer: W) -> 
    where
      I: IntoIterator,
      I::Item: Into<StackCount<S>>,
      S: Iterator<Item = &str>,
      W: Write
  {
  }
}

from_samples would require that the input is given in sorted order (see #28), and then write a flame graph output to writer. The existing code that does parsing would call from_samples with an iterator created from the lines iterator, mapped something like this:

lines.map(|line| {
  let (stack, nsamples) = ...;
  StackCount {
    count: nsamples,
    stack: stack.split(';'),
  }
})

@koute: what do you think of an interface roughly like the above? You think that's an iterator that nperf could easily produce? What would be a good interface for collapse (if that's even something you might consider using)?

[koute]

Sounds good to me; I should be able to produce such iterator easily.

I wonder though if in the long run an interface which has collapsing integrated wouldn't be better - the extra integration could probably me made more performant, and it would be potentially simpler to use.

Something like this maybe:

struct FlameBuilder<T> {}
impl FlameBuilder<T> where T: PartialEq + Eq + PartialOrd + Ord + ... {
    fn new() -> Self {}
    fn add_stack_trace<I>(&mut self, I)
        where I: IntoIterator<Item = T> {}
    fn generate<F>(self, output: F, write_frame: W) -> Result<()>
        where F: Write, W: FnMut(&T, &mut F) -> Result<()> {}
}

The write_frame is there since the Ts might not be strings, e.g. in my case they wouln't be printable by themselves as they contain IDs to interned strings, hence the customizable writer.

[jonhoo]

@koute sadly the algorithm for producing the flamegraph actually requires walking through all the frames present in each stack sample. That's why I proposed the above: we need both the count for each stack sample present, and the frames of that stack sample to be able to detect and merge shared parent frames.

[koute]

@jonhoo The API in my post does allow you to walk through all the frames though. (: The add_stack_trace method isn't meant to be called only once per a unique stack trace, but once every sample, so it can be internally collated and processed in whatever way you'd see fit. (I guess add_sample would be a better name for it; sorry, it was late and I was tired.)

[jonhoo]

Oh, I see. Hmm, I still don't think that's enough, as we actually need to walk each stack multiple times (twice, specifically) to do the merging. Maybe if we require that the iterator also be Clone?

Actually, thinking some more about it, that interface looks more like what you'd pass to collapse than to flamegraph. collapse would then collapse the samples into their counts, and then pass that to flamegraph. Keeping that interface generic I think will be tricky. One alternative would be to include the collapsed count in add_stack_trace, and then you could totally have it be the interface to flamegraph.

[koute]

Yes, it does look like an interface to collapse, and that's deliberate. The distinction between collapsing the stack traces and generating the flamegraph is somewhat artificial I think - it definitely makes sense for standalone scripts since you want multiple collapse-like scripts to normalize the input (which can be of various different formats) into a common format and one flamegraph script to generate the desired output, however for an API you'd ideally want to just throw a bunch of stack traces and have the library massage it in whatever way it deems necessary.

Oh, I see. Hmm, I still don't think that's enough, as we actually need to walk each stack multiple times (twice, specifically) to do the merging. Maybe if we require that the iterator also be Clone?

You don't need to make the iterator Clone; it'd be enough to mark the T with Clone (since those are either going to be integers, or &str, which are both cheap to copy), and then you could whatever with those, e.g. push those frames to a Vec, and then you can iterate over as many times as you'd like (and you can cache the Vec inside of FlameBuilder, so it'd be essentially free).

[jonhoo]

I was more thinking if we don't want to (potentially re-)allocate a Vec for each stack. I'd be totally fine making what you propose the interface to collapse, and then the same but with counts the interface for flamegraph, and then also provide an interface that's the same as the one to collapse but that also does the flamegraphing (which is then what you'd use).

[koute]

I'd be totally fine making what you propose the interface to collapse, and then the same but with counts the interface for flamegraph, and then also provide an interface that's the same as the one to collapse but that also does the flamegraphing (which is then what you'd use).

So, basically, we'd have something like this for the "collapse or directly generate a flamegraph":

struct FlameBuilder<T> {}
impl FlameBuilder<T> where T: PartialEq + Eq + PartialOrd + Ord + Clone {
    fn new() -> Self {}
    fn add_sample<I>(&mut self, I)
        where I: IntoIterator<Item = T> {}
    fn collapse<F>(self, output: F, write_frame: W) -> Result<()>
        where F: Write, W: FnMut(&T, &mut F) -> Result<()> {}
    fn generate_flamegraph<F>(self, output: F, write_frame: W) -> Result<()>
        where F: Write, W: FnMut(&T, &mut F) -> Result<()> {}
}

and another (different) interface just for generating a flamegraph from already collapsed frames?

[jonhoo]

Almost. The stuff the code has to do in response to an add_sample call differs depending on whether you're just trying to collapse or also wanting to produce a flame graph, so I suspect we'll want them to be separate. I also don't think that'll come at too much of a cost, since collapsing will need a separate "pass" anyway.

[Licenser]

I was thinking about something similar but would like to suggest taking it one step further:

1. parse (reads the data and emits stacks) but doesn't combine - data gets streamed.
2. collapses stack traces (takes data from 1 and combines them)
3. sort
4. render

Now, where I'm going with this is the ability to create a live view from this. we could have cargo flamegraph --serve that opens a port and lets you see the flame graph building up live in the browser as your system runs.

And I imagine the same interface, as it is more split apart will also work for other tools or am I missing something?