perf: 1000 heap allocations per read in the align path (and how to fix it)

[BenjaminDEMAILLE]

What I measured

Wrapping the global allocator in a counter and running 200 000 real reads (yeast, ERR12389696) at --runThreadN 8:

ALLOCSTATS count=200093070 bytes=401267330431

1 000 heap allocations per read, and 2 MB allocated per read.

For context, at 16 threads on 2M reads a sampled profile attributes roughly 8% of on-CPU time to mimalloc itself (mi_bchunk_try_find_and_clearNX, mi_free, mi_malloc_aligned, mi_bitmap_clearN) and another ~3.5% to _platform_memmove. So this is the second-largest cost in the aligner after find_best_junction_position, and unlike that one it is not intrinsic work — it is bookkeeping.

Where it comes from

stitch_recurse clones a WorkingTranscript at each include/exclude branch (src/align/stitch.rs:1195, :1320, :2403), and MAX_RECURSION is 100 000 per cluster. Each clone copies four Vecs:

pub(crate) struct WorkingTranscript {
    pub(crate) exons: Vec<ExonBlock>,
    pub(crate) junction_motifs: Vec<SpliceMotif>,
    pub(crate) junction_annotated: Vec<bool>,
    pub(crate) junction_shifts: Vec<(u32, u32)>,
    ...
}

The three junction vectors are empty on an unspliced read, and an empty Vec does not allocate, so the steady-state cost is exons plus whatever the spliced reads add. cluster_seeds contributes its own per-read set: anchor_set, anchor_indices, windows, the win_bin map, a Vec per window, and diag_ranges with a Vec per diagonal.

What I am not doing without asking

The obvious fix is inline storage for those four vectors, which in practice means smallvec with inline capacities around 8/4/4/4. CONTRIBUTING.md says a new dependency has to be raised before the PR, so I am raising it rather than opening one.

Three ways I can see, and I have no strong preference between the first two:

1. smallvec. Widely used, no build-script or C, MSRV-friendly. One more dependency on a project that publishes to crates.io and builds on five platforms.
2. A small in-tree inline vector. No dependency, but it is unsafe-adjacent code to review and maintain for a type this project would only use in one place.
3. Per-read scratch reuse instead, hoisting the cluster_seeds containers into thread-local buffers cleared per read. This attacks a different share of the 1 000 and needs no new type, but it is a larger and more invasive change to a function the code already calls the top align hotspot.

What I would want to agree before writing any of it

The ceiling is roughly 11% of wall clock, not more, since that is what the allocator and the copies add up to in the profile. That is worth having, but it is not the 2× that "1 000 allocations per read" might suggest at first reading, because mimalloc is genuinely fast and is already tuned in src/main.rs.

I would rather hear which of the three you want than pick one and have the shape of it be the thing that gets sent back. Happy to do the measurement for whichever you prefer first.

Reproducing the number takes about ten lines: wrap mimalloc::MiMalloc in a GlobalAlloc that increments two atomics, and print them from a Drop guard in main. I can push that as a feature-gated helper if it would be useful to keep around.

[BenjaminDEMAILLE]

Correcting myself on two counts, and downgrading the recommendation.

The cause I named was wrong

I wrote above that WorkingTranscript cloning in stitch_recurse was where the 1 000 allocations per read come from. I counted instead of assuming, and it is not.

Per read, at 200 000 reads and 8 threads:

site	per read
WorkingTranscript clones	121 clones, but only 85 allocations (the three junction vectors are empty on unspliced reads, and an empty Vec does not allocate)
finalised Transcripts	~50, each allocating several vectors
SeedCluster creation (window.alignments.clone())	~8

So the clones are about 8.5% of the total, not the bulk. My "obvious" cause was one of several, and not the largest.

And removing 7.6% of the allocations changes nothing measurable

Transcript::read_seq turned out to be a pub field that is filled with a full copy of the read at every finalised transcript and never read anywhere in the crate — the compiler confirms it, every error after deleting it is a write. Removing it is #170.

	allocations	bytes
before	200 093 070	401 267 330 431
after	184 966 576	397 400 813 793

15.1 million allocations gone, 7.6% of the total, 3.87 GB less copying. Wall clock across six interleaved rounds at 87-92% CPU idle: medians 20.90 s against 20.65 s, direction mixed, inside the spread. No measurable change.

What that means for this issue

I estimated an ~11% ceiling from the profile's mimalloc share. That estimate does not survive the experiment: if 7.6% of the allocations can go without moving the clock, the share attributed to the allocator is not sitting on the critical path the way a self-time ranking makes it look. mimalloc is fast, and it is already tuned in src/main.rs.

So I would not spend a new dependency on this, and I withdraw the smallvec question rather than leave it open for someone to answer. Option 3 (per-read scratch reuse in cluster_seeds) is still defensible as a cleanup, but on present evidence it should not be sold as a performance change either.

If someone has a workload where allocation shows up differently — long reads, high multimapping, a much larger genome where the working set is not cache-resident — that would be the thing to measure before revisiting. On yeast at 150 bp it does not pay.

Happy to close this unless you want it kept open as a record of the numbers.

[Psy-Fer]

I'm not sure why this was made a PR?

[BenjaminDEMAILLE]

I'm not sure why this was made a PR?

It's a issue

[Psy-Fer]

okay sure. Not sure why this is an issue.

[BenjaminDEMAILLE]

Fair, and it stopped being one while it was open.

I opened it to ask whether a new dependency was worth it for the allocation work, then measured instead of waiting: removing 7.6% of the allocations (#170) moved the clock not at all, so the answer is no and there is nothing to decide. That is the whole of it.

Closing. The only thing worth keeping from it is the number, in case someone else looks at mimalloc's share of a profile and reaches for the same idea: it is not on the critical path at this scale.

Sorry for the round trip.