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.