On 09/11/2015 09:19 AM, Andy Thomason wrote:

With my commercial background I am very septical about O(lg(N)) search algorithms as they do not work well on modern hardware unless you are very careful with the data layout.

I am very careful with the data layout, my container is implemented using a counted B+Tree which is cache efficient.

A vector will linear search faster than a tree with up to a few hundred elements. Easy to prove and search for Stroustrup's opininion on complex data structures.

A B+Tree has the same layout as a vector until a certain size. Your argumens seem to be against binary trees.

A middle-first tree is often better (I don't now if there is an academic equivlent). Store the middle element first in a vector and the two quartiles second and third etc.

The first few and last few accesses are in the same cache lines.

This is very similar to the layout of a B+Tree.

I see a lot of pointers and allocated data structures in this as well as about eight levels of indirection of push_back which will be fun in debug mode :) I don't want to piss on the bonfire...

Andy.

Rene Rivera writes:

I say that because I was trying to figure out how your container attains the O9log n) you claim. And AFAICT, because of this < https://github.com/det/segmented_tree_seq/ blob/master/include/boost/container/segmented_tree_seq.hpp#L1278>, that your container is just another implementation of an order statistic tree https://en.wikipedia.org/wiki/Order_statistic_tree. Which is a data structure that has been proposed for Boost (and standardization) at various times.

FWIW, as of Boost 1.59 Boost.MultiIndex sports ranked indices: http://www.boost.org/doc/libs/1_59_0/libs/multi_index/doc/tutorial/indices.h... whose inplementation is basically an order statistic tree. Joaquín M López Muñoz Telefónica

On 12/09/2015 1:10, Glen Fernandes wrote:

...

Useful links: - Source code: https://github.com/det/segmented_tree_seq - Documentation: http://det.github.io/segmented_tree_seq/ - Benchmarks: https://github.com/det/segmented_tree_seq/tree/benchmarks

Any feedback is greatly appreciated.

The benchmarks are impressive. I hope to take a deeper look this weekend, but from my cursory glance: the implementation looks very clean too.

Ion: Is this something you would be interested in reviewing?

I'd like to separate the proposal to put that data structure into Boost and the proposal to put it into Boost.Container. The implementation looks good although I have no experience with B+Trees or augmented data structures. I think we should have more innovative container in Boost and there have been more proposals to similar data structures that were not. Regarding Boost.Container, one of the biggest problems with adding new stuff into Boost.Container is that it should be consistent with the rest of the library. The library supports C++03, supports Interprocess requirements, recursive types, SCARY iterators, etc... it must be maintained and documented as the rest of the library. I wouldn't like to maintain data structures I really don't fully understand or just left them unmaintained. We added stable_vector and static_vector but those were easier data structures. Just like we have Boost.CircularBuffer or Boost.Unordered I'd like to propose adding adding new containers in its own library. Maybe an (optionally augmented) B+Tree library would be nice, and it could also contain a sequence container based on that data structure. Just my 2 cents, does it make sense? Ion

On 09/12/2015 03:46 AM, Ion Gaztañaga wrote:

I'd like to separate the proposal to put that data structure into Boost and the proposal to put it into Boost.Container.

The implementation looks good although I have no experience with B+Trees or augmented data structures. I think we should have more innovative container in Boost and there have been more proposals to similar data structures that were not.

Regarding Boost.Container, one of the biggest problems with adding new stuff into Boost.Container is that it should be consistent with the rest of the library. The library supports C++03, supports Interprocess requirements, recursive types, SCARY iterators, etc... it must be maintained and documented as the rest of the library. I wouldn't like to maintain data structures I really don't fully understand or just left them unmaintained. We added stable_vector and static_vector but those were easier data structures.

Just like we have Boost.CircularBuffer or Boost.Unordered I'd like to propose adding adding new containers in its own library. Maybe an (optionally augmented) B+Tree library would be nice, and it could also contain a sequence container based on that data structure.

Just my 2 cents, does it make sense?

That makes sense. It may not be the best fit for Boost.Container. FWIW, I beleive I support all your requirements except for C++03 support and SCARY iterators. I think SCARY iterators should not be terribly hard to implement. Am I correct that to be SCARY iterator compatible it is ok to parameterize my iterators by allocator::pointer? It's just a problem if they depend on the allocator itself?

On Sat, Sep 12, 2015 at 8:46 PM, Ion Gaztañaga wrote:

On 12/09/2015 1:10, Glen Fernandes wrote:

...

Useful links:

...

- Source code: https://github.com/det/segmented_tree_seq - Documentation: http://det.github.io/segmented_tree_seq/ - Benchmarks: https://github.com/det/segmented_tree_seq/tree/benchmarks

Any feedback is greatly appreciated.

The benchmarks are impressive. I hope to take a deeper look this weekend, but from my cursory glance: the implementation looks very clean too.

Ion: Is this something you would be interested in reviewing?

I'd like to separate the proposal to put that data structure into Boost and the proposal to put it into Boost.Container.

The implementation looks good although I have no experience with B+Trees or augmented data structures. I think we should have more innovative container in Boost and there have been more proposals to similar data structures that were not.

Regarding Boost.Container, one of the biggest problems with adding new stuff into Boost.Container is that it should be consistent with the rest of the library. The library supports C++03, supports Interprocess requirements, recursive types, SCARY iterators, etc... it must be maintained and documented as the rest of the library. I wouldn't like to maintain data structures I really don't fully understand or just left them unmaintained. We added stable_vector and static_vector but those were easier data structures.

Just like we have Boost.CircularBuffer or Boost.Unordered I'd like to propose adding adding new containers in its own library. Maybe an (optionally augmented) B+Tree library would be nice, and it could also contain a sequence container based on that data structure.

Just my 2 cents, does it make sense?

All of your considerations make sense. I understand technical problems that can be created by adding other (potentially quite different) types of containers to Boost libraries. But I am sure that there will be new proposals and new requests for advanced data structures. Sequences are everywhere in real life applications, not only texts and strings. In addition to this, there is an interesting lesson that I have learned since written "STL extensions" library. These days big interest and selling point for augmented data structures is not so much single augmenting by count of container elements, but multiple augmenting, which supports fast summation algorithms (more generally fast computations using binary operations). These data structure can be used to compute important statistical parameters, such as mean value and standard deviation, in logarithmic running time on cheap single processor systems. The algorithms are general and can be applied to both ordered and unordered data sets. Alternative parallel computations require supercomputers to achieve the same performance. The application area - big data and data science. Regards, Vadim Stadnik

There are many variants of B+ trees. A document with explanation of the implemented data structure and key algorithms would be quite helpful. It should provide figures.

Is this a level-linked variant of B+ trees or not? No, it is not. In fact the bottom level of the tree doesn't contain any

On 09/12/2015 06:12 AM, Vadim Stadnik wrote: metadata at all. This is done to minimize cache misses. All other levels include parent pointer/parent index/length metadata.

To make this B+ tree much more useful, it should supports not only sequences, but also std::set<T>, std::multiset<T>, std::map<T> and std::multimap<T>. Alternatively, you can implement all of these standard containers using your B+ tree as underlying data structure.

Yes, I agree this would increase its usefullnes, but it's not something I plan on supporting now. You might also be interested to see the benchmarks[1] I've included in the repository. Your container is included for comparison (bpt_sequence). [1] https://github.com/det/segmented_tree_seq/tree/benchmarks

You have these characteristic in the Countertree library ( https://github.com/fjtapia/countertree_2.0) You have a data structure with the same interface than the std::vector and std::deque, with access by position like the vectors. All the operations ( read, write, modification ) are O (logN). You can find a concurrent and not concurrent version of the data structure. You have Random access iterators with access time O(logN) ( you can run a std::sort over the data structure with good results). You have too, a STL compatible set, multiset , map and multimap, with concurrent versions, with a new type of mutex designed for to improve the concurrency. And associated to this , parallel algorithms over these data structures. The library is pending of the final approval since more than a year ago. Actually, I am busy with the parallel sorting algorithms. When finish with it, I will continue with the Countertree I have designed the main part of the new version, designed for a very big trees, with new parallel algorithms. By example : create a std::set with 30000000 random elements uint64_t, my computer needs 52 seconds, with the new algorithms with 1 thread 6 seconds , and with 4 threads 3 seconds. This can be important, for the data base in memory, and in many search applications. ( A single server permit millions of operations per second ). When finish the new version , I will propose to the Boost community for the acceptation test

On 09/14/2015 04:56 AM, Chris Clearwater wrote:

I wonder too how you get constant time push_back/push_front when such an operation requires updating log(n) branch nodes in a typical counted tree implementation.

My mistake, you don't make this claim.

You have Random access iterators with access time O(logN) ( you can run a std::sort over the data structure with good results).

Traversal operations are mandated to be Amortized O(1) for random-access iterators. If the traversal is O(log N) it isn't a random-access iterator. http://en.cppreference.com/w/cpp/concept/RandomAccessIterator Neil

On 14 September 2015 at 15:11, Francisco José Tapia wrote:

The iterators are not like the vector's itertors, but they are not like the list iterators. They permit you go directly to a position without travel all the previous nodes. It's a different type. You can do a std::sort over the data structure with good results. Really the ++operator and --operator are O(1), because involve a small number of nodes, and don't depend of the tree size. The polynomy of any algorith must be multiplied by logN. Then que quicksort is O ( (logN)²).

This new type of iterator was not defined, because until now, it was not necessary. But now appear and we must name it, I name as random iterators wth access O(logN), If we agree any other name, I will use. It's a semantic problem only.

I understand the problem. I completely agree that the standard categories for Iterators are sub-optimal. The separation between orthogonal concepts such as traversal, dereference type etc. is frequently problematic. You can define a new Concept, and interfaces. There is no rational reason to reduce your potential set of actions to waiting or violating a Concept. You can't sensibly abuse an existing Concept weakening the guarantees. The standard algorithms such as std::sort provide complexity guarantees that it simply would not be able to adhere to with your iterators since the supplied iterators would be outside of the pre-conditions of calling the algorithm. Often this would 'work' without breaking. However if code has a side-effect during dereference operations it is possible that code could go wrong due to an excessive number of dereference invocations. Even if your internal iterators were robust against this, if they were wrapped in iterator adaptors that made an assumption, and forwarded the random_access guarantee it can go wrong. Violating Concept conditions is not going to be populate with Boost developers. I strongly recommend doing what you are doing, but with a clear new Concept and you will need to make clear calling standard algorithms for RandomAccessIterators with these is technically undefined-behaviour. You might even be able to provide some equivalent non-member functions. I could work with you to make some Boost.Range extension points to make optimal algorithms selected, but with very clear, precise and correct complexity guarantees.

In the same way, the interface of STL set , map , multiset and multimap is dangerous in a concurrent environment, because you obtain an iterator to a node, and before to access, other thread delete that node , and your program crash. We can wait until the C++ standard define a new interface or we can propose an interface, and begin to use, correct the failures, and learn with the experience, in order to obtain the best solution. When the standard define something, change and adapt.

This example is not at all the same since the standard guarantees nothing about concurrent access in the Concept definition. It absolutely does guarantee O(1) access. Not specifying something is very different from specifying a tighter condition you wish to ignore. Adapt by all means, but please don't violate design contracts for anything we are to include in Boost. Please don't misunderstand my intent. I'm trying to help you reach a proposal that'll be acceptable. I've frequently been tempted, while developing Boost.Range to do things that work on an implementation level, loosening Concepts. It has uniformly been an error. Now the code has extension points, but these are largely done using non-member functions and overloads and selecting tuned algorithms while retaining strict conformance for other cases. Neil Groves

Without having looked in any detail at the new container in question, the discussion does remind me of a similar container proposed by Aleksandr Kupriianov some months ago. http://lists.boost.org/Archives/boost/2014/07/215224.php It might be worth justifying why your container is better than that one, whether we can abstract aspects of both, etc. We can ask whether it is OK to add these augmented containers one by one as they are offered or whether it might be better to consider a few at once in order to design some consistent interface. Cheers. Jeremy On 16 September 2015 at 08:52, Francisco José Tapia wrote:

Thanks by your interest.

I think it will be a good idea create a Concept.

About the iterators are similar to the iterators of std::deque as say the description in cppreference.com. “As opposed to std::vector http://en.cppreference.com/w/cpp/container/vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.”

You have an valid iterator before begin (), you can use begin() -1 , if you increment this iterator you have the begin iterator. In the same way, if you decrement the end() iterator , the iterator obtained pointed to the last element.

The iterators can obtain their position in the data structure. The iterator begin() - 1 , return the value -1. This is the reason of the signed integers in the position of the elements, and the explanations of the “tons of warnings” of Mr. Clearwater.

You can add or subtract any value to an iterator, and obtain a new iterator in a time proportional to the logarithm of the distance.

The increment or decrement an iterator is a O(1) operation, because the average of jumps for to reach the previous or next node is less than 4, independent of the size of the tree.

I didn't examine in deep the Concepts before now, but after read the documentation, I think is an excellent idea.

Thanks by your information

2015-09-14 16:26 GMT+02:00 Neil Groves :

...

...

The iterators are not like the vector's itertors, but they are not like

...

list iterators. They permit you go directly to a position without

On 14 September 2015 at 15:11, Francisco José Tapia wrote: the travel

...

all the previous nodes. It's a different type. You can do a std::sort over the data structure with good results. Really the ++operator and --operator are O(1), because involve a small number of nodes, and don't depend of the tree size. The polynomy of any algorith must be multiplied by logN. Then que quicksort is O ( (logN)²).

This new type of iterator was not defined, because until now, it was not necessary. But now appear and we must name it, I name as random iterators wth access O(logN), If we agree any other name, I will use. It's a semantic problem only.

I understand the problem. I completely agree that the standard categories for Iterators are sub-optimal. The separation between orthogonal concepts such as traversal, dereference type etc. is frequently problematic. You can define a new Concept, and interfaces. There is no rational reason to reduce your potential set of actions to waiting or violating a Concept. You can't sensibly abuse an existing Concept weakening the guarantees. The standard algorithms such as std::sort provide complexity guarantees that it simply would not be able to adhere to with your iterators since the supplied iterators would be outside of the pre-conditions of calling the algorithm. Often this would 'work' without breaking. However if code has a side-effect during dereference operations it is possible that code could go wrong due to an excessive number of dereference invocations. Even if your internal iterators were robust against this, if they were wrapped in iterator adaptors that made an assumption, and forwarded the random_access guarantee it can go wrong.

Violating Concept conditions is not going to be populate with Boost developers. I strongly recommend doing what you are doing, but with a clear new Concept and you will need to make clear calling standard algorithms for RandomAccessIterators with these is technically undefined-behaviour. You might even be able to provide some equivalent non-member functions. I could work with you to make some Boost.Range extension points to make optimal algorithms selected, but with very clear, precise and correct complexity guarantees.

...

In the same way, the interface of STL set , map , multiset and multimap is dangerous in a concurrent environment, because you obtain an iterator to a node, and before to access, other thread delete that node , and your program crash. We can wait until the C++ standard define a new interface or we can propose an interface, and begin to use, correct the failures, and learn with the experience, in order to obtain the best solution. When the standard define something, change and adapt.

This example is not at all the same since the standard guarantees nothing about concurrent access in the Concept definition. It absolutely does guarantee O(1) access. Not specifying something is very different from specifying a tighter condition you wish to ignore.

Adapt by all means, but please don't violate design contracts for anything we are to include in Boost.

Please don't misunderstand my intent. I'm trying to help you reach a proposal that'll be acceptable. I've frequently been tempted, while developing Boost.Range to do things that work on an implementation level, loosening Concepts. It has uniformly been an error. Now the code has extension points, but these are largely done using non-member functions and overloads and selecting tuned algorithms while retaining strict conformance for other cases.

Neil Groves

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost