Parallel in-place sort for numpy arrays

Question

I often need to sort large numpy arrays (few billion elements), which became a bottleneck of my code. I am looking for a way to parallelize it.

Are there any parallel implementations for the ndarray.sort() function? Numexpr module provides parallel implementation for most math operations on numpy arrays, but lacks sorting capabilities.

Maybe, it is possible to make a simple wrapper around a C++ implementation of parallel sorting, and use it through Cython?

You could take a look at Theano (deeplearning.net/software/theano/index.html). I'm not sure if its sort() function is parallel - but it is compiled and runs on a GPU. — Dietrich
– Dietrich, Commented Dec 20, 2014 at 14:59

Maxim Imakaev · Accepted Answer · 2016-02-15 17:14:01Z

10

I ended up wrapping GCC parallel sort. Here is the code:

parallelSort.pyx

# cython: wraparound = False
# cython: boundscheck = False
import numpy as np
cimport numpy as np
import cython
cimport cython 

ctypedef fused real:
    cython.char
    cython.uchar
    cython.short
    cython.ushort
    cython.int
    cython.uint
    cython.long
    cython.ulong
    cython.longlong
    cython.ulonglong
    cython.float
    cython.double

cdef extern from "<parallel/algorithm>" namespace "__gnu_parallel":
    cdef void sort[T](T first, T last) nogil 

def numpyParallelSort(real[:] a):
    "In-place parallel sort for numpy types"
    sort(&a[0], &a[a.shape[0]])

Extra compiler args: -fopenmp (compile) and -lgomp (linking)

This makefile will do it:

all:
    cython --cplus parallelSort.pyx  
    g++  -g -march=native -Ofast -fpic -c    parallelSort.cpp -o parallelSort.o -fopenmp `python-config --includes`
    g++  -g -march=native -Ofast -shared  -o parallelSort.so parallelSort.o `python-config --libs` -lgomp 

clean:
    rm -f parallelSort.cpp *.o *.so

And this shows that it works:

from parallelSort import numpyParallelSort
import numpy as np 
a = np.random.random(100000000)

numpyParallelSort(a) 
print a[:10]

edit: fixed bug noticed in the comment below

edited Feb 15, 2016 at 17:14

answered Feb 22, 2015 at 21:18

Maxim Imakaev

1,5452 gold badges15 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Nelz11 Over a year ago

Great answer, and works well (sorts 3.2 billion floats in under two minutes!!!) However, there is an interesting error. If you look at the end of the list a[-10:0] you will see that the last element of the original is not sorted. I had to change &a[a.shape[0]-1] to a[a.shape[0]] to get correct sorting.

Zach Boyd Over a year ago

To spare someone a bunch of time, it is actually important to turn off bounds checking in this example, since otherwise, it will be unhappy that you are accessing one beyond the end of the array in the call to sort.

Maxim Imakaev Over a year ago

I don't think it matters here, since the sort is done in C++ STL, not in cython. There is even no copying data in Cython, just passing pointers. However, In general, that would be important in Cython.

antho Over a year ago

I have a ImportError while trying to compile, an idea? thanks ImportError: dynamic module does not define module export function (PyInit_parallelSort)

Eelco Hoogendoorn · Accepted Answer · 2014-12-27 10:40:34Z

2

Mergesort parallelizes quite naturally. Just have each worker pre-sort an arbitrary chunk, and then run a single merge pass on it. The final merging should require only O(N) operations, and its trivial to write a function for doing so in numba or somesuch.

Wikipedia agrees

answered Dec 27, 2014 at 10:40

Eelco Hoogendoorn

10.8k1 gold badge46 silver badges43 bronze badges

1 Comment

Maxim Imakaev Over a year ago

Actually, there is a parallel implementation of stl sort, as described here: gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html

Collectives™ on Stack Overflow

Parallel in-place sort for numpy arrays

2 Answers 2

4 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related