Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2011-07-29 17:24:47

Hi Tim!

On Jul 29, 2011, at 3:00 PM, Tim Blechmann wrote:
>> IMO the big question with a library like this is not so much the design as
>> the correctness.  What can we do as reviewers to verify the correctness,
>> assuming we are not lockfree gurus ourselves?  Go back to the original
>> sources.  So I did; see below.
> 
> well, there is one problem about the publications done by the lock-free gurus: 
> they don't care about the implementation, but assume a sequencially consistent 
> memory model, so they don't need to care about the required memory barriers or 
> the like ...

Yes.  Your rationale that the default options for atomic operations should ensure sequential consistency makes sense to me (from my limited experience).  

>> Could the freelist be moved into the public interface?  This is a useful
>> data structure and a simple way to avoid calls to the memory allocator.
> i need to think about this. i have changed the freelist implementation a bit in 
> order to use array indices as alternative to pointers (for ll/sc platforms 
> without support for double-word CAS).

It's better to say double-width CAS - there was a double-word CAS in separate locations that died a long time ago.

> 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.

> 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.

>> I'd like to see references for the other two algorithms, which the doc
>> currently ascribes to "folklore" - if someone would like to verify them in
>> the way I did for the queue, where would they go?  What could they read to
>> understand how it works?
> 
> 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.

In other words, you want to verify that top still points to what you just put in new->next, not that top again points to whatever it pointed to before you started looping.

I have not compared the 'folkloric' queue yet.

>> I'd like to see some performance comparisons on a couple of architectures. 
>> It is okay to have a big disclaimer saying these results may not be
>> typical and the user should do their own benchmarks.
> 
> i've started to implement a set of simple benchmarks, for including results, i 
> will need some help (my access to multiprocessor hardware is limited to my 
> workstation and my laptop)

Yes, I'm sure myself and others can find resources for that.

>> I am not experienced enough to evaluate whether the use of barriers and the
>> c++ memory model is correct.  I would like to see something in the
>> rationale describing how these choices are made.  I also thought I
>> recalled Tim saying that one of the algorithms might require more barriers
>> for untested architectures, but I couldn't find anything about that in the
>> documentation.
> 
> hopefully this is not the case anymore: all memory barriers are abstracted in 
> the memory model of atomic<>. no memory barrier needs to be issued manually, but 
> all barriers are issued via atomic<> members.

Aha, the new memory model is starting to make a little sense to me!

> 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!

> hazard pointers are patented, so they are not an option for boost.

I didn't like them anyway.  (sour grapes, actually they seem the safest way.  sigh.)

> finding the 
> right positions for memory barriers can be quite hard and usually requires a 
> full understanding of the data structure. atomic<> will make it way easier to 
> write a correct algorithm, since their member functions by default to a 
> sequencially consistent memory model.

Thank you for the illumination!  I now feel ready to try reading Anthony Williams' book again.  The memory model stuff in there gave me the willies at first glance; hopefully it has improved or I have.

>> 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.

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.

> 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.

Cheers,
Gordon