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