ChipSort.jl

Sorting deeds done down the chip
Author nlw0
Popularity
19 Stars
Updated Last
12 Months Ago
Started In
February 2019

ChipSort.jl

ChipSort is a sorting module containing SIMD and cache-aware techniques. It's based on a couple of academic papers from 2008. More details can be found in our documentation.

Installation and usage

Like any experimental Julia package on GitHub you can install ChipSort from the Julia REPL by first typing `]` to enter the package management prompt, and then

``````pkg> add https://github.com/nlw0/ChipSort.jl
``````

You can now try out the basic functions offered by the package such as `sort_net` to use a sorting network, or try the full array sort function prototype `chipsort`.

``````julia> using ChipSort

julia> using SIMD

julia> data = [Vec(tuple(rand(Int8, 4)...)) for _ in 1:4]
4-element Array{Vec{4,Int8},1}:
<4 x Int8>[-15, 98, 5, -28]
<4 x Int8>[47, -112, 98, -14]
<4 x Int8>[-18, -3, -111, 85]
<4 x Int8>[79, -12, -44, -85]

julia> x = sort_net(data...)
(<4 x Int8>[-18, -112, -111, -85], <4 x Int8>[-15, -12, -44, -28], <4 x Int8>[47, -3, 5, -14], <4 x Int8>[79, 98, 98, 85])

julia> y = transpose_vecs(x...)
(<4 x Int8>[-18, -15, 47, 79], <4 x Int8>[-112, -12, -3, 98], <4 x Int8>[-111, -44, 5, 98], <4 x Int8>[-85, -28, -14, 85])

julia> z = merge_vecs(y...)
<16 x Int8>[-112, -111, -85, -44, -28, -18, -15, -14, -12, -3, 5, 47, 79, 85, 98, 98]

julia> bigdata = rand(Int32, 2^20);

julia> chipsort_large(bigdata, Val(8), Val(32)) == sort(bigdata)
true
``````

Make sure you check our documentation for more information.

Latest benchmark results are: 81% speedup on a 1M Int32 array, 2x speedup on 8k Int32 and 4x on 64 values.

Used By Packages

No packages found.