Boost logo

Boost :

Subject: Re: [boost] [lockfree] review
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-07-30 05:11:07


hi gordon,

> > the new interface is rather complex because i need to resolve from a
> > `handle' (pointer or 16bit index) to a node pointer (and reverse). maybe
> > tagged_pointer and freelist can be exposed to the public interface at a
> > later point, but for now i hesitate to expose the full freelist
> > interface.
> > maybe but maybe a simplified version could be exposed?
>
> An interesting problem. If my team adapts split-ordered list to freelists,
> it will give another basis for the abstraction.

that would be useful!

> > good eye, the missing word is `freelist'. the michael/scott paper only
> > mentions that they use a freelist, but they simply omit the that part
> > from the pseudocode. in my implementation, the same memory location is
> > used for linking the nodes of the queue and the nodes of the freelist.
>
> Aha. I'd like to see this kind of stuff in the documentation, either on
> the pages describing each algo or in the Rationale.

well, maybe a rationale shall be added, describing the implementation in detail
...

> > i should probably add a recommendation to `the art of multiprocessor
> > programming'. iirc it also covers the michael/scott queue ...
>
> Oh cool, I have that but I haven't looked at it. If the 'folklore' is via
> there, please say so.
>
> So I looked at Herlihy's stack versus yours, and there is one mismatch in
> push():
>
> bool push(T const & v)
> {
> node * newnode = pool.construct(v);
>
> if (newnode == 0)
> return false;
>
> tagged_node_ptr old_tos = tos.load(detail::memory_order_relaxed);
>
> for (;;) {
> tagged_node_ptr new_tos (newnode, old_tos.get_tag());
> newnode->next.set_ptr(old_tos.get_ptr());
>
> if (tos.compare_exchange_weak(old_tos, new_tos))
> return true;
> }
> }
>
> In the Herlihy implementation, old_tos is fetched effectively at the
> beginning of the loop. It seems to me that with your code, if someone
> else pushes or pops between when old_tos is fetched and the CAS, it will
> keep on looping until it sees the same node that used to be at the top is
> on top again.

compare_exchange actually updates old_tos, so there is no need to load it again
...
again, this is the difference between paper and actual implementation ;)

> > lock-free data structures cannot scale linear: when multiple threads try
> > to perform the same operations, one compare_exchange will fail and one
> > of the threads has to retry. the more threads the more retries.
>
> Well, you happen to have chosen the data structures with the tightest
> memory access patterns. :-D
>
> Since you are only accessing the beginning and end of the stack/queue,
> you're seeing massive contention. A hash table can scale linearly. I
> didn't believe it until I saw it with my own eyes!

sure, a hash table will have less contention, so it should scale linearly ...

> >> We could clean up the split-ordered list code and adapt it to freelists
> >> for donation to Lockfree, if the library is accepted.
> >
> > as a workaround for the dcas requirement one can use array indices (the
> > reason for my current freelist refactoring).
>
> Ideally the freelist could have one consistent interface with different
> underlying behavior (i.e. size of return type) depending on what's
> supported. I don't know if this is possible.

currently, i have to use two freelist implementations (one for tagged pointers
and one for tagged indices), both share the same interface, but introduce the
concept of a `handle' that can converted to a pointer using a member function of
the freelist (and a `tagged handle' for ABA prevention). i just hesitate to
expose these classes, because the interface couldn't not be changed anymore ...

> I assume your freelist has the problem that the size of the counter tag
> determines the probability of some horrible silent ABA failure? This
> should also be documented.

actually the tagged pointer and tagged index. i'll queue it for the `rationale'
section of the docs.

> > if i feel comfortable with your
> > implementation, i am happy to adopt it!
>
> I'm checking with my team to see if they're still willing to put in the
> effort to bring this to Boost. Obviously I'd also put in good work and be
> ultimately responsible for it if it happens.

cool! i'll definitely try to help integrating it into boost.atomic

cheers, tim




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk