[boost] [COUNTERTREE + SUBALLOCATOR ] version 2.0

Subject: [boost] [COUNTERTREE + SUBALLOCATOR ] version 2.0
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2013-08-26 11:02:17

 Hi

this message is to announce the version 2.0 of the *[countertree +
suballocator]* library.

 1 year ago I presented the request for the evaluation of the [countertree+
suballocator] version 1.0. The approval process is stopped due to the
absence of review managers, and in the meanwhile I continued with the
develop of this version 2.0.

 Actually the most important libraries and environments for parallel
development, *don't provide parallel algorithms for th**e** data structures
based on trees* ( set , multiset, map and multimap), and all the operations
with these data structures are done with 1 thread.

 This is due to the difficult to divide the element of the tree between an
arbitrary number of threads. (If you want to access to the element in the
position 1000, you must go sequentially forward from the position 0 or
sequentially backward from the last position.

 The [countertree + suballocator] library provide data structures set,
multiset,map and multimap compatibles with the STL data structures *plus
the access to the elements by their position like in a vector, and random
access iterators*, You can manage it like a vector. Many parallel
algorithms designed for vectors, can be used without changes with the
countertree data structures. This make *easy **the **design **of **parallel
algorithms* for these data structures.

 In the library there are a concurrent and a non concurrent versions of all
the data structures. The non concurrent version are designed for to be
executed inside 1 thread, or for to be accessed by several threads only in
read operations (like the STL data structures), they provide a bit more
speed than the concurrent version.

 The concurrent version is *thread safe with all the operations*, one
thread can be read and other writing over the same data structure in a safe
mode ( as you can see in 2.3 -examples)

 The concurrent library provide the full set of functions of the STL , plus
an *additional set of functions*. These functions have the mission of
resolve the problems appeared in the concurrent development. By example,
you have a map, find an iterator from a key and with the iterator modify
the element, but in the middle, other thread delete the element, and when
try to access with the iterator, the program crash, and it is very
difficult to reproduce the error for to debug. These additional functions
make a pack with the two things, first with a read lock which permit
concurrent reads, and when obtain the iterator with an exclusive lock for
to modify.

 These additional functions *prevent the problems* like the previously
described, with an *easy interface* for to understand and use for the final
user.

 I don't know if exist any other library with tree based structures with
random access iterators. I had search for and didn't find. If someone knows
someone, please, say me, I am interested to know something new and collect
good ideas. I suppose it don't exist because i didn't see parallel support
for data structures based on trees, in any library or parallel tools.

 I request help to the Boost community because I am in the *moment “perhaps”
*. Perhaps I forgot something, perhaps something is wrong, perhaps someone
decision was not correct, perhaps it can be done in other way...

 *Please*, is someone see any fail, any omission, any alternative or simply
any comment, please say me, in order to reach the final objective, *provide
to the C++ community a good, fast, robust and reliable tool.*

 In my opinion, this library or other with similar functionality, is the
last big part needed for to begin to think about a *concurrent STL* . You
can find concurrent libraries with vectors and arrays. You have too,
concurrent libraries with containers based on hash functions. With the
countertree library you have concurrent set, multiset,map and multimap. The
concurrent linked list can be implemented with the concurrent vector_tree (
other data structure of the library).

 The concurrent STL is a very big project, and must involve many agents and
perspectives. From the users associations, to big computers makers and big
data providers, passing by the compiler makers, the parallel tools
providers... But I am sure the *Boost community* will play a central role
by prestige, knowledge and experience designing libraries

 You can find the documentation and the code in the GitHub

https://github.com/fjtapia/countertree_2.0

 or you can see online in my dropbox page :

https://dl.dropboxusercontent.com/u/8437476/works/countertree_2.0/index.html
>

If you prefer download a file with all the code and the documentation :

https://github.com/fjtapia/countertree_2.0/blob/master/doc/countertree_2.0.zip

 Sincerely yours

Francisco Tapia

fjtapia_at_[hidden]

 ** I you don't try the library, perhaps the most interested parts of the
documentation is the 1.5.- Next improvements. Where explain the future parallel
algorithms for the library and how they can improve others areas of the
computation with the augmented trees.*