This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
[PATCH 1/1] msort : optimizing merge sort.
- From: Ayush Mittal <ayush dot m at samsung dot com>
- To: libc-alpha at sourceware dot org
- Cc: pankaj dot m at samsung dot com, Ayush Mittal <ayush dot m at samsung dot com>, Vaneet Narang <v dot narang at samsung dot com>
- Date: Thu, 6 Jul 2017 09:29:04 +0530
- Subject: [PATCH 1/1] msort : optimizing merge sort.
- Authentication-results: sourceware.org; auth=none
- Cms-type: 105P
- References: <CGME20170706040233epcas5p2ce07fffff862ed1c60c1fc7a83b244be@epcas5p2.samsung.com>
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(-)
diff --git a/stdlib/msort.c b/stdlib/msort.c
index 02ef28b..498de09 100644
--- a/stdlib/msort.c
+++ b/stdlib/msort.c
@@ -39,7 +39,7 @@ static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
static void
msort_with_tmp (const struct msort_param *p, void *b, size_t n)
{
- char *b1, *b2;
+ char *b1, *b2, *b3;
size_t n1, n2;
if (n <= 1)
@@ -49,6 +49,7 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
n2 = n - n1;
b1 = b;
b2 = (char *) b + (n1 * p->s);
+ b3 = (char *) b + ((n1-1) * p->s);
msort_with_tmp (p, b1, n1);
msort_with_tmp (p, b2, n2);
@@ -60,6 +61,8 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
switch (p->var)
{
case 0:
+ if((*cmp) (b3, b2, arg) <= 0)
+ return ;
while (n1 > 0 && n2 > 0)
{
if ((*cmp) (b1, b2, arg) <= 0)
@@ -78,6 +81,8 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
}
break;
case 1:
+ if((*cmp) (b3, b2, arg) <= 0)
+ return ;
while (n1 > 0 && n2 > 0)
{
if ((*cmp) (b1, b2, arg) <= 0)
@@ -96,6 +101,8 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
}
break;
case 2:
+ if((*cmp) (b3, b2, arg) <= 0)
+ return ;
while (n1 > 0 && n2 > 0)
{
unsigned long *tmpl = (unsigned long *) tmp;
@@ -119,6 +126,8 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
}
break;
case 3:
+ if((*cmp) (*(const void **)b3,*(const void **) b2, arg) <= 0)
+ return ;
while (n1 > 0 && n2 > 0)
{
if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
@@ -137,6 +146,8 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
}
break;
default:
+ if((*cmp) (b3, b2, arg) <= 0)
+ return ;
while (n1 > 0 && n2 > 0)
{
if ((*cmp) (b1, b2, arg) <= 0)
--
1.9.1