Scala List sort vs Python list sort. Execution time comparison

Scala List sort vs Python list sort. Execution time comparison.

I'm learning Scala right now.
I was interested to compare Scala's List sort with Python's list sort.
To my surprise, sorting a list of 1_000_000 integers works 5 times faster in Python than in Scala.
As far as I know, Scala is faster than python.
Who can explain the reason for such a large advantage of Python over Scala?

Scala code:

import scala.util.Random

@main
def Main(args: String*): Unit =
  def cmillis = System.currentTimeMillis()
  val n = 1_000_000

  val xs = List.fill(n)(Random.nextInt(n))

  var currentMillis = cmillis
  xs.sorted
  println("Sorted in " + (cmillis - currentMillis) + "ms")

Python code:

from time import time
from random import randint

n = 1_000_000

xs = [randint(0, n) for _ in range(n)]

start = time()
sorted(xs)
print(f"Sorted in {(time() - start)* 1000} ms")

Python is the fastest language on Earth, if you call C code.

Jokes aside, the difference here can be explained by the fact that you are using List in Scala, which is a singly-linked list. While it's a very simple data structure, it has poor locality (the nodes of the list can be anywhere on the heap, leading to frequent cache misses) and more importantly its structure makes operations requiring indexing (including sorting) quite inefficient.

You can see a comparison of data structure in the Scala standard library here.

To make a fair comparison, you should select data structures that have a similar backing structure and use a sorting approach that is also comparable. If Python lists are backed by mutable arrays, comparing with immutable linked lists will always have mutable arrays win. If that's the case, you can use ArraySeq in Scala, and instead of sorted (which creates a new structure) you can use sortInPlace.

A couple more notes on your benchmark:

• System.currentTimeMillis() shouldn't be used because it's not guaranteed to be monotonic, for benchmarks System.nanoTime() makes sure you are measuring elapsed time
• You should run a benchmark many times to make sure you have some statistically relevant result. On the JVM you can use JMH to perform microbenchmarks that take this in consideration and also allows you to make a few runs to "warm up" the JVM (which can dynamically compile hot spots in your bytecode to native code for faster execution). I'm not sure about similar tools in the Python ecosystem, but I'm sure there's one.

Note that depending on the specific implementation of sorted in Python, you might still see it outperforming Scala (going back to my initial joke, if it calls C code, it's hard to beat it). I would generally expect Scala to have an advantage over Python code in terms of execution time, but this of course depends on what you are testing.

EDIT 1

A commenter correctly pointed out that a 5x factor seems too fast if indeed sorting on Seqs is done with a naive approach using indexing. I looked into the code and Seqs (including Lists) seem to perform the sorting by copying themselves into an Array and sorting that (code), which would explain why this is slow but not as slow as naively sorting an immutable linked list by indexing and swapping.

EDIT 2

Just out of pure curiosity, I tried to run the naive benchmark locally. Your Scala code ran in ~650ms on my laptop and the Python code took ~250ms. Just changing the List into an ArraySeq and sorted into sortInPlace makes the Scala version run in ~200ms. While this is not statistically relevant, it's an indication that those changes seem to have the expected impact. You might want to perform further benchmarks using a more scientific approach to get better results.