Thread overview
RedBlackTree with Array Store
Jan 14, 2011
%u
Jan 14, 2011
Steven Wawryk
Jan 14, 2011
%u
Jan 14, 2011
Steven Wawryk
Jan 15, 2011
%u
January 14, 2011
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
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
> 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
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
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
> 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
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