Boost logo

Boost :

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

> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at