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

Subject: Re: [boost] [container] New container: why is everybody silent?
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2014-08-19 21:15:20

On 18 August 2014 19:24, Aleksandr Kupriianov <alexkupri_at_[hidden]> wrote:

>
> 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.
>

OK.  I might have missed it, but I can't see in the docs an explanation of
how to choose L and M for a given data structure and cache line size.  Is
there a formula?
Knowing data structure size sounds reasonable but how many people know the
size of their cache line?  And do I understand correctly that since it is
specified as a compile-time constant, the value in the source code needs to
be changed or at least checked when compiled on a given machine for the
first time?
I guess I'm concerned that these L and M values limit the ease of
portability, by which I mean the additional effort required to consider the
performance effects of the parameters on one machine or another is very
different to the ease of use of std::vector.

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.

Well, the point of the bibliography is primarily for anyone looking at your
data structure to understand why it is designed that way.  A specific
reference to a textbook or paper allows us to see that and also potentially
see what you missed.  If your implementation is based on a Wikipedia
article then cite that.  Maybe I'm banging the science drum too hard, but I
personally find that kind of explicit trail of theory helpful.

Jeremy