In a language with GC, RCU is just an thing you can atomically swap to a new version. C is why RCU is complicated.<a href="https:&#x2F;&#x2F;pkg.go.dev&#x2F;sync&#x2F;atomic#example-Value-Config" rel="nofollow">https:&#x2F;&#x2F;pkg.go.dev&#x2F;sync&#x2F;atomic#example-Value-Config</a>

In GC languages, RCU is just atomic pointer update with immutable data structure. In a language without GC, it requires delayed destruction to avoid memory safety issues.Linux kernel&#x27;s RCU waits for all CPU cores to context switch and disables preemption when reading RCU data structure. This is not usable in normal application programming.

Related reading:What is RCU, Fundamentally? - <a href="https:&#x2F;&#x2F;lwn.net&#x2F;Articles&#x2F;262464&#x2F;" rel="nofollow">https:&#x2F;&#x2F;lwn.net&#x2F;Articles&#x2F;262464&#x2F;</a>Amusingly, the first several hits for &quot;Golang RCU&quot; point to GitHub repos which contain a bunch of Mutexes (locks), import &quot;unsafe&quot;, and haven&#x27;t been updated in 7+ years. Perhaps this is not the most well-understood area of computer science.Let&#x27;s face it, when was the last time you needed RCU for a web app?

Math definition goes something like this: f(n)=O(g(n)), if exists C such that f(n) &lt; C x g(n), when n goes to infinity.Function “quickSortExecutionTime(permutation)” depends on exact input (each permutation&#x2F;shuffle has different exec time), parameter “permutation” can not go to infinity, so it can’t be used with O(n) directly. (Parameter need to be single real number)QuickSortWorstCaseTime(n) is single valued function thus, it can be used with O(n) notation. Same is true for quickSortAvgCaseTime(n) and quickSortBestCaseTime(n).But you answered my question. (Very indirect “Yes” :) )

No, I believe you are forgetting the context. Big O is a upper bound on the growth rate of a function. In this case the function describes the time taken, therefore a higher time is a &quot;worse case&quot;. So Big O is, in this scenario, a bound on the worst case time taken (essentially what the commenter said).Certainly as I understand it your definition of Big O is incorrect - it provides exclusively an upper bound. Big Omega is used for a lower bound and Big Theta for an upper and lower bound.

Not according to my understanding of the subject, my copy of &quot;Introduction to Algorithms&quot;, and Wikipedia.Big O is an upper bound for a function growth - being O(f(n)) means growing asymptotically slower than f(n) (up to a multiplication by a constant).Small o is a lower bound for a function growth - being o(f(n)) means growing asymptotically faster than f(n) (up to a multiplication by a constant).Big theta means the function grows exactly that fast - being Θ(f(n)) means the function is both O(f(n)) and o(f(n)), so being exactly f(n) up to a multiplication by a constant. In practice, due to typographical limitations, people use O(n) where Θ(n) would be more precise.Average case, best case, worst case, amortized etc complexities are a wholly different thing. For example, quick sort is Θ(n^2) worst case and Θ(n log n) average case.

Big O is upper bound (worst case), big theta is average case, big omega is lower bound (best case).

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?

A JVM with a moving GC can have wildly difference performance characteristics than C. A moving collector can use a bump allocator which can result in these independently allocated chain nodes ending up adjacent in memory which will mitigate lots of the cache miss costs of linked hash tables. Especially in microbenchmarks where basically all allocations come from the hash table under measurement.In C it is much more likely that these allocations are spread around memory and in different cache lines.

I&#x27;d love to read it if it did, but honestly I wonder if enough&#x27;s changed to warrant a new edition. Everything I&#x27;m reading now is still relevant.

That&#x27;s a fantastic book. I hope it gets a new edition at some point.

Interestingly, I was just reading the book &quot;Java Concurrency in Practice&quot; 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 poked through a few messages in that thread and while there is a space benchmark, there is no time benchmark, something I would expect to see on switching from a LL to a cache-aware implementation. Phoronix, who would benchmark a potato if you told them it gave you better performance, has an article with no benchmarks. The commit says it should be good enough for someone to run a perf benchmark.Is it common to add an unused data structure into the kernel without understanding its performance characteristics? If they are available it is not obvious to someone who has read the article, read the commit message, read lkml, went looking for benchmarks, and has still come up with no concept of how this might perform in realistic or synthetic scenarios.

I&#x27;m pretty sure pphysch is correct.&gt; Seriously, a simple google search or taking a minute to follow the first link in the article would have shown you that the patch set obviously came with a benchmark [1].If you&#x27;re referring to the table with headers &quot;number xarray maple rhash rosebush&quot;, it&#x27;s an estimate of memory usage, not a benchmark. And the author (Matthew Wilcox) says &quot;I&#x27;ve assumed an average chain length of 10 for rhashtable in the above memory calculations&quot;, which folks questioned. So there&#x27;s reason to doubt its correctness.&gt; It’s someone posting a patch to the kernel mailing list, not some random kid on GitHub, there is no point assuming they are an idiot to try to shine.Let&#x27;s just let the work speak rather than flagging the author as an idiot or genius...at present rosebush is unproven and based on questionable assumptions. That might change in future rounds.

The entire point of a LWN article like this is to accurately summarize the patch sets and email discussions for casual readers. No need for the snark.

Seriously, a simple google search or taking a minute to follow the first link in the article would have shown you that the patch set obviously came with a benchmark [1]. It’s performance data on actual real use in the kernel which are missing. It’s someone posting a patch to the kernel mailing list, not some random kid on GitHub, there is no point assuming they are an idiot to try to shine.My days as a LWN subscriber are now far behind but gosh reading the comments there was a blast. I had forgotten how good proper technical discussions used to be.[1] <a href="https:&#x2F;&#x2F;lore.kernel.org&#x2F;lkml&#x2F;20240222203726.1101861-1-willy@infradead.org&#x2F;" rel="nofollow">https:&#x2F;&#x2F;lore.kernel.org&#x2F;lkml&#x2F;20240222203726.1101861-1-willy@...</a>

That&#x27;s how I read it too, and that seems bizarre to me. The one request for actual performance numbers was ignored? That seems pretty crappy.

Because many others did that benchmarks before and come to vast improvements over simple linked lists.

&gt; &quot;I&#x27;ve assumed an average chain length of 10 for rhashtable in the above memory calculations.&quot;&gt; Reviewers were, as ever, skeptical in the face of assertions about performance without corresponding measurements. Peng Zhang asked &quot;how much performance improvement is expected if it is applied to dcache?&quot; Wilcox didn&#x27;t reply to Zhang&#x27;s question.Am I reading this right that the author supplied no actual (benchmarking) evidence to support their proposed performance optimization?

That would be fine, except that in v2 the buckets are fixed size.What happens when more than 20 objects end up with the exact same hash?

No? From the text at least, the low bits are just used to select the bucket, this is a common technique (and reason for using power of two sizes such that you don&#x27;t need a full modulo).Once you&#x27;re in a bucket, it does full hash match, then I assume (didn&#x27;t look at the patch) actual key comparison.

The rhashtable&#x27;s bucket_table struct stores a random seed (the hash_rnd field) that is folded into the calculation of the hash. Without knowing what the seed is going to be, an attacker has no way to precompute keys with colliding hashes.

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)

A hash table by any other name