WIP: faster string sort

Internals & Design
,
45

I did a quick implementation of MSD string radixsort in C (btw most C radixsort found on google were “joke” implementations mostly) and it was slow compared to the implementation in Julia. So not very useful as a benchmark since it’s so unoptimised. I also found this lecture which contains some useful algorithms to try.

Here is how I am calling the C radixsort in Julia


cradixsort(x) = ccall(
    (:radix_sort,"libuntitled3"),
     Void, 
     (Ptr{Ptr{UInt8}},UInt),
    pointer(x), length(x)
)

const M = 100_000_000; const K = 100;
srand(1);
svec = rand(["id"*dec(k,10) for k in 1:M÷K], M);

# yy = svec[1:2_000_000];
@time cradixsort(svec) # 2.5 minutes
issorted(svec)

using FastGroupBy

@time radixsort!(svec) # 18 seconds
issorted(svec)