1 unstable release
0.1.0 | Jul 10, 2024 |
---|
#1136 in Algorithms
25KB
401 lines
IntTable
This crate primarily exists to provide the IntTable type, a u64 -> V map that doesn't hash its keys. Naturally, this means it is very fast and very simple, but it also means you can shoot yourself in the foot if your keys aren't random.
This wraps hashbrown's excellent HashTable.
This crate is similar in concept to intmap, but even more specialised.
On an Intel(R) Core(TM) i7-10610U(c) CPU(SM) benchmarks give:
test tests::u64_get_built_in ... bench: 137,371.43 ns/iter (+/- 9,054.12)
test tests::u64_get_indexmap ... bench: 149,108.03 ns/iter (+/- 7,065.53)
test tests::u64_get_intmap ... bench: 75,162.35 ns/iter (+/- 6,712.48)
test tests::u64_get_inttable ... bench: 26,691.09 ns/iter (+/- 1,751.50)
test tests::u64_insert_built_in ... bench: 171,752.70 ns/iter (+/- 1,718.64)
test tests::u64_insert_checked_intmap ... bench: 90,894.35 ns/iter (+/- 1,546.25)
test tests::u64_insert_checked_inttable ... bench: 66,617.80 ns/iter (+/- 735.63)
test tests::u64_insert_entry_intmap ... bench: 112,376.50 ns/iter (+/- 34,792.00)
test tests::u64_insert_entry_inttable ... bench: 47,010.84 ns/iter (+/- 967.00)
test tests::u64_insert_indexmap ... bench: 190,656.54 ns/iter (+/- 1,239.85)
test tests::u64_insert_intmap ... bench: 89,994.67 ns/iter (+/- 7,028.86)
test tests::u64_insert_inttable ... bench: 64,322.85 ns/iter (+/- 3,030.45)
test tests::u64_insert_without_capacity_built_in ... bench: 400,817.85 ns/iter (+/- 3,907.70)
test tests::u64_insert_without_capacity_intmap ... bench: 867,470.10 ns/iter (+/- 40,745.32)
test tests::u64_insert_without_capacity_inttable ... bench: 158,921.34 ns/iter (+/- 1,686.26)
test tests::u64_resize_intmap ... bench: 59,305.74 ns/iter (+/- 16,336.20)
test tests::u64_resize_inttable ... bench: 229.94 ns/iter (+/- 1.89)
On an actually decent CPU you can probably get faster numbers.
Legal-ish notice
I've done my best to respect the original MIT license as much as possible, but I may have overlooked some code to which it applied. If such is the case, please point out the problematic section and I will include the notice there.
Dependencies
~485–780KB
~12K SLoC