List.sort() very slow if list is already sorted or nearly so.

[PureFox48]

I noticed recently that List.sort(), which is based on the Quicksort algorithm, is very slow indeed when applied to lists which are already sorted or nearly so.

For example, this code takes around 5.7 seconds to run on my Core i7 machine:

var list = (1..10000).toList
list.sort()

I tracked down the problem to the choice of pivot in the private partition_ method in wren_core.wren:

partition_(low, high, comparer) {
    var p = this[high]
    // blah
}

If instead of always using the high value we use the mid value:

partition_(low, high, comparer) {
    var mid = ((low + high)/2).floor
    this.swap(mid, high)
    var p = this[high]
    // blah
}

then the code now runs in around 0.014 seconds. Moreover, the effect of adding these two lines has negligible effect on the time taken to sort unsorted lists.

The implementation also has a problem when the list contains repeated elements. For example this code takes around 2.8 seconds to run whatever the pivot choice:

var list = [1] * 10000
list.sort()

However, I can't think of a simple way to solve this particular problem which probably occurs much less often than the 'already sorted' one in practice. If anyone has an idea on this, please post it.

These, of course, are known issues with Quicksort generally which is also very slow when sorting small lists. The latter could be solved by using an insertion sort for lists under 10 elements say but, frankly, I doubt whether it's worth the effort in a simple scripting language such as Wren.

[ruby0x1]

For the last snippet I was wondering. I'm assuming so but did you measure only the sort or both lines? If not what does this version measure at?

var list = List.filled(10000, 1)
list.sort()

[ruby0x1]

Thanks for digging btw, we can probably add some tests around this kinda thing to give us a baseline to compare with and validate against.

[PureFox48]

I just measured the sort.

The time to create the list is virtually the same at 0.0183 seconds whether one uses: List.filled or the List.* operator so possibly they're using the same code under the hood.

Incidentally, the Wikipedia article on Quicksort suggests that using a 'median of three' may be better than a simple midpoint. It was actually a shade slower in my own tests possibly because the cost of interpreting the extra code outweighed any efficiency gained.

[PureFox48]

Oops, sorry, I messed up the timings for the list creation.

List.* takes 0.00092 seconds but List.filled only takes around 1 millionth of a second. However, either way, it's still insignificant compared to the sort time of 2.8 seconds.

[mhermier]

Did you tried with a more dumb algorithm, like bubble sort? That way it would use less stack memory and could compute a little less.

[ruby0x1]

here's one I had in my libs laying around

    static bubble_sort(list, compare) {
      if(list.count == 0) return
      var done = false
      while(!done) {
        done = true
        for(i in 0 ... list.count-1) {
          var comp = compare.call(list[i], list[i+1])
          if(comp > 0) {
            var tmp = list[i]
            list[i] = list[i+1]
            list[i+1] = tmp
            done = false
          }
        }
      }
    } //bubble_sort

[PureFox48]

Using the following optimized implementation of an ascending bubble sort:

var bubbleSort = Fn.new { |a|
    var n = a.count
    while (true) {
        var n2 = 0
        for (i in 1...n) {
            if (a[i - 1] > a[i]) {
                a.swap(i, i - 1)
                n2 = i
            }
        }
        n = n2
        if (n == 0) break
    }
}

the results are a bit variable but it's typically taking around 0.0008 seconds for both the 'already sorted' and 'all the same' cases.

@ruby0x1's version is slightly slower than this.

As expected, this is much quicker than Quicksort even with the modified pivot but, of course, it would be a completely different story if the list contained random values.

[ruby0x1]

one has a predicate so not a direct comparison (and not that it matters grand scheme, interesting none the less!)

[PureFox48]

After reading through the salient parts of the Wikipedia article, I wonder whether the best solution here would be to change the partition scheme from Lomuto (which we seem to have at present) to Hoare?

On the face of it, this would give reasonable (albeit sub-optimal) performance for the 'already sorted' and 'all the same' cases and should be no slower for unsorted data. The interface of List.sort would be the same and so this change would be invisible to users.

The alternative would be to stick with what we have, changing the pivot choice to midpoint (or median of three) to give reasonable performance for already sorted lists and just accept the hit on cases where a lot of the data is the same on the grounds that this shouldn't occur very often in practice. We could perhaps put a warning in the docs about this so that knowledgeable users could use an alternative algorithm for this kind of scenario.

[ruby0x1]

If the Hoare version works better in all cases @PureFox48, then it makes sense to consider it. A PR would be the ideal path then, if you're up for it.

[PureFox48]

OK, when I have a clearer head, I'll try and do a Hoare version and see how it compares.

[mhermier]

Do you have numbers with random values with Buble sort? I mean, the stress on the stack is less heavy with it. And in our case it could be enough unless we have a very large amount of data.

[mhermier]

You optimized version can optimized a little bit more with: `while (n != 0)`and removing: `if (n == 0) break`.

[PureFox48]

Both bubble sort and insertion sort are hopelessly slow when sorting random data even for lists as small as 100 elements.

Check out the Wren results for this Rosetta code task, comparing the performance of various sorting methods, which I did some time ago.

To keep things simple, I think we must stick with quicksort for the List.sort method which is easily the fastest algorithm for random data of non-trivial size and should (with Hoare partitioning which I'm working on just now) still give reasonable results even when the data is already sorted or all the same.

[PureFox48]

OK, I've done the Hoare version and it seems to be working OK.

To make it easier to play about with them, I've put it (and also the modified Lomuto code) in separate classes for now.

import "random" for Random

// Lomuto partitioning (as per List.sort()) but with midpoint pivot.
class List2 {
  static sort(a) { sort(a) {|low, high| low < high } }

  static sort(a, comparer) {
    if (!(comparer is Fn)) {
      Fiber.abort("Comparer must be a function.")
    }
    quicksort_(a, 0, a.count - 1, comparer)
    return a
  }

  static quicksort_(a, low, high, comparer) {
    if (low < high) {
      var p = partition_(a, low, high, comparer)
      quicksort_(a, low, p - 1, comparer)
      quicksort_(a, p + 1, high, comparer)
    }
  }

  static partition_(a, low, high, comparer) {
    var mid = ((low + high)/2).floor // added this line
    a.swap(mid, high)                // ditto
    var p = a[high]
    var i = low - 1
    for (j in low..(high-1)) {
      if (comparer.call(a[j], p)) {
        i = i + 1
        var t = a[i]
        a[i] = a[j]
        a[j] = t
      }
    }
    var t = a[i+1]
    a[i+1] = a[high]
    a[high] = t
    return i+1
  }
}

// Hoare partitioning as per Wikpedia article.
class List3 {
  static sort(a) { sort(a) {|low, high| low < high } }

  static sort(a, comparer) {
    if (!(comparer is Fn)) {
      Fiber.abort("Comparer must be a function.")
    }
    quicksort_(a, 0, a.count - 1, comparer)
    return a
  }

  static quicksort_(a, low, high, comparer) {
    if (low >= 0 && high >= 0 && low < high) {
      var p = partition_(a, low, high, comparer)
      quicksort_(a, low, p, comparer)
      quicksort_(a, p+1, high, comparer)
    }
  }

  static partition_(a, low, high, comparer) {
    var mid = ((low + high)/2).floor
    var p = a[mid]
    var i = low - 1
    var j = high + 1
    while (true) {
      while (true) {
        i = i + 1
        if (!comparer.call(a[i], p)) break
      }
      while (true) {
        j = j - 1
        if (!comparer.call(p, a[j])) break
      }
      if (i >= j) return j
      a.swap(i, j)
    }
  }
}

var n = 20
var sorted = (1..n).toList
var same = List.filled(n, 1)
var rand = Random.new()
var unsorted = sorted.toList
rand.shuffle(unsorted)

System.print("Tests for List3.sort (Hoare):\n")

System.print(sorted)
List3.sort(sorted)
System.print(sorted)
System.print()

System.print(same)
List3.sort(same)
System.print(same)
System.print()

var unsorted2 = unsorted.toList // make a copy
System.print(unsorted)
List3.sort(unsorted) { |a, b| a < b }
System.print(unsorted)
System.print()

System.print(unsorted2)
List3.sort(unsorted2) { |a, b| a > b } // descending sort
System.print(unsorted2)

/* output:
Tests for List3.sort (Hoare):

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[8, 12, 14, 19, 15, 1, 20, 11, 3, 6, 2, 16, 13, 18, 5, 10, 9, 4, 17, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

[8, 12, 14, 19, 15, 1, 20, 11, 3, 6, 2, 16, 13, 18, 5, 10, 9, 4, 17, 7]
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
*/

I'm doing some comparative benchmarks and will post those shortly.

[PureFox48]

OK, here's the performance figures for the existing List.sort method (Lomuto) with the midpoint pivot:

Benchmarks for List2.sort (modified Lomuto):

Running 'Sorted data size 10' over 10 iteration(s):

Best 0.004 ms
Mean 0.004 ms
Worst 0.007 ms

Running 'Same data size 10' over 10 iteration(s):

Best 0.005 ms
Mean 0.007 ms
Worst 0.019 ms

Running 'Random data size 10' over 10 iteration(s):

Best 0.004 ms
Mean 0.008 ms
Worst 0.024 ms

Running 'Sorted data size 100' over 10 iteration(s):

Best 0.060 ms
Mean 0.064 ms
Worst 0.096 ms

Running 'Same data size 100' over 10 iteration(s):

Best 0.304 ms
Mean 0.309 ms
Worst 0.340 ms

Running 'Random data size 100' over 10 iteration(s):

Best 0.076 ms
Mean 0.080 ms
Worst 0.110 ms

Running 'Sorted data size 1000' over 10 iteration(s):

Best 0.840 ms
Mean 0.850 ms
Worst 0.908 ms

Running 'Same data size 1000' over 10 iteration(s):

Best 27.987 ms
Mean 28.121 ms
Worst 28.585 ms

Running 'Random data size 1000' over 10 iteration(s):

Best 1.144 ms
Mean 1.159 ms
Worst 1.208 ms

Running 'Sorted data size 10000' over 10 iteration(s):

Best 11.382 ms
Mean 11.455 ms
Worst 11.632 ms

Running 'Same data size 10000' over 10 iteration(s):

Best 2773.198 ms
Mean 2777.167 ms
Worst 2792.362 ms

Running 'Random data size 10000' over 10 iteration(s):

Best 16.246 ms
Mean 16.354 ms
Worst 16.724 ms

[PureFox48]

...and here's the performance figures for the Hoare partitioning version:

Benchmarks for List3.sort (Hoare):

Running 'Sorted data size 10' over 10 iteration(s):

Best 0.005 ms
Mean 0.005 ms
Worst 0.007 ms

Running 'Same data size 10' over 10 iteration(s):

Best 0.005 ms
Mean 0.006 ms
Worst 0.007 ms

Running 'Random data size 10' over 10 iteration(s):

Best 0.005 ms
Mean 0.006 ms
Worst 0.007 ms

Running 'Sorted data size 100' over 10 iteration(s):

Best 0.065 ms
Mean 0.067 ms
Worst 0.068 ms

Running 'Same data size 100' over 10 iteration(s):

Best 0.080 ms
Mean 0.081 ms
Worst 0.083 ms

Running 'Random data size 100' over 10 iteration(s):

Best 0.084 ms
Mean 0.085 ms
Worst 0.086 ms

Running 'Sorted data size 1000' over 10 iteration(s):

Best 0.839 ms
Mean 0.846 ms
Worst 0.901 ms

Running 'Same data size 1000' over 10 iteration(s):

Best 1.080 ms
Mean 1.100 ms
Worst 1.167 ms

Running 'Random data size 1000' over 10 iteration(s):

Best 1.183 ms
Mean 1.217 ms
Worst 1.303 ms

Running 'Sorted data size 10000' over 10 iteration(s):

Best 10.046 ms
Mean 10.114 ms
Worst 10.231 ms

Running 'Same data size 10000' over 10 iteration(s):

Best 13.034 ms
Mean 13.129 ms
Worst 13.248 ms

Running 'Random data size 10000' over 10 iteration(s):

Best 14.275 ms
Mean 14.372 ms
Worst 14.620 m

[PureFox48]

For good measure, here are some figures for lists containing 100,000 and 1,000,000 random elements.

Benchmarks for existing list.sort (Lomuto):

Running 'Random data size 100000' over 10 iteration(s):

Best 175.197 ms
Mean 180.517 ms
Worst 184.312 ms

Running 'Random data size 1000000' over 10 iteration(s):

Best 2273.706 ms
Mean 2315.149 ms
Worst 2338.914 ms

Benchmarks for List2.sort (modified Lomuto):

Running 'Random data size 100000' over 10 iteration(s):

Best 188.390 ms
Mean 190.232 ms
Worst 192.531 ms

Running 'Random data size 1000000' over 10 iteration(s):

Best 2380.935 ms
Mean 2383.646 ms
Worst 2392.719 ms

Benchmarks for List3.sort (Hoare):

Running 'Random data size 100000' over 10 iteration(s):

Best 174.246 ms
Mean 174.686 ms
Worst 175.152 ms

Running 'Random data size 1000000' over 10 iteration(s):

Best 2028.855 ms
Mean 2031.921 ms
Worst 2036.394 ms

This demonstrates just how fast the quicksort algorithm is, even for large amounts of data and using an interpreted language such as Wren.

[PureFox48]

Whilst we're at it, I think we should also add ordering operators to the String class so that (amongst other things) we can easily sort strings lexicographically by codepoint. This code should do it:

class String is Sequence {
  /* existing stuff */
  
  // Compares this to another string lexicographically by codepoint.
  // Returns -1, 0 or +1 depending on whether
  // this < other, this == other or this > other respectively.
  compareTo(other) {
     if (!(other is String)) Fiber.abort("Other must be a string")
     if (this == other) return 0
     var cp1 = this.codePoints
     var cp2 = other.codePoints
     var len = (cp1.count <= cp2.count) ? cp1.count : cp2.count
     for (i in 0...len) {
        if (cp1[i] < cp2[i]) return -1
        if (cp1[i] > cp2[i]) return 1
     }
     return (cp1.count < cp2.count) ? -1 : 1
  }

  // Comparison operators.
  <  (other) { compareTo(other) <  0 }
  <= (other) { compareTo(other) <= 0 }
  >  (other) { compareTo(other) >  0 }
  >= (other) { compareTo(other) >= 0 } 
}

[mhermier]

Please open a separate discussion for this, it can be optimized more than that.

[PureFox48]

Done. See #1142.

[ruby0x1]

Thanks for the detailed posts @PureFox48, it's always appreciated ✨

[mhermier]

For reference, can you benchmark the algorithm provided by List, and the Hoare applied to it (It should optimize a little bit more, because functional is a little bit sub-optimal in wren).

[PureFox48]

The only one we haven't benchmarked so far is the existing list.sort() method which is based on Lomuto partitioning but with the high value pivot. Consequently, it's very slow when the data is already sorted or is the same.The figures for that are given below:

Benchmarks for existing list.sort (Lomuto):

Running 'Sorted data size 10' over 10 iteration(s):

Best 0.007 ms
Mean 0.008 ms
Worst 0.012 ms

Running 'Same data size 10' over 10 iteration(s):

Best 0.005 ms
Mean 0.005 ms
Worst 0.006 ms

Running 'Random data size 10' over 10 iteration(s):

Best 0.003 ms
Mean 0.004 ms
Worst 0.004 ms

Running 'Sorted data size 100' over 10 iteration(s):

Best 0.578 ms
Mean 0.583 ms
Worst 0.595 ms

Running 'Same data size 100' over 10 iteration(s):

Best 0.296 ms
Mean 0.300 ms
Worst 0.304 ms

Running 'Random data size 100' over 10 iteration(s):

Best 0.069 ms
Mean 0.070 ms
Worst 0.070 ms

Running 'Sorted data size 1000' over 10 iteration(s):

Best 53.978 ms
Mean 55.671 ms
Worst 57.360 ms

Running 'Same data size 1000' over 10 iteration(s):

Best 27.065 ms
Mean 27.468 ms
Worst 28.218 ms

Running 'Random data size 1000' over 10 iteration(s):

Best 1.151 ms
Mean 1.161 ms
Worst 1.213 ms

Running 'Sorted data size 10000' over 10 iteration(s):

Best 5471.917 ms
Mean 5604.434 ms
Worst 5644.828 ms

Running 'Same data size 10000' over 10 iteration(s):

Best 2754.123 ms
Mean 2757.615 ms
Worst 2764.081 ms

Running 'Random data size 10000' over 10 iteration(s):

Best 14.600 ms
Mean 14.767 ms
Worst 15.056 ms

List2.sort differs from the above in that it uses a mid-value pivot to remedy the 'already sorted' problem.

List3.sort uses Hoare partitoning to remedy both the 'already sorted' and 'are the same' problems.

To ensure all 3 methods use exactly the same data, I've updated the figures for the other two in my earlier posts.

My overall conclusion is that we should change to the Hoare method which gives reasonable results across the board and seems a shade faster than Lomuto for large lists.

[PureFox48]

As it seems clear from these figures that a change to Hoare partitioning will be beneficial, I've now opened a PR for it.

[mhermier]

By having the preconditions of `count > 1` are the conditions `low >= 0 && high >= 0` not always true and could be removed?

[PureFox48]

The only time when high is less than 0 is when the list is empty and it's then equal to -1. However, low is then 0 and the condition low < high then fails and the method just returns without doing anything.

So, yes, we can get rid of the low >= 0 && high >= 0 part and I'll change the code in the PR when I have time.