Re: [boost] Determining interest in container with efficient random access insert and erase

Subject: Re: [boost] Determining interest in container with efficient random access insert and erase
From: Andy Thomason (a.thomason_at_[hidden])
Date: 2015-09-11 12:19:02

With my commercial background I am very septical about
O(lg(N)) search algorithms as they do not work well on modern hardware
unless you are very careful with the data layout.

A vector will linear search faster than a tree with up to a few hundred
elements. Easy to prove and search for Stroustrup's opininion on complex
data structures.

A middle-first tree is often better (I don't now if there is an academic 
equivlent).
Store the middle element first in a vector and the two quartiles second 
and third etc.

The first few and last few accesses are in the same cache lines.

I see a lot of pointers and allocated data structures in this as well as 
about
eight levels of indirection of push_back which will be fun in debug mode :)

I don't want to piss on the bonfire...

Andy.

On 11/09/2015 16:16, Rene Rivera wrote:
> On Fri, Sep 11, 2015 at 5:10 AM, Chris Clearwater <chris_at_[hidden]> wrote:
>
>> Greetings,
>>
>> I have written a library with the intention of submitting it to
>> Boost.Container. My container implements O(log n) random access
>> insert/erase and has a strong focus on performance while supporting the
>> interfaces of the standard library sequence types. An example application
>> would be the character buffer of a text editor.
>>
>> Useful links:
>>   - Source code: https://github.com/det/segmented_tree_seq
>>   - Documentation: http://det.github.io/segmented_tree_seq/
>>   - Benchmarks: https://github.com/det/segmented_tree_seq/tree/benchmarks
>>
>> Any feedback is greatly appreciated.
>>
> First.. You are going to need to add some documentation as to how your
> container works with regards to complexity order. Second.. Your
> implementation is rather hard to follow (but this is not a necessarily a
> bad thing). I say that because I was trying to figure out how your
> container attains the O9log n) you claim. And AFAICT, because of this <
> https://github.com/det/segmented_tree_seq/blob/master/include/boost/container/segmented_tree_seq.hpp#L1278>,
> that your container is just another implementation of an order statistic
> tree <https://en.wikipedia.org/wiki/Order_statistic_tree>. Which is a data
> structure that has been proposed for Boost (and standardization) at various
> times.
>
>

---
This email has been checked for viruses by Avast antivirus software.
http://www.avast.com