Re: Performance improvements for std::sort

[Jonathan Wakely <jwakely dot gcc at gmail dot com>]

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.