4 ms·
I'm not sure this is useful for a traditional database. There are lots of costs that are orders of magnitude more important. This is a CPU optimization, howeve
by srcreigh 5y ago
I'm not sure this is useful for a traditional database. There are lots of costs that are orders of magnitude more important.
This is a CPU optimization, however in a DB the major costs are 1) pulling blocks from disk 2) transferring results over a network.
Even if you assume nodes are cached in memory, a B-Tree node for a database probably fits in L1 cache. SQLite page size is 4098 bytes by default vs 8KB+ L1 cache size. Shouldn't you pay 100x the cost just to load the next node from memory, if you have a large tree? In theory that's <1% faster overall.
I'm curious whether 3x improvement is overall, or just from the binary search. (according to the benchmark it is overall 2x faster - very curious).
Also curious the size of the tree in benchmarks and the spread factor (ie how many children each B-Tree node has). I couldn't find this info from the repo. This could affect the % of time you can find the next node already in a cache.
- srcreigh 5y agoI found the answers - the tree uses 256 children by default, implying ~16kb node size on 64 bit architecture. The size of the tree in the benchmark is 1M nodes, so ~16GB tree. Pretty hefty tree! :) It's the seqential insert/get benchmarks which benefits the most from path hints. You'd only have 1 hot path down the tree in this setup (the rightmost path). Is it possible the CPU is caching multiple non-contiguous blocks (ie the hot path)? That would explain why memory access doesn't have as much of a factor as I originally thought. In other words - this technique may be useful in DBs! Disk and memory are both heavily cached in the CPU, so CPU optimizations can help for sequential/repeated local accesses
- tidwall 5y agoIt’s a 1M items, not nodes. Each item is a Go interface{}, about 16 bytes each. the benchmarks actually show that the tree is around 36MB.