[Bug libstdc++/40852] [parallel-mode] parallel sort run time increases ~10 fold when vector size gets over ~4*10^9

["singler at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #10 from singler at gcc dot gnu dot org  2009-10-22 07:15 -------
The problem is in multiseq_selection.h, where this line has an overflow

(static_cast<uint64_t>(__total) * __rank / __N - __leftsize)

if (__total * __rank) exceeds 64 bits.  The quick fix is to use a temporary
double, which solves the original test case:

4 x 10^9 ints: 64 seconds used in sort
5 x 10^9 ints: 80 seconds used in sort

Find patches for branch (4.4) and trunk (4.5) attached.

However, I do not fully trust the double arithmetics yet, although some test
cases work.  Does anybody else know a better way to avoid an overflow in ((a *
b) / c) with only integer arithmetics and normal rounding?

Maybe I can find a way to avoid this calculation altogether.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=40852