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

Subject: Re: [boost] [COUNTERTREE + SUBALLOCATOR ] version 2.0
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2013-08-28 13:05:14

Hi Jeremy

Thanks by your interest in the library

About the interface with Multi Index, I think it's a good idea, but I think
first we must build a robust library with all the functionality, and to be
checked by the Boost users, and after export ideas and code to others
libraries. I insist in the checking of the users for don't export bugs and
problems.

I think Multi Index and countertree can share many useful information, with
the additional advantage than the author of Multi Index , and I are living
in the same city, and comment face to face taking a coffee, is more
pleasant.

About the synchronization, my idea is to do a lock-free data structure from
the user view-point. The locks are automatic, and don't be managed by the
users. The users don' need lock, only must take care about what they want
to do. But for a safe code they must use the new functions. As say in the
message

*“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.”*

This design permit to the user think the problem as if you have isolated
threads, because the relation between the threads through the data
structure is safe.

If you have any other question, please, ask me, and I will try to respond.
The questions are an excellent source of ideas.

Sincely yours

Francisco Tapia

2013/8/27 Jeremy Maitin-Shepard <jeremy_at_[hidden]>

> 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.
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost