Comment by NorwegianDude
1 month ago
40 million reads per second, on a single core? 40 million reads/s is 25 ns per read, that is faster than any RAM I know of.
1 month ago
40 million reads per second, on a single core? 40 million reads/s is 25 ns per read, that is faster than any RAM I know of.
It's not like every read would make a separate trip all the way to RAM, caches are a thing and SIMD pipelines/parallelizes comparisons within a hash bucket quite well. Lookups from a hash map should amortize to something like 5-20ns per lookup these days. Abseil's Swiss Tables for C++ and Rust's Hashbrown both should reach that.
If you're looking up values from a 3 GB DB, most would have to hit RAM. Lookups form a hash map can be fast, but SQLite does quite a bit more than just a hash map lookup, and it would usually hit RAM, not L3 cache.
Parent comment said "with a million or so rows". I looked up numbers for benchmarks with ~1M entries in the hashmap.
1M 64-bit integers is only 8MB, that's still a small keyspace.
1 reply →