Tachyon: use bounded columnar blocks for binary profiles

Tachyon currently stores samples in one compressed stream. The reader decompresses the whole sample section before replay, so long captures need a large allocation.

I propose small blocks with separate columns for thread and interpreter IDs, timestamps, flags, stack changes, and frame indices. Each block stores each thread/interpreter pair once. Samples refer to that pair with a small index. Timestamps store the difference from the expected sample time, without loss of precision. Stacks reuse common frames or refer to a previous stack in the same block.

Each column can use zstd, a single repeated value, or raw bytes, whichever is smaller. Similar values sit together, which can help compression. The reader processes one block at a time, so its sample buffer no longer grows with capture length. Shared string and frame tables still need memory.

The aim is smaller files and cheaper replay. We need to preserve the current format’s efficiency for repeated stacks. This needs a new format version, with the same public collector and replay APIs. Live output remains separate work in #145464.

Linked PRs

gh-159207: Store Tachyon samples in bounded columnar blocks #160313

I tried a C prototype against current main. The captured JSON/zlib workload gives a 63% smaller file and uses 16% less replay CPU time. For an eight-million-sample synthetic capture, peak replay RSS drops from 268 MiB to 22 MiB.

@ivonastojanovic

I plan for @ivonastojanovic to implement this :)

I'm very excited about this one! More than happy to help / review!

OK, some pieces we could consider for this design:

We could try independent blocks of about 1 MiB, with one block decoded at a time. We would also need limits on samples, bytes, stack storage, and caches.
One possible split is six columns: stream dictionary, stream indices, timestamp residuals, status flags, stack edits, and new frame indices.
We could give each block a dictionary of thread/interpreter pairs. Each sample would then need only a small index.
```
dictionary: 0 = (thread 41, interpreter 0)
            1 = (thread 82, interpreter 1)
samples:    [0, 1, 0, 0]
```
Perhaps timestamps could store the difference from the expected sample time, separately for each stream. The first prediction would be the block’s base timestamp. This would preserve exact values.
```
base:       10000 us
interval:    1000 us
timestamps: 10000, 11003, 12001
residuals:      0,    +3,    -2
```
An unchanged stack could have a single repeat command, with no frame payload. For [A, B, C] -> [A, B, C], that would be just repeat.
We could store stacks from root to leaf and retain common root frames when the stack changes.
```
previous: [A, B, C, D]
next:     [A, B, E]
stored:   keep 2, append [E]
```
A small cache of complete stacks may help within each block. For stack 1, stack 2, stack 1, the third sample could refer to the first stack’s frame range. We could cap the search work and confirm matches with a full comparison.
We could store frame indices in byte planes, with the smallest width that fits. Similar bytes would then sit together for compression.
```
indices: [0x0123, 0x0456]
encoded: [width=2] [0x23, 0x56] [0x01, 0x04]
                   low bytes    high bytes
```
Perhaps constant status bits could appear once, with each variable bit in its own bit plane. Tachyon’s flag meanings would stay the same.
```
sample flags:  [0x03, 0x01, 0x03]
constant bits:  0x01
variable flag: 0x02 -> [1, 0, 1] -> packed byte 0b00000101
```
Here, the first sample occupies the lowest bit in the packed byte.
Compact varint headers could reduce overhead for small captures. Small counts, lengths, and codec tags would need only one byte.
We could compress each column separately and choose the smallest representation: raw bytes, one repeated byte, or zstd. For [7, 7, 7, 7], that could be one byte with value 7 and a decoded length of 4.
We could start with zstd level 3. For large frame columns, a small probe could select level 1 when level 3 gives little extra compression.
The shared string and frame tables may benefit from compression too. We could retain raw storage when compression does not help and decode the tables incrementally. These tables would still grow with the capture.
We could decode frame indices and status flags in batches. One byte from each status bit plane gives that flag for eight samples.
Replay could retain batches for repeated stacks. For 100 consecutive samples from one stream with the same stack, we could reconstruct it once and retain all timestamps and status values.
We could reuse buffers and compression contexts across blocks, but reset stream history and stack caches. Each completed block could go through one output call.
This would need a new format version. The aim would be to preserve Tachyon’s APIs, output stack order, 64-bit sample count, capture settings, and profile statistics.

OK, some pieces we could consider for this design:
We could try independent blocks of about 1 MiB, with one block decoded at a time. We would also need limits on samples, bytes, stack storage, and caches.

One possible split is six columns: stream dictionary, stream indices, timestamp residuals, status flags, stack edits, and new frame indices.
We could give each block a dictionary of thread/interpreter pairs. Each sample would then need only a small index.
dictionary: 0 = (thread 41, interpreter 0)
            1 = (thread 82, interpreter 1)
samples:    [0, 1, 0, 0]
Perhaps timestamps could store the difference from the expected sample time, separately for each stream. The first prediction would be the block’s base timestamp. This would preserve exact values.
base:       10000 us
interval:    1000 us
timestamps: 10000, 11003, 12001
residuals:      0,    +3,    -2
An unchanged stack could have a single repeat command, with no frame payload. For [A, B, C] -> [A, B, C], that would be just repeat.
We could store stacks from root to leaf and retain common root frames when the stack changes.
previous: [A, B, C, D]
next:     [A, B, E]
stored:   keep 2, append [E]
A small cache of complete stacks may help within each block. For stack 1, stack 2, stack 1, the third sample could refer to the first stack’s frame range. We could cap the search work and confirm matches with a full comparison.
We could store frame indices in byte planes, with the smallest width that fits. Similar bytes would then sit together for compression.
indices: [0x0123, 0x0456]
encoded: [width=2] [0x23, 0x56] [0x01, 0x04]
                   low bytes    high bytes
Perhaps constant status bits could appear once, with each variable bit in its own bit plane. Tachyon’s flag meanings would stay the same.
sample flags:  [0x03, 0x01, 0x03]
constant bits:  0x01
variable flag: 0x02 -> [1, 0, 1] -> packed byte 0b00000101
Here, the first sample occupies the lowest bit in the packed byte.
Compact varint headers could reduce overhead for small captures. Small counts, lengths, and codec tags would need only one byte.

We could compress each column separately and choose the smallest representation: raw bytes, one repeated byte, or zstd. For [7, 7, 7, 7], that could be one byte with value 7 and a decoded length of 4.

We could start with zstd level 3. For large frame columns, a small probe could select level 1 when level 3 gives little extra compression.

The shared string and frame tables may benefit from compression too. We could retain raw storage when compression does not help and decode the tables incrementally. These tables would still grow with the capture.

We could decode frame indices and status flags in batches. One byte from each status bit plane gives that flag for eight samples.

Replay could retain batches for repeated stacks. For 100 consecutive samples from one stream with the same stack, we could reconstruct it once and retain all timestamps and status values.

We could reuse buffers and compression contexts across blocks, but reset stream history and stack caches. Each completed block could go through one output call.

This would need a new format version. The aim would be to preserve Tachyon’s APIs, output stack order, 64-bit sample count, capture settings, and profile statistics.

Thanks! This is actually very close to what I’ve been prototyping, so here’s where I am at the moment.

The sample section is split into independent blocks, while the string and frame tables are still stored once for the whole file. I’m keeping this scoped to file exports for now, streaming would probably need block-local metadata, so I think that’s better handled separately.

The decoded size of each block is currently capped at a hardcoded value. I’ll lower that to around 1 MiB as you suggested, and then we can experiment to find a good default.

Each block currently has six columns:

the (thread ID, interpreter ID) pairs used in the block
one stream index per sample
timestamp residuals
status flags, with constant bits stored once in the block header and one bit plane for each bit that varies
stack instructions
frame indices

Compression follows the existing compression option. Each column is compressed independently and stored as raw bytes, a single repeated byte, or zstd, whichever is smallest.

For stacks, the reader keeps the previous stack for each stream and supports three instructions:

REPEAT count: same stack for the stream's next count samples, even if other threads' samples come in between.
REPLACE_SUFFIX keep_count new_count: keep the outer frames and append new ones.
REUSE offset count: point at a stack stored earlier in the block.

I'll try the rest of your list next (varint headers, zstd level 3, limits, shared table compression, batched replay).

One question: should we keep the repeat count per stream? It saves a byte per repeated sample and gives replay batches for free, but the reader then needs a counter per stream. With zstd, a plain REPEAT per sample is almost free too.

Some extra info on the status stuff...

Today Tachyon stores one status byte per sample. We could split that into bits that stay fixed for the block and bits that change.

E.g. take 03 01 03 (all values here are hex). Bit 0, HAS_GIL, stays set. Bit 1, ON_CPU, goes 1, 0, 1.

We could store var=02 to say that bit 1 changes, and const=01 for the bits that are always set. Then we pack the CPU flag across samples into 05, binary 00000101. The first sample goes in the lowest bit, the second in the next bit, etc.

old: 03 01 03
new: 02 01 05   # var, const, packed CPU bits

To decode, we start each status with const, then put that sample’s CPU bit back in bit 1. So sample 0 gets 01 | 02 = 03, sample 1 gets 01, and sample 2 gets 03.

If another flag changes, it gets another packed sequence. We could store these in flag-bit order, so var tells the reader which sequence belongs to which flag. Each sequence needs ceil(n / 8) bytes for n samples. Unused bits in the last byte would be zero.

Still 3 bytes in this example. With 1,000 samples and one variable flag, it becomes 2 mask bytes + 125 packed bytes = 127 bytes. Two variable flags would take 252 bytes. The current layout takes 1,000 bytes.

If every status is identical, we could store just that one byte. The block already gives us the sample count.

These are sizes before zstd. We would need to compare compressed size and decode cost, especially for small blocks or blocks where many flags change.

A few extra things we could consider:

We could make REUSE lookup cheaper with a small key from the stack depth and a few frame IDs. Different keys mean different stacks. If the keys match, we still compare all frames before emitting REUSE. That avoids full comparisons for most misses.
On the reader side, we could cache decoded frame ranges. E.g. if REUSE points to the same 20 frames several times, we decode those IDs once. Later references can copy the decoded IDs. Perhaps we cap both the entry count and total cached frames, since a few deep stacks could take lots of memory.
For status bits, we could expand eight samples at once with a small lookup table. E.g. packed byte 05 becomes [1,0,1,0,0,0,0,0]. We shift those values to the original flag position and combine them with the other flags. This could reduce the work per sample.
For frame IDs, we could check the byte width once per range. E.g. with width 2, the whole loop reads one low byte and one high byte per ID. We then avoid checking “is this 1, 2, 3 or 4 bytes?” for every frame.
Perhaps large frame columns could get a quick compression probe. We compress a small part at two zstd levels. If the slower level barely saves any bytes, we could pick the faster one for that column. We would still compare the final result with raw storage. The probe adds work, so this probably only makes sense for larger columns.
We could keep column headers small by storing only sizes we need. A raw column needs one length. A constant column needs its decoded length and one value. Only a compressed column needs both decoded and stored lengths. The codec could fit in the low 2 bits of the length field, with the length in the remaining bits.

Navigation Menu

Repository navigation

Tachyon: use bounded columnar blocks for binary profiles #159207

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Tachyon: use bounded columnar blocks for binary profiles #159207

Description

Linked PRs

Activity

pablogsal commented on Oct 12, 2026

pablogsal commented on Oct 12, 2026

maurycy commented on Oct 12, 2026

pablogsal commented on Oct 20, 2026

ivonastojanovic commented on Oct 20, 2026

pablogsal commented on Oct 20, 2026

pablogsal commented on Oct 20, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions