[1/1] msort : optimizing merge sort.

  This patch improves the performance of merge sort when most of the elements are already sorted .
It improves performace of merge procedure by skipping comparison and copying of elements 
when last element of first array and first element of second array is already sorted .

When we simulated optimzed merge sort,the performace increases by 84% when mergesort 
is used for already sorted elements .

Signed-off-by: Vaneet Narang <v.narang@samsung.com>
Signed-off-by: Ayush Mittal <ayush.m@samsung.com>
---
 stdlib/msort.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)
  

On Thursday 06 July 2017 09:29 AM, Ayush Mittal wrote:
> This patch improves the performance of merge sort when most of the elements are already sorted .
> It improves performace of merge procedure by skipping comparison and copying of elements 
> when last element of first array and first element of second array is already sorted .
> 
> When we simulated optimzed merge sort,the performace increases by 84% when mergesort 
> is used for already sorted elements .

Please also include the benchmark you used to measure this.  Take a look
at benchtests/README to know ways in which you can include your
benchmark in glibc.

Also, please take a moment to review the contribution checklist[1] to
know the kind of information you need to include in your patch
submission.  For example this submission is missing a ChangeLog.

Thanks,
Siddhesh

[1] https://sourceware.org/glibc/wiki/Contribution%20checklist
  

On Thursday 06 July 2017 04:38 PM, Ayush Mittal wrote:
> We have shared test case for this change with results(performance) .
> 
> https://sourceware.org/bugzilla/show_bug.cgi?id=21719

That test only shows the amount of improvement in the case that you've
optimized for, not the inputs that could get worse due to the additional
check.  You need a benchmark that exercises different kinds of input
arrays to determine what the impact is on those loads.  A good set of
inputs for this would be based on an existing and commonly used
application program that uses msort extensively on different kinds of
inputs.  If that is not possible, a set of inputs that exercises all of
the major branches in the code proportionately would be acceptable.  The
fast paths (such as this one, where the array is almost sorted)
typically get lower weight compared to other paths through the function.

Finally, the benchmark should be included in the patch as an addition to
benchmarks in the benchtests directory.  There is a benchtests/README
that describes how you can do that.

>> Also, please take a moment to review the contribution checklist[1] to
>> know the kind of information you need to include in your patch
>> submission.  For example this submission is missing a ChangeLog.
> 
> Regarding ChangeLog we are not sure about which ChangeLog to change.
> 
> https://sourceware.org/bugzilla/show_bug.cgi?id=21719

The contribution checklist I linked to below tells you what a ChangeLog
is; see "12. Properly Formatted GNU ChangeLog"

>>
>> [1] https://sourceware.org/glibc/wiki/Contribution%20checklist

Siddhesh