Re: [boost] [lockfree] review

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