'list::sort' is very slow

[jiribenes]

Warning

My measurements are, well, not great (ran only once), but I think they are good enough to showcase the trendline.
I did try to run the native sort first and only then the Effekt sort just to make sure.

I tried to use list::sort on List[Int] in order to sort a few hundred thousand relatively small numbers and, well, it was quite hard to do so on both the JS and the LLVM backend.

So I went ahead and tried measuring it in comparison with doing a native sort on the JS backend (converting a list to an array and then building it back up). The trendline clearly shows that Effekt's sort is pretty darn slow, especially in the case of relatively small numbers:

Sorting
✓ Effekt JS sort: 1..10 [0.69ms]
✓ Effekt LLVM sort: 1..10 [0.4ms]
✓ Native sort: 1..10 [0.41ms]
✓ Effekt JS sort: 1..100 [7.33ms]
✓ Effekt LLVM sort: 1..100 [2.74ms]
✓ Native sort: 1..100 [0.4ms]
✓ Effekt JS sort: 1..1000 [8084.8ms]
✓ Effekt LLVM sort: 1..1000 [359.22ms]
✓ Native sort: 1..1000 [0.23ms]


✓ Effekt JS sort: 10x [-10, 10] [0.12ms]
✓ Effekt LLVM sort: 10x [-10, 10] [0.1ms]
✓ Native sort: 10x [-10, 10] [0.6ms]
✓ Effekt JS sort: 100x [-10, 10] [0.47ms]
✓ Effekt LLVM sort: 100x [-10, 10] [0.16ms]
✓ Native sort: 100x [-10, 10] [0.3ms]
✓ Effekt JS sort: 1000x [-10, 10] [19.11ms]
✓ Effekt LLVM sort: 1000x [-10, 10] [4.86ms]
✓ Native sort: 1000x [-10, 10] [0.39ms]
✓ Effekt JS sort: 10000x [-10, 10] [17440.90ms] // ❗️❗️❗️
✓ Effekt LLVM sort: 10000x [-10, 10] [915.96ms] // ❗️
✓ Native sort: 10000x [-10, 10] [3.3ms]


✓ Effekt JS sort: 10x [-10000000, 10000000] [0.9ms]
✓ Effekt LLVM sort: 10x [-10000000, 10000000] [0.1ms]
✓ Native sort: 10x [-10000000, 10000000] [0.14ms]
✓ Effekt JS sort: 100x [-10000000, 10000000] [0.26ms]
✓ Effekt LLVM sort: 100x [-10000000, 10000000] [0.16ms]
✓ Native sort: 100x [-10000000, 10000000] [0.11ms]
✓ Effekt JS sort: 1000x [-10000000, 10000000] [6.44ms]
✓ Effekt LLVM sort: 1000x [-10000000, 10000000] [2.24ms]
✓ Native sort: 1000x [-10000000, 10000000] [0.30ms]
✓ Effekt JS sort: 10000x [-10000000, 10000000] [80.81ms]      // but now it's pretty OK?
✓ Effekt LLVM sort: 10000x [-10000000, 10000000] [28.44ms]    // dtto
✓ Native sort: 10000x [-10000000, 10000000] [3.76ms]

Of course, the implementation of sort is currently pretty simple:

effekt/libraries/common/list.effekt

Lines 652 to 665 in adf76cf

	/// Sort a list using a given comparison function.
	///
	/// Note: this implementation is not stacksafe!
	///
	/// O(N log N)
	def sortBy[A](l: List[A]) { compare: (A, A) => Bool }: List[A] =
	l match {
	case Nil() => Nil()
	case Cons(pivot, rest) =>
	val (lt, gt) = rest.partition { el => compare(el, pivot) };
	val leftSorted = sortBy(lt) { (a, b) => compare(a, b) }
	val rightSorted = sortBy(gt) { (a, b) => compare(a, b) }
	leftSorted.append(Cons(pivot, rightSorted))
	}

but I think it would be nice to look into it and try to speed it up.

I don't think we need to be competitive with a mutable array in JS, but for my usecase it would be nice if this particular difference wouldn't be so huge. I'm fine with it taking -- let's say, 100ms -- but 17s is kinda a lot, even for linked lists:

✓ Effekt JS sort: 10000x [-10, 10] [17440.90ms] // ❗️❗️❗️
✓ Effekt LLVM sort: 10000x [-10, 10] [915.96ms] // ❗️
✓ Native sort: 10000x [-10, 10] [3.3ms]

As an alternative, we could also provide array::sort (ideally written in Effekt though).

Here's the code I measured with

import array
import test

extern io def unsafeSort(array: Array[Int]): Unit = 
  js"(function() { ${array}.sort(); return $effekt.unit; })()"

def jsSort(list: List[Int]): List[Int] = {
  val arr = array::fromList(list)
  arr.unsafeSort()
  arr.toList
}

extern io def noopt[T](x: T): T = 
  js"${x}"

extern js"""
  function getRandomInt(min, max) {
    const minCeiled = Math.ceil(min);
    const maxFloored = Math.floor(max);
    return Math.floor(Math.random() * (maxFloored - minCeiled) + minCeiled); // The maximum is exclusive and the minimum is inclusive
  }
"""

extern llvm"""
  declare i32 @rand() 
"""

extern def randomInt(minInclusive: Int, maxExclusive: Int): Int =
  js"getRandomInt(${minInclusive}, ${maxExclusive})"
  llvm"""
    ; Entry block
    %min32 = trunc i64 ${minInclusive} to i32         ; Convert i64 to i32
    %max32 = trunc i64 ${maxExclusive} to i32         ; Convert i64 to i32
    %range = sub i32 %max32, %min32                   ; Calculate the range (M - N)
    %randVal = call i32 @rand()                       ; Get a random number
    %scaled = urem i32 %randVal, %range               ; Scale it to [0, range)
    %shifted = add i32 %scaled, %min32                ; Shift it to [N, M)
    %result64 = sext i32 %shifted to i64              ; Convert result back to i64
    ret i64 %result64                                 ; Return the result as i64
  """

// NOTE: Only JS, needs a little bit of tweaking for LLVM
def main() = mainSuite("Sorting") {
  // in order
  [10, 100, 1000].foreach { n =>
    var data = Nil()
    each(1, n + 1) { I =>
      data = Cons(i, data)
    }
    data = data.reverse

    test("Native sort: 1.." ++ show(n)) {
      noopt(data.jsSort)
      ()
    }

    test("Effekt sort: 1.." ++ show(n)) {
      noopt(data.sort)
      ()
    }
  }

  // random tiny
  [10, 100, 1000, 10000].foreach { n =>
    var data = Nil()
    each(1, n + 1) { I =>
      data = Cons(randomInt(-10, 11), data)
    }
    data = data.reverse

    test("Native sort: " ++ show(n) ++ "x [-10, 10]") {
      noopt(data.jsSort)
      ()
    }

    test("Effekt sort: " ++ show(n) ++ "x [-10, 10]") {
      noopt(data.sort)
      ()
    }  
  }

  // random large
  [10, 100, 1000, 10000].foreach { n =>
    var data = Nil()
    each(1, n + 1) { I =>
      data = Cons(randomInt(-10000000, 10000001), data)
    }
    data = data.reverse

    test("Native sort: " ++ show(n) ++ "x [-10000000, 10000000]") {
      noopt(data.jsSort)
      ()
    }

    test("Effekt sort: " ++ show(n) ++ "x [-10000000, 10000000]") {
      noopt(data.sort)
      ()
    }  
  }
}

[jiribenes]

I was bored today so I spent some time investigating on current master.

1. A Quick Fix (partition3)

Change the quick sort implementation to do a three-way partition: smaller elements, equal elements, and greater elements.
Unfortunately, this has its downsides: now we have to take actual comparators compare: (A, A) => Ordering instead of lessThan: (A, A) => Bool and it's not really quicker per se.

2. A Quick Fix with an Explicit Accumulator (partition3+acc)

Reducing the number of appends in half by using accumulators. Doesn't really seem worth it

3. Classic Mergesort (classic)

Already seems much quicker by just using a textbook mergesort in most cases, but seems to struggle on small data.
Also still doesn't solve the problem of possibly quickly running out of stack space.

4. Natural Mergesort (natural)

This is what Koka and Haskell do. In short:

1. instead of splitting completely like in Mergesort, we split into monotonic runs (either all decreasing or all increasing)
2. only then we merge, somewhat linearly (left-to-right)

I was genuinely surprised how good this performs!
Unfortunately, it's quite unpleasant to write this quickly in Effekt as all of the functions are mutually recursive and need to pass the comparator.

Measurements

Native sort is just calling JavaScript FFI. zig-zag is a bit weird, just a [3, 2, 1, 6, 5, 4]-style pattern, otherwise the tests should be pretty legible. All tests are performed with a quick noopt thingy just to prevent Effekt from optimising it too much :)

Apologies if the image is too huge, just open it in a new tab if needed.

Conclusion

We should just add natural mergesort as it performs really well in all of the scenarios that I care about. 😇