Re: [boost] [container] New container: why is everybody silent?

Subject: Re: [boost] [container] New container: why is everybody silent?
From: Aleksandr Kupriianov (alexkupri_at_[hidden])
Date: 2014-08-18 05:24:02

Jeremy Murphy <jeremy.william.murphy <at> gmail.com> writes:

> 
> Did you create it as part of a thesis?  If so, it would be nice to see the
> thesis too.  If not, it would be nice to see some discussion about
> which/whose B-Tree you have implemented and a bibliography.  I'm not
> intimately familiar with this literature but a question that immediately
> comes to mind is whether your implementation is cache-oblivious and why.

1) It's not a part of a thesis.
2) Well, it is cache-efficient, not cache-oblivious. (In other words, you 
should choose L and M so, that they fit well for a desired data structure and 
size of cache line. If it was cache-oblivious, it would work for all sizes of 
cache line.) Cache-oblivious implementation (like in your reference) would 
probably require custom allocator and might trigger problems with fragmentation. 
On the other hand, many processors have small size of cache line (for example, 
i7 has 64 bytes for L1, L2 and L3), so I don't think that cache-oblivious 
implementation is necessary.
3) I just combined concept of sequence container and b-tree for access. I did 
not use any existing concepts or code, just did it from scratch. There are many 
implementations of similar concepts, for example, __gnu_cxx::rope. rope combines 
binary tree and sequence in the similar way. There is an article in wikipedia 
on the rope. There is a comparison of my container with rope in my main.cpp, 
although it is switched off.