Performance improvements for std::sort

Performance improvements for std::sort

[Furkan Usta]

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?

Re: Performance improvements for std::sort

[Jonathan Wakely]

On 7 October 2017 at 17:11, Furkan Usta wrote:
> 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)?

Contributing to GCC is a bit more complicated. To assign copyright to
the FSF you need to be the copyright holder, and if you copy someone
else's code then you aren't the copyright holder.

> 2) Can I sign copyright assignment form online or do I have to actually
> print some forms, sign and send them?

You send a form to the FSF who send you back paperwork to print and
sign. You can return a scanned copy.