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.