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.
