Re: [boost] Review managers wanted for augmented data structures

Subject: Re: [boost] Review managers wanted for augmented data structures
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2013-03-03 01:57:14

On Sun, Mar 3, 2013 at 1:21 AM, Martin Knoblauch Revuelta <
mkrevuelta_at_[hidden]> wrote:

> > [...]
> > Augmented red-black trees could have been included in the very first
> > version of STL.
> >
> > Why is it difficult and has not been done yet?
> >
> > The major obstacle for the integration is the C++ standard specification
> of
> > computational complexities of single operations for containers and
> > iterators.
>
> I totally agree.
>

It looks like you already gained quite significant experience in this area.
Do you know any other reasons and/or concerns why augmented data structures
should NOT be added to STL?

> In the meantime, I would like to point out some previous proposals of
> similar containers (including mine):
>
> 2004 (The oldest mention I could find. I don't know if it got
> implemented): http://lists.boost.org/Archives/boost/2004/03/62823.php
> 2006: "Hierarchical Data Structures"
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierarchy.augment
> 2006: "AVL Array" (terrible name, I know)
> http://sourceforge.net/projects/avl-array
>     Renamed as "Rank List" after some debate when proposed for Boost:
>
> http://boost.cvs.sourceforge.net/viewvc/boost-sandbox/boost-sandbox/libs/rank_list/
>     This last version is probably outdated with respect to "AVL Array".
> And finally...
> 2012: Countertree
> http://dl.dropbox.com/u/8437476/works/countertree/doc/index.html
>
> I think that there are very interesting ideas in some of them.
>

Thank you for these links,
The discussion of augmented trees by Boost community is particularly
interesting.
Do you know if there was a formal Boost review of any variant of augmented
data structures and/or containers?

...

I made some design decisions favouring functionality and low
> computational complexity over space. Every node contained pointers to
> the next and previous nodes in-order. Between this and the NPSV, they
> used a lot of space. At some point I increased their size even
> further, and the shocking result was that my experiments run faster.
> This leads me to think that a specific allocator ---like the one
> proposed in Countertree--- might help a lot.
>
>
I am interested in any ideas and methods that can improve performance of
augmented data structures. The problem with dynamically allocated augmented
trees is poor locality of reference and, thus, worse performance compared
to array based data structures. Custom allocators are helpful. However,
array based variants of augmented trees are better, since they improve
locality of reference when elements are stored contiguously. B+ trees have
the important advantage over red-black trees. B+ trees can implement
various combinations of two data structures: one linear and the other one
is a B-tree. In particular, they can support a segmented array that offers
high efficiency of sequential processing close to that of a single array or
std::vector. This is one of the main reasons why I proposed for the Boost
review array based augmented B+ trees and decided to postpone the review of
dynamically allocated augmented B+ trees.

> I will love to discuss these ideas if anybody is interested. I would
> have said all this before, but I was disconnected from the Boost list
> for a long while and I didn't know that augmented trees had been
> proposed again. Sorry.
>
>
It is quite symbolic that the current Boost review schedule has 2 proposals
with different types of augmented trees. Even if both of these libraries
fail there will be new proposals, because augmented data structures are
beneficial for many user algorithms.

Thank you for very useful feedback,
Vadim Stadnik