Cache-Friendly B+Tree Nodes with Dynamic Fanout
jacobsherin.com
Cache-Friendly B+Tree Nodes with Dynamic Fanout
1–10 of 31 posts
Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#2Many mentions of things being too slow and other things being high performance. I'm not doubting the truthfulness, but it would have been really nice to see some hard numbers that show the magnitude of improvement in a scenario or two.
Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#3One 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.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.
Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#4> This pattern was officially standardized in C99,
No it wasn't; the C99 flexible array uses [] not [1] or [0].
When using the [1] hack, you cannot use the sizeof the structure to get the offset, because it includes the [1] array.
When using C99, you also cannot use sizeof to get the offset of the [0] element of the flexible array; sizeof is allowed to pretend that there is padding as if the flexible member were not there.
>
// The (N - 1) adjusts for the 1-element array in Payload struct
Payload *item = malloc(sizeof(Payload) + (N - 1) * sizeof(char))
If you are in C++ you need a cast; the void * return value of malloc cannot implicitly convert to Payload *.
Payload *item = static_cast(malloc(...));
Payload *item = (Payload *) malloc(...);
Payload *item = malloc(offsetof(Payload, elements) + N);
By taking the offset of the elements array, we don't need to subtract 1 from N to account for the [1] element being skipped by sizeof.
These kinds of little things take away complexity for something that must be carefully coded to avoid a memory safety issue. You really want the calculations around the memory to use the simplest possible formulas that are as easy as possible to reason about to convince yourself they are correct.
Also, when you do use sizeof in a malloc expression, the following pattern avoids repeating the type name for the size, and also lets a pair of parentheses be dropped since sizeof only requires parentheses when the operand is a type:
Payload *item = malloc(sizeof *item);Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#5is there an implementation of B+ trees that fluidly pulls from disk vs RAM?
e.g., two B+ trees, one in RAM and one on disk, with the RAM one evicted with sieve caching? possibly a very lite WAL?
something that lets you use a B+ tree bigger than RAM, and persist to disk
Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#6One 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.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.
LSM is great for write heavy loads. not sure about random reads, isn't that a B+ tree's turf?
Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#7One 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.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.
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.
Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#8Many mentions of things being too slow and other things being high performance. I'm not doubting the truthfulness, but it would have been really nice to see some hard numbers that show the magnitude of improvement in a scenario or two.
Yeah, this is some weird "performance" optimizer that half-misuses terminology and complains that using an underlying container is bad for implementing their own basic container.
Eh yes, you're implementing your basic container, naturally a basic container won't cut it.
Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#9> This pattern was officially standardized in C99, No it wasn't; the C99 flexible array uses [] not [1] or [0]. When using the [1] hack, you cannot use the sizeof the structure to get the offset, because it includes the [1] array. When using C99, you also cannot use sizeof to get the offset of the [0] element of the flexible array; sizeof is allowed to pretend that there is padding as if the flexible member were not…
Strictly speaking, in the C++ object model, malloc allocates storage but doesn't create objects. Accessing that memory as if it contains an object (even a trivial one like int) without properly giving it object lifetime is technically UB. For trivial types, this is rarely enforced in practice, but the standard says to use placement new or std::start_lifetime_as (C++23) to properly begin object lifetime.
Re: Cache-Friendly B+Tree Nodes with Dynamic Fanout
#10> This pattern was officially standardized in C99, No it wasn't; the C99 flexible array uses [] not [1] or [0]. When using the [1] hack, you cannot use the sizeof the structure to get the offset, because it includes the [1] array. When using C99, you also cannot use sizeof to get the offset of the [0] element of the flexible array; sizeof is allowed to pretend that there is padding as if the flexible member were not…
Even better and simpler..
Payload *item = (Payload *)malloc(offsetof(Payload, elements[N]));