...

...

Please tell me something about my container, don't be silent. I firmly intend to offer it to boost, because it's much faster than competitors (by a constant factor).

...

I am interested in using the container on a microcontroller, for which performance is crucial. I intend to use your container in combination with a custom allocator.

Cheers Chris

Hi Chris! Thank you for your answer. If you have any questions regarding the container, feel free to ask me.

Hi Alex, I can provide you with my benchmark results below. Please do not be discouraged by the potentially disappointing report, as I suspect my benchmark might be stressing the node-linked list in the wrong areas --- and with the wrong competition (std::vector). I tested the container with a floating-point benchmark that also performs numerous sequential operations on iterators ranging from [begin, end). I used a desktop PC with Microsoft Visual Studio 2013 and an ARM(R) A8 microcontroller with GCC 4.8.2. I used the container with a custom allocator having a memory pool of 512 bytes. Here is my report and the interpretation of the report below the report: --------------------------------------------------------------- I found many warnings in both GCC as well as VC: - redundant semicolons (empty statements) - local variables shadowing class members. - non-explicit conversion to/from signed/unsigned - signed / unsigned comparison - unary minus applied to unsigned type - unreferenced local variables I stripped the implementation: * I removed all exception handling and asserts. I identified the container uses in the benchmark: * Create two containers. * One container has 4 floats, the other has 5 floats. Do in a loop about 10 times the following: * On each container apply std::accumulate with std::multiplies. * On each container apply std::for_each with element incrementation. * Do the normal floating-point operations and loop management. I use a custom allocator with 512 byte pool: * typedef util::ring_allocator<T> allocator_type; I use either btree_seq or std::vector: * typedef btree_seq container_type; * typedef std::vector container_type; I perform the numerical correctness analysis: * Run on PC with VS2012.  Result OK. * Run on ARM A8 with GCC. Result OK. I perform the size analysis on the ARM(R): * using neither     :  7344 byte * using std::vector :  8928 byte, delta = 1584 * using btree_seq   : 15968 byte, delta = 8624 I perform the runtime analysis on the ARM(R): * using std::vector : 4.4 microseconds * using btree_seq   : 5.3 microseconds ----------------------------------------------------------------------------- Interpretation: The btree_seq obtains the correct result and can be used on a PC as well as microcontroller with a custom allocator. This is very positive! The btree_seq creates much more code than the corresponding use of std::vector. In addition, btree_seq runs significantly slower than std::vector in this particular benchmark. One possible explanation for this might be due to the large overhead of creating a linked list in the constructor. This is not consistent with your expected result and deserves further investigation. The code could be potentially cleaned up significantly. For this, build at very high warning levels and eliminate all warnings. As mentioned earlier, some C++11 awareness might be mandatory. An awareness of move construction, nullptr where appropriate, and construction / equating with std::initializer_list. Boost has C++11 compiler switches for these and more C++11 features. If you would like to see the code of the benchmark, it is available in the public domain. If you would like me to provide more measurement data, I might have time to compare with std::deque. I could also potentially provide you with a greater granularity regarding where the cycles and the bytes get lost with btree_seq. Please do not be discouraged by this report. It is only stressing a few use-cases, and certainly does not test btree_seq in its entirety. I encourage you to keep going. Cheers Chris On Tuesday, July 15, 2014 2:20 PM, Aleksandr Kupriianov wrote: Christopher Kormanyos writes:

...

Please tell me something about my container, don't be silent. I firmly intend to offer it to boost, because it's much faster than competitors (by a constant factor).

I am interested in using the container on a microcontroller, for which performance is crucial. I intend to use your container in combination with a custom allocator.

I think folks are still working very hard on the release. I am also very busy with normal work and the GSoC 2014 program. So could you please grant us maybe a bit more time?

Cheers Chris

Hi Chris! Thank you for your answer. If you have any questions regarding the container, feel free to ask me. By the way, if you are going to use it on microcontroller, other template parameters L,M might be better (smaller, I think), also default are good enough, I believe. I mean: btree_seq. Everybody! If you are going to use it, just tell me: Alex, I'm using it, it's cool (or not so cool). Best regards, Aleksandr Kupriianov _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

...

I tested the container with a floating-point benchmark that also performs numerous sequential operations on iterators ranging from [begin, end).

2) Performance. Yes, for iterative and random-access the vector is slightly better (but only slightly, I'm also encouraged by 5.3 : 4.2 score). Vector is champion for these operations, and probably nobody can outperform it. But as soon as insertions/deletions are necessary, my container can outperform.

I agree. Then it is important to provide the users with information regarding where btree_seq is most efficient, and where it is less efficient. Some library developers might wonder how btree_seq is different from std::list. What missing niche in the STL does btree_seq intend to fill?

3) Real app. Are you writing the real app for microcontroller now? If you use insertions/deletions, especially random ones, my container can significantly outperform.

Yes. I can work out a test case.

Even if you just use push_back, my thing can slightly outperform. However, if you use iterative-access, vector wins, but not too much. I suggest you to try to use my thing in the real app.

Yes. That's aood idea.

4) Benchmark - can you provide a link?

Yes.

5) C++11 - fully accepted. I'll deal with it soon.

OK. Give me a few days for cleanup. It's all at Github. Links will follow.

6) Warnings - fully accepted Some very high GCC Warning settings are shown below.

-Wall                          \ -Wextra                        \ -pedantic                      \ -Wmain                         \ -Wundef                        \ -Wsign-conversion              \ -Wunused-parameter             \ -Wuninitialized                \ -Wshadow                       \ -Wunreachable-code             \ -Wswitch-default               \ -Wswitch-enum                  \ -Wcast-align                   \ -Wmissing-include-dirs         \ -Winit-self                    \ -Wfloat-equal                  \ -Wdouble-promotion If you have -std=c++11, then you can also use: -Wzero-as-null-pointer-constant I also tested btree_seq on an 8-bit Atmel(R) AVR(R) microcontroller today. It was about 500 times slower than the ARM(R) core, but got the right results. So now btree_seq has seen some action on 8-bit, 32-bit. and 64-bit systems. ----------------------------------------------------------------- 8-bit Atmel(R) AVR(R) microcontroller Size analysis: * using neither     :  2240 byte * using std::vector :  4448 byte, delta =  2208 * using btree_seq   : 13504 byte, delta = 11264 Runtime analysis: * using std::vector : 1500 microseconds * using btree_seq   : 2200 microseconds ----------------------------------------------------------------- Cheers Chris On Wednesday, July 16, 2014 8:42 AM, Aleksandr Kupriianov wrote: Christopher Kormanyos writes:

Hi Alex,

I tested the container with a floating-point benchmark that also performs numerous sequential operations on iterators ranging from [begin, end).

Here is my report and the interpretation of the report below the report:

---------------------------------------------------------------

I found many warnings in both GCC as well as VC:

I stripped the implementation: * I removed all exception handling and asserts.

I identified the container uses in the benchmark: * Create two containers. * One container has 4 floats, the other has 5 floats.

Do in a loop about 10 times the following: * On each container apply std::accumulate with std::multiplies. * On each container apply std::for_each with element incrementation. * Do the normal floating-point operations and loop management.

I use a custom allocator with 512 byte pool: * typedef util::ring_allocator<T> allocator_type;

I use either btree_seq or std::vector: * typedef btree_seq container_type; * typedef std::vector container_type;

I perform the numerical correctness analysis: * Run on PC with VS2012.  Result OK. * Run on ARM A8 with GCC. Result OK.

I perform the size analysis on the ARM(R): * using neither     :  7344 byte * using std::vector :  8928 byte, delta = 1584 * using btree_seq   : 15968 byte, delta = 8624

I perform the runtime analysis on the ARM(R): * using std::vector : 4.4 microseconds * using btree_seq   : 5.3 microseconds

---------------------------------------------------------------------------- -

Interpretation:

The btree_seq obtains the correct result and can be used on a PC as well as microcontroller with a custom allocator. This is very positive!

The btree_seq creates much more code than the corresponding use of std::vector. In addition, btree_seq runs significantly slower than std::vector in this particular benchmark.

The code could be potentially cleaned up significantly. For this, build at very high warning levels and eliminate all warnings.

As mentioned earlier, some C++11 awareness might be mandatory. An awareness of move construction, nullptr where appropriate, and construction / equating with std::initializer_list. Boost has C++11 compiler switches for these and more C++11 features.

If you would like to see the code of the benchmark, it is available in the public domain.

I encourage you to keep going.

Cheers Chris

Hi, Chris! 1) Thank you for spending some time to test my container. 2) Performance. Yes, for iterative and random-access the vector is slightly better (but only slightly, I'm also encouraged by 5.3 : 4.2 score). Vector is champion for these operations, and probably nobody can outperform it. But as soon as insertions/deletions are necessary, my container can outperform. 3) Real app. Are you writing the real app for microcontroller now? If you use insertions/deletions, especially random ones, my container can significantly outperform. Even if you just use push_back, my thing can slightly outperform. However, if you use iterative-access, vector wins, but not too much. I suggest you to try to use my thing in the real app. 4) Benchmark - can you provide a link? 5) C++11 - fully accepted. I'll deal with it soon. 6) Warnings - fully accepted. Best regards, and thank you again Aleksandr _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On 17 July 2014 06:44, Aleksandr Kupriianov wrote:

...

Some library developers might wonder how btree_seq is different from std::list. What missing niche in the STL does btree_seq intend to fill?

Shortly speaking my thing is between list and vector.

Instead of yet another container, have you thought about adding another kind of index to Boost.Multi-index? The big benefit to that is that it makes it very easy to compare different types of indices with real world data. I've done this kind of thing with sequenced indices vs. random access indices.

Another niche is possible porting string on its basis. I.e., something like this:

typedef string_abstraction string; typedef string_abstraction scalable_string;

Unlikely to be that useful, as the iterator invalidation and contiguous guarantees are vastly different in the two cases. -- Nevin ":-)" Liber mailto:nevin@eviloverlord.com (847) 691-1404

Ion Gaztañaga writes:

A btree based data structure seems useful. However, in your links, I see little documentation on how the data structure works, how you mapped an associative container into a sequence container, the implementation of insert,erase,operator[]... That would help a lot to receive more feedback.

Hi Ion! The documentation added: http://alexkupri.github.io/array/ C++11 features coming soon. Best regards, Aleksandr

On Mon, Aug 11, 2014 at 8:52 AM, Aleksandr Kupriianov wrote:

All requirements fulfilled: documentation, license, c++11, warnings suppressed. http://alexkupri.github.io/array/

It does not yet support the C++11 allocator model. Some changes required: 1. Do not call .construct or .destroy directly, but only via std::allocator_trails Note: If you want to support both C++11 and C++03 compilers then do this when BOOST_NO_CXX11_ALLOCATOR is _not_ defined - and when it is defined, use placement new for construction Note: Do this only for construction of value_type objects; for all other construction use placement new 2. Do not use the ::pointer member types of the allocator type directly. Use std::allocator_traits to obtain these types. 3. A C++11 allocator's 'pointer' type may not be a raw pointer, so do not make that assumption. p = a.allocate(n); - p should be the allocator's ::pointer type. If you need a raw pointer from it, std::addressof(*p) will get you that address - but preserve the value of p for as long as you keep that address around, because p is what you will give back to .deallocate(). Note: Both std::addressof and std::allocator_traits mentioned have Boost equivalents; boost::addressof and boost::allocator_traits; if you want to avoid the BOOST_NO_CXX11_* checks and conditional code for each. Glen

I'm pretty excited by this container; I'll start testing it as soon as I find an excuse for it. 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. My limited understanding is that a CO structure would be more general and thus work on supercomputers and microcontrollers equally well without the programmer needing to tweak the L and M parameters. I still need to read the relevant paper [1] and your implementation in detail. Cheers. Jeremy [1] http://epubs.siam.org/doi/abs/10.1137/S0097539701389956 http://www.cc.gatech.edu/~bader/COURSES/UNM/ece637-Fall2003/papers/BDF00.pdf

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

Nigel Stewart writes:

Just curious if this container might be better suited to sorting (and re-sorting) than a std::vector.

btree_seq is better than vector in insert/delete intensive applications. Since sorting does not require insert/delete, btree_seq will be comparable (but slower) with vector in sorting.

And, I guess, for containers of large structs that are relatively expensive to copy or swap by value?

I expect that after including btree_seq into boost, ptr_btree_seq will be built upon the btree_seq, like ptr_vector upon vector. Leaves of ptr_btree_seq will physically contain only pointers to the large objects, but the container will have the same interface as btree_seq. (This should not take much effort, since ptr_* implementation already exists for vector.)

Vadim Stadnik writes:

Hi Alexander,

I have already made a few comments. I'd like say a bit more about one of previous comments.

Normally, Boost community does NOT review projects published without Boost license. Are you going to add Boost license to your project?

Regards, Vadim Stadnik

Hi, Vadim! Thank you for your kind words. 1) License - accepted. 2) Documentation - accepted (coming soon). 3) Examples - accepted (after adding c++11 features). Best regards, Aleksandr