[boost] [lockfree] Review

Subject: [boost] [lockfree] Review
From: Grund, Holger (Holger.Grund_at_[hidden])
Date: 2011-07-30 12:27:27

Hi everyone,

I'm sorry for the late review -- things have been busy as usual.

I've briefly gone over the code and think Tim's Lockfree library would make an excellent addition to Boost and should be accepted, provided some points are addressed. First and foremost, I don't think the library can be called ready when it doesn't support Visual C++/x86 in a meaningful way -- which I believe it doesn't right now.

What is your evaluation of the design?
--------------------------------------

The library seems well-designed. As I believe has been discussed in a separate thread, naming is somewhat inconsistent. 
The failure modes are not clear to me (e.g. does enqueue/push return false or throw an exception when there is no more memory), but overall I think Tim did an excellent job.

What is your evaluation of the implementation?
----------------------------------------------

As mentioned, it would appear that bundled atomic implementation has a lot of shortcomings, but one is particularly bad: atomic<tagged_ptr> is not actually lock-free for Visual C++. The DCAS implementation should be straightforward, but seems to be absent . in case you wonder I did an initial implementation of <(cstd)atomic> and added all required intrinsics for a simple implementation to the compiler. These made it all into VC++2010 RTM (IIRC, there was only one 64-bit, most where 8 & 16-bit variants)

There are a few points that make me a bit nervous. Specifically, the alignment story is a bit weak. It seems there is only one use of BOOST_LOCKFREE_CACHELINE_ALIGNMENT and that's for fifo<>::node. Older compilers (GCCs and VC at least) don't dynamically align the stack with __declspec(align)/__attribute__((aligned).
Other classes do not use alignment at all. It seems somewhat inconsequent to add internal padding to move members to different cachelines, but at the same time not ensuring alignment (which means potential cacheline overlaps at back and front of the object). Also the code seems to assume that compilers will use an empty base class optimization for noncopyable -- I guess, that's fine for most major compilers.

Also it is not clear how it is ensured that nodes allocated are actually aligned. Allocators can and usually do ignore alignment requirements greater than intmax_t types. Some may just fail to instantiate.

likely/unlikely are often defined as macros as in the Linux kernel. People probably shouldn't do that for C++, but I have seen it quite a bit. It probably doesn't help that many compilers' inlining oracles don't do very well for modern code.

The name freelist_t is somewhat confusing for a template parameter and while I'm not sure what harm it could do it should probably follow the general convention of CamelCase. 

What is your evaluation of the documentation?
---------------------------------------------

This is a bit of a weak point right now. There isn't much documentation to begin with. 

The definition of wait-free and lock-free is a bit weird. Specifically, the term concurrent operations is a bit vague. I think it's easier to grasp if you say something along the lines of at least one thread makes forward progress at any given point in time. With the current definition in the docs (and most others I know of), it may not be immediately clear why a mutex-based implementation wouldn't be lock-free.

There's a paragraph:
> The synchronization is done completely in user-space with no interaction without any direct interaction with the operating system [1] . 
> This implies that they are not prone to issues like priority inversion (a low-priority thread needs to wait for a high-priority thread). 

I think there's some duplication in the first sentence. I'm not sure what lock-free has to do with priority inversion and I would think that priority inversion means priorities are -- well, inverted. I.e. a high-priority thread is not scheduled, because a lower priority thread owns a resource needed by the high-priority thread.

This also makes it sound a bit like lock-free is superior to OS mechanisms, but that really depends. A standard lock-free list is not fair for writers, but an implementation making use of OS facilities can be. On the other hand ticket lockets can provide some fairness.

fifo<> and ringbuffer::empty says it is not thread-safe. I would assume that means the value returned is potentially stale, but it can't break class invariants, or can it?

What is your evaluation of the potential usefulness of the library?
-------------------------------------------------------------------

I think the library addresses a very important use-case and could therefore be a very useful addition to Boost. But to reiterate, I would expect Lockfree to actually be lock-free on all mainstream platforms.

Did you try to use the library? With what compiler? Did you have any problems?
------------------------------------------------------------------------------

I don't have Boost libs built here, so only tried some simple tests with VC++ 10 SP1. No problems. I'm planning to run some perf tests with GCC 4.1 on AS5 x86_64.

How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
--------------------------------------------------------------------------------------------

I spent about four hours mostly going over the code and the docs.

Are you knowledgeable about the problem domain?
-----------------------------------------------

I have done quite a lot of lock-free work over the last the last 8 years. I did an initial implementation of <atomic> for Microsoft and my current job involves a lot of tweaking of very low latency code, where we very much care about upper limits for execution time (but also about throughput). While I'm still constantly surprised by modern CPUs, I do consider myself to be quite knowledgeable about this area.

-hg

Holger Grund, Vice President   
Morgan Stanley | MS Strats and Modeling   
25 Cabot Square | Canary Wharf | Floor 03   
London, E14 4QA   
Phone: [phone]   
Holger.Grund_at_[hidden]   

--------------------------------------------------------------------------
NOTICE: Morgan Stanley is not acting as a municipal advisor and the opinions or views contained herein are not intended to be, and do not constitute, advice within the meaning of Section 975 of the Dodd-Frank Wall Street Reform and Consumer Protection Act. If you have received this communication in error, please destroy all electronic and paper copies and notify the sender immediately. Mistransmission is not intended to waive confidentiality or privilege. Morgan Stanley reserves the right, to the extent permitted under applicable law, to monitor electronic communications. This message is subject to terms available at the following link: http://www.morganstanley.com/disclaimers. If you cannot access these links, please notify us by reply message and we will send the contents to you. By messaging with Morgan Stanley you consent to the foregoing.