Lock free containers.

[Dhruv Matani]

Hello,
  Thanks for the detailed plan. However, I did notice that you have
missed out hash_[map|set|multimap|multiset] from the stuff that you
intend working on for making lock free(or at least reentrant for
certain key operations). I admit that I do have some personal vested
interest in the hash family of containers becoming lock free(if
possible) since I use them quite extensively. So, if possible, it
would be great to have that working too.

Regards,
-Dhruv.





On 5/29/06, Phillip Jordan <phillip.m.jordan@gmail.com> wrote:
> Hi,
>
> As has been mentioned, I'm the GSOC student who'll be working on this
> stuff. I may as well use this opportunity to outline my plans for this
> project and have them taken to pieces by everyone. ;-)
>
> >> "Dhruv Matani" <dhruvbird@gmail.com> writes:
> >>
> >>>   I happened to notice that the Lock-free containers project has been
> >>> assigned in SOC. I presume that it's a library project(this one by the
> >>> looks of things). I would be interested in following the development
> >>> of the lock free containers, so I wanted to know if this is the place
> >>> where all the discussions are going to happen?
> Yes, that's certainly the plan.
>
> > On Fri, May 26, 2006 at 03:39:07PM -0700, Ian Lance Taylor wrote:
> >> I guess the people to check with would be the student doing the
> >> proposal (Phillip Jordan, phillip.m.jordan at gmail.com) and the mentor
> >> overseeing the proposal (Benjamin Kosnik, bkoz at redhat.com).
> Benjamin has said that Ulrich Drepper is co-mentoring, though I've not
> yet had any correspondence with him at all, and only found out about
> this on Friday.
>
> Joe Buck wrote:
> > However, discussions should be on this list, I think.  This may be
> > even more important with Summer Of Code projects, if we wind up with
> > someone who works hard for three months and disappears, it would be
> > nice to have some record of what the hell they did that isn't just in
> > the mentor's private mailbox. :-)
> Indeed. I've still got one written exam left on the 1st of June for
> which I have to do some work, which is why I've not posted here so far.
> After that I can commit full-time almost continuously until the end of
> August when GSOC ends and I'll be released in to this 'real world' us
> students hear so much about. :-) I certainly *plan* to hang around after
> this time. I'd probably be doing this even if I wasn't being paid
> through GSOC, as I *loved* the idea as soon as I read about it.
> Obviously, working on it full-time won't be happening once I have some
> sort of job, but I'm hoping I can get quite a lot done before that.
>
> I'm under no illusions about making *everything* lock-free, I very much
> doubt it's going to happen, so documenting what exactly works and what
> doesn't is a high priority for me. Having all these features is no good
> to users if they don't know what they are. I'll try to document as I go
> along, but there probably will be a bit of lag compared to the code.
>
>
> Despite the university-related stuff I'm currently busy with, I've had
> some time to think and poke around in existing libstdc++ and boost code,
> so the plan for the immediate future is the following:
>
> - figure out how the latest boost implements its lock-free shared_ptr,
> and use those concepts in std::tr1::shared_ptr<> in libstdc++ in a
> portable way
> - work out if shared_ptr can be made lock-free-writeable from many
> threads in a way that doesn't affect single-threaded performance (much)
> and that everyone is happy with
> - have a good look at __mt_alloc and see what can and needs to be done
> with it for lock-free containers.
> - look at a simple container (I'm thinking std::list at the moment) and
> try to make as many operations lock-free as I can
> - document exactly what is safe and what isn't, any caveats
>
> This will probably keep me busy for a while anyway, but hopefully I can
> work on some of the other containers, too, std::deque and std::vector
> would be very useful, and I think std::tr1::unordered_* can benefit as well.
> The tree-based associative containers are a problem, and I don't think
> it's possible to implement lock-free insertion/deletion operations on
> them while maintaining iterator validity semantics required by the C++
> standard. If there is any time at all to worry about this, I'll look at
> the policy-based associative containers, as Benjamin has suggested.
>
>
> I have a pretty good idea of what to do with shared_ptr, and given that
> the latest version of boost has x86(_64) and PPC asm based lock-free
> implementations of it, it essentially amounts to porting, and thus
> should be fairly simple to do. I have a couple of ideas for making
> shared_ptr multi-write-safe, but we have to look into the cost/benefit
> of it on this list.
>
>
> I'm still wading through the documentation and on mt_alloc, so I can't
> say much about that and the containers yet.
>
> By the way, I'm aware that shared_ptr isn't a container itself: I've
> been told it's a high priority, though, and since it's easy to do and
> fairly related to the container-based work, I figured it would be a
> useful way to 'warm up'.
>
> I'll post more as soon as I can.
>
> ~phil
>


-- 
   -Dhruv Matani.
http://www.geocities.com/dhruvbird/

"The biggest room is the room for improvement."
     -- Navjot Singh Siddhu.