]> git.ipfire.org Git - thirdparty/libsolv.git/commit
Add hash table to dirpool for O(1) directory lookup 611/head
authorAlberto Ruiz <aruiz@redhat.com>
Wed, 18 Mar 2026 07:23:09 +0000 (07:23 +0000)
committerAlberto Ruiz <aruiz@redhat.com>
Wed, 18 Mar 2026 07:25:38 +0000 (07:25 +0000)
commited609d9554227ccc3969b704273c8c1da29eab43
tree9c3a46840fbc355141b9cb6049b82887e868c593
parent1e377699be108ec82bb798ec9c223d45d84a733c
Add hash table to dirpool for O(1) directory lookup

Profiling repo2solv with perf on a full primary+filelists workload
(Fedora 42, ~75K packages) revealed that dirpool_add_dir consumed
48.6% of all cycles and caused 92% of last-level cache misses.

The root cause: directories sharing a parent are stored across
multiple non-contiguous blocks in the dirs[] array, linked through
the dirtraverse[] auxiliary array. Looking up whether a (parent,
component) pair already exists required scanning every block for
that parent -- O(B*C) where B is the number of blocks and C the
average block size. Popular parents like /usr accumulate hundreds
of blocks from filelists data, causing cache-hostile pointer chasing
across scattered memory.

Replace the dirtraverse-based lookup with an open-addressed hash
table mapping (parent, comp) pairs to directory ids. The hash is
computed via relhash() (same scheme used for reldeps), and parent
is verified by a short backward walk to the block header -- always
within a few entries of the matched slot, so it stays in the same
cache line.

The hash table is built on demand and resized at 50% load factor.
The dirtraverse array is kept for dirpool_child/dirpool_sibling
traversal APIs but is no longer needed for the add_dir fast path.

Benchmark results (Fedora 42 metadata, 5 runs, median wall-clock):

  primary + filelists:  10,256 ms  vs  20,028 ms baseline  (49% faster)
  primary only:          2,629 ms  vs   2,546 ms baseline  (within noise)

perf profile after the change shows dirpool_add_dir dropped from
48.6% to 1.78% of cycles. Output is byte-identical to baseline.
src/dirpool.c
src/dirpool.h