Try another hash algorithm #741

Activity

1. samueltardieu

   assigned

   Copilot

   and

   samueltardieu

   on Jan 3, 2026
2. tachsin commented on Sep 12, 2026

   

   tachsin

   on Sep 12, 2026

   Last edited by tachsin

   Contributor

   More actions

   I ran this experiment. The short answer is that ahash is consistently slower than rustc-hash for the key types this crate uses, so by the "only keep improvements" rule there is nothing to keep. Numbers and method below so it can be checked.

   What was changed

   Two trees from the same commit, differing only in:

   -type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
   -type FxIndexSet<K> = IndexSet<K, BuildHasherDefault<FxHasher>>;
   +type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<ahash::AHasher>>;
   +type FxIndexSet<K> = IndexSet<K, BuildHasherDefault<ahash::AHasher>>;

   Those two aliases are the largest single step available: they cover 49 of the ~91 hashing sites, including dijkstra, astar, bfs, fringe, idastar, the parents map in dfs, and edmonds_karp. The remaining sites use FxHashMap/FxHashSet directly (scc, topological_sort, yen, cliques, prim, connected_components) and were deliberately left alone, so their benchmarks act as a control group.

   ahash is pulled with default-features = false, features = ["std"], so neither runtime-rng nor compile-time-rng is active and AHasher::default() uses fixed constants. Iteration order therefore stays reproducible, which matters because tie-breaking in several algorithms depends on it. The full test suite passes unchanged, so this is a like-for-like comparison.

   Instruction counts (iai, the same method iai-callgrind.yml uses)

   benchmark	hash containers used	rustc-hash	ahash	change
   corner_to_corner_idastar	FxIndexSet	66,028	73,190	+10.8%
   corner_to_corner_bfs_bidirectional	FxIndexMap	2,787,240	3,038,749	+9.0%
   no_path_dijkstra	FxIndexMap	3,047,873	3,278,815	+7.6%
   corner_to_corner_dijkstra	FxIndexMap	3,077,484	3,301,434	+7.3%
   no_path_dfs	FxIndexMap (parents)	3,225,106	3,411,881	+5.8%
   corner_to_corner_iddfs	none	3,712,137	3,717,954	+0.2%

   corner_to_corner_iddfs is the control: it is the one benchmark here that touches no hash container, and it moves 0.2%. Everything that hashes gets slower, roughly in proportion to how much it hashes.

   The other 8 iai_algos benchmarks are excluded because they do not currently measure the work they run: they report on the order of a hundred instructions for searches that execute hundreds of thousands of basic blocks. That is a separate problem and I have filed it as #833.

   iai_edmondskarp is unaffected by that problem, and agrees in direction:

   benchmark	rustc-hash	ahash	change
   wikipedia_example_sparse	46,001	46,526	+1.1%
   wikipedia_example_dense	22,288	22,582	+1.3%

   Wall clock

   The project's own benches/algos.rs

   Four order-swapped passes, same harness. Positive means ahash is slower.

   benchmark	pass 1	pass 2	pass 3	pass 4	median
   corner_to_corner_dfs	+27.3	+21.7	+25.7	+20.6	+25.7%
   no_path_bfs	+12.8	+21.6	+22.7	+15.7	+21.6%
   corner_to_corner_dijkstra	+20.1	+17.6	+22.4	+21.6	+21.6%
   corner_to_corner_bfs_bidirectional	+20.6	+16.6	+21.7	+18.9	+20.6%
   corner_to_corner_bfs	+13.7	+18.0	+22.1	+19.1	+19.1%
   no_path_astar	+9.6	+17.6	+25.2	+18.2	+18.2%
   no_path_fringe	+16.3	+11.6	+25.6	+17.9	+17.9%
   no_path_dfs	+15.5	+14.6	+21.8	+16.8	+16.8%
   corner_to_corner_fringe	+2.0	+12.5	+5.5	+13.2	+12.5%
   no_path_bfs_bidirectional	+12.4	+11.8	+16.7	+11.5	+12.4%
   corner_to_corner_idastar	+2.2	+4.9	+7.9	+10.3	+7.9%
   corner_to_corner_astar	+7.6	+1.6	+1.5	+8.1	+7.6%
   separate_components (not reached by the change)	-1.8	-2.8	-1.4	-1.2	-1.4%

   All 12 benchmarks reached by the change keep their sign across every pass. separate_components is the one algorithm in this file the change does not reach, and it stays slightly negative throughout, so there is no slowdown where nothing was touched.

   Two benchmarks in this file are unusable in this harness and I have left them out:

   benchmark	as criterion printed it, each pass
   corner_to_corner_iddfs	+93%, +94%, +91%, +93%
   no_path_dijkstra	+267%, +176%, +262%, +176%

   Those figures are "the binary measured second, against the one measured first". Whichever build ran second was slower every time, so they report run order rather than code, and corner_to_corner_iddfs touches no hash container at all, so a 90% swing there cannot be the hasher.

   Large-input benchmarks (custom, 10k-250k node graphs)

   Four passes, alternating which build runs first. A result is only trustworthy if it keeps its sign in every pass, since whichever binary runs second is measured on a warmer machine.

   Algorithms reached by the change:

   benchmark	pass 1	pass 2	pass 3	pass 4	median	sign held
   grid_bfs_reachable_400	+20.9	+7.6	+21.1	+16.3	+20.9%	yes
   bfs_500	+21.2	+18.8	+20.3	+19.7	+20.3%	yes
   bfs_reach_300	+19.7	+17.1	+22.1	+17.9	+19.7%	yes
   yen_60x60_k20	+20.2	+12.1	+19.2	+13.5	+19.2%	yes
   dijkstra_500	+17.4	+18.6	+14.1	+18.1	+18.1%	yes
   dijkstra_bidirectional_500	+14.7	+19.7	+11.0	+16.9	+16.9%	yes
   dijkstra_reach_300	+16.3	+16.7	+16.5	+16.2	+16.5%	yes
   fringe_200	+15.5	+15.2	+19.5	+16.0	+16.0%	yes
   astar_500	+17.1	+14.3	+15.7	+14.3	+15.7%	yes
   dijkstra_all_200	+12.6	+13.7	+12.6	+13.5	+13.5%	yes
   astar_bag_120	+11.1	+8.3	+4.4	+2.8	+8.3%	yes
   grid_dfs_reachable_400	+7.7	-6.2	+9.3	+7.7	+7.7%	no
   edmonds_karp_dense_122	+5.5	-2.1	+1.2	+5.0	+5.0%	no
   edmonds_karp_sparse_122	+4.4	-3.2	+1.9	+0.9	+1.9%	no

   Control group — algorithms still on FxHashMap/FxHashSet, i.e. code that did not change at all:

   benchmark	pass 1	pass 2	pass 3	pass 4	median	sign held
   toposort_60k	+18.8	-25.5	-1.2	+9.1	+9.1%	no
   kruskal_20k	+3.6	-1.8	+4.2	+1.1	+3.6%	no
   toposort_groups_60k	+7.9	-13.6	+1.9	-2.6	+1.9%	no
   scc_60k	-0.7	-25.4	+0.8	+1.4	+0.8%	no
   separate_components_20k	-1.1	-12.7	+0.0	+1.3	+0.0%	no
   prim_1500n_9500e	-2.6	-6.2	-0.8	+2.0	-0.8%	no
   kuhn_munkres_250	+0.0	-4.9	-0.9	-1.9	-0.9%	no
   components_20k	-0.9	-12.4	-0.4	-1.1	-0.9%	no
   dfs_reach_300	-1.4	-5.4	-1.6	-0.1	-1.4%	no
   cliques_130	+9.1	-6.6	-2.2	-5.6	-2.2%	no

   Not one control benchmark holds its sign across the four passes, and the ones that look large in a single pass (toposort_60k at +18.8 then -25.5) flip. Eleven of the changed benchmarks hold their sign in all four. That contrast is what rules out machine drift and code-layout effects, which on this machine are worth several percent on their own.

   Standalone workload (Linux, inputs guarded with black_box)

   A second wall-clock check that cannot be affected by #833, on a 256x256 grid with Pt { x: u16, y: u16 } keys, taking the fastest of 40 runs and alternating which build goes first across 5 rounds:

   workload	rustc-hash	ahash	change
   bfs	2.684 ms	3.213 ms	+19.7%
   dijkstra	4.365 ms	5.145 ms	+17.9%
   bfs_reach	3.154 ms	3.706 ms	+17.5%
   dijkstra_all	5.464 ms	6.345 ms	+16.1%
   astar	0.031 ms	0.032 ms	+3.3%
   fringe	0.028 ms	0.029 ms	+2.9%

   ahash was slower in 5 of 5 rounds for every workload. The per-round minima, in ms:

   round	1	2	3	4	5
   dijkstra rustc-hash	4.39	4.43	4.37	4.38	4.51
   dijkstra ahash	5.19	5.18	5.16	5.15	5.17
   bfs_reach rustc-hash	3.18	3.26	3.20	3.28	3.15
   bfs_reach ahash	3.71	3.71	3.83	3.73	3.89

   The two distributions do not overlap at any point. astar and fringe move least because the Manhattan heuristic is exact on an open grid, so they expand very few nodes and do correspondingly little hashing — which is the same proportionality the instruction counts show.

   Both builds return identical results on every workload, so there is no accuracy difference to trade against.

   Why

   Hasher cost in isolation, filling and then looking up 400,000 entries in an IndexMap, best of 7:

   key type	rustc-hash	ahash	ahash/fx	with -C target-cpu=native
   (u16,u16)	11.11 ms	12.34 ms	1.11x	1.04x
   (u32,u32)	9.58 ms	13.91 ms	1.45x	1.42x
   (usize,usize)	11.96 ms	16.41 ms	1.37x	1.30x
   u64	7.99 ms	9.04 ms	1.13x	1.14x
   [u64;8]	28.29 ms	29.19 ms	1.03x	0.98x
   String (long)	54.48 ms	58.09 ms	1.07x	0.99x

   The String rows build their keys with format! inside the timed region, so allocation dominates and the hasher difference is understated there; the integer rows are the clean comparison, and they are also the ones that matter for this crate.

   ahash only reaches parity on large keys, and only once AES is enabled. FxHash is a multiply-xor per word, so for an 8-byte key it is a couple of instructions and very hard to beat; ahash's fallback path has a longer dependency chain for the same work.

   This is structural rather than benchmark-specific. Almost every hashing site in the crate keys on the caller's generic N, so the crate cannot pick a hasher per key type, and the node types in practice are small — the benchmarks use Pt { u16, u16 }, (u32,u32), (usize,usize) and u64. Grid is the only site with a concrete key type, (usize, usize), which is exactly where FxHash is strongest.

   On AES

   ahash's fast path needs AES-NI, which a default cargo build does not enable. I rebuilt both trees with -C target-cpu=native and repeated the wall-clock comparison on large inputs (10k-250k node graphs): bfs +18.9%, fringe +15.9%, astar +15.3%, bfs-reach +15.0%, dijkstra +14.3%, each holding its sign across four order-swapped passes. The isolated hasher figures in the table above tell the same story: AES narrows the gap on small keys but does not close it. A library cannot assume its users build with target-cpu=native in any case.

   Conclusion

   Every measurement points the same way, so I would suggest closing this as measured-and-rejected rather than opening a PR. Happy to test a narrower variant if you have a specific site in mind — a site with a large concrete key type would be the one case where ahash could plausibly win, and I do not think the crate currently has one.

   ---

   Measured on Windows 11, Intel Core Ultra 7 265K, 64 GB RAM; Linux figures from WSL2 Ubuntu 24.04 on the same machine, valgrind 3.22.0, iai-callgrind 0.16.1.

   Wall-clock workload source

   //! Standalone workload for issue #741.
   //!
   //! Built identically against both trees and run as `hashbench <mode> <reps>`, which
   //! reports the fastest of `reps` runs in nanoseconds. Inputs go through `black_box` and
   //! every result is folded into a printed checksum, so no part of a search can be
   //! optimised away.
   
   use pathfinding::prelude::{astar, bfs, bfs_reach, dijkstra, dijkstra_all, fringe};
   use std::hint::black_box;
   use std::time::Instant;
   
   #[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
   struct Pt {
       x: u16,
       y: u16,
   }
   
   impl Pt {
       const fn new(x: u16, y: u16) -> Self {
           Self { x, y }
       }
   }
   
   const SIZE: u16 = 256;
   
   fn successors(pt: &Pt) -> Vec<Pt> {
       let mut ret = Vec::with_capacity(4);
       if 0 < pt.x {
           ret.push(Pt::new(pt.x - 1, pt.y));
       }
       if pt.x < SIZE {
           ret.push(Pt::new(pt.x + 1, pt.y));
       }
       if 0 < pt.y {
           ret.push(Pt::new(pt.x, pt.y - 1));
       }
       if pt.y < SIZE {
           ret.push(Pt::new(pt.x, pt.y + 1));
       }
       ret
   }
   
   const fn heuristic(p: &Pt) -> usize {
       ((SIZE - p.x) + (SIZE - p.y)) as usize
   }
   
   fn at_goal(n: &Pt) -> bool {
       n.x == SIZE && n.y == SIZE
   }
   
   #[inline(never)]
   fn run(mode: &str) -> usize {
       let start = black_box(Pt::new(0, 0));
       // Every arm folds its result into a checksum that is returned, so no work can be elided.
       match mode {
           "nop" => 0,
           "dijkstra" => dijkstra(
               &start,
               |n| successors(n).into_iter().map(|n| (n, 1)),
               at_goal,
           )
           .map_or(0, |(p, c)| p.len() + c),
           "astar" => astar(
               &start,
               |n| successors(n).into_iter().map(|n| (n, 1)),
               heuristic,
               at_goal,
           )
           .map_or(0, |(p, c)| p.len() + c),
           "fringe" => fringe(
               &start,
               |n| successors(n).into_iter().map(|n| (n, 1)),
               heuristic,
               at_goal,
           )
           .map_or(0, |(p, c)| p.len() + c),
           "bfs" => bfs(&start, successors, at_goal).map_or(0, |p| p.len()),
           "bfs_reach" => bfs_reach(start, successors).count(),
           "dijkstra_all" => dijkstra_all(&start, |n| successors(n).into_iter().map(|n| (n, 1))).len(),
           other => panic!("unknown mode {other}"),
       }
   }
   
   fn main() {
       let mode = std::env::args().nth(1).unwrap_or_else(|| "nop".to_owned());
       let reps: u32 = std::env::args()
           .nth(2)
           .map_or(0, |r| r.parse().expect("reps must be a number"));
   
       // No rep count: run the workload exactly once, for counting under callgrind.
       if reps == 0 {
           println!("{mode} {}", black_box(run(black_box(&mode))));
           return;
       }
   
       // Otherwise time it, reporting the fastest run. Process startup is outside the timer,
       // and the minimum is far more robust to scheduler noise than a mean.
       let mut best = u128::MAX;
       let mut checksum = 0;
       for _ in 0..reps {
           let t = Instant::now();
           checksum = black_box(run(black_box(&mode)));
           best = best.min(t.elapsed().as_nanos());
       }
       println!("{mode} {checksum} {best}");
   }