ChipSort.jl Documentation

ChipSort is a Julia module that implements SIMD and cache-aware sorting techniques.

This documentation contains:

• A description of the API and how to use the Julia functions defined in the module.
• A presentation of the theory behind ChipSort.
• Some further details from the algorithm implementations.
• A report with some benchmark results.

Installation and basic 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