- Boost - lists.boost.org

[lockfree] Review
by Grund, Holger 09 Aug '11

09 Aug '11

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: +44 20 7677-4095 Holger.Grund(a)morganstanley.com -------------------------------------------------------------------------- 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.

5 16

Re: [boost] [math][accumulators] Empirical distribution function
by Denis Arnaud 09 Aug '11

09 Aug '11

On 8/8/11, er wrote: > Thanks, but it was just, I quote, a "basis for a conversation" at the > request of a user (Denis Arnaud), but it failed to go anywhere at the time. Note that I am still interested in using such a component/library. The difficulty I had was the integration with the rest of Boost and, therefore, the build of that component. Indeed, I use CMake (from the Ryppl initiative) rather than bjam, for the Boost sandbox components, and the integration is therefore a little bit different. AFAIU, Daniel Pfeifer is now close to have a CMake-ified Boost able to integrate Boost sandbox libraries. One of the first such use case would be to integrate and to test your Empirical CDF component. Nevertheless, thanks for having proposed a solution, even though I understand it is still not perfect. Best Denis

1 0

[tti] Write access to Boost
by Edward Diener 09 Aug '11

09 Aug '11

For my TTI library I need write access to the Boost repository si I can check the library into the trunk and maintain it there. Eddie Diener

2 2

[function][bind] Crash with g++ 4.5.0 -O[23]
by Daniel Larimer 08 Aug '11

08 Aug '11

I recently wrote some code that only crashes with g++ 4.5.0 -O[23] and am not sure whether it is a g++, boost::bind, or boost::function bug. I have prepared a minimum test case that crashes every time: 0 test 0x00000001000016ba Private::method_name(std::string const&) + 26 1 test 0x0000000100001348 boost::detail::function::function_obj_invoker1<boost::_bi::bind_t<void_t, boost::_mfi::mf1<void_t, Private, std::string const&>, boost::_bi::list2<boost::_bi::value<Private*>, boost::arg<1> > >, void_t, std::string const&>::invoke(boost::detail::function::function_buffer&, std::string const&) + 24 2 test 0x00000001000027bb boost::detail::function::void_function_obj_invoker2<functor<std::string, boost::function<void_t ()(std::string const&)> >, void, std::string const&, std::string&>::invoke(boost::detail::function::function_buffer&, std::string const&, std::string&) + 59 3 test 0x0000000100003893 Private::test() + 2723 4 test 0x00000001000012d8 main + 56 5 test 0x0000000100001250 start + 52 Mac OS X 10.6 Snow Leopard g++-4.5.0 -O3 or -02 crashes g++-4.5.0 -O1 works. g++-4.2 -O3 works. g++-4.0 -O3 works llvm-g++-4.2 -O3 works The odd thing is that if I replace boost::bind() with my own custom functor then it does not crash. If I include both working and non-working functors (uncomment code) then they both work. Because older versions of g++ work (pre C++0x support) it could be a bug in how boost::function or boost::bind use rvalue references. Because replacing boost::bind() with my own custom functor also fixes it, I suspect that the problem, if not g++, lies in boost::bind. If I remove boost::function from the equation by creating functor<Seq,Functor> with Functor = TYPEOF( boost::bind( ... ) ) via the use of a helper method, then it also does not crash. Thus some combination of creating a boost::function<...> from a boost::bind() functor on g++4.5 causes the crash.

2 2

[Containers] Should flat_* expose implementation vector?
by Phil Endecott 08 Aug '11

08 Aug '11

Dear All, Should Ion's proposed flat_set, flat_map etc. expose the underlying vector that they use as their implementation? Pros: it lets the user efficiently load and save the content, and implement algorithms that cannot be done via the flat_* interface. Cons: it lets the user break the invariants. Const access to the impl is another possibility. Related to that: could the implementation type be a template parameter? Example: could one implement a flat_set on top of a stable_vector? (Is that useful?) And/or: should flat_* actually be adaptors that take a reference to their underlying implementation? Regards, Phil.

8 10

[gsoc] mentor summit
by Andrew Sutton 08 Aug '11

08 Aug '11

Mentors, If you are interested in attending the mentor summit (Mountain View, CA Oct 22-24 -- check the calendar that might be wrong), please let me know. We send 2 people to represent Boost. I will not be one of them since I have a prior engagement. The reimbursement scheme looks like it's going to change this year. Essentially, Boost (actually the SFC) will submit a single purchase order for mentored projects + the cost of mentor summit air travel. That means that actual reimbursement for your flight costs may not happen until... I don't know. June 2012? The process is ridiculously slow, and I never got word that Boost received mentor payments from last summer. Andrew

1 0

[Date Time] bug in documentation example (Localization Demonstration)
by Frédéric Bron 08 Aug '11

08 Aug '11

In "Localization Demonstration": http://www.boost.org/doc/libs/1_47_0/doc/html/date_time/examples.html#date_… 11 should be 12 and 6 should be 7 in the following lines: std::copy(&de_short_month_names[0], &de_short_month_names[11], std::back_inserter(short_months)); std::copy(&de_long_month_names[0], &de_long_month_names[11], std::back_inserter(long_months)); std::copy(&de_short_weekday_names[0], &de_short_weekday_names[6], std::back_inserter(short_weekdays)); std::copy(&de_long_weekday_names[0], &de_long_weekday_names[6], std::back_inserter(long_weekdays)); Regards, Frédéric

1 0

Boost.Atomic, pushing forward and a little request for help
by Helge Bahmann 07 Aug '11

07 Aug '11

Hi folks, from the comments to Boost.Lockfree I understand that you consider a non-reviewed Boost.Atomic as a "blocker"? I apologize that I have not pushed forward for review (considering that "it just works for me", and considering the length of the review queue...), but if you consider it blocking please just let me know what I would need to do to clear the path. What I will do shortly is to provide and uptodate package containing several fixes, several contributed by others (they are in the repo, but not in any release archive) as well as some missing bits to more closely match latest C++0X draft. The big sore point is still support for the various flavours of VC -- I know that there are (especially older) versions for which it is not working, but I am lacking test systems, so if you are affected please let me know and I will do my best to resolve the issues. Cheers, Helge

10 14

[interprocess::file_mapping] Please add resize method
by Dmytro Ovdiienko 07 Aug '11

07 Aug '11

Hello, Could you please add resize method to the file_mapping class? Also please don't fill file with zeros by default? This functionality increases latency spikes. Make it as quick as possible. Thanks. Best regards. Dima -- Dmytro Ovdiienko e-mail: dmitriy.ovdienko(a)gmail.com skype: dmitriy.ovdienko(a)gmail.com mobile: +38050-1909731

2 5

[containers] review
by Gordon Woodhull 07 Aug '11

07 Aug '11

Hi Ion, John, all, I apologize that I don't have time for a full review, as I'm going offline hiking for the rest of the review period. Obviously the library should be accepted. Move emulation, stateful allocators, emplace, recursive containers, ... so many excellent features. And this code has been tested as part of Interprocess for years. However, I do find the documentation lacking. While the Doxygen reference looks very complete, I want to see the overview documentation expanded, including covering the following topics: Stateful allocators seem to be unmentioned. Do they affect performance or behavior? I know this might be a big topic; links are okay. My understanding is that these are fully supported but other allocator improvements are not yet present? Out of curiosity I'd like to see a bit of text about the future directions, mentioning N1953 & N2045. Could the contents of Joachin's blog post http://bannalia.blogspot.com/2008/08/stable-vectors.html go into an overview section for stable_vector? Recursive container is not defined, also maybe link to http://en.wikipedia.org/wiki/Recursive_data_type What is it used for: directed graph. Some guideline about when it's better to use flat_*. I figure you would use such a structure when you're not doing a lot of inserts or when there are few elements. The advice can be somewhat handwavy and instruct the user to do measurements, but it should be there. Silly question, but I'm not clear how to use this ordered_unique_range_t that's in the Doxygen - is there a constant or do you default construct it or what? As earlier pointed out, a lot of the Doxygen parameters and descriptions have gotten out of sync k/x first/i etc. Well, I've run out of time. Hope this helps a little. Cheers, Gordon

3 3