Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8481

Re: btree vs binary tree

Show all headers | View raw

In article <p8gnv3$jm$1@news.albasani.net>,
Melzzzzz  <Melzzzzz@zzzzz.com> wrote:
>On 2018-03-16, Dan Cross <cross@spitfire.i.gajendra.net> wrote:
>> In article <p8cu67$bm2$1@news.albasani.net>,
>> Melzzzzz  <Melzzzzz@zzzzz.com> wrote:
>>>I am playing with different implementation of binary trees, and compare
>>>to btree that is provided in Rust. btree blows out of water any binary
>>>tree regarding cache performance. eg just iterating through btree is
>>>order of magnitude faster then binary tree.
>>>So question is : Why implementations use still red black tree for maps
>>>instead of btree (eg C++)?
>>>I can think in direction to make binary trees more cache friendly but
>>>this is difficult. Just using btree is much more efficient on current
>>>hardware ;(
>>
>> Most of them still use RB trees, but they do so for a reason.
>>
>> Btrees are indeed more cache efficient. However, they require
>> movement of data to split and rebalance nodes; this can invalidate
>> iterators, which violates the C++ standard for e.g. std::map and
>> std::set.
>
>Oh, I forgot that ;p
>
>>
>> Rust has more precise semantics with respect to ownership, lifetimes
>> and borrowing, so can statically guarantee that an iterator to some
>> node in a btree (which would presumably require borrowing an immutable
>> reference to the tree) doesn't exist at the same time that a node
>> is being inserted into that tree (which would require a mutable
>> reference). At least, this is true with the usual caveats about
>> unsafe code, etc, etc.
>
>Yeah, you can't mutate btree in Rust while iterating. But mine
>implementation of binary trees in Rust can ;)
>I completely forgot that you can't iterate and change btree in same loop
>;)
>
>
>>
>> C++ can't make that sort of guarantee, so C++ uses a different data
>> structure: if I have an interator that points to a node in an RB
>> tree, then even if I rebalance the tree to maintain the RB invariants,
>> I'm I can still safely indirect the iterator to manipulate that
>> node.
>
>Well, I don't really get why C++ can just say that changes into that
>structure (btree), just invalidate iterators. 
>It's really much faster because of cache hits.

You can, and there are implementations of btree in C++ that mimic
the interface of some common STL containers:

https://opensource.googleblog.com/2013/01/c-containers-that-save-memory-and-time.html

You just can't use them as drop-in substitutes for structures where
the standard guarantees that iterators won't be invalidated if you
modify the container.

	- Dan C.

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

btree vs binary tree Melzzzzz <Melzzzzz@zzzzz.com> - 2018-03-15 04:52 +0000
  btree vs binary tree Chad <cdalten@gmail.com> - 2018-03-15 14:27 -0700
    Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 15:13 +0000
  Re: btree vs binary tree "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-03-16 21:51 +0800
  Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 15:06 +0000
    Re: btree vs binary tree Melzzzzz <Melzzzzz@zzzzz.com> - 2018-03-16 15:30 +0000
      Re: btree vs binary tree cross@spitfire.i.gajendra.net (Dan Cross) - 2018-03-16 18:20 +0000

csiph-web