5 ms·

Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.

• j-pb 5y ago
  Since you double the table size after failing to insert/displace above a constant threshhold, e.g. 8. You have O(1) insert performance. You don't need to rehash the table either, you can add additional hash functions on each grow, or reuse your existing hash function and use bit masking, (that one does require a copy of the table, albeit no rehashing, and copying chunks is something our CPUs are really good at)
• adrianN 5y ago
  Most popular data structures only provide average case guarantees with bad worst-case bounds. Dynamic arrays also have O(wildly erratic) append. I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs.
  • toxik 5y ago
    They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.
    • touisteur 5y ago
      Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard' (quicksort, mergesort...) don't shine, with their horrid /worst case/ complexity, but also depending a lot on your input data. Quicksort with a badly chosen pivot, for example, has caused me headaches recently.
      • karpierz 5y ago
        Mergesort worst case is O(nlog(n)). If there's a downside to it, it's that you need to allocate memory.
        • touisteur 5y ago
          Which is where you get problematic tail latencies. Or your data fits on the stack.
      • phkahler 5y ago
        Heapsort is O(n * Log(n)) worst case. It is also O(n * Log(n)) in most cases, including already sorted data. Most implementations also seem to have a slightly larger constant factor than quicksort, but I think that's largely due to implementation details (one should not actually swap values that are likely to be immediately swapped again). Which one is right really does come down to a decision based on how much you care about Typical/Average/WorstCase time complexity and the actual size of your data set.
  • jcelerier 5y ago
    > I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs. we must not use the same programs :-(
• 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 ago
    The 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 ago
      There 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.