Why is coreutils sort slower than Python?

Question

I wrote the following script to test the speed of Python's sort functionality:

from sys import stdin, stdout
lines = list(stdin)
lines.sort()
stdout.writelines(lines)

I then compared this to the coreutils sort command on a file containing 10 million lines:

$ time python sort.py <numbers.txt >s1.txt
real    0m16.707s
user    0m16.288s
sys     0m0.420s

$ time sort <numbers.txt >s2.txt 
real    0m45.141s
user    2m28.304s
sys     0m0.380s

The built-in command used all four CPUs (Python only used one) but took about 3 times as long to run! What gives?

I am using Ubuntu 12.04.5 (32-bit), Python 2.7.3, and sort 8.13

Answer 1

Izkata's comment revealed the answer: locale-specific comparisons. The sort command uses the locale indicated by the environment, whereas Python defaults to a byte order comparison. Comparing UTF-8 strings is harder than comparing byte strings.

$ time (LC_ALL=C sort <numbers.txt >s2.txt)
real    0m5.485s
user    0m14.028s
sys     0m0.404s

How about that.

Answer 2

Both of the implementations are in C, so a level playing field there. Coreutils sort apparently uses the mergesort algorithm. Mergesort does a fixed number of comparisons which increases logarithmically to the input size, i.e. big O(n log n).

Python's sort uses a unique hybrid merge/insertion sort, timsort, which will do a variable number of comparisons with a best case scenario of O(n) -- presumably, on an already sorted list -- but is generally logarithmic (logically, you can't get better than logarithmic for the general case when sorting).

Given two different logarithmic sorts, one could have an advantage over the other on some particular data set. A traditional merge sort does not vary, so it will perform the same regardless of the data, but e.g., quicksort (also logarithmic), which does vary, will perform better on some data but worse on others.

A factor of three (or more than 3, since sort is parallelized) is quite a bit though, which makes me wonder if there isn't some contingency here, such as sort swapping to disk (the -T option would seem to imply it does). However, your low sys vs. user time implies this isn't the issue.

Answer 3

This is more of an extra analysis than an actual answer but it does seem to vary depending on the data being sorted. First, a base reading:

$ printf "%s\n" {1..1000000} > numbers.txt

$ time python sort.py <numbers.txt >s1.txt
real    0m0.521s
user    0m0.216s
sys     0m0.100s

$ time sort <numbers.txt >s2.txt
real    0m3.708s
user    0m4.908s
sys     0m0.156s

OK, python is much faster. However, you can make coreutils sort faster by telling it to sort numerically:

$ time sort <numbers.txt >s2.txt 
real    0m3.743s
user    0m4.964s
sys     0m0.148s

$ time sort -n <numbers.txt >s2.txt 
real    0m0.733s
user    0m0.836s
sys     0m0.100s

That's much faster but python still wins by a wide margin. Now, let's try again but with a non-sorted list of 1M numbers:

$ sort -R numbers.txt > randomized.txt

$ time sort -n <randomized.txt >s2.txt 
real    0m1.493s
user    0m1.920s
sys     0m0.116s

$ time python sort.py <randomized.txt >s1.txt
real    0m2.652s
user    0m1.988s
sys     0m0.064s

The coreutils sort -n is faster for unsorted numerical data (though you might be able to tweak the python sort's cmp parameter to make it faster). Coreutils sort is still significantly slower without the -n flag. So, what about random characters, not pure numbers?

$ tr -dc 'A-Za-z0-9' </dev/urandom | head -c1000000 | 
    sed 's/./&\n/g' > random.txt

$ time sort  <random.txt >s2.txt 
real    0m2.487s
user    0m3.480s
sys     0m0.128s

$ time python sort.py  <random.txt >s2.txt 
real    0m1.314s
user    0m0.744s
sys     0m0.068s

Python still beats coreutils but by a much smaller margin than what you show in your question. Surprisingly, it is still faster when looking at pure alphabetical data:

$ tr -dc 'A-Za-z' </dev/urandom | head -c1000000 |
    sed 's/./&\n/g' > letters.txt

$ time sort   <letters.txt >s2.txt 
real    0m2.561s
user    0m3.684s
sys     0m0.100s

$ time python sort.py <letters.txt >s1.txt
real    0m1.297s
user    0m0.744s
sys     0m0.064s

It is also important to note that the two don't produce the same sorted output:

$ echo -e "A\nB\na\nb\n-" | sort -n
-
a
A
b
B

$ echo -e "A\nB\na\nb\n-" | python sort.py 
-
A
B
a
b

Oddly enough, the --buffer-size option didn't seem to make much (or any) difference in my tests. In conclusion, presumably because of the different algorithms mentioned in goldilock's answer, python sort seems to be faster in most cases but numerical GNU sort beats it on unsorted numbers¹.

---

The OP has probably found the root cause but for the sake of completeness, here's a final comparison:

$ time LC_ALL=C sort   <letters.txt >s2.txt 
real    0m0.280s
user    0m0.512s
sys     0m0.084s


$ time LC_ALL=C python sort.py   <letters.txt >s2.txt 
real    0m0.493s
user    0m0.448s
sys     0m0.044s

---

¹_{Someone with more python-fu than I should try to test tweaking list.sort() to see of the same speed can be achieved by specifying the sorting method.}