5 ms·

One would be better off implementing cache-oblivious lookahead array [1] or even log-structured merge trees. [1] https://www3.cs.stonybrook.edu/~bender/newpub/

by thesz 1y ago

One would be better off implementing cache-oblivious lookahead array [1] or even log-structured merge trees. [1] https://www3.cs.stonybrook.edu/~bender/newpub/BenderFaFi07.pdf https://www3.cs.stonybrook.edu/~bender/newpub/BenderFaFi07.p... Both structures exploit the fact that most of the data does not change much and can be packed as tight as one wishes. Even prefixes (and suffixes) can be factored out.

pluto_modadic 1y ago
LSM is great for write heavy loads. not sure about random reads, isn't that a B+ tree's turf?
- thesz 1y ago
  B+-tree is an optimization for slightly faster sequential read, when leafs are organized into a list. LSM allow for very compact data representation because most levels of the tree do not change much through time, and this is what we are talking about here. This compact representation makes LSM trees faster at sequential reads too (less pointer chasing). Also, you can differently construct LSM trees for different operations: higher LSM tree with more narrow levels allows for faster writes, flatter LSM tree with less but wider levels allow for faster reads.
moab 1y ago
Do you know of important real-world use-cases where cache-oblivious data structures are used? They are frequently mentioned on HN when relevant discussions like this one pop up, but I would love to hear about places where they are actually used in production.
- thesz 1y ago
  You may not encounter a situation where cache oblivious structure is needed, but the knowledge that some algorithms are cache oblivious can help. For example, if you represent a set of values as an ordered array, you can perform many set operations with the (array) merge algorithm, which is cache oblivious one. You can avoid pointer chasing, etc, but your structure becomes static instead of dynamic as with, say, red-black trees. This is already a win because you can save memory and compute if at least one of your sets does not change much. But, if you apply logarithmic method [1] you can have dynamic data structure (over static one, a sorted array) and still perform most of operations without pointer chasing and with cache oblivious merging. [1] https://www.scilit.com/publications/4dd8074c2d05ecc9ed96b5cf4d6f2a9d https://www.scilit.com/publications/4dd8074c2d05ecc9ed96b5cf...
whizzter 1y ago
This article doesn't seem to be for any disk based structure but rather in-memory, in an in-memory scenario with order requirements some users have reported B-tree's as being quite competitive in mostly-read scenarios. "Write-heavy" scenarios will probably be just fine with std::map (backed by an RB-tree) since the main downside of B-tree's is write amplification that isn't an issue since memory doesn't really have any block granularity. LSM tree's in-memory will probably not be that useful as scanning becomes much more complicates (it's an interesting structure though if you have append-only workloads and want to implement dictionary for size-coded projects on top of a list).
- thesz 1y ago
  We are talking about cache friendliness here, including compact data representation. B-trees algorithm requires leaf nodes to be filled up to some prespecified fill factor, usually from 50% to 70%. This is not compact by any measures. Both LSM trees and COLA allow for much more compact storage. They also pretty cache friendly in the "cache oblivious" sense.
  - whizzter 1y ago
    Read up more on the COLA paper and funnily enough inspired by LSM-tree's I implemented something alike "basic-cola" a few months back (the thing I mentioned for size-coding), add to end of array, hierarchically re-sort for each of the bits of the new size that turns 0 from bottom up (divisible by 2, sort last 2, divisible by 4, sort last 4 and so on) and search with O((log2(n))^2) complexity. B-tree fill factors are a parameter that can be tuned to avoid extra splits depending on your insertion patterns, an in-memory variant doesn't need to be tuned like a disk-based variation. Also nothing preventing the "bottom" of an LSM variation to be a dense B-tree like structure that just gets less updates. The COLA paper also never mentions threading, an in-memory B-tree should scale better with size if there is multi-threading while I don't see an easy way to avoid big locks with COLA, maybe why the COLA paper was from 2000 and we haven't seen much additional development on it? (LSM-tree's work beautifully of course but then you basically have the double-space issue like with semi-space garbage collectors). In the end, what you choose is dependent on your application and patterns, COLA is a clever structure that probably shines in some scenarios. Like my scenario was a mostly heavy on consecutive insertions as well as lookups of potentially arbitrary compound keys, perfect for cola like since those are cheap.

by thesz 1y ago

pluto_modadic 1y ago

LSM is great for write heavy loads. not sure about random reads, isn't that a B+ tree's turf?

thesz 1y ago
B+-tree is an optimization for slightly faster sequential read, when leafs are organized into a list. LSM allow for very compact data representation because most levels of the tree do not change much through time, and this is what we are talking about here. This compact representation makes LSM trees faster at sequential reads too (less pointer chasing). Also, you can differently construct LSM trees for different operations: higher LSM tree with more narrow levels allows for faster writes, flatter LSM tree with less but wider levels allow for faster reads.

moab 1y ago

Do you know of important real-world use-cases where cache-oblivious data structures are used? They are frequently mentioned on HN when relevant discussions like this one pop up, but I would love to hear about places where they are actually used in production.

thesz 1y ago
You may not encounter a situation where cache oblivious structure is needed, but the knowledge that some algorithms are cache oblivious can help. For example, if you represent a set of values as an ordered array, you can perform many set operations with the (array) merge algorithm, which is cache oblivious one. You can avoid pointer chasing, etc, but your structure becomes static instead of dynamic as with, say, red-black trees. This is already a win because you can save memory and compute if at least one of your sets does not change much. But, if you apply logarithmic method [1] you can have dynamic data structure (over static one, a sorted array) and still perform most of operations without pointer chasing and with cache oblivious merging. [1] https://www.scilit.com/publications/4dd8074c2d05ecc9ed96b5cf4d6f2a9d https://www.scilit.com/publications/4dd8074c2d05ecc9ed96b5cf...

whizzter 1y ago

This article doesn't seem to be for any disk based structure but rather in-memory, in an in-memory scenario with order requirements some users have reported B-tree's as being quite competitive in mostly-read scenarios. "Write-heavy" scenarios will probably be just fine with std::map (backed by an RB-tree) since the main downside of B-tree's is write amplification that isn't an issue since memory doesn't really have any block granularity. LSM tree's in-memory will probably not be that useful as scanning becomes much more complicates (it's an interesting structure though if you have append-only workloads and want to implement dictionary for size-coded projects on top of a list).

thesz 1y ago
We are talking about cache friendliness here, including compact data representation. B-trees algorithm requires leaf nodes to be filled up to some prespecified fill factor, usually from 50% to 70%. This is not compact by any measures. Both LSM trees and COLA allow for much more compact storage. They also pretty cache friendly in the "cache oblivious" sense.
- whizzter 1y ago
  Read up more on the COLA paper and funnily enough inspired by LSM-tree's I implemented something alike "basic-cola" a few months back (the thing I mentioned for size-coding), add to end of array, hierarchically re-sort for each of the bits of the new size that turns 0 from bottom up (divisible by 2, sort last 2, divisible by 4, sort last 4 and so on) and search with O((log2(n))^2) complexity. B-tree fill factors are a parameter that can be tuned to avoid extra splits depending on your insertion patterns, an in-memory variant doesn't need to be tuned like a disk-based variation. Also nothing preventing the "bottom" of an LSM variation to be a dense B-tree like structure that just gets less updates. The COLA paper also never mentions threading, an in-memory B-tree should scale better with size if there is multi-threading while I don't see an easy way to avoid big locks with COLA, maybe why the COLA paper was from 2000 and we haven't seen much additional development on it? (LSM-tree's work beautifully of course but then you basically have the double-space issue like with semi-space garbage collectors). In the end, what you choose is dependent on your application and patterns, COLA is a clever structure that probably shines in some scenarios. Like my scenario was a mostly heavy on consecutive insertions as well as lookups of potentially arbitrary compound keys, perfect for cola like since those are cheap.