# Faster Sorting With GPU?

**URL:** <https://discourse.julialang.org/t/faster-sorting-with-gpu/8409>\
**Category:** New to Julia\
**Tags:** gpu, sort, arrays\
**Created:** [January 16, 2018, 5:55pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409 "2018-01-16T17:55:18Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![judsoncs](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@judsoncs](https://discourse.julialang.org/u/judsoncs)\
**Post date:** [January 16, 2018, 5:55pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/1 "2018-01-16T17:55:18Z")

</div>

I’ve written a program which needs to sort massive multi-dimensional arrays (several million rows). The problem is, as you know, QuickSort is not all that quick. I was wondering if anyone knows of a way to outsource the sort function to the GPU instead? It occurs to me that the GPU is essentially doing this nonstop with z-buffering anyways and is obviously considerably better optimized for this sort of task.

---

<div class="post-metadata">

**Author:** ![rveltz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rveltz/32/2707_2.png) [@rveltz](https://discourse.julialang.org/u/rveltz)\
**Post date:** [January 16, 2018, 7:28pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/2 "2018-01-16T19:28:09Z")

</div>

ArrayFire has one!

---

<div class="post-metadata">

**Author:** ![judsoncs](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@judsoncs](https://discourse.julialang.org/u/judsoncs)\
**Post date:** [January 16, 2018, 8:19pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/4 "2018-01-16T20:19:04Z")

</div>

Ok so it looks like AFArray is formatted a bit differently than what I’m used to. My original array was initialized like this:  
Data=Array{Any}(length(rows,columns)  
And called by:  
Data[row#,column#]  
How does the format change for AFArray?

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 16, 2018, 8:36pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/5 "2018-01-16T20:36:07Z")

</div>

> [@judsoncs](#):
>
> Data=Array{Any}(length(rows,columns)

Don’t use arrays of `Any` if you want performance. In fact, seeing this, I would recommend typing this better and just trying it on the CPU again.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 16, 2018, 8:36pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/6 "2018-01-16T20:36:34Z")

</div>

> [@judsoncs](#):
>
> Data[row#,column#]
> 
> How does the format change for AFArray?

Don’t use indexing with GPUs.

---

<div class="post-metadata">

**Author:** ![judsoncs](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@judsoncs](https://discourse.julialang.org/u/judsoncs)\
**Post date:** [January 16, 2018, 8:48pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/7 "2018-01-16T20:48:41Z")

</div>

Oh, ok. So the reason I used type Any was because I have columns in the array that contain bools. Would it be more efficient to just keep the floats in one array and the bools in another and use the sorting order from the float array to organize the bools?

---

<div class="post-metadata">

**Author:** ![simonbyrne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simonbyrne/32/19_2.png) [@simonbyrne](https://discourse.julialang.org/u/simonbyrne)\
**Post date:** [January 16, 2018, 8:50pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/8 "2018-01-16T20:50:45Z")

</div>

How many columns do you have? It may be faster to create a vector of Tuples and sort that, or use something like DataFrames.jl or JuliaDB.jl.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 16, 2018, 8:53pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/9 "2018-01-16T20:53:54Z")

</div>

perhaps you can post a small example of your data? I am working on sorting algorithms so I may have some ideas.

Do you need to sort on multikeys keys or just one key?

---

<div class="post-metadata">

**Author:** ![judsoncs](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@judsoncs](https://discourse.julialang.org/u/judsoncs)\
**Post date:** [January 16, 2018, 9:08pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/10 "2018-01-16T21:08:39Z")

</div>

It’s a pretty simple setup, just a massive data set. I have 8 columns (plus 1 column of bools which I’ve cut off for the performance reasons mentioned) and anywhere from 1 million to 12 million rows. I’m using the sortrows function and I’m organizing the data first according to the 2nd column, then the 3rd, then the 1st.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [January 16, 2018, 10:07pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/11 "2018-01-16T22:07:50Z")

</div>

Could you post explicit code that generates something like your data (e.g. using rand for data generation), and explicit code that you think is too slow?

Have you thought about whether Float32 is enough? Also, are you sure you don’t want to transpose your data? In Julia, accessing an entire column is fast, and accessing an entire row is slow. Hence sortrows should be avoided if possible.

However, compared to the use of Any, none of this matters.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 16, 2018, 11:17pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/12 "2018-01-16T23:17:02Z")

</div>

what are the 8 columns? are they integers, floats? and how many distinct values are in each of the columns? Can we assume anything about the distributions of numbers in these columns? Or we don’t know, can we assume that they are completely random and span the whole range?

The reason why I ask is, say one of the columns can only contains values from 1 to 1000 then there are faster algorithms than quicksort (e.g. counting sort).

---

<div class="post-metadata">

**Author:** ![judsoncs](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@judsoncs](https://discourse.julialang.org/u/judsoncs)\
**Post date:** [January 17, 2018, 12:33am UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/13 "2018-01-17T00:33:22Z")

</div>

They are all floats and nothing’s absolute but it would be reasonable to assume that they all fall between -100 and 100.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 17, 2018, 12:41am UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/14 "2018-01-17T00:41:07Z")

</div>

for floats between -100 and 100 isn’t as useful as integer. Therefore you can use float16 to store the values?

---

<div class="post-metadata">

**Author:** ![judsoncs](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@judsoncs](https://discourse.julialang.org/u/judsoncs)\
**Post date:** [January 17, 2018, 12:59am UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/15 "2018-01-17T00:59:48Z")

</div>

I’ll look into it.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 17, 2018, 1:05am UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/16 "2018-01-17T01:05:43Z")

</div>

12 million rows isn’t that big nowadays. what would be ur definition of fast? sub 1 second or sub 10 second sort?

---

<div class="post-metadata">

**Author:** ![judsoncs](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@judsoncs](https://discourse.julialang.org/u/judsoncs)\
**Post date:** [January 17, 2018, 1:38am UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/17 "2018-01-17T01:38:23Z")

</div>

Preferably sub 1 second-I may have to repeat the sort function hundreds of thousands of times.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 17, 2018, 1:44am UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/18 "2018-01-17T01:44:10Z")

</div>

Have you tested the timing with it being strictly typed yet?

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 17, 2018, 11:21am UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/20 "2018-01-17T11:21:48Z")

</div>

Can you post your code for how you use `sortrows`?

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [January 17, 2018, 1:30pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/21 "2018-01-17T13:30:00Z")

</div>

After taking a short look into sort.jl, the code for sortrows and sortcols appears to simply suck (so don’t use it if you care for performance).

Consider the following quick and dirty code, which should do the same:

```julia
using StaticArrays

function Base.isless(a::SVector, b::SVector)
#may segfault on bad input; too lazy to do right now
       @inbounds for i in 1:length(a)
       a[i] < b[i] && return true
       a[i] > b[i] && return false
       end
       return false
       end

A= rand(SVector{8,Float32},10_000_000);
A2 = rand(Float32, 8, 10_000_000);

#post warm-up
@time sortcols(A2);
 26.563095 seconds (10.12 M allocations: 921.714 MiB, 3.65% gc time)
@time sort(A; alg=QuickSort);
  3.976193 seconds (13 allocations: 305.176 MiB, 1.73% gc time)
@time sort(A; alg=MergeSort);
  5.784950 seconds (15 allocations: 457.764 MiB, 0.07% gc time)

```

edit: On julia 0.62, might be better on 0.7.

---

<div class="post-metadata">

**Author:** ![sdanisch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sdanisch/32/1406_2.png) [@sdanisch](https://discourse.julialang.org/u/sdanisch)\
**Post date:** [January 17, 2018, 1:51pm UTC](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409/22 "2018-01-17T13:51:50Z")

</div>

you could also do:

```nohighlight
julia> A2 = rand(Float32, 8, 10_000_000)
julia> Atup = reinterpret(NTuple{8, Float32}, A2, (size(A2, 2),));

julia>sort(Atup; alg=QuickSort)# compile

julia> @time sort(Atup; alg=QuickSort);
  2.695609 seconds (13 allocations: 305.176 MiB, 1.50% gc time)

```

[Next page](https://discourse.julialang.org/t/faster-sorting-with-gpu/8409.md?page=2)