diff mbox series

avoid unnecessary copying of a left_subarray's tail

Message ID CAKs8_O+maxaD4n-Fbh_DbCG96=ETqoOLMCibs6V=WbngLYmdpg@mail.gmail.com
State New
Headers show
Series avoid unnecessary copying of a left_subarray's tail | expand

Commit Message

Viktor Reznov May 20, 2024, 11:07 a.m. UTC 
Let's imagine a test case in which all elements of the right subarray
must be placed to the left of any element of the left subarray.

Before merge loop:
    tmp => _ _ _ _ _ _
    b   => 4 5 6 1 2 3
After merge loop:
    tmp => 1 2 3 _ _ _
    b   => 4 5 6 _ _ _

Next begins the section of code modified by the patch:

    The old code (current master) first copies 3 elements from `b` to the
end of `tmp`,
    then 6 elements from `tmp` to `b`.

    The changed code immediately copies 3 elements from the left subarray
    to the end of `b` and then copies 3 elements from `tmp` to the
beginning of `b`.

Signed-off-by: Viktor Reznov <yann.collet.is.not.a.perfectionist@gmail.com>
---
 stdlib/qsort.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

 static void
diff mbox series

Patch

diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index be47aebbe0..51ecf1e5c0 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -288,9 +288,10 @@  msort_with_tmp (const struct msort_param *p, void *b,
size_t n)
       break;
     }

+  const size_t d = tmp - p->t;
   if (n1 > 0)
-    memcpy (tmp, b1, n1 * s);
-  memcpy (b, p->t, (n - n2) * s);
+    memcpy ((char *) b + d, b1, n1 * s);
+  memcpy (b, p->t, d);
 }