View mode: basic / threaded / horizontal-split · Log in · Help
January 14, 2011
RedBlackTree with Array Store
Hi,

I've noticed that, just as you can have a heap with an array-backed store, you
can also have a binary search tree with the same store (although structured
differently; see attachment for a bare-bones unsorted binary tree
implementation -- which I have NOT yet tested, but which I can test if it will
be used). The improvement will be in data locality, and while it may seem to
use a bit more space than a link-based tree, I think it's worth it to let the
RedBlackTree class use a custom store, such as any store that has
getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.

How does this idea sound?
Thank you!
January 14, 2011
Re: RedBlackTree with Array Store
I haven't looked at your code, but I came across the idea of a vector 
map in C++ (based on a std::vector of std::pairs) with some performance 
advantages over std::map if there aren't a lot of insertions and 
deletions.  The idea is a good one.  Whether it's best as a custom store 
for RedBlackTree or as a separate container I don't know.

The "unsorted binary tree" you mention doesn't sound right.  Such a 
container would need to be kept sorted.

On 14/01/11 15:55, %u wrote:
> Hi,
>
> I've noticed that, just as you can have a heap with an array-backed store, you
> can also have a binary search tree with the same store (although structured
> differently; see attachment for a bare-bones unsorted binary tree
> implementation -- which I have NOT yet tested, but which I can test if it will
> be used). The improvement will be in data locality, and while it may seem to
> use a bit more space than a link-based tree, I think it's worth it to let the
> RedBlackTree class use a custom store, such as any store that has
> getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.
>
> How does this idea sound?
> Thank you!
January 14, 2011
Re: RedBlackTree with Array Store
> The "unsorted binary tree" you mention doesn't sound right.  Such a
container would need to be kept sorted.

It would, IF it was implemented the same way as a heap. But it's not. Take a look
at my implementation if you get the chance; every node has four members in
addition to the value, which are the indices of the (1) node (self-pointer), (2)
parent, (3) left child, and (4) right child. There's no direct mapping between the
place of a node in the tree and its place in the array, so there's no need to keep
anything sorted.

Hopefully that made sense... let me know if it doesn't. :)
January 14, 2011
Re: RedBlackTree with Array Store
I see.  It's not what I meant when I described the vector map.  That has 
no pointers/indices stored in it.  The position in the tree is implied 
by the index.

On 14/01/11 18:21, %u wrote:
>> The "unsorted binary tree" you mention doesn't sound right.  Such a
> container would need to be kept sorted.
>
> It would, IF it was implemented the same way as a heap. But it's not. Take a look
> at my implementation if you get the chance; every node has four members in
> addition to the value, which are the indices of the (1) node (self-pointer), (2)
> parent, (3) left child, and (4) right child. There's no direct mapping between the
> place of a node in the tree and its place in the array, so there's no need to keep
> anything sorted.
>
> Hopefully that made sense... let me know if it doesn't. :)
January 14, 2011
Re: RedBlackTree with Array Store
On Fri, 14 Jan 2011 00:25:17 -0500, %u <wfunction@hotmail.com> wrote:

> Hi,
>
> I've noticed that, just as you can have a heap with an array-backed  
> store, you
> can also have a binary search tree with the same store (although  
> structured
> differently; see attachment for a bare-bones unsorted binary tree
> implementation -- which I have NOT yet tested, but which I can test if  
> it will
> be used). The improvement will be in data locality, and while it may  
> seem to
> use a bit more space than a link-based tree, I think it's worth it to  
> let the
> RedBlackTree class use a custom store, such as any store that has
> getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.
>
> How does this idea sound?
> Thank you!

Didn't look at your code exactly, but from reading this discussion, what  
you have implemented is basically a memory pool ;)  Yes it's possible, and  
dcollections does this.  in our discussions on bringing dcollections' red  
black tree to std.container, I asked if my custom allocator that uses an  
array for storage should be ported or not, and we decided to defer custom  
allocation until later.  I fully expect that a custom allocation scheme  
will be introduced at some point in std.container.

-Steve
January 15, 2011
Re: RedBlackTree with Array Store
> Didn't look at your code exactly, but from reading this discussion, what you
have implemented is basically a memory pool ;)

Huh, interesting... I didn't think about it that way, but in a way, that's true.
:) I just thought of it as some tree representation that did not use pointers.


> Yes it's possible, and dcollections does this.  in our discussions on bringing
dcollections' red black tree to std.container, I asked if my custom allocator that
uses an array for storage should be ported or not, and we decided to defer custom
allocation until later.  I fully expect that a custom allocation scheme will be
introduced at some point in std.container.

Oh cool! So long as it's on the (probably very long!) to-do list, that's great.
Thanks for letting me know. :]

(By the way, if I happen to find enough time to modify the current version to
allow for a custom allocator, would that be potentially of any use?)
January 15, 2011
Re: RedBlackTree with Array Store
On Fri, 14 Jan 2011 20:57:18 -0500, %u <wfunction@hotmail.com> wrote:

>> Didn't look at your code exactly, but from reading this discussion,  
>> what you
> have implemented is basically a memory pool ;)
>
> Huh, interesting... I didn't think about it that way, but in a way,  
> that's true.
> :) I just thought of it as some tree representation that did not use  
> pointers.
>
>
>> Yes it's possible, and dcollections does this.  in our discussions on  
>> bringing
> dcollections' red black tree to std.container, I asked if my custom  
> allocator that
> uses an array for storage should be ported or not, and we decided to  
> defer custom
> allocation until later.  I fully expect that a custom allocation scheme  
> will be
> introduced at some point in std.container.
>
> Oh cool! So long as it's on the (probably very long!) to-do list, that's  
> great.
> Thanks for letting me know. :]
>
> (By the way, if I happen to find enough time to modify the current  
> version to
> allow for a custom allocator, would that be potentially of any use?)

Sure, in fact you could currently use dcollections to test it, since it  
allows for custom allocators ;)

-Steve
Top | Discussion index | About this forum | D home