A hash table by any other name
In lwn comments a guy insists that “O(f(n)) is by definition a bound over the worst-case case input to a function.”
Is that actually true?
Mathematically: O(f(n)) is asymptotic bound when n approaches infinity, which could be used to describe worst, best, average and other cases.
Have programmers redefined O to specifically mean worst case?
Interestingly, I was just reading the book "Java Concurrency in Practice" where the author measures the performance of an array-based hash table like the one described here with a linked-list based hash table and finds that the linked list comes out ahead performance-wise.
> "I've assumed an average chain length of 10 for rhashtable in the above memory calculations."
> Reviewers were, as ever, skeptical in the face of assertions about performance without corresponding measurements. Peng Zhang asked "how much performance improvement is expected if it is applied to dcache?" Wilcox didn't reply to Zhang's question.
Am I reading this right that the author supplied no actual (benchmarking) evidence to support their proposed performance optimization?
Is it just me, or is this unsafely assuming that collisions can only happen in low bits, not for the full hash (despite it being only 32 bits)
Related reading:
What is RCU, Fundamentally? - https://lwn.net/Articles/262464/
Amusingly, the first several hits for "Golang RCU" point to GitHub repos which contain a bunch of Mutexes (locks), import "unsafe", and haven't been updated in 7+ years. Perhaps this is not the most well-understood area of computer science.
Let's face it, when was the last time you needed RCU for a web app?