22

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

4
  • @goldilocks Yes it is, look at the user vs real time.
    – augurar
    Nov 24, 2014 at 19:01
  • Huh -- you're right. Apparently it was parallelized in coreutils 8.6.
    – goldilocks
    Nov 24, 2014 at 19:03
  • Can you use --buffer-size to specify that sort use all available physical memory and see if that helps?
    – iruvar
    Nov 24, 2014 at 19:46
  • @1_CR Tried it with 1 GB buffer, no significant change in timing. It only used about .6 GB of that, so increasing the buffer size further wouldn't help.
    – augurar
    Nov 24, 2014 at 20:08

3 Answers 3

25

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.

5
  • And how do they compare for UTF-8 strings? Nov 24, 2014 at 22:07
  • @Gilles Modifying the Python script to use locale.strxfrm to sort, the script took ~32 seconds, still faster than sort but much less so.
    – augurar
    Nov 24, 2014 at 22:16
  • 3
    Python 2.7.3 is doing byte comparison, but Python3 would be doing unicode word comparison. Python3.3 is about twice as slow Python2.7 for this "test". The overhead of packing the raw bytes into Unicode representation is even higher than the already significant packing objects that Python 2.7.3 has to do.
    – Anthon
    Nov 24, 2014 at 22:16
  • 2
    I found the same slow-down with cut, and others too. On several machines I now have export LC_ALL=C in .bashrc. But beware: this essentially breaks wc (except wc -l), just to name an example. "Bad bytes" are not counted at all... Nov 27, 2014 at 22:23
  • 2
    This performance problem also occurs with grep: you can get a substantial performance improvement when grepping huge files by disabling UTF-8, especially when doing grep -i Nov 28, 2014 at 9:15
9

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.

2
  • Good point that both implementations are written in C. I'm sure if I implemented a sorting algorithm in Python it would be much, much slower.
    – augurar
    Nov 24, 2014 at 20:09
  • By the way, the file consists of randomly generated float values between 0 and 1, so there shouldn't be too much structure to exploit.
    – augurar
    Nov 24, 2014 at 20:11
8

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 numbers1.


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

1Someone 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.

4
  • 5
    Python sort has an additional speed advantage, based on your last sample: ASCII numerical order. sort seems to be doing a bit of extra work for uppercase/lowercase comparisons.
    – Izkata
    Nov 24, 2014 at 21:16
  • @Izkata That's it! See my answer below.
    – augurar
    Nov 24, 2014 at 21:56
  • 1
    Actually python has quite a bit of overhead creating its internal strings out of the raw stdin input. Converting those to numbers (lines = map(int, list(stdin))) and back (stdout.writelines(map(str,lines))) makes the whole sorting go slower, up from 0.234s real to 0.720s on my machine.
    – Anthon
    Nov 24, 2014 at 22:07
  • Nice analysis. At the end of the day I'll take either Python list.sort() or coreutil's sort over bubble sorting a string array using bash (yuk!) Jul 21, 2020 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.