Nailgun: A Rust DNS performance testing client
leshow.github.io
leshow.github.io
in_flight: FxHashMap<u16, QueryInfo>
in_flight: [Option<QueryInfo>; 65536]
anyways, fun project
The nice thing about the stack is that it's warmer (more likely to be in cache), but this is less valuable for these larger sizes where the structure is too large to all fit in fast cache anyway.
Actually depending on how sparse the map is, that's a reason not to do this at all. I don't know what a FxHashMap is, but if you've got a u16 key and only a small number of entries in your map, some maps won't need more than a few cachelines to store that data, far smaller than the 1.5MB contemplated above.
Anyway with anything like this, measure three times, mark twice, cut once. If you don't have a performance problem, needn't do anything, if you do have a performance problem you need to measure it before you try to fix it.
It is the stdlib hashmap with the default hashing function changed from siphasher to fxhash.
I fully expect there to be some low hanging fruit, for instance the hashmap should probably be created with some default pre-allocated capacity but instead it's just initialized with `new`. It's as you said though, it seems plenty fast (at least to me) at the moment so while the rabbit holes are interesting I'd probably be better served by cleaning up certain bits of code.
I would add the size hint if your program has any reason to know what hint to give (blind guesses are worse than just calling new) and otherwise forget optimizing it until it's too slow.
I mean, probably today, but:
1. If you're worried about bounds checks you are likely not thinking about this problem in the right way. The bounds check is a couple of CPU instructions, a register compare and a conditional jump. The jump is never taken, the CPU will remember that if we do this often, and everything is in registers or instruction cache. Then, having discerned that we're in bounds, we do a memory dereference.
Actually no modern CPU waits until then, the CPU has concluded that we probably aren't going to branch, so it will emit the memory read, and while that takes its sweet time the CPU can do the comparison, and as anticipated decide not to take the branch it never takes.
So we're actually waiting on the memory read, which is why we care about not using a hash map, because the hash map might incur two memory reads if we get unlucky. But on the other hand, if the hash map was small enough to fit in cache at least it arrives before the CPU goes into a coma because of how slow memory reads are to main memory.
2. Optimizers get smarter. It's clearly not impossible to do the analysis and decide this check isn't necessary. So I think that means you shouldn't rule it out.