Re: [boost] [COUNTERTREE + SUBALLOCATOR ] version 2.0

Subject: Re: [boost] [COUNTERTREE + SUBALLOCATOR ] version 2.0
From: Jeremy Maitin-Shepard (jeremy_at_[hidden])
Date: 2013-08-27 16:03:18

Francisco José Tapia <fjtapia <at> gmail.com> writes:

>[snip]
>  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)

I haven't looked too carefully at the library, but certainly a tree that
maintains rank information is a useful data structure.  In principle it
seems it would be ideal to make it as generic as possible, i.e. built on top
of a generic binary search tree that supports maintaining an arbitrary
aggregate statistic, i.e. with a user-specified type and user-specified
update function.  Your countertree, which would provide random access
iterators, etc. could then be a simple wrapper over the more generic tree
library.

It also seems it would be ideal if your library could interface with the
Boost Multi Index Containers library, as that would maximize usage options,
but I don't know how feasible that is.

Another comment is that my own experience is that more often than not, in a
multithreaded program, synchronization is needed for more than just
maintaining the invariants of a particular data structure, like your
countertree, and therefore it generally makes sense for any necessary
locking to be handled by the application rather than by any particular data
structure library.  That is, the set of operations that need to appear
atomic will depend on the application, and may likely involve things outside
the control of your single data structure.  Lock-free data structures are
the exception, where you actually gain something by integrating the
syncronization with the data structure.