This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Performance improvements for std::sort
- From: Furkan Usta <furkanusta17 at gmail dot com>
- To: libstdc++ at gcc dot gnu dot org
- Date: Sat, 7 Oct 2017 19:11:29 +0300
- Subject: Performance improvements for std::sort
- Authentication-results: sourceware.org; auth=none
Hi, I was checking sort implementation in other languages/implementations
and found out a simple optimization that is performed by libc++ and BSD
qsort.
I've implemented the same idea on libstdc++ and observed some improvements.
All the test cases include 10M elements, and results are in ms.
Increasing
Modified: 65
Original: 236
Decreasing
Modified: 55
Original: 173
Random
Modified: 1039
Original: 1054
Pipe Organ
Modified: 26
Original: 81
Main point of the optimization is that, if during partition no swaps have
been made, then the list might be almost sorted, or even already sorted. In
that case, perform an incomplete insertion sort (allowing only 8-insertion
runs) and reduce the bounds of the list accordingly.
I would like to contribute that optimization to libstdc++, but I have 2
questions:
1) I've found the idea from an another project, would it be a problem
license-wise (though they both have permissive licenses)?
2) Can I sign copyright assignment form online or do I have to actually
print some forms, sign and send them?