Mathias Gaunard wrote:

The code above calls the std::_Equal symbol, not memcmp. The code given for std::_Equal also does not contain a jump to any other function.

memcmp is inlined into _Equal. Replacing std::equal with memcmp yields the same assembly code, this time inlined directly at the point where == is invoked.

Don't forget alignment. Those DWORD comparisons/copies may only work well for aligned memory but when you call memcmp, you erase alignment information and the compiler may assume it's only char-aligned. I did not forget it. My words about alignment was just skipped. No doubt you can align uuid::data[16] almost any suitable way even for uint64_t. You can even start the comparison from the back if you feel that your uuids start to differ from the back to speed up the approach even more.

I would also like to confirm and further elaborate the statement in the discussion (I will not quote it from another message) that memcmp is intrinsic in MSCV for many cases (I have enforced it with Oi compiler switch), it is alignment, underlying data type and array sizes aware. You may want to have a look at the following example: #include <cstdint> #include <cstring> int main() { uint8_t d1[16], d2[16]; return memcmp(d1,d2,16); } Here is the result. $LL4@main: mov esi, DWORD PTR [edx] cmp esi, DWORD PTR [ecx] jne SHORT $LN5@main sub eax, 4 add ecx, 4 add edx, 4 cmp eax, 4 jae SHORT $LL4@main xor eax, eax Pretty neat. I wish the boost and C++ standard library to develop the same way. -- Michael Kochetkov

even though uuid::data is uint8_t[16]. I see an assembly listing that is virtually identical to the one you posted for _Equal, which is also just a memcmp call: You may probably want to make sure the Oi switch is present.

inline bool __CLRCALL_OR_CDECL _Equal(const unsigned char *_First1, const unsigned char *_Last1, const unsigned char *_First2, random_access_iterator_tag, _Range_checked_iterator_tag) { // compare [_First1, _Last1) to [First2, ...), for unsigned chars #if _HAS_ITERATOR_DEBUGGING _DEBUG_RANGE(_First1, _Last1); if (_First1 != _Last1) _DEBUG_POINTER(_First2); #endif /* _HAS_ITERATOR_DEBUGGING */

return (::memcmp(_First1, _First2, _Last1 - _First1) == 0); } You have an indirection here and the original code has two indirections -- iterators plus _Equal call. As you may see this is too complex for MS optimizer -- it looks like the optimizer loses the data size and alignment information and gives up.

I'm using VC++2005 though. I do remember that at least memcpy intrinsic worked pretty smart in that compiler. Though the optimizers of the subsequent versions are no doubt better.

Although in both cases, the loop that is actually executed is identical to the one you give above. You are right. And I was unable to make the VC to unroll it. That is why I do believe the library that is intended to be used in commercial applications shall do its best in manual optimization of evident cases. And I believe the uint8_t data[16] is crystal evident case in all respects including alignment issues.

-- Michael Kochetkov

Interestingly, if I try the following program, the "stupid" my_memcmp produces the fastest result. #include <boost/uuid/uuid.hpp> #include <iostream> #include <windows.h> #include <mmsystem.h> typedef unsigned uint32_t; inline bool Eq16( unsigned char const * p, unsigned char const * q ) { return *reinterpret_cast<const uint32_t*>( p ) == *reinterpret_cast<const uint32_t*>( q ) && *reinterpret_cast<const uint32_t*>( p+4 ) == *reinterpret_cast<const uint32_t*>( q+4 ) && *reinterpret_cast<const uint32_t*>( p+8 ) == *reinterpret_cast<const uint32_t*>( q+8 ) && *reinterpret_cast<const uint32_t*>( p+12) == *reinterpret_cast<const uint32_t*>( q+12); } inline bool my_memcmp( unsigned char const * p, unsigned char const * q, size_t n ) { for( size_t i = 0; i < n; ++i ) { if( p[i] != q[i] ) return false; } return true; } int main() { boost::uuids::uuid id1 = {}, id2 = {}; int const N = 100000000; DWORD t1 = timeGetTime(); int s = 0; for( int i = 0; i < N; ++i ) { //s += ( id1 == id2 ); //s += Eq16( id1.data, id2.data ); //s += memcmp( id1.data, id2.data, 16 ); s += my_memcmp( id1.data, id2.data, 16 ); id2.data[ i % 16 ] += i & 0xFF; } DWORD t2 = timeGetTime(); std::cout << s << ": " << t2 - t1 << std::endl; }

BTW if you are interested in the final result you do need to initialize your uuids with some random values. VC initializes all bytes with zeros and is smart enough to remember that id1 does not change: Ok. I just cannot help it. I have corrected the ids declarations myself the following way int main() { boost::uuids::uuid id1((boost::uuids::random_generator()())), id2((boost::uuids::random_generator()())); ...

and my results are as following: Eq16 -- 100% my_memcmp -- 138.89 % memcmp -- 169.17 % operator == -- 199.72 % Eq16 became even faster. This is most likely due to the fact the first comparison became to fire much more often. Anyway with proper alignment (and I am dead sure every compiler that is sensitive to the alignment has a proper tweakster for it) Eq16 (it shall read Eq32 indeed) shall be the fastest way to compare uint8_t[16] array. Unless you are going to implement Eq64 for x64 platforms... BTW, for unoptimized (Debug) mode: Eq16 (optimized) -- 100 % operator == (optimized) -- 199.72 % Eq16 (unoptimized) -- 247.5 % operator == (unoptimized) -- 1419.16 % No comments. -- Michael Kochetkov

...

boost::uuids::uuid id1((boost::uuids::random_generator()())), id2((boost::uuids::random_generator()()));

I prefer to leave id2 identical to id1 at the start, because otherwise the two are never equal. Ok.

Core i7-920, VC++ 2005 32 bit: I have 6 years old Xeon 5130 and for your original code (with zeros):

operator== 48830: 1087 735

Eq16 48830: 311 406

memcmp -53027366: 560 625

my_memcmp: 48830: 281 485

I can see VC 2010 is probably better in optimization. Anyway the real problems are that 1. boost's implementation of uuid is at least weird in terms there are much better approaches that cost nothing in implementation but are ignored. 2. the investigation of opinions of boost people (I have made another inquiry in "[boost] [function] The cost of boost::function" thread) shows that boost still is not ready for production usage. It requires too high qualification of the real life programmers to be able to slalom in dark corners of boost and C++ itself so it puts the success of a project at high risk. And I have some real life examples (you do not think I study the cases with the debugger on purpose, do you? :) ) 3. The words on the top of the boost.org page ""...one of the most highly regarded and expertly designed C++ library projects in the world." - Herb Sutter and Andrei Alexandrescu, C++ Coding Standards" really need some grounds. I thank you all for your opinions and help. -- Michael Kochetkov

On 17/04/12 12:52, Michael Kochetkov wrote:

Anyway the real problems are that 1. boost's implementation of uuid is at least weird in terms there are much better approaches that cost nothing in implementation but are ignored.

Comparing 16 bytes is hardly the important part in a UUID library. Boost.UUID is using the correct construct for this, it is sad some compilers cannot optimize it properly, but it's still the ideal solution from a C++ point of view. The approach you suggest is not well-formed C++ and is specific to your particular configuration; it might fare worst on others. So it's not really "better" nor does it "cost nothing". An option is to simply fix the problem in your local copy of Boost. That being said, I'm sure the library author will consider fixing it if you file a bug for it.

2. the investigation of opinions of boost people (I have made another inquiry in "[boost] [function] The cost of boost::function" thread)

boost::function is heavyweight and has significant costs. If you don't need the features boost::function provides, simply don't use it and avoid the costs associated with it. The same thing can be said about any feature in C++.

shows that boost still is not ready for production usage.

You realize Boost has been used in many production environments, some very high-profile, for more than a decade now?

It requires too high qualification of the real life programmers to be able to slalom in dark corners of boost and C++ itself so it puts the success of a project at high risk. And I have some real life examples (you do not think I study the cases with the debugger on purpose, do you? :) )

This is understandable. Using any external library is a risk to take.

3. The words on the top of the boost.org page ""...one of the most highly regarded and expertly designed C++ library projects in the world." - Herb Sutter and Andrei Alexandrescu, C++ Coding Standards" really need some grounds.

Those are citations from well-known people in the C++ community. They themselves are grounds.

On 18/04/12 11:09, Michael Kochetkov wrote:

...

The approach you suggest is not well-formed C++ and is specific to your particular configuration; it might fare worst on others. Why it is not well-formed C++?

I've already pointed out why.

The people I deal with in the real world do not think about its weight. They just cannot memorize boost::_bi::bind_t<int,int (*)(int),boost::_bi::list1<boost::arg<1> > > and type it correctly. So they use boost::function just for convenience.

The good thing to do, as with all similar mechanisms (lambda, phoenix), is to avoid naming the result entirely or using auto/decltype/typeof facilities.

Hi, Am 19. April 2012 18:58 schrieb Michael Kochetkov <michael.kv@gmail.com>:

[...] I use boost UUID as global unique identifiers and I do compare them in the total majority of usages. I do admit I can misuse the UUIDs concept so I am just curious what have the boost people intended the boost::uuid to be used for?..

Planned to use it as a key in a multi index container that uses shared memory allocators.. Or even as kind of property id for a tree like recursive property value db. But I dropped that idea, and now I am looking into something like boost::flyweight' (where ' stands for the ability to store the map and values inside certain shared memory segment) as a fast comparable identifier type for the property value db. regards Andreas

...

I do remember that at least memcpy intrinsic worked pretty smart in that compiler.

It does.

I think I see what's going on. memcmp has to return -1, 0 or 1. This is why it does an initial DWORD loop to find the first mismatch, then does a byte compare to determine the return value. Thank you for pointing it out. Frankly speaking being busy with finding out the attitude of the boost people towards the problem I have really skipped the rest of generated code that have probably made the MS compiler to look a little bit smarter than it really is.

-- Michael Kochetkov

on Mon Apr 16 2012, Michael Kochetkov <michael.kv-AT-gmail.com> wrote:

...

Don't forget alignment. Those DWORD comparisons/copies may only work well for aligned memory but when you call memcmp, you erase alignment information and the compiler may assume it's only char-aligned.

I did not forget it. My words about alignment was just skipped.

I didn't see your words about alignment, and I was responding to Peter.

No doubt you can align uuid::data[16] almost any suitable way even for uint64_t. You can even start the comparison from the back if you feel that your uuids start to differ from the back to speed up the approach even more.

I would also like to confirm and further elaborate the statement in the discussion (I will not quote it from another message) that memcmp is intrinsic in MSCV for many cases (I have enforced it with Oi compiler switch), it is alignment, underlying data type and array sizes aware. You may want to have a look at the following example: #include <cstdint> #include <cstring>

int main() { uint8_t d1[16], d2[16]; return memcmp(d1,d2,16); } Here is the result.

$LL4@main: mov esi, DWORD PTR [edx] cmp esi, DWORD PTR [ecx] jne SHORT $LN5@main sub eax, 4 add ecx, 4 add edx, 4 cmp eax, 4 jae SHORT $LL4@main xor eax, eax

Pretty neat. I wish the boost and C++ standard library to develop the same way.

Yeah, that's great. My point is that it may well be that int main() { uint8_t d1[16], d2[16]; return memcmp((char*)d1,(char*)d2,16); } (or something only a little more complex, like a call through another layer of inline function) is enough to foil that optimization. -- Dave Abrahams BoostPro Computing http://www.boostpro.com

That's not really a fair test since it's all in one compilation scope. I try to just make an obj which has function which takes the stuff as a parameters like: void foo(boost::uuids::uuid&, boost::uuids::uuid&)

Then the compiler cann't know where it aligned the thing on the stack or do any other quick optimizations (beyond the alignment of the type). It is fair as far as the data type is aligned regardless where it is placed: in the heap or on the stack. If you do really want to foil the case you need to get rid of data type information (as it was proposed with the conversion to the pointer to char) and information about the data size.

The fastest thing on x86 to do this might be an MMX instruction. I remember gcc doing MOVDQA to memset() a 16 byte structure. Though I remember it because it falsely assumed 16 byte alignment and crashed.

Is your beef with the compiler?

Looking at the code the performance would probably be better if a larger integer type were used and alignment>1.

I have no doubt that one can spoil any the most brilliant idea. And that is what I see in boost: with iterators and intermediate Feng shui call it leaves the stupid MS compiler no chances to deduce the original data type, its size and alignment. Being the person who is called when a program crashes or works very slow I am pretty happy with the current situation. But while hacking another sami-failed project I was asked to join a company and start a completely new project. So I just decide now if the boost is suitable for early prototyping only or it may be used in the production too. And I do not care much about the defects like this one -- they are trivial to find and fix. I am more interested in people attitude on the problems like this one because the modern C++ approach "a compiler will take care of it" does not work for me. And as you may see I can prove my words. -- Michael Kochetkov