Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-07-27 10:50:31

hi artyom,

thanks for your review!

> ------------------------------------------------------
> - What is your evaluation of the design?
> 
> Basically it looks quite simple and straight forward. As the
> data structures are based (according to the author) on the 
> current papers and studies; it uses quite standard features
> and seems fine.

a side note: lock-free data structures are a patent minefield. these data 
structures are the most simple ones and the ones which are (ianal) not patented.

> ------------------------------------------------------
> - What is your evaluation of the documentation?
> 
> I think it is too brief and misses important parts.
> 
> For example: html/boost/lockfree/ringbuffer.html
> 
> 
> Should include in the reference general requirements
> like it should be single writer single reader and not
> mentioned in some other places.
> 
> In the first glance I assumed that it was multiple-readers-writers
> ring buffer.

yes. this has already been discussed earlier and i have significantly changed 
the docs to ensure this!

> ------------------------------------------------------
> - What is your evaluation of the potential usefulness of the library?
> 
> 
> 
> ok...
> 
> This is probably the biggest problem with this library.
[snip]
> 
> I'd like to see more:
> 
> 
> 1. Queues with OS support like waiting - non-waiting with
>    lock-free access when the queue not-empty and not-full

i have avoided this intentionally because i consider this as out of the scope of 
the library: afaict, in order to wait for empty/full queues, one needs to use 
either condition variables or semaphores. condition variables will block, if the 
condition is modified. semaphores are very os-dependent, and i have no idea, if 
any semaphore operations are actually lockfree. so from my understanding it is 
not possible without violating the lock-free property

> 2. Queues with different optimization for different cases.

i'd be curious: what are you thinking about?

> 3. There are several ways to optimize stacks to reduce
>    contention.

what are you referring to? backoff and elimination?

> 4. Some transactional memory blocks that allow to implement
>    optimistic strategies

again, do you have any suggestions, ideas, or papers that you suggest i should 
look at?

> 5. Combination of locking and lock-free parts.

this again is out of the scope of the library for me.

> 6. Hash tables

this has already been suggested before. maybe in a future version of the 
library...

> So I vote "Yes" but I strongly recommend and expect from the author:
> 
> - Make some building blocks available in detains to library interface
>   allowing users to implement other data-structures easier.

the important building blocks will probably be the tagged_ptr and the freelist. 
however i'd prefer to keep it an implementation detail, because once they are 
exposed, their semantics cannot be changed.

> - Improve documentation about what and how it should be done

i am already working on this ;)

> - Provide more data structures in future and provide data structures
>   with different policies

which policies do you suggest?

cheers, tim