Path: csiph.com!xmission!news.snarked.org!news.linkpendium.com!news.linkpendium.com!panix!not-for-mail From: cross@spitfire.i.gajendra.net (Dan Cross) Newsgroups: comp.programming Subject: Re: btree vs binary tree Date: Fri, 16 Mar 2018 18:20:09 +0000 (UTC) Organization: PANIX Public Access Internet and UNIX, NYC Lines: 61 Message-ID: References: NNTP-Posting-Host: spitfire.i.gajendra.net X-Trace: reader2.panix.com 1521224409 18348 166.84.136.80 (16 Mar 2018 18:20:09 GMT) X-Complaints-To: abuse@panix.com NNTP-Posting-Date: Fri, 16 Mar 2018 18:20:09 +0000 (UTC) X-Newsreader: trn 4.0-test77 (Sep 1, 2010) Originator: cross@spitfire.i.gajendra.net (Dan Cross) Xref: csiph.com comp.programming:8481 In article , Melzzzzz wrote: >On 2018-03-16, Dan Cross wrote: >> In article , >> Melzzzzz 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.