On 18 August 2014 19:24, Aleksandr Kupriianov
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