Modern multi-threaded systems are highly complex. This makes their behavior difficult to understand. Developers frequently capture behavior in the form of program traces and then manually inspect these traces. Existing tools, however, fail to scale to traces larger than a million events.

In this paper we present an approach to compress multi-threaded traces in order to allow developers to visually explore these traces at scale. Our approach is able to compression traces that contain millions of events down to a few hundred events. We use this approach to design and implement a tool called NonSequitur.

We evaluate NonSequitur with 42 participants on traces from RocksDB and WiredTiger, two complex database back-ends. We demonstrate that with NonSequitur, participants performed some performance analysis tasks on large execution traces up to 11 times more accurately as compared with other tools. Additionally, for some performance analysis tasks, the participants spent on average three times longer with other tools than with NonSequitur.