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

Groups > comp.programming > #8479

Re: btree vs binary tree

Show all headers | View raw

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.

>
>         - Dan C.
>


-- 
press any key to continue or any other to quit...

Back to comp.programming | Previous | Next — Previous in thread | Next 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