Sort is incredibly slow

[blackxored]

[davidchambers]

Have you tried with type checking disabled?

> S.create({checkTypes: false, env: []}).sort([1, 4, 10, 8, 9, 10])
[1, 4, 8, 9, 10, 10]

I imagine this will make a big difference.

[CrossEye]

Note that this comparison is not accurate. R.sort is not used that way. (The fact that those numbers show it twice as fast as the native sort, which doesn't have to reallocate anything, should be a giveaway.)

---

I was going to leave it at that, but I wanted to make sure the numbers seemed more reasonable. My tests show that Sanctuary is extremely slow, even without type-checking:

const R = require('ramda');
const S = require('sanctuary');

const COUNT = 1e4

const time = (msg, fn) => {
  let arr = [1, 4, 10, 8, 9, 10]
  const now = new Date();
  for (let i = 0; i < COUNT; i++) {
    fn(arr)
  }
  console.log(`${msg}: ${(new Date() - now) / COUNT}`)
}

time('Native', arr => arr.sort())
time('Ramda', arr => R.sort((a, b) => a - b, arr))
time('Sanctuary', arr => S.sort(arr))

const S2 = S.create({checkTypes: false, env: []})
time('Sanctuary w/o type-checking', arr => S2.sort(arr))

Native: 0.0007
Ramda: 0.0009
Sanctuary: 0.5779
Sanctuary w/o type-checking: 0.1062

  - Ubuntu 17.04, 16GB, Intel Core i7-4710MQ @ 2.50GHz 

Running it with 1e5 iterations is painful; I wouldn't even try 1e6.

Of course, Ramda is not trying to sort an arbitrary foldable monoid over an arbitrary ordered type. Nor is the native version. They content themselves with plain arrays. Sanctuary does much more. But this performance is scary: a tenth of a millisecond to sort a 6-element list, half of a millisecond with type-checking turned on.

Edit:

That timing function is wrong, but the results are similar if you change it to:

const time = (msg, fn) => {
  const now = new Date();
  for (let i = 0; i < COUNT; i++) {
    fn([1, 4, 10, 8, 9, 10])
  }
  console.log(`${msg}: ${(new Date() - now) / COUNT}`)
}

(obviously, in the native case, we shouldn't be re-sorting the resulting sorted array every time.)

[davidchambers]

Thoughts on how to improve the performance of Z.sortBy would be much appreciated. @Avaq?

[Avaq]

We can definitely look into improving its performance. One thing that comes to mind is implementing an array-specialised path. Let's get benchmarks sorted first though:

• by merging Add benchmarking sanctuary-type-classes#60;
• which depends on sanctuary-benchmark Everything sanctuary-benchmark#1;
• which depends on sanctuary-scripts everything sanctuary-scripts#1.

[paldepind]

The current algorithm is O(n^2) so that's probably why it's slow. I'm guessing performance could be very drastically improved by implementing it like:

1. Convert foldable into array
2. Sort array using Array#sort with a comparison function that uses < for primitives and ord for FL Ords
3. Convert array back into foldable

If the argument to sort is already an array the last step could be skipped.

That is O(n*log(n)) and should be much faster. But, it will not be stable since Array#sort is not stable.

[paldepind]

The above could also be used to implement a stable sort. Then one would have to turn the Foldable into an array where each element is tagged with its original index. The comparison function should then break ties by using the index. That would probably make it a bit slower though.

[davidchambers]

Are you interested in submitting a pull request, Simon?

[paldepind]

I'd love to 😄 Are there benchmarks I can run to compare the performance before and after?

I've implemented the above approach for List. The implementation can be seen here.

I've created a benchmark that measures the overall performance and roughly measures the cost of doing a stable sort vs. doing an unstable sort. With stability, the algorithm is only about 50% slower than Array#sort. Stability makes the sorting about 15% slower compared to the unstable version.

I personally think doing a stable sort is worth it. The performance difference isn't that huge and a stable sorts goes well with functional programming.

To get a bit extra performance I pull off a trick: I check the first element of the list. If it is a number or a string I do an unstable sort since it's impossible to tell if two identical numbers or strings gets exchanged. I'm not sure if there's any downsides to that.

[davidchambers]

I'd love to

Wonderful!

Are there benchmarks I can run to compare the performance before and after?

https://github.com/sanctuary-js/sanctuary-type-classes/blob/master/bench/README.md

I'm sure @Avaq will be happy to answer questions if it's not clear how to run the benchmarks.