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

Groups > comp.programming > #8474 > unrolled thread

btree vs binary tree

Back to article view | Back to comp.programming

Contents

  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

#8474 — btree vs binary tree

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 ;(

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

[toc] | [next] | [standalone]

#8475

I have no idea. I'm just repyling in order to look cool. So with that....

I've seen red black trees implemented in Linux (the kernel?). It's the area where half the people have either MIT or Berkeley email addresses. It's also the same area where they refer to the Knuth books and speak of the golden ratio.

[toc] | [prev] | [next] | [standalone]

#8478

In article <f3987261-2105-4273-b43a-9f81870575fd@googlegroups.com>,
Chad  <cdalten@gmail.com> wrote:
>I have no idea. I'm just repyling in order to look cool. So with that....

Lemme know how that works out for you, Chad.

>I've seen red black trees implemented in Linux (the kernel?). It's the
>area where half the people have either MIT or Berkeley email addresses.
>It's also the same area where they refer to the Knuth books and speak
>of the golden ratio.

Yup.  Possibly among other things, the Linux kernel uses an
RB-tree to hold the set of VMAs (Virtual Memory Areas) used by a
process.  That is, the regions of the process's address space
that have been mapped, either to hold RAM or refer to a device
or file backing store.  This makes lookups for handling things
like page faults fast

Golden-ratio style numbers are sometimes used to control the
policy for rebalancing the tree, so as to amortize the cost of
doing so across several insertions.

Since btrees were mentioned, here's an example of a different
approach for a VM system implementation that scales better to
large multicore machines:

https://people.csail.mit.edu/nickolai/papers/clements-radixvm-2014-08-05.pdf

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#8476

On 15/3/2018 12:52, 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
 > ...


Reminded me of BTrieve....

-- 
   @~@   Remain silent! Drink, Blink, Stretch! Live long and prosper!!
  / v \  Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
   ^ ^   (x86_64 Ubuntu 9.10)  Linux 2.6.39.3
不借貸! 不詐騙! 不賭錢! 不援交! 不打交! 不打劫! 不自殺! 不求神! 請考慮綜援 
(CSSA):
http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa

[toc] | [prev] | [next] | [standalone]

#8477

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.

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.

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.

        - Dan C.

[toc] | [prev] | [next] | [standalone]

#8479

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...

[toc] | [prev] | [next] | [standalone]

#8481

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web