This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Lock free containers.


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]