6 ms·

A hash table by any other name

127 points by signa11 2y ago

pphysch 2y ago
> "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?
- kelnos 2y ago
  That'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.
- RandomThoughts3 2y ago
  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] https://lore.kernel.org/lkml/20240222203726.1101861-1-willy@infradead.org/ https://lore.kernel.org/lkml/20240222203726.1101861-1-willy@...
  - jonhohle 2y ago
    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.
  - pphysch 2y ago
    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.
  - scottlamb 2y ago
    I'm pretty sure pphysch is correct. > 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're referring to the table with headers "number xarray maple rhash rosebush", it's an estimate of memory usage, not a benchmark. And the author (Matthew Wilcox) says "I've assumed an average chain length of 10 for rhashtable in the above memory calculations", which folks questioned. So there's reason to doubt its correctness. > 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'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.
- rurban 2y ago
  Because many others did that benchmarks before and come to vast improvements over simple linked lists.
o11c 2y ago
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)
- masklinn 2y ago
  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't need a full modulo). Once you're in a bucket, it does full hash match, then I assume (didn't look at the patch) actual key comparison.
  - o11c 2y ago
    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?
    - samatman 2y ago
      If it were my hash table, the arrays would just be unrolled linked lists. So a "twenty object" bucket would actually store 19 objects, and if the last one wasn't null it would contain a pointer to the next bucket. I'm willing to presume these folks know what they're doing, so that's probably what's happening here.
    - tialaramex 2y ago
      Yes it does seem like a problem, by my reading this will just endlessly try to "split" the bucket of 20 items, hoping that eventually one of the items goes into a new bucket leaving space, but if they have the same hash that never happens, disaster. If I'm wrong I don't think this code does a good enough job of explaining what's going on, and if I'm correct it's defective and should not ship. Even if this situation "shouldn't" happen, it clearly can happen, you just have to get unlucky, and it's difficult to compute how unlikely that is for real systems, so better to ensure that "We got unlucky" isn't a disaster for the kernel.
metadat 2y ago
Related reading: What is RCU, Fundamentally? - https://lwn.net/Articles/262464/ 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?
- yencabulator 2y ago
  In a language with GC, RCU is just an thing you can atomically swap to a new version. C is why RCU is complicated. https://pkg.go.dev/sync/atomic#example-Value-Config https://pkg.go.dev/sync/atomic#example-Value-Config
- facturi 2y ago
  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'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.
commandlinefan 2y ago
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.
- kevincox 2y ago
  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.
- NoahKAndrews 2y ago
  That's a fantastic book. I hope it gets a new edition at some point.
  - commandlinefan 2y ago
    I'd love to read it if it did, but honestly I wonder if enough's changed to warrant a new edition. Everything I'm reading now is still relevant.
    - NoahKAndrews 2y ago
      Virtual threads seem like a change worth covering, but yes, it's hardly obsolete.
stoperaticless 2y ago
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?
- lkirkwood 2y ago
  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 "worse case". 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.
  - stoperaticless 2y ago
    Math definition goes something like this: f(n)=O(g(n)), if exists C such that f(n) < C x g(n), when n goes to infinity. Function “quickSortExecutionTime(permutation)” depends on exact input (each permutation/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” :) )
    - lkirkwood 2y ago
      It's true that in the case of a sorting algorithm it's not immediately obvious how to analyse the time complexity with Big O. However, I feel that you may be getting bogged down in semantics. Perhaps it is accurate to say that when Big O is used to describe the time complexity of a function in computer science the variable n in O(f(n)) usually describes the size of the input, which may not be common knowledge. But if the question is: > Have programmers redefined O to specifically mean worst case? Then in general I would say no. I suppose to answer more concretely I would have to ask: "Which programmers?"

127 points by signa11 2y ago

> "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?

kelnos 2y ago
That'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.
RandomThoughts3 2y ago
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] https://lore.kernel.org/lkml/20240222203726.1101861-1-willy@infradead.org/ https://lore.kernel.org/lkml/20240222203726.1101861-1-willy@...
- jonhohle 2y ago
  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.
- pphysch 2y ago
  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.
- scottlamb 2y ago
  I'm pretty sure pphysch is correct. > 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're referring to the table with headers "number xarray maple rhash rosebush", it's an estimate of memory usage, not a benchmark. And the author (Matthew Wilcox) says "I've assumed an average chain length of 10 for rhashtable in the above memory calculations", which folks questioned. So there's reason to doubt its correctness. > 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'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.
rurban 2y ago
Because many others did that benchmarks before and come to vast improvements over simple linked lists.

o11c 2y ago

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)

masklinn 2y ago
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't need a full modulo). Once you're in a bucket, it does full hash match, then I assume (didn't look at the patch) actual key comparison.
- o11c 2y ago
  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?
  - samatman 2y ago
    If it were my hash table, the arrays would just be unrolled linked lists. So a "twenty object" bucket would actually store 19 objects, and if the last one wasn't null it would contain a pointer to the next bucket. I'm willing to presume these folks know what they're doing, so that's probably what's happening here.
  - tialaramex 2y ago
    Yes it does seem like a problem, by my reading this will just endlessly try to "split" the bucket of 20 items, hoping that eventually one of the items goes into a new bucket leaving space, but if they have the same hash that never happens, disaster. If I'm wrong I don't think this code does a good enough job of explaining what's going on, and if I'm correct it's defective and should not ship. Even if this situation "shouldn't" happen, it clearly can happen, you just have to get unlucky, and it's difficult to compute how unlikely that is for real systems, so better to ensure that "We got unlucky" isn't a disaster for the kernel.

metadat 2y ago

Related reading: What is RCU, Fundamentally? - https://lwn.net/Articles/262464/ 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?

yencabulator 2y ago
In a language with GC, RCU is just an thing you can atomically swap to a new version. C is why RCU is complicated. https://pkg.go.dev/sync/atomic#example-Value-Config https://pkg.go.dev/sync/atomic#example-Value-Config
facturi 2y ago
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'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.

commandlinefan 2y ago

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.

kevincox 2y ago
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.
NoahKAndrews 2y ago
That's a fantastic book. I hope it gets a new edition at some point.
- commandlinefan 2y ago
  I'd love to read it if it did, but honestly I wonder if enough's changed to warrant a new edition. Everything I'm reading now is still relevant.
  - NoahKAndrews 2y ago
    Virtual threads seem like a change worth covering, but yes, it's hardly obsolete.

stoperaticless 2y ago

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?

lkirkwood 2y ago
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 "worse case". 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.
- stoperaticless 2y ago
  Math definition goes something like this: f(n)=O(g(n)), if exists C such that f(n) < C x g(n), when n goes to infinity. Function “quickSortExecutionTime(permutation)” depends on exact input (each permutation/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” :) )
  - lkirkwood 2y ago
    It's true that in the case of a sorting algorithm it's not immediately obvious how to analyse the time complexity with Big O. However, I feel that you may be getting bogged down in semantics. Perhaps it is accurate to say that when Big O is used to describe the time complexity of a function in computer science the variable n in O(f(n)) usually describes the size of the input, which may not be common knowledge. But if the question is: > Have programmers redefined O to specifically mean worst case? Then in general I would say no. I suppose to answer more concretely I would have to ask: "Which programmers?"