Do you have some numbers? Of course we can make progress on this, but we'd like to know when it's good enough.

Well, it made my specific application very slow, when using vector<bool> as key_type for (ordered) map.  What kind of numbers would be usefull? I think it should simply have a specialised operator< implementation comparing chunks of 32/64 bits, there is also a specialised hash implementation, it should be like that one.

I meant: which improvement do you expect, in practice? I supposed you are aware if other implementations of the library already including the optimization. I'm looking for some concrete evidence, because you know, vector<bool> is deprecated, isn't a real container, and all the well known bad things about it, thus we normally don't do much development work on it beyond ghe basic maintainance. Of course, if you have already a patch, that would definitely speed things up ;)

In libc++ it is the same, specialised hash, but no specialised operator<.

In libc++ it seems to be the same, specialised hashing, but no specialised comparison. Ok, I can write a patch and test if it is actually faster (it should). Is there any coding-guide line (style, variables etc.)?

Ok, I can write a patch and test if it is actually faster (it
should). Is there any coding-guide line (style, variables etc.)?

If I understand correctly, operator< is supposed to give a lexicographic order, and vector<bool> stores {true,false,false} as 1 and {false,false,true} as 4, so we can't just make operator< compare chunks. Reversing the order of the bits in an unsigned long is a bit complicated, although it would still lead to code faster than the current (easiest would be to compare byte by byte, and mirror each byte using a table).

But you don't seem particularly interested in using the lexicographic order, is that true? In that case you could try and specify some other order to std::map, say comparing hashes ;-) I understand that the lexicographic order of the chunks would be a fine order, but I don't think it can be exposed. I haven't thought about the potential drawbacks of implementing vector<bool> backwards.

For my application I should simply use an unordered_map and all the overhead has gone. :D But operator< simply should not be that slow.

“I haven't thought about the potential drawbacks of implementing vector<bool> backwards.”
What do you mean? Chunk wise backwards?

“but I don't think it can be exposed.”
Well, that would not be portable.

Hmm, reversing really is not that nice.

There seem to be a lot of tricks to achieve that:
http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv

(In reply to comment #8)
> For my application I should simply use an unordered_map and all the overhead
> has gone. :D

Great.

> “I haven't thought about the potential drawbacks of implementing vector<bool>
> backwards.”
> What do you mean? Chunk wise backwards?

Er, yes, start filling each chunk from the most significant bit to the least significant, but otherwise keep things the same.

> Hmm, reversing really is not that nice.

Any particular reason? Not that the current implementation is likely to change anytime soon, but if you found drawbacks it would be nice to have them written somewhere in case the same question ever arises again.

“Any particular reason?”
No particular one, but a small specialisation would be nicer than changing everything or doing bitfiddling.

To be precise, we are talking about overloading not specializing. The issue, in general, reminds me the way we overload std::fill and std::copy for ranges of deque<>::iterator, but then in detail, there are the difficulties pointed out by Marc. I'm certainly available for patch reviews, anyway.

Created attachment 25143 [details]
bits/stl_vector.h patch

moved operator== and operator< inside class, because I want to overload them

Created attachment 25144 [details]
b

More efficient (non representative benchmark!) implementation of operator< and operator== for vector<bool>

Added basic patch…

(In reply to comment #14)
> moved operator== and operator< inside class, because I want to overload them

huh, why is that needed?  it's not acceptable anyway, it needs to be a non-member

(In reply to comment #17)
> (In reply to comment #14)
> > moved operator== and operator< inside class, because I want to overload them
> 
> huh, why is that needed?  it's not acceptable anyway, it needs to be a
> non-member

Correct me, if I am wrong, isn't it considered as partial specialisation when writing it straight-forward as non-member?

I'm wondering if processing an unsigned long at a time wouldn't be a step in the right direction. Then, a compiler intrinsics would be the right place for that, would naturally fit in the set of builtins fiddling with bits of integer types. On top of that the library-proper code would become very simple, in particular no ugly reinterpret_cast & co (by the way, Ch. 7 of "Hacker's Delight" has some info about such operations). Assuming indeed, we *do* have to revert the order, I'm not 101% sure.

Largely irrelevant here, but partial specialization of function templates simply does not exist. We have been talking about adding an overload like:

 template<typename _Alloc>
   bool
   operator<(const vector<bool, _Alloc>&, const vector<bool, _Alloc>&)

or overloading std::lexicographical_compare, seems also an option.

It would indeed be nice to have such a builtin function (8, 16, 32, 64 bit reversing), currently there is none in gcc, only bytewise reversing iirc. Should that be put as wishlist-item in the bugzilla or something like that?

Reversing is necessary because the ordering should be lexicographic, but the internal representation uses least-significant-first, reversing the internal representation would probably not be that nice.

Can't you do ~a < ~b ?

@Paolo

Okay, I am sometimes overcautious with function-templates, because I often had a lot of errors because of partial specialisation when it was indeed necessary (function templates with explicit parameters).

@Andrew

Nope:
10000001 > 00000001 (lexicographically)
10000001 > 00000001 (as little-endian)
01111110 < 11111110 (as little-endian)

I think a separate Bugzilla requesting as an enhancement such intrinsics would be certainly appropriate. I'm sure other code could exploit those.

Note, in the meanwhile we could as well do the exercise of separating the operation to a C function - for unsigned long, the 32-bit and 64-bit cases would be good enough for now - coded perhaps along the lines explained at the beginning of Ch. 7 of "Hacker's Delight" and use the function for operator< (please, not inline). See which performance come out.

Various processors have an instruction to reverse the bit order in a word 
(ARMv6T2 and later have RBIT, for example, and C6X has BITR on C64X and 
above).  I think a generic built-in function (variants for different type 
sizes) with associated generic RTL representation and lowering for 
processors without such an instruction makes sense.

(In reply to comment #25)
[builtins to reverse the bit order]
> I think a separate Bugzilla requesting as an enhancement such intrinsics would
> be certainly appropriate.

Has this RFE already been filed?

I think we should. Can you do that? Thanks!

See Bug 50481 about bit-reversal builtins (and feel free to add details there).

Sorry, thank you for creating the feature-request.