News for hackers. Stuff that matters.
Re:Btrees are the new black by checker659 on Wednesday April 02, 2014 @03:34AM (#7514108)
What about false sharing?
Re:Btrees are the new black by jjh42 on Wednesday April 02, 2014 @03:36AM (#7514113)
I only benchmarked and considered the single-threaded case. Multithreading is a whole new can of worms.
Re:Btrees are the new black by warmfuzzykitten on Wednesday April 02, 2014 @06:22PM (#7519481)
Trivially, one could synchronize around the entire tree.

However, if modified nodes are always copied, then the only node that matters is the root node (since there can never be a partially modified tree accessible from the root), which boils down to atomic update of a root node pointer. Should be very efficient.

There is, of course, a performance implication of node copying, but it only affects add/delete/replace performance - read access runs at full speed - and it is cache-friendly, as well.

Re:Btrees are the new black by jjh42 on Thursday April 03, 2014 @08:03PM (#7528127)
If you want different threads to see the same data structure then I think you would also need a mechanism to prevent multiple threads modifying the same node and clobbering each other's changes.
Re:Btrees are the new black by warmfuzzykitten on Monday April 14, 2014 @04:50PM (#7588844)
Yes, of course. But there is a difference between read, which only requires synchronization at the root node, and write, which requires synchronization at the modified leaf and potentially all the way back up the path from leaf to root.
Re:Btrees are the new black by hyc_symas on Thursday April 03, 2014 @01:00PM (#7524183)
LMDB was written specifically for multi-threading; all of its shared data structures are cache-line aligned to prevent false sharing. This is also essential to allowing readers to run with no locks.