[Bug libstdc++/50160] New: vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 Bug #: 50160 Summary: vector comparison very slow (no specialisation) Classification: Unclassified Product: gcc Version: 4.6.2 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ AssignedTo: unassig...@gcc.gnu.org ReportedBy: de...@the-user.org Hi! Comparison (operator<) on vector 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
[Bug libstdc++/50160] vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #2 from Jonathan Schmidt-Dominé 2011-08-23 13:50:09 UTC --- Well, it made my specific application very slow, when using vector 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.
[Bug libstdc++/50160] vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #4 from Jonathan Schmidt-Dominé 2011-08-23 18:21:36 UTC --- In libc++ it is the same, specialised hash, but no specialised operator<.
[Bug libstdc++/50160] vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #5 from Jonathan Schmidt-Dominé 2011-08-23 18:26:48 UTC --- 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.)?
[Bug libstdc++/50160] vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #6 from Jonathan Schmidt-Dominé 2011-08-23 18:29:19 UTC --- Ok, I can write a patch and test if it is actually faster (it should). Is there any coding-guide line (style, variables etc.)?
[Bug libstdc++/50160] vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #8 from Jonathan Schmidt-Dominé 2011-08-23 19:04:25 UTC --- 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 backwards.” What do you mean? Chunk wise backwards? “but I don't think it can be exposed.” Well, that would not be portable.
[Bug libstdc++/50160] vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #9 from Jonathan Schmidt-Dominé 2011-08-23 19:10:06 UTC --- Hmm, reversing really is not that nice.
[Bug libstdc++/50160] vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #10 from Jonathan Schmidt-Dominé 2011-08-23 19:15:20 UTC --- There seem to be a lot of tricks to achieve that: http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv
[Bug libstdc++/50160] vector comparison very slow (no specialisation)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #12 from Jonathan Schmidt-Dominé 2011-08-23 19:31:37 UTC --- “Any particular reason?” No particular one, but a small specialisation would be nicer than changing everything or doing bitfiddling.
[Bug libstdc++/50160] vector comparison very slow (no overload)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #14 from Jonathan Schmidt-Dominé 2011-08-30 23:25:25 UTC --- Created attachment 25143 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25143 bits/stl_vector.h patch moved operator== and operator< inside class, because I want to overload them
[Bug libstdc++/50160] vector comparison very slow (no overload)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #15 from Jonathan Schmidt-Dominé 2011-08-30 23:30:00 UTC --- Created attachment 25144 --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25144 b More efficient (non representative benchmark!) implementation of operator< and operator== for vector
[Bug libstdc++/50160] vector comparison very slow (no overload)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #16 from Jonathan Schmidt-Dominé 2011-08-30 23:30:36 UTC --- Added basic patch…
[Bug libstdc++/50160] vector comparison very slow (no overload)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #18 from Jonathan Schmidt-Dominé 2011-08-30 23:56:38 UTC --- (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?
[Bug libstdc++/50160] vector comparison very slow (no overload)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #21 from Jonathan Schmidt-Dominé 2011-08-31 00:30:58 UTC --- 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.
[Bug libstdc++/50160] vector comparison very slow (no overload)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #23 from Jonathan Schmidt-Dominé 2011-08-31 00:34:28 UTC --- @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).
[Bug libstdc++/50160] vector comparison very slow (no overload)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #24 from Jonathan Schmidt-Dominé 2011-08-31 00:39:57 UTC --- @Andrew Nope: 1001 > 0001 (lexicographically) 1001 > 0001 (as little-endian) 0110 < 1110 (as little-endian)
[Bug libstdc++/50160] vector comparison very slow (no overload)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50160 --- Comment #30 from Jonathan Schmidt-Dominé 2011-09-22 13:39:22 UTC --- Sorry, thank you for creating the feature-request.
[Bug middle-end/50481] builtin to reverse the bit order
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50481 Jonathan Schmidt-Dominé changed: What|Removed |Added CC||de...@the-user.org --- Comment #1 from Jonathan Schmidt-Dominé 2011-09-23 15:30:33 UTC --- Informative web-page listing some methods: http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv
