Is python's builtin sort parallelized?

user_5609685 0
Viewed 285

Will python automatically parallelize sorting across all cores?

Sorting a list of objects based on an integer property, which sorts a list of size 2M in ~1.7s. My machine has 16 logical cores and 4 GPUs which I would like to leverage to speedup the sort. I found a couple parallel merge sort implementations online but none seemed popular which is surprising given the parallel hardware available today. Would these implementations be better on machines with 8-16 cores?

sorting python
2 Answers

EDIT: This method doesn't really perform very well due to the overhead of copying memory around (among other reasons) and the slowness of the built-in heapq.merge operation. I suggest just using numpy.ndarray.sort() if possible since it's surprisingly quick.

A simple method for parallelizing to n threads is to split your collection into n equal pieces, and then feed each chunk into a separate thread. Once the threads are done, collate their sorted results into one list via a stable merge operation.

from heapq import merge
from multiprocessing.pool import Pool

def sort_parallel(xs, n_workers):
    pool = Pool(n_workers)
    pos = [i * len(xs) // n_workers for i in range(n_workers + 1)]
    xss = [xs[i:j] for i, j in zip(pos[:-1], pos[1:])]
    pool.map(sort_inplace, xss)
    return list(merge(*xss))

def sort_inplace(xs):
    xs.sort()
user_3651020

Will python automatically parallelize sorting across all cores?

There is nothing in the Python Language Specification (or more precisely, the Python Standard Library Specification) that would prevent an implementor from parallelizing either list.sort() or sorted(). There is, however, also nothing in the Python Language Specification or the Python Standard Library Specification that would force an implementor to parallelize either list.sort() or sorted().

Therefore, it is completely up to each implementation whether they implement them serial, parallel, or print out the list, fax it to Malaysia, and have it hand-sorted in a sweat shop. Also, an implementation is free to change the implementation strategy at any time without warning, as long as it does not violate the invariants guaranteed by the Library Specification. (Which is basically only that the result must be sorted and that the sort must be stable.)

Or, to answer the question succinctly:

Will python automatically parallelize sorting across all cores?

You can't know.

user_29880
Related