From: s_sourceforge@nedprod.com To: boost-users@lists.boost.org Date: Tue, 11 Feb 2014 20:08:59 +0000 Subject: Re: [Boost-users] Boost or Standard when there is the choice?

A standard library implementation is /probably/ more stable, better tested and more micro-optimised than Boost *eventually*. I stress the eventually - right now, C++ 11 standard libraries are still getting the bugs wringed out of them. but they are settling down and in the past year certainly I've found bugs more frequently in Boost implementations of C++11 features than in say Dinkumware's STL.

Regarding the micro optimisation remark, I make this purely based on my experience with Visual Studio where the Dinkumware implementation almost always outperforms or is similar to a Boost implementation, especially in VS2013. This is partially because a Boost implementation usually has a lot more features and therefore a larger code footprint, but it's also because Dinkumware do a lot of micro optimisation once code is known stable.

Since I'm pedantic, I think there's a phenomenon here that you're seeing but not ascribing properly. Dinkumware's initial implementation tends to not have much concern for performance at all and Boost's solution tends to be more mature by the time it's standardized and gets implemented by Dinkumware, which usually results in Boost being faster. The reason that Microsoft's STL ends up performing better than both Dinkumware's and Boost's implementations is because Microsoft cares about performance and implements most of the optimizations and because, like you said, Boost has more surface area. Microsoft currently cares and they know their compiler/platform better. Note: the STL that Dinkumware ships is not the same as the one Microsoft ships, so perhaps I'm just being pedantic about naming. As an example, Dinkumware's STL didn't have the make_shared optimization that Boost implemented until Microsoft rewrote make_shared to include it. That's a case where Boost did better until the standard provider improved their implementation. Granted, I don't think shared_ptr is complex enough that there is any difference between optimal implementations. PS. This ignores optional parts of the standard like advanced math functions which Boost provides but most standard library vendors will not, or if they do, it will only be to get the 'complete implementation' rubber stamp.

Lastly, using STL implementations is probably more future proof over say the next twenty years than using Boost. I can certainly see that once C++11 is ubiquitous, the incentive to maintain Boost C++11 implementations of standard features will drop substantially. Future users of your code base will then have to port over code away from Boost to gain timely access to fixes.

All that said, I still choose Boost.Thread primitives over STL primitives, mainly due to the much superior feature set and I know many of those superior features will end up in C++1y, so why wait till then? Note that I use the namespace mapping technique to map /some/ implementation into a private namespace, that makes switching to a STL implementation later fairly trivial.

[Niall]

When running a diff between VS2013's STL and the vanilla one we had at BlackBerry I saw a large drop in size of the patchset as compared to VS2012. I didn't investigate, so in fairness the cause could be anything.

Probably the elimination of faux variadics. [Ahmed]

As an example, Dinkumware's STL didn't have the make_shared optimization that Boost implemented until Microsoft rewrote make_shared to include it.

This is incorrect (or at least phrased in an ambiguous way; I am objecting to the timing implications). I explained the story at GoingNative 2012, so I can explain it again here. First, Boost invented shared_ptr and make_shared. Then Dinkumware implemented shared_ptr and make_shared, which Microsoft picked up (shared_ptr in 2008 SP1, make_shared in 2010). When I saw Dinkumware's implementation of make_shared, which achieved Boost/C++0x's recommended single allocation with a special deleter, I rewrote it (in faux variadics) to use a dedicated control block. While doing so, I paid attention to the layout and developed what I referred to as the "We Know Where You Live" optimization, squeezing out an unnecessary pointer. VC 2010 shipped with 5 control blocks (traditional, deleter, deleter/allocator, make_shared, allocate_shared), which were optimal (except that they did not attempt to compress the storage of provided but empty deleters/allocators; on my todo list). This optimization has been maintained in 2012 and 2013 (now true variadic). At GN 2012, I observationally determined that both Boost and libstdc++ had not implemented We Know Where You Live, with significant impacts on total memory consumption, so I explained the optimization without code, as a gift to Boost (who gave the world shared_ptr/make_shared). I don't think anyone figured this out before I did, or if they did, they didn't ship it, which is what matters. Since then, it has been explained to me that Boost paid the cost of an extra pointer as make_shared was implemented "non-intrusively", while libstdc++ accidentally paid an extra pointer (not noticing the control block redundancy). I don't know when Boost implemented the optimization, and whether libstdc++ has yet, but they are both aware, and I hope libc++ is too (I should ask Marshall/Howard). (Note: make_shared didn't ship in 2008 SP1 as it needed rvalue references, and at no time - even prerelease - did VC have a make_shared that performed two allocations.) [Ahmed]

That's a case where Boost did better until the standard provider improved their implementation.

It's the reverse. See http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/STL11-Magic-Sec... slide 7, comparing VC10 SP1, Boost 1.48.0, and GCC 4.6.1. Boost is difficult to beat in correctness and performance for the reason that you mentioned (Boost gets a head start, when their features are standardized), so please, give us credit for this one thing! :-> (And for contributing the optimization back. I didn't have to tell anyone about that.) [Niall]

(i) how close is vanilla Dinkumware to the STL shipped in VS2013

I am unable to answer this question, as I have never seen Dinkumware's vanilla library. I can tell you that we work closely with Dinkumware, and that (in 2010 and above) what may appear to be Microsoft-specific edits, have actually been sent upstream to Dinkumware's master sources, which are capable of generating drops for Microsoft or other clients (whose existence, but not identity, I am aware of). Between 2005 and 2010 the sources were divergent, which caused difficulty in picking up new features (starting with TR1). Now we can rapidly acquire new features.

(ii) would you, Stephan, say that the VS2013 STL is likely to be on average better performance than a Boost implementation of some given C++ 11 feature,

It varies. Some regexes we do better, some we do worse (e.g. many alternations). make_shared, we did better, because (oddly enough) I had the luxury of (re)writing it from scratch, without any attempt to be "non-intrusive". Our shared_ptr on ARM is likely to be better than Boost, since we go to the trouble of using weaker-than-SC atomics. Our <atomic> is probably better on 2013 since we've figured out how to use intrinsics for almost everything (and even better in the next major version), although maybe not if you've looked at our intrinsics carefully too. Our threading stuff, we've tried to be fast by powering our futures with ConcRT, but I also know where a few bodies are buried (e.g. call_once). Correctness-wise is another story (e.g. I need to rewrite <functional>, Boost.Bind is more solid), although I will say that for the type traits, VC is likely to give more correct answers because I can request compiler hooks as I need them (and more importantly, compiler fixes). Hope this helps, STL

[Niall]

I will mention with regard to the above that the non-intrusiveness of Boost implementations is - as you acknowledged - done deliberately. This can make maintenance in the face of refactors easier to grok,

As a library maintainer, I can say that I appreciate maintainability, but performance for users is more important. I am willing to add a fair amount of complexity in the pursuit of performance (e.g. I recently added a bunch of code to is_permutation() to optimize various things). In the specific case of make_shared, the dedicated control block was about the same amount of code as the special deleter, and it ended up being more robust (in particular, wrt enable_shared_from_this). That said, in Issaquah I learned (via Peter Dimov's proposal) that the shared_ptr casts can now be implemented non-intrusively via the aliasing constructors, which is obvious in hindsight, so I'll probably do that soon. STL

----------------------------------------

From: s_sourceforge@nedprod.com To: boost-users@lists.boost.org Date: Wed, 12 Feb 2014 19:50:47 +0000 CC: stl@microsoft.com Subject: Re: [Boost-users] Boost or Standard when there is the choice?

...

The reason that Microsoft's STL ends up performing better than both Dinkumware's and Boost's implementations is because Microsoft cares about performance and implements most of the optimizations and because, like you said, Boost has more surface area. Microsoft currently cares and they know their compiler/platform better.

I agree that Microsoft do a ton of customisation of the Dinkumware STL, or rather, they /used/ to do a ton of customisation up till VS2013. From my reading of the Dinkumware STL headers, most of the customisation was MSVC specific workarounds rather than optimisations per se. When running a diff between VS2013's STL and the vanilla one we had at BlackBerry I saw a large drop in size of the patchset as compared to VS2012. I didn't investigate, so in fairness the cause could be anything.

My point here, though apparently I didn't get it across well at all, was to give credit to Microsoft and STL for caring about performance and pushing to make it better. My example of make_shared was wrong, but I think the pattern still holds that Boost starts with a 'better' implementation and the standard implementers catch up and sometimes 'beat' Boost in some respect.

...

Note: the STL that Dinkumware ships is not the same as the one Microsoft ships, so perhaps I'm just being pedantic about naming.

It's pretty close. The BB10 NDK also uses the Dinkumware STL, and it was not unheard of for us to compare the two when a bug turned up to see our STL had been fixed without us realising.

Correct, they are likely to be very close because Microsoft gives fixes back, which for portable fixes, means everyone benefits.

On 15 February 2014 21:11, gast128 wrote:

...

my experience with Visual Studio where the Dinkumware implementation almost always outperforms or is similar to a Boost implementation

I had one big bad experience with std::unordered_map in the past, see topic 'Performance difference between std::unordered_map and boost::unordered_map' (https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/pFBjDiW6mW0).

According to Joaquin's recent benchmarks the recent standard implementations are generally faster than the boost implementation, which IMO is how it should be. I'm looking forward to Boost.Unordered's obsolescence. http://bannalia.blogspot.co.uk/

Niall Douglas writes:

On 16 Feb 2014 at 13:04, Daniel James wrote:

...

According to Joaquin's recent benchmarks the recent standard implementations are generally faster than the boost implementation, which IMO is how it should be. I'm looking forward to Boost.Unordered's obsolescence.

http://bannalia.blogspot.co.uk/

[...]

Also, performance isn't everything, memory footprint is also very important. It's unfortunate that blog didn't show differences in unordered_map<> memory consumption. I'd warrant that Dinkumware's unordered_map<> is very, very good on memory footprint. For the other STLs, I wouldn't like to guess.

No practical measure was taken, but one can guess from the layout of the different data structures as described in http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered_25.html The overhead (memory minus sizeof(value_type)) in words for a container of N elments and B buckets is: * Dinkum: 2B + 2N * libstdc++: 1B + 2N (1B + 1N is hash is fast and does not throw) * libc++: 1B + 2N * Boost.Unordered - unique elements: 1B + 2N - duplicate elements: 1B + 3N * Boost.MultiIndex: 1B + 2N So, in fact Dinkumware and Boost.Unordered-duplicate are the ones that use the most memory. Joaquín M López Muñoz Telefónica Digital

Daniel James writes:

On 15 February 2014 21:11, gast128 wrote:

...

...

my experience with Visual Studio where the Dinkumware implementation almost always outperforms or is similar to a Boost implementation

I had one big bad experience with std::unordered_map in the past[...]

According to Joaquin's recent benchmarks the recent standard implementations are generally faster than the boost implementation, which IMO is how it should be.

I think this nos the story the benchmarks tell. 15 different scenarios were tested: * Insertion without rehashing, unique elements * Insertion with rehashing, unique elements * Insertion without rehashing, duplicate elements * Insertion without rehashing, duplicate elements, high load factor * Insertion with rehashing, duplicate elements * Insertion with rehashing, duplicate elements, high load factor * Erasure, unique elements * Erasure, dupicate elements * Erasure, dupicate elements, high load factor * Successful lookup, unique elements * Unsuccessful lookup, unique elements * Successful lookup, duplicate elements * Unsuccessful lookup, duplicate elements * Successful lookup, duplicate elements, high load factor * Unsuccessful lookup, duplicate elements, high load factor and results do not show any definite winner (< means "better than"): * VS 2012 http://bannalia.blogspot.com/2014/01/a-better-hash-table.html - insert_norehash_unique: BMI < Dinkum < BU - insert_rehash_unique: BMI < Dinkum < BU - insert_norehash_duplicate: Dinkum < BMI < BU - insert_norehash_duplicate_highlf: Dinkum < BMI < BU - insert_rehash_duplicate: Dinkum < BMI ~ BU - insert_rehash_duplicate_highlf: Dinkum ~ BMI ~ BU - erase_unique: BMI < Dinkum < BU - erase_duplicate: Dinkum < BMI < BU - erase_duplicate_highlf: Dinkum < BMI < BU - ok_lookup_unique: BMI < Dinkum < BU - nok_lookup_unique: Dinkum < BMI < BU - ok_lookup_duplicate: BMI < Dinkum < BU - nok_lookup_duplicate: BMI < BU < Dinkum - ok_lookup_duplicate_highlf: BMI < BU < Dinkum - nok_lookup_duplicate_highlf: BU ~ BMI < Dinkum * GCC 4.8.2 http://bannalia.blogspot.com/2014/01/a-better-hash-table-gcc.html - insert_norehash_unique: BMI < BU < libstdc++ - insert_rehash_unique: BMI < BU < libstdc++ - insert_norehash_duplicate: libstdc++ < BMI < BU - insert_norehash_duplicate_highlf: libstdc++ < BMI < BU - insert_rehash_duplicate: libstdc++ < BMI < BU - insert_rehash_duplicate_highlf: libstdc++ < BMI < BU - erase_unique: libstdc++ < BMI < BU - erase_duplicate: libstdc++ < BMI < BU - erase_duplicate_highlf: libstdc++ < BMI < BU - ok_lookup_unique: BMI < BU < libstdc++ - nok_lookup_unique: BMI < BU http://bannalia.blogspot.com/2014/01/a-better-hash-table-clang.html - insert_norehash_unique: BMI < BU < libstdc++ - insert_rehash_unique: libstdc++ ~ BU ~ BMI - insert_norehash_duplicate: libstdc++ < BMI < BU - insert_norehash_duplicate_highlf: libstdc++ < BMI < BU - insert_rehash_duplicate: libstdc++ < BMI < BU - insert_rehash_duplicate_highlf: libstdc++ < BMI < BU - erase_unique: libstdc++ < BMI < BU - erase_duplicate: libstdc++ < BMI < BU - erase_duplicate_highlf: libstdc++ < BMI < BU - ok_lookup_unique: BMI < BU < libstdc++ - nok_lookup_unique: BMI < BU < libstdc++ - ok_lookup_duplicate: BMI < BU < libstdc++ - nok_lookup_duplicate: BMI < BU < libstdc++ - ok_lookup_duplicate_highlf: BMI < BU < libstdc++ - nok_lookup_duplicate_highlf: BMI < BU < libstdc++ * Clang 3.4 with libc++ http://bannalia.blogspot.com/2014/01/a-better-hash-table-clang.html - insert_norehash_unique: BMI < BU < libc++ - insert_rehash_unique: BMI < BU < libc++ - insert_norehash_duplicate: BMI < BU < libc++ - insert_norehash_duplicate_highlf: BMI < BU < libc++ - insert_rehash_duplicate: BMI < BU < libc++ - insert_rehash_duplicate_highlf: BMI < BU < libc++ - erase_unique: BMI < libc++ < BU - erase_duplicate: BMI < BU < libc++ - erase_duplicate_highlf: BMI < BU < libc++ - ok_lookup_unique: BMI < BU < libc++ - nok_lookup_unique: BMI < BU < libc++ - ok_lookup_duplicate: BMI < BU < libc++ - nok_lookup_duplicate: BMI ~ BU < libc++ - ok_lookup_duplicate_highlf: BMI < BU < libc++ - nok_lookup_duplicate_highlf: BMI ~ BU < libc++ In particular, Boost containers (Unordered and MultiIndex) fare better on lookup. Also, they are the only ones using a special data structure to skip duplicate elements in constant time, which shows in much faster lookups for high load factors. Dinkum is generally faster at erasure, but does so at the expense of potentially throwing where no throwing is permitted (Stephan already knows about this). Some fixed conditions for the tests, like the fact that easy-to-hash uints are used, do certainly bias some results in favor of containers *not* storing hash values (Dinkum, BMI, libstdc++ in some cases). But, summarizing, I wouldn't say standard library implementations can be unconditionally be deemed superior. Joaquín M López Muñoz Telefónica Digital

Daniel James writes:

On 16 February 2014 17:25, Joaquin M Lopez Munoz wrote:

...

I think this not the story the benchmarks tell. 15 different scenarios were tested:

[...]

and results do not show any definite winner (< means "better than"):

[...] I think yours are the first benchmarks I've seen to deal with elements with equivalent keys. But what I'm not sure about, is how closely benchmarks reflect actual use.

Neither am I :-/

A minor dilemma that I've got at the moment is that on 64-bit machines the newer versions use a different bucket placement strategy to avoid the costly prime modulus. It's typically faster, but for certain cases (such as inserting consecutive integers) the old version is much faster as there are no collisions at all. The problem is I have no idea how often this happens in real world cases.

My gut feeling is that inserting more or less consecutive ranges of integers is a fairly common scenario. In order to speed modulo calculations, I do this trick: instead of having size_t hash_to_bucket(size_t h) { return h%bucket_size; } I write the following: size_t hash_to_bucket(size_t h) { switch(bucket_size_index){ case 0: return h%53; case 1: return h%97; case 2: return h%193; case 2: return h%389; ... case 59: return h%18446744073709551557ul; } } Each h%constant operation the compiler is able to heavily optimize by emulating integer division with precalculated multiplications (there's a section in Hacker's Delight on this I guess). I took a look at the generated assembly code and integer divisions were in fact gone, and the thing is considerably faster despite the huge number of cases (switching on [0,...n) can be coded very efficiently and I think CPU branch prediction plays a role here also). See http://tinyurl.com/okou28x for the actual implementation. You might want to try someting similar in Boost.Unordered. Joaquín Mª López Muñoz Telefónica Digital

On 16 February 2014 19:34, Joaquin M Lopez Munoz wrote:

See http://tinyurl.com/okou28x for the actual implementation. You might want to try someting similar in Boost.Unordered.

I saw this in your code a little while ago and tried it, and it is faster than the old implementation, but it's still slower than the newer version, because of the way I find the bucket for a node. I cache the mixed hash function in a node, rather than the original hash function, so that the bucket for a node can be found with a single 'and' operation. This can be done several times when searching for a node, so even an optimised modulus is notably slower. Of course this doesn't apply to MultiIndex as you use a different data structure.