Re: [boost] Review Request: boost.lockfree

Subject: Re: [boost] Review Request: boost.lockfree
From: Tim Blechmann (tim_at_[hidden])
Date: 2009-11-25 05:02:00

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

>> since my first review request for boost.lockfree [1] was completely
> ignored
> 
> I have stated that multiple times, I think a mailing list is the wrong  
> format for boost. important posts are missed in the noise.

well, there are bigger projects, like the linux kernel, which are using
mailinglists quite successfully ... imo, nothing is wrong with
mailinglists, but the boost lists are not read well enough by the boost
devs :/

> could you post a link that lists known lock-free data structures so  
> people not already familiar with lock-free data structures can see how  
> your library matches that?

something like these?
http://en.wikipedia.org/wiki/Non-blocking_synchronization
http://www.audiomulch.com/~rossb/code/lockfree

>> boost.lockfree provides:
>> * boost::lockfree::fifo, a lock-free fifo queue
>> * boost::lockfree::stack, a lock-free stack
> 
> I only had a look at the documentation sor far. there are a few things  
> I found surprising:
> 
>   - noncopyable: is the only reason for this that containers can't be  
> copied atomically?

yes ... in theory it would be possible to copy a stack or fifo (possibly
the freelist code would need some changes), but i decided to make them
copyable, to avoid that people are using and copying the stack/fifo at
the same time ... during a copy constructor, not enqueue/dequeue would
be allowed

>   - fifo: the STL fifo is called std::queue and has a very different  
> interface than your fifo class. I guess you have to change some  
> things, e.g. std::queue::pop() has a void result, but it could  
> resemble the STL interface, can't it?

i am open for naming suggestions ... push/pop or enqueue/dequeue, fifo
or queue, all of this is open for discussion.
the interface itself should probably stay as it is, since the stl
interface doesn't really match the interface of lockfree data structures

>   - that free_list thing...looks very much like an allocator.
> I understand that you want to make sure that push/pop doesn't call the  
> default allocator (-> mutex lock), but couldn't you make lock-free  
> containers accept stateful allocators and provide a default allocator  
> that keeps free-d objects in a free_list?
> am I missing a reason why you need a seperate allocation interface? I  
> haven't found the concept the free_list_t template parameter in the  
> documentation, can it do anythiong beyond what the interface of a  
> std::allocator provides?

these stack/fifo implementations use a freelist to avoid returning the
internal memory to the os. this is required since boost.lockfree doesn't
use any safe memory reclamation algorithm such as hazard pointers or
pass-the-buck. so freelists are not really a replacement for allocators,
but rather a wrapper ...
there are two freelist implementations provided, static_freelist and
caching_freelist (names are open for discussion). static_freelist
allocates a number of nodes from the allocator and `enqueue' only hits
the freelist, but not the allocator (to avoid blocking in the allocator
code), while caching_freelist may allocate from the allocator, if no
node is available from the freelist. the static_freelist is especially
useful for real-time systems.
using a stateful allocator doesn't improve the situation, since two
threads may concurrently call enqueue and thus some synchronization
mechanism for the allocator would be required.

cheers, tim

- -- 
tim_at_[hidden]
http://tim.klingt.org

/"\  ASCII Ribbon Campaign
\ /   no HTML in email & vCards
 X     no proprietary attachments
/ \     use open standards
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAksNAJMACgkQdL+4qsZfVstQkACfQnHC+qRLuv9Ip0/2YRr9UWB8
YzgAn0oIl+B4nI5jVJ42aZA8oIkObtnj
=nIPJ
-----END PGP SIGNATURE-----