Generate execution flow diagram

[markerikson]

We're recording the entire app. Can we generate an execution flow diagram from that info?

I'd love to be able to see, say, a trace of the startup sequence for Replay itself:

• Recording page component
• Redux store gets created somewhere
• Extra store bootstrap code runs
• Some client data gets fetched
• etc

Like, give me a way to visualize what files I'm jumping through, including the ability to blackbox things like React so we skip that stuff. Some potential visualizations:

• Filenames / line snippets
• some kind of dotviz graph
• UML sequence diagrams
• gotta be plenty of other examples out there

[jasonLaster]

@markerikson how much of this would be solved by showing a call tree and user timings? curious what use cases would not be captured...

[jasonLaster]

Also - i know that a lot of user timings are dev only, but we can do a lot of this similar stuff at the framework level after the fact

[markerikson]

A call tree is probably one valid way to visualize this kind of info. I'm also sorta picturing (waves hands wildly) something more diagram-y, possibly with embedded snippets of code kinda like we have in comments.

[markerikson]

From @kettanaito in Reactiflux, asking separately without knowing about Replay :

Is there a concept opposite to Error stack traces?
Stack trace prints the execution stack before the error. I'd like to know the execution stack after a certain point.

Let's say I import a foo function from a third-party package. I want to go through all the underlying code it executes. foo is quite complex, and I don't even know where exactly it goes with its logic. Is there a way to print the execution "path"?

In other words, I'd like to travel through foo as it executes on runtime. So the execution is rather precise, fixed (foo receives concrete parameters that lead it to a concrete path in a static source code). There must be something for this.

[kettanaito]

I was excited to find out Replay can do something similar to what I'm looking for. My work is focused on creating tools that work in harmony with other tools. For that, I often inspect how things work. Being able to achieve a tangible execution trace would be awesome.

[markerikson]

Some more ideas and feedback, including suggesting using a "flame graph" diagram for navigating the execution of a replay:

• https://twitter.com/bitandbang/status/1507775758495891459
• https://twitter.com/geoffreylitt/status/1507777464868741121

[markerikson]

The dbux debugger tool generates some async call flow diagrams:

https://domiii.github.io/dbux/acg

Pasting some screenshots:

Those look basically like what I had in my head

[Domiii]

hi, this is Domi, creator of Dbux.

Let me quickly introduce Dbux's "maps", i.e. global runtime visualization tools:

(But I definitely also recommend checking out the much more complete (and generously timestamped) intro video.)

1. The Synchronous Call Graph is a basic dynamic call graph.
   • It is similar to the flamegraph, but designed for investigating control flow, and, unlike the flamegraph, not optimized for profiling.
   • It allows you to not only see the "call stack evolved over time", but also see inputs and outputs of calls etc.
   • Call Graph Roots are files/functions (or partial files/functions) that are called or resumed from the JS engine, i.e. that do not have a caller.
   • The roots are just listed on a single (vertical) timeline.
   • The dynamic call graph has been implemented many times before, but only either for (1) profiling, or (2) in research experiments. To my knowledge, there is no proper interactive call graph tool for control flow analysis out there. But please let me know, if you have seen anything even remotely close!
2. The Asynchronous Call Graph, on the other hand, is our own invention.
   • Our (short) paper on the ACG just got accepted to ICSE 2022 (link not up yet).
   • Asynchronous execution models are concurrent execution models. The ACG's goal is to capture that concurrency and, in doing so, compliment the synchronous call graph (above). It is designed to help us understand the relationship at the level where there are no callers, that is only between the roots.
   • The val (value) button allows you to render the value of a selected expression for every root, allowing you to identify which root handled which data.
3. The Asynchronous Call Stack stitches the data used for the two of them to produce the complete asynchronous call stack at point of investigation. Turns out, there is no JavaScript environment that produces a complete asynchronous call stack that can cope with all different types of asynchronous events.

Some realizations after starting to use these tools

1. I don't want to live without them anymore.
2. They changed my entire perception and ability to reason about the overall call graph structure.
3. Because of (2), even, when I don't have them available, I feel I am in a much better position to cull my search space, once I understand some of the caller-callee relationships.
4. The two graphs compliment each other. You would usually want both. Without the ACG, a lot of the concurrency escapes you. Without the SCG, the synchronous call stack fragments might elude you. But maybe, just having the ACG + the Asynchronous Call Stack (ACS) would suffice.
5. Once you start using these tools to hunt for bugs, you thirst for more. I have already started adding more little extras to help us answer all kinds of remaining questions:
   • Given a promise, what are all its own and its nested roots (the paper's technical report explains the semantics of CGR and promise nesting)?
   • Given any root, promise or async function invocation, which line of code scheduled it?
   • Given any root, promise or async function invocation, at a specific point in time, what was the last piece of code it executed before this root?
   • Given any root, promise or async function invocation, what is it synchroizing against? (Promises sometimes have their own asynchronous control flow (i.e. their own roots), but sometimes, they are used to synchronize between control flows of other promises.)
   • And many more!

Implementation + Performance notes

1. Naturally, you would always have a lot more file/function executions than roots.
   • Thus, the SCG can get pretty heavy.
   • You probably want to build it partially/on the fly, if you can. Dbux is doing Ok with up to several hundred thousand calls.
   • You probably want to be able to filter packages and/or file path regexes to cull the search space. Dbux has that, too.
     • Having all libraries in there can make things unnecessarily messy.
2. The data needed for the ACG, on the other hand is usually relatively small.
   • I have not done the analysis on this yet. But naturally, you won't usually have more than a few hundred (or worst case, a few thousand) call graph roots.
   • Unless you have long running async loops. In that case, some loop comprehension/summarization probably can reduce the data needed there.

Some more pretty pictures and stuff

Dbux (recent) Intro Video

Fibonacci Call Graph vs. Call Stack (w/ val turned on)

Conceptual ACG demonstrating how missing awaits lead to FORKing

Sequelize ACG: running two queries in parallel (zoomed out, details disabled)

• NOTE1: Somewhere near the middle, you see the two queries forking off into two individual "threads".
• NOTE2: If an Error is thrown inside of a node, it is visualized with a flame icon.
  • side note: Those error icons helped me find a logged bug and a second, not logged, bug basically instantly (when you click the flame icon, they take you to the origin of the error).

Editor.md ACG: editing and saving markdown strings.

• The two long purple "threads" in the middle are UI event handler invocations. I think it was keyup and keydown events.
• The "beige" roots forking off to the right are buffered auto-save events

In Conclusion

If done right, these graphs can tell powerful stories.

Let me know, if there is anything I can do to help!

[markerikson]

YES YES YES! This is ABSOLUTELY the kind of visualization I want to see in Replay!

[markerikson]

Another set of interesting diagrams: Kolo for Django:

https://kolo.app/

[Domiii]

Reminds me of the "circular bundle view" from Extravis (Execution Trace Analysis through Massive Sequence and Circular Bundle Views, 2008). Even though, they work very differently, they both represent circular call graph summaries.

I guess, the Kolo visualization can quickly get out of control, when you have more than a few events (I'm guessing, I see about 10-ish what-I-guess is routes (or also other types of events?) in the Django screenshot?); but then again, everything will spin out of control, if you just throw enough data at it - hah!

If I'm not mistunderstanding them, the Extravis authors claim such "summary views" can be useful for some overview tasks, but usually need some complimenting views to better orient yourself and detect patterns-over-time.

[markerikson]

Some more prior art:

https://github.com/janestreet/magic-trace

[Domiii]

Not to be a negative Nancy, but is this different from Browser Dev Tools' profiler's flamecharts or icycle plots?

[Domiii]

I personally always prefer putting the time dimension on "control flow maps" on the vertical dimension (and of course only if there are two clear dimensions to begin with), if the goal is readability and comprehension (rather than, in case of profilers: highlighting of bottlenecks).
Else the text gets very hard to read.

Generally speaking: if the goal is "highlighting of patterns", of course more discussions are to be had, but generally, I would avoid trying to stack text horizontally.

[markerikson]

Throwing something else in here:

This extremely long article on perf profiling the guts of the Rust compiler talks about OpenTelemetry, and how to generate "spans" that can be visualized. Maybe something related we could do?

https://fasterthanli.me/articles/when-rustc-explodes

[Domiii]

Is the goal to aid profiling or program comprehension?

[markerikson]

Comprehension, mostly. If there's a crash with an error, I'd like to be able to see not just "the stack trace at the time of the error", but also "what functions and logic did we execute leading up to this spot".

For example, when I was debugging https://app.replay.io/recording/logpoint-02js--2d7e7544-33f3-4e39-b82d-b4f7d0b2daf5?point=22067261651551680457036465793139134&time=10896.647887323943&hasFrames=true# yesterday, I had to do a bunch of back-tracing to go from the final test failure to figure out where things actually went wrong long before that. Having this sort of a trace diagram might have made that faster.

[Domiii]

It looks like a normal, vertically arranged call graph but a bit coarser, focusing only on processes and system interactions?