Subject: [boost] [COUNTERTREE + SUBALLOCATORS] Errors corrected, .New Lock system, manycore strategies
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2013-12-02 02:01:39
I have corrected several errors ( thanks to the people who sent me comment,
suggestions and bugs).
The lock mechanism ( 1 Writer / N Readers) have been redesigned in order
to correct previous errors and increment the speed. The actual version is
built over spinlocks and yield functions. It provide an alternative to the
upgrade mutex. You have a detailed description with diagrams and examples
This library provide a concurrent and thread safe implementation of the *tree
based data structures* (set, multiset, map and multimap, plus a unordered
tree named vector_tree) with *random access iterators* and *access by
position like a vector*. This permit to *distribute the elements* stored in
the trees, between an *arbitrary number of threads*, identically as do with
the vectors. Over it you can use many algorithms designed for vectors ( as
quicksort over an unsorted tree) and *making easy the design of parallel
algorithms* applied to the tree based data structures , and their use by
the multicore development tools..
[image: Imágenes integradas 1]
These data structures are based on a kind of augmented red-black trees,
where each node have a counter with with the number of nodes under which
permit the access by position, like in a vector, to the elements stored in
the tree, and random access iterators. I named this tree of counters
Until now, in many practical problems, the binary trees was not used , by
the difficult for to distribute the elements stored between an arbitrary
number of cores, and the difficult for to develop parallel algorithms. This
limitation force to use only 1 thread with these data structures. And with
big problems, usually it is not a good solution. With the countertrees,
perhaps it would be interested reevaluate some algorithms, and make an
comparison between the present algorithms and the possible options, in
order to see the performance, the memory used and the flexibility.
If you are interested, you have a brief document ( 2 pages) about the manycore
this library, and other brief
pages) where provide a global vision of the project and their parts. I
think is a good starting point in order to examine the library.
*You can find the code and the documentation in my web pages in dropbox*
*or if you prefer in a git format*
Please, if you have any idea , any comment or see any fail, any lack,
please say me in order to improve the library, and provide between all ,a
fast, robust and reliable tool to the C++ programmers.
If you want more information, need something, please, say me, and I will
try to do.
Thanks by your interest. Yours
Francisco Jose Tapia
e-mail : fjtapia_at_[hidden]