public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/113811] New: std::rotate does 64-bit signed division
@ 2024-02-07 16:15 terra at gnome dot org
2024-02-08 9:13 ` [Bug libstdc++/113811] " rguenth at gcc dot gnu.org
` (4 more replies)
0 siblings, 5 replies; 6+ messages in thread
From: terra at gnome dot org @ 2024-02-07 16:15 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113811
Bug ID: 113811
Summary: std::rotate does 64-bit signed division
Product: gcc
Version: 13.1.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: terra at gnome dot org
Target Milestone: ---
In stl_algo.h, function __rotate for RandomAccessIterator lines 1280-1362 for
me, there are two divisions of integers:
__n %= __k;
on lines 1332 and 1356. They look harmless.
But in the common case on x86_64 where _Distance is, essentially, int64_t this
is a 64-bit signed division which is absurdly slow.
By my reading of https://www.agner.org/optimize/instruction_tables.pdf page
296:
64-bit signed: 57 cycles
64-bit unsigned: 36 cycles
smaller sizes: 10 cycles
(excluding the 64-to-128-bit sign extension needed too)
I believe the numbers involved are all positive, so at the very least the
division could be unsigned. It might even make sense to check if __n is
smaller than 2^32 and do a 32-bit division instead.
Somewhat related: bug 102580
Note: I do not actually have benchmark results that show this matters in a
practical case.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/113811] std::rotate does 64-bit signed division
2024-02-07 16:15 [Bug libstdc++/113811] New: std::rotate does 64-bit signed division terra at gnome dot org
@ 2024-02-08 9:13 ` rguenth at gcc dot gnu.org
2024-02-08 10:21 ` redi at gcc dot gnu.org
` (3 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: rguenth at gcc dot gnu.org @ 2024-02-08 9:13 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113811
--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
In case __n is the minimum signed integer and __k is -1 the division would also
trap ;) So yes, they should be unsigned.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/113811] std::rotate does 64-bit signed division
2024-02-07 16:15 [Bug libstdc++/113811] New: std::rotate does 64-bit signed division terra at gnome dot org
2024-02-08 9:13 ` [Bug libstdc++/113811] " rguenth at gcc dot gnu.org
@ 2024-02-08 10:21 ` redi at gcc dot gnu.org
2024-02-08 21:31 ` redi at gcc dot gnu.org
` (2 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2024-02-08 10:21 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113811
Jonathan Wakely <redi at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Last reconfirmed| |2024-02-08
Ever confirmed|0 |1
--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
They're never negative unless the arguments to the algorithm are incorrect, in
which case maybe trapping is better than trashing the data!
I was going to suggest that we could just add an assertion and/or hint that
they're never negative, but I guess PR 102580 means that wouldn't help.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/113811] std::rotate does 64-bit signed division
2024-02-07 16:15 [Bug libstdc++/113811] New: std::rotate does 64-bit signed division terra at gnome dot org
2024-02-08 9:13 ` [Bug libstdc++/113811] " rguenth at gcc dot gnu.org
2024-02-08 10:21 ` redi at gcc dot gnu.org
@ 2024-02-08 21:31 ` redi at gcc dot gnu.org
2024-02-15 11:44 ` cvs-commit at gcc dot gnu.org
2024-02-15 12:45 ` redi at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2024-02-08 21:31 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113811
--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
It seems fairly easy to do:
commit 12a028d76bbdf26d34d4d90a2ecdc39c6c0a4bd4 (HEAD -> master)
Author: Jonathan Wakely
Date: Thu Feb 8 15:40:32 2024
libstdc++: Use unsigned division in std::rotate [PR113811]
Signed 64-bit division is much slower than unsigned, so cast the n and
k values to unsigned before doing n %= k. We know this is safe because
neither value can be negative.
libstdc++-v3/ChangeLog:
PR libstdc++/113811
* include/bits/stl_algo.h (__rotate): Use unsigned values for
division.
diff --git a/libstdc++-v3/include/bits/stl_algo.h
b/libstdc++-v3/include/bits/stl_algo.h
index 9496b53f887..7a0cf6b6737 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -1251,6 +1251,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
+#if __cplusplus >= 201103L
+ typedef typename make_unsigned<_Distance>::type _UDistance;
+#else
+ typedef _Distance _UDistance;
+#endif
+
_Distance __n = __last - __first;
_Distance __k = __middle - __first;
@@ -1281,7 +1287,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
++__p;
++__q;
}
- __n %= __k;
+ __n = static_cast<_UDistance>(__n) %
static_cast<_UDistance>(__k);
if (__n == 0)
return __ret;
std::swap(__n, __k);
@@ -1305,7 +1311,7 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
--__q;
std::iter_swap(__p, __q);
}
- __n %= __k;
+ __n = static_cast<_UDistance>(__n) %
static_cast<_UDistance>(__k);
if (__n == 0)
return __ret;
std::swap(__n, __k);
Conditionally using 32-bit types would be a bit trickier, as it needs runtime
branches, or making the type of __n and __k a template parameter, so we can
call __rotate_with<unsigned> to use a smaller type than
make_unsigned<_Distance> if max(n,k) < UINT_MAX.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/113811] std::rotate does 64-bit signed division
2024-02-07 16:15 [Bug libstdc++/113811] New: std::rotate does 64-bit signed division terra at gnome dot org
` (2 preceding siblings ...)
2024-02-08 21:31 ` redi at gcc dot gnu.org
@ 2024-02-15 11:44 ` cvs-commit at gcc dot gnu.org
2024-02-15 12:45 ` redi at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2024-02-15 11:44 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113811
--- Comment #4 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:
https://gcc.gnu.org/g:4d819db7f229a23cb15ef68f310e0bb51d201c45
commit r14-9001-g4d819db7f229a23cb15ef68f310e0bb51d201c45
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Thu Feb 8 15:40:32 2024 +0000
libstdc++: Use unsigned division in std::rotate [PR113811]
Signed 64-bit division is much slower than unsigned, so cast the n and
k values to unsigned before doing n %= k. We know this is safe because
neither value can be negative.
libstdc++-v3/ChangeLog:
PR libstdc++/113811
* include/bits/stl_algo.h (__rotate): Use unsigned values for
division.
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/113811] std::rotate does 64-bit signed division
2024-02-07 16:15 [Bug libstdc++/113811] New: std::rotate does 64-bit signed division terra at gnome dot org
` (3 preceding siblings ...)
2024-02-15 11:44 ` cvs-commit at gcc dot gnu.org
@ 2024-02-15 12:45 ` redi at gcc dot gnu.org
4 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2024-02-15 12:45 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113811
Jonathan Wakely <redi at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Resolution|--- |FIXED
Status|NEW |RESOLVED
Target Milestone|--- |14.0
--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for gcc-14, thanks for the suggestion.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2024-02-15 12:45 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-02-07 16:15 [Bug libstdc++/113811] New: std::rotate does 64-bit signed division terra at gnome dot org
2024-02-08 9:13 ` [Bug libstdc++/113811] " rguenth at gcc dot gnu.org
2024-02-08 10:21 ` redi at gcc dot gnu.org
2024-02-08 21:31 ` redi at gcc dot gnu.org
2024-02-15 11:44 ` cvs-commit at gcc dot gnu.org
2024-02-15 12:45 ` redi at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).