Bug #13358: intersect, unique and gsort were slow on already sorted elements 66/14466/3
Pierre-Aime Agnel [Mon, 28 Apr 2014 09:48:42 +0000 (11:48 +0200)]
see rationale here https://sourceware.org/ml/newlib/2013/msg00087.html

Change-Id: Ibbd326ea3e69200745f15a6dda3284ec3dda8837

scilab/CHANGES_5.5.X
scilab/modules/elementary_functions/src/c/qsort.c
scilab/modules/elementary_functions/tests/nonreg_tests/bug_13358.dia.ref [new file with mode: 0644]
scilab/modules/elementary_functions/tests/nonreg_tests/bug_13358.tst [new file with mode: 0644]

index d9db55a..8eeca55 100644 (file)
@@ -49,6 +49,8 @@ Scilab Bug Fixes
 
 * Bug #13351 fixed - xstringb failed with LaTeX code.
 
+* Bug #13358 fixed - Intersect and unique were slow due to an issue in quicksort implementation.
+
 * Bug #13365 fixed - Data bounds werenot correctly updated in 3-D.
 
 * Bug #13378 fixed - The "Console" handle display was not homogeneous with others.
@@ -106,6 +108,7 @@ Xcos Bug Fixes
 * Bug #13396 fixed - MBLOCK did not work with an external file containing the modelica class.
 
 
+
                      Changes between version 5.4.1 and 5.5.0
                      =======================================
 
index 1a6d4e8..cd912cb 100644 (file)
@@ -65,10 +65,9 @@ void sciqsort(char *a, char *tab, int flag, int n, int es, int es1, int (*cmp)()
 {
     char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
     char *taba, *tabb, *tabc, *tabd, *tabl, *tabm, *tabn;
-    int d, dind, r, r1,  swap_cnt;
+    int d, dind, r, r1;
 
 loop:
-    swap_cnt = 0;
     if (n < 7)   /* Insertion sort on smallest arrays */
     {
         for (pm = a + es, tabm = tab + es1 ; pm < (char *) a + n * es; pm += es, tabm += es1 )
@@ -134,7 +133,6 @@ loop:
             if (r == 0)  /*The pivot and  value pointed to by pb are equal */
             {
                 /* store the equal value at the location pa and increase pa */
-                swap_cnt = 1;
                 swapind(taba, tabb);
                 taba += es1;
                 swap(pa, pb);
@@ -151,7 +149,6 @@ loop:
             if (r == 0)  /*The pivot and  value pointed to by pc are equal */
             {
                 /* store the equal value at the location pd and decrease pd */
-                swap_cnt = 1;
                 swapind(tabc, tabd);
                 tabd -= es1;
                 swap(pc, pd);
@@ -180,7 +177,6 @@ loop:
         tabb += es1;
         tabc -= es1;
         swap(pb, pc);
-        swap_cnt = 1;
         /* increase pb and decrease pc */
         pb += es;
         pc -= es;
@@ -190,18 +186,6 @@ loop:
         */
     }
 
-    if (swap_cnt == 0)    /* Switch to insertion sort */
-    {
-        for (pm = a + es, tabm = tab + es1 ; pm < (char *) a + n * es; pm += es, tabm += es1)
-        {
-            for (pl = pm, tabl = tabm ; pl > (char *) a && cmp(pl - es, pl, tabl - es1, tabl, flag) > 0;  pl -= es, tabl -= es1)
-            {
-                swapind(tabl, tabl - es1);
-                swap(pl, pl - es);
-            }
-        }
-        return;
-    }
     /* put the equal values in the middle */
     pn = a + n * es;
     r = (int)Min(pa - (char *)a, pb - pa);
diff --git a/scilab/modules/elementary_functions/tests/nonreg_tests/bug_13358.dia.ref b/scilab/modules/elementary_functions/tests/nonreg_tests/bug_13358.dia.ref
new file mode 100644 (file)
index 0000000..e0caf20
--- /dev/null
@@ -0,0 +1,45 @@
+// =============================================================================
+// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+// Copyright (C) 2014 - Scilab Enterprises - Pierre-Aime Agnel
+//
+//  This file is distributed under the same license as the Scilab package.
+// =============================================================================
+//
+// <-- Non-regression test for bug 13358-->
+//
+// <-- Bugzilla URL -->
+// http://bugzilla.scilab.org/13358
+//
+// <-- Short Description -->
+// intersect and unique are slower due to gsort behaving in o(n^2) on sorted arrays
+//
+// <-- CLI SHELL MODE -->
+err = 0.15
+ err  =
+    0.15  
+seed = getdate("s");
+rand("seed", seed);
+nb_test = 5;
+A = 1:1E5;
+B = 2:2:2E5;
+delta_i = [];
+delta_u = [];
+delta_s = [];
+// Checks relative time between sort on a random table and a sorted one is within 15%
+for i = 1:nb_test
+    A_rand = rand(1, 1E5);
+    B_rand = rand(1, 1E5);
+    tic(); intersect(A, B); t_elapsed_sorted = toc();
+    tic(); intersect(A_rand, B_rand); t_elapsed_rand = toc();
+    delta_i = [delta_i, abs(t_elapsed_rand - t_elapsed_sorted) / (t_elapsed_rand + t_elapsed_sorted)];
+    tic(); unique(A); t_elapsed_sorted = toc();
+    tic(); unique(A_rand); t_elapsed_rand = toc();
+    delta_u = [delta_u, abs(t_elapsed_rand - t_elapsed_sorted) / (t_elapsed_rand + t_elapsed_sorted)];
+    tic(); gsort(1:1E6); t_elapsed_sorted = toc();
+    tic(); gsort(rand(1,1E6)); t_elapsed_rand = toc();
+    delta_s = [delta_s, abs(t_elapsed_rand - t_elapsed_sorted) / (t_elapsed_rand + t_elapsed_sorted)];
+end
+assert_checktrue(mean(delta_i) <= err);
+assert_checktrue(mean(delta_u) <= err);
+assert_checktrue(mean(delta_s) <= err);
diff --git a/scilab/modules/elementary_functions/tests/nonreg_tests/bug_13358.tst b/scilab/modules/elementary_functions/tests/nonreg_tests/bug_13358.tst
new file mode 100644 (file)
index 0000000..287fbbc
--- /dev/null
@@ -0,0 +1,48 @@
+// =============================================================================
+// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+// Copyright (C) 2014 - Scilab Enterprises - Pierre-Aime Agnel
+//
+//  This file is distributed under the same license as the Scilab package.
+// =============================================================================
+//
+// <-- Non-regression test for bug 13358-->
+//
+// <-- Bugzilla URL -->
+// http://bugzilla.scilab.org/13358
+//
+// <-- Short Description -->
+// intersect and unique are slower due to gsort behaving in o(n^2) on sorted arrays
+//
+
+// <-- CLI SHELL MODE -->
+
+err = 0.15
+seed = getdate("s");
+rand("seed", seed);
+nb_test = 5;
+A = 1:1E5;
+B = 2:2:2E5;
+delta_i = [];
+delta_u = [];
+delta_s = [];
+
+// Checks relative time between sort on a random table and a sorted one is within 15%
+for i = 1:nb_test
+    A_rand = rand(1, 1E5);
+    B_rand = rand(1, 1E5);
+    tic(); intersect(A, B); t_elapsed_sorted = toc();
+    tic(); intersect(A_rand, B_rand); t_elapsed_rand = toc();
+    delta_i = [delta_i, abs(t_elapsed_rand - t_elapsed_sorted) / (t_elapsed_rand + t_elapsed_sorted)];
+
+    tic(); unique(A); t_elapsed_sorted = toc();
+    tic(); unique(A_rand); t_elapsed_rand = toc();
+    delta_u = [delta_u, abs(t_elapsed_rand - t_elapsed_sorted) / (t_elapsed_rand + t_elapsed_sorted)];
+
+    tic(); gsort(1:1E6); t_elapsed_sorted = toc();
+    tic(); gsort(rand(1,1E6)); t_elapsed_rand = toc();
+    delta_s = [delta_s, abs(t_elapsed_rand - t_elapsed_sorted) / (t_elapsed_rand + t_elapsed_sorted)];
+end
+
+assert_checktrue(mean(delta_i) <= err);
+assert_checktrue(mean(delta_u) <= err);
+assert_checktrue(mean(delta_s) <= err);