platter-walk

A recursive directory entry iterator that optimizes traversal based on physical disk layout. Takes block offsets (via FIEMAP[1]), inode tables and disk cache locality into account.

For users (root) who have read access to the underlying block device it also performs readaheads on the directory indicies spanning several directories. This is somewhat of a hack since readahead() and posix_fadvise() do not work on directories directly since they use a separate cache.[2][3]

The largest benefits can be realized on HDDs with ext4 filesystems.

Traversal can be optimized for

• simple directory entry listing (name and d_type only)
• detailed entry listing (stat)
• reading file contents. Entry batches are sorted by physical offset.

See ffcnt and fastar for benchmarks.