Hi! Comparison (operator<) on vector<bool> seems to be extremely slow, because it uses a generic implementation, i.e. bitwise iteration. It should be specialised and use integer-comparisons provided by the CPU. Regards
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.
Nice post. Thank you for taking the time to publish this information very useful! I've been looking for books of this nature for a way too long. I'm just glad that I found yours. Looking forward for your next post. Thanks :) <a href="http://www.honeywellcentral.com/humidifiers">Honeywell Humidifiers</a>
Soo long conversation. It's booring. <a href="http://www.buyanessay.com/">buy essays</a>
This is such a great resource that you are providing and you give it away for free. I love seeing websites that understand the value of providing a quality resource for free. It is the old what goes around comes around routine. <a href="http://www.genesishealthinstitute.com/testosterone.php">http://www.genesishealthinstitute.com/testosterone.php</a>
positively enjoying each little bit of it and I have you bookmarked to check out new stuff you weblog AIHL http://www.accidentinjuryhelplines.co.uk/
Well said….positively enjoying each little bit of it and I have you bookmarked to check out new stuff you weblog airlinesplanet http://www.airlinesplanet.com/
Now that was an amazing post about the comparison of vector and their additional features. It is a really useful post that helps to simplify the issues and also helps to clarify the doubts regarding vectors and bool. Awaiting new posts.<a href="http://www.outlookemailsetup.com/outlook-express-help/how-to-merge-your-email-account-with-outlook-express/">outlookemailsetup.com</a>
“It is better to take many small steps in the right direction than to make a great leap forward only to stumble backward.” http://rajasthanispecial.com/index.php/womens-collection/sarees.html
It is a really useful post that helps to simplify the issues and also helps to clarify the doubts regarding vectors and bool. Awaiting new posts. <a href="http://www.monsteribeatsbydrejp.com/">transparent music widget android</a>
inproper installation or setting up program is might be the reason for such kind of the problem. Its looks like a slower internet connection is also reason for that. http://small-fridge.net/selecting-a-best-small-fridge/
Key factors might be the reason due to which its showing slow behavior. Make a class of it and use it for the simple. https://sourceforge.net/projects/working-of-smoothie-machines/ sometimes they shows the abnormal behavior their might be list of reason you have to Go for.
Bugs and error can be quiet destructive for any system. So it's better to get solved the problems on time. Like a cooling system a refrigerator or an air conditioner are our daily us appliances but some times due to carelessness in the maintenance it fails to deliver the desire results http://airconditioner-notcooling.com/how-to-identify-problems-of-your-air-conditioner-and-get-it-fixed/ shows complete way out to face such kind of the problems.
<a href="http://www.10ults.com/escorts-in-usa.html" rel="dofollow">Escorts in USA</a>
http://www.10ults.com/escorts-in-usa.html thanks for