O(N^2) if all elements are equal

[behdad]

Hi,

I'm using this code in https://github.com/behdad/harfbuzz/, and our fuzzers have found a timeout for us, which I tracked down to this code performing slow. Upon inspection, it's clear that if all array elements are the same, the code performs at its worst case. The median-pivot method helps with the case of array being mostly sorted or reverse-sorted, but doesn't help all-the-same.

Given that elements equal to the pivot can be partitioned on either side, I'm going to modify the code to use that property to choose a more central breaking point. I'll report on my progress. Thanks.

[behdad]

This patch seems to do it for me:

diff --git a/src/hb-dsalgs.hh b/src/hb-dsalgs.hh
index 9ccd7f25..0cee280c 100644
--- a/src/hb-dsalgs.hh
+++ b/src/hb-dsalgs.hh
@@ -412,7 +412,7 @@ static inline void sort_r_simple(void *base, size_t nel, size_t w,
 
     /* Use median of first, middle and last items as pivot */
     char *x, *y, *xend, ch;
-    char *pl, *pr;
+    char *pl, *pm, *pr;
     char *last = b+w*(nel-1), *tmp;
     char *l[3];
     l[0] = b;
@@ -434,13 +434,15 @@ static inline void sort_r_simple(void *base, size_t nel, size_t w,
     pr = last;
 
     while(pl < pr) {
-      for(; pl < pr; pl += w) {
+      pm = pl+((pr-pl+1)>>1);
+      for(; pl < pm; pl += w) {
         if(sort_r_cmpswap(pl, pr, w, compar, arg)) {
           pr -= w; /* pivot now at pl */
           break;
         }
       }
-      for(; pl < pr; pr -= w) {
+      pm = pl+((pr-pl)>>1);
+      for(; pm < pr; pr -= w) {
         if(sort_r_cmpswap(pl, pr, w, compar, arg)) {
           pl += w; /* pivot now at pr */
           break;

Can you please verify the logic?

[noporpoise]

sort_r_cmpswap(a, b) swaps and returns true if-and-only-if a>b. For a list of equal values those lines swap anything.

I've added a program run_tests.c which benchmarks various data sets:

./run_tests
       Equal: n=   100000000,    0.45 s,    200000010 comparisons (2.0X vs 26.6X)
   Ascending: n=   100000000,    0.78 s,    300000006 comparisons (3.0X vs 26.6X)
  Descending: n=   100000000,    3.91 s,   1100001339 comparisons (11.0X vs 26.6X)
      Random: n=   100000000,   22.04 s,   2898461757 comparisons (29.0X vs 26.6X)
       Mixed: n=   100000000,   21.27 s,   2874720285 comparisons (28.7X vs 26.6X)
Ran in 48.45 s

It looks like we do pretty well for all these example datasets.

[noporpoise]

Sorry it took me so long to look at this btw.

[behdad]

sort_r_cmpswap(a, b) swaps and returns true if-and-only-if a>b. For a list of equal values those lines swap anything.

They don't swap anything. But the loops themselves run in O(N^2). No? I'm pretty sure I observed this for real, and fixed it for real. Somethings not lining up. Humm. Your numbers don't agree with me.

Isn't it the case that if all are equal, we end up with pl moving all the way to pr in the first loop, and hence we recursing with all but one item? Isn't that quadratic?

[noporpoise]

Isn't it the case that if all are equal, we end up with pl moving all the way to pr in the first loop, and hence we recursing with all but one item? Isn't that quadratic?

Actually that makes sense. I'll take another look. If that is the case I can change it to always swap for equal values, which should solve that issue by putting exactly half of values on each side of the pivot.

[noporpoise]

Your solution is possibly nicer than the one I just proposed as it avoids swapping so much.

[noporpoise]

Ah - I was benchmarking qsort_r() instead of sort_r_simple(). I'll look into fixes for quadratic behaviour.

[noporpoise]

PR #9 will address this problem now in the most basic way. When I get more time I'll optimise the solution.

[behdad]

Your changes look a lot more complicated than mine! Why did you need to separate compare and swap function calls?

[noporpoise]

Coming back to this thread very late - sorry about that!

Your changes look a lot more complicated than mine! Why did you need to separate compare and swap function calls?

Rather than do a swap every time we find a value on the left greater than the pivot, or a value on the right less than the pivot, we find the two values (one of the left greater-than-the-pivot and one on the right less-than-than-the-pivot) then swap them with each other. This has no effect on the number of comparisons calculated, but approximately halves the number of swap operations needed (the pivot remains stationary).