3 ms·
A below transition fullness the insertion process takes N kicks with exponentially decreasing probability (for some constants depending on the fullness level an
by nullc 5y ago
A below transition fullness the insertion process takes N kicks with exponentially decreasing probability (for some constants depending on the fullness level and number of hash functions). E.g. 1/2^n kicks.
Not something you can really describe as wildly erratic.
If latency is particularly critical in your application, you could couple the hash table with a small "stash" map and perform a constant maximum number of kicks per insert, and when you reach the limit stick the current straggler in the map to be continued on the next insertion. As long as the constant maximum is well above the average the map will stay empty most of the time.
- toxik 5y agoThe fact that you're talking about probabilities sort of proves my point. You're instead saying it could be worse, and I'm saying random execution times in your critical paths is generally undesirable. It depends on your application of course, but if you have anything realtime or near realtime, I would definitely take consistent execution times. There is a related e-mail from IdSoft's John Carmack about this at [1] which I found very interesting. [1] http://number-none.com/blow/blog/programming/2014/09/26/carmack-on-inlined-code.html http://number-none.com/blow/blog/programming/2014/09/26/carm...
- nullc 5y agoThere are 'random' execution times in the critical paths of essentially everything on a modern general purpose computer, unfortunately. What matters for realtime operation is that the worst case is bounded and that the bound is acceptable.