Why we wrote a GPU disk treemap in Rust

• Three crates, one job each
• Scanning: parallel walk, then a sequential pass
• The tree is a flat array
• Sizes that match du
• Layout: squarified, and truthful
• Rendering: never draw a million rectangles
• Why wgpu
• Two things we got wrong
• The stack, in full
• Try it or read it

Storage Sifter scans a Linux filesystem and draws every file and folder as a rectangle sized by what it actually uses on disk. The tree in the screenshots on its product page is about 1.1 million items across 106 GiB. It has to stay smooth while you hover, drill in, and zoom back out.

This is how it is built, including the two places where our first instinct was wrong.

Three crates, one job each#

The workspace is three crates, and the split is the most useful decision in the project:

• scanner walks the filesystem and produces a tree. It knows nothing about drawing.
• treemap turns a list of weights and a rectangle into one rectangle per weight. It has no dependencies at all, not on the scanner and not on the UI.
• app is the eframe/egui program that puts the two together.

treemap being pure geometry is what makes it testable. The squarified algorithm has a worked example in the original paper, so the test suite can assert against known numbers rather than against a screenshot.

Scanning: parallel walk, then a sequential pass#

Scanning happens in two stages, and the second one is deliberately not parallel.

The first stage walks directories concurrently with Rayon, calling lstat on every entry, and produces an owned intermediate tree. Symlinks are recorded as leaves and never followed, which is what structurally prevents symlink loops. Subtrees on a different device are pruned, matching du -x. A directory it cannot read is flagged and the scan continues.

The second stage flattens that into the final tree in a single depth-first pass. It assigns ids, sets parent pointers, de-duplicates hard links by (st_dev, st_ino), and aggregates sizes bottom-up.

Doing the de-duplication in the sequential pass is the point. If two hard links to the same data are found by two threads, something has to decide which one gets charged for the bytes. Deciding it during the parallel walk means shared mutable state and a result that changes between runs. Deciding it in a depth-first pass means the first link in depth-first order is charged, every time, which is also what du does. The walk stays free of shared state and the output is deterministic.

The tree is a flat array#

Every filesystem object is a Node in one Vec<Node>, addressed by a u32 index. Each node stores its parent as well as its children.

The u32 is not a micro-optimisation for its own sake. It keeps each node small enough that a million of them stay cheap, and it still addresses far more entries than any real filesystem holds. Storing the parent means that when you delete something, the reclaimed bytes can be subtracted from every ancestor by walking up the chain in O(depth), with no tree rebuild and no rescan.

Sizes that match du#

Every tool in this space has to answer one question honestly: how much space will I actually get back?

Sizes come from real on-disk block counts (st_blocks * 512), not from the apparent file size. Hard links are counted once. The scan stays on one filesystem. A sparse file reports what it occupies, not what it claims. Get any of this wrong and the numbers look fine right up until somebody deletes 40 GB and gets 6 GB back.

Hard-linked files are still flagged in the UI, because deleting one link of several reclaims nothing until the last one goes.

Layout: squarified, and truthful#

The layout is the squarified treemap from Bruls, Huizing and van Wijk (2000). Children are laid out in rows along the shorter side of the remaining rectangle. The current row is extended for as long as adding the next item does not make the worst aspect ratio in that row worse. When it would, the row is fixed, its strip is carved off, and a new row starts.

The alternative, slice-and-dice, degenerates into slivers you cannot click or label. Squarified cells stay close to square, which is what makes areas comparable by eye.

One rule in that crate matters more than the algorithm: areas stay proportional, always. A zero-weight item gets a zero-area rectangle and does not distort anything else. The set tiles the bounds exactly. Nothing gets a minimum size to make it visible.

That is a deliberate refusal. It is tempting to give tiny files a floor so they can be seen, and it makes the picture a lie, because a treemap only means anything if area equals size. Hiding cells that are too small to draw is the renderer's problem, further down.

Rendering: never draw a million rectangles#

Here is the part we expected to be hard and is not.

A frame never lays out the whole tree. It lays out the children of the node you are currently looking at, and optionally one or more levels of preview inside them. On any real filesystem that is tens to hundreds of cells, not a million.

Culling happens before recursion. A cell whose short side comes out under three pixels is not drawn, and its entire subtree is skipped with it. A directory only gets a nested preview if it is tall enough for a header strip plus a cell, and wide enough for three. So the frame cost is bounded by what is visible on screen, which is bounded by the size of the window.

The drill-down zoom is a cross-fade between two full layouts, the parent zooming in and the child growing out, blended over a few frames. It morphs continuously with no snap at the end, and it costs two layouts of one level each.

The hover highlight that shows which cell a click would drill into is a single tiled texture quad rather than a per-pixel effect, so it is free.

Why wgpu#

The UI is egui through eframe, on the wgpu backend with Vulkan, and the glow (OpenGL) backend switched off. Wayland and X11 are both enabled, which covers every current Linux session type.

wgpu earns its place mainly through predictability. Painting thousands of filled rectangles with 1px borders, plus text, every frame during an animated zoom is trivial work for a GPU and irritating work for a CPU rasteriser. It also gives us one rendering path across drivers instead of an OpenGL path that behaves differently on three vendors.

The honest cost: it needs a Vulkan-capable driver. That is standard on modern desktops and absent in a VM with no GPU passthrough, over plain SSH, and on some older hardware. When that is your situation, ncdu is the right tool and we say so on the comparison page.

Two things we got wrong#

The release profile. We started with lto = true and codegen-units = 1, the usual "make it fast" defaults. For a workload that is I/O-bound in the scanner and GPU-bound in the renderer, the runtime benefit was too small to measure. The build cost was not: across a large GUI dependency tree it made compilation slow and memory-hungry enough to thrash swap and deadlock a parallel build on a modest machine. Both are gone. Plain opt-level = 3 is what ships.

Assuming the bottleneck. We assumed drawing would be the constraint and that scanning would be the easy half. It was the other way round. Drawing is bounded by the window; scanning is bounded by how fast the kernel will answer lstat, and every correctness rule above (block counts, hard links, one filesystem, never follow symlinks) lands on the scan path.

If you are building something similar, spend your time on the walk.

The stack, in full#

Try it or read it#

Storage Sifter is MIT licensed with no telemetry and no account. The AppImage runs on any distro, storagesifter-bin is on the AUR, and the source is on GitHub.

If you want to lift the layout crate for something else, it is about 200 lines and has no dependencies. Take it.

Storage Sifter is built by Fopull LLC, a software studio in Knoxville, TN. We also build this kind of thing for other people.