# WIP: faster string sort

**URL:** <https://discourse.julialang.org/t/wip-faster-string-sort/7671>\
**Category:** Internals & Design\
**Tags:** strings, sort\
**Created:** [December 10, 2017, 11:54am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671 "2017-12-10T11:54:40Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![nalimilan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nalimilan/32/147_2.png) [@nalimilan](https://discourse.julialang.org/u/nalimilan)\
**Post date:** [December 18, 2017, 10:17am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/21 "2017-12-18T10:17:11Z")

</div>

Makes sense. Though they could do something clever by sorting the unique strings only once, and then sorting the full array based on that ordering. If that’s the case, the implementation will take more time when you increase the proportion of unique values.

The fact that the default `sort` is slow is a weak proof IMHO. R manages to get many things slow, and radix sort can be faster than other methods even if applied to pointers.

---

<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:** [December 18, 2017, 10:48am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/22 "2017-12-18T10:48:24Z")

</div>

Yeah it’s not a solid proof but just conjecture, and given Julia doesn’t have global pools I have to try and push the performance as far as I can. For categorical arrays I have already an algorithm that was demonstrably faster than data.table so it’s not an issue.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 18, 2017, 5:39pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/23 "2017-12-18T17:39:41Z")

</div>

One problem could be inlined (means unavoidable) checkbound in codeunit:

```julia
julia> @inbounds codeunit(svec1[1],8)
ERROR: BoundsError: attempt to access "i080648"
  at index [8]
Stacktrace:
 [1] checkbounds at ./strings/basic.jl:180 [inlined]
 [2] codeunit(::String, ::Int64) at ./strings/string.jl:74
 [3] top-level scope

```

So you probably don’t want to use `codeunit` for superfast solution!

Second problem (or solution) could be using (undocumented? unguaranteed?) internal structure of String:

```julia
julia> all(x->unsafe_load(pointer(x)+sizeof(x))==0x00, svec1)
true

```

So you don’t need to have `codeunit_check_length` if `Char` after last `Char` of `String` is equal to 0x00.

It could be true with UTF-8 too.

Although I am not sure if it is simple task to write algorithm which don’t violate unicode principles 😜 of ordering (see: [UTS #10: Unicode Collation Algorithm](http://www.unicode.org/reports/tr10/) ).

If you need just binary comparison/ordering then maybe you could try to ccall strcmp too…

---

<div class="post-metadata">

**Author:** ![nalimilan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nalimilan/32/147_2.png) [@nalimilan](https://discourse.julialang.org/u/nalimilan)\
**Post date:** [December 18, 2017, 5:50pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/24 "2017-12-18T17:50:54Z")

</div>

> [@Liso](#):
>
> One problem could be inlined (means unavoidable) checkbound in codeunit:

I think that’s just because `@inbounds` doesn’t work at the global scope (it needs inlining):

```julia
f() = @inbounds codeunit("i080648",18)
f() # No error

```

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 18, 2017, 7:57pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/25 "2017-12-18T19:57:10Z")

</div>

Thanks! 🙂 Couldn’t it fire warning?

---

<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:** [December 18, 2017, 8:39pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/26 "2017-12-18T20:39:31Z")

</div>

Using everyone’s ideas I got. In another thread I already learned about `unsafe_load.(Ptr{UInt}.(pointer.(x)))` to load 8 bytes at a time. But it doesn’t guarantee that the bytes be set to `0x00` where there isn’t a character, but I can do the below to bitshift away the redundant bytes, but the below is 3 times slower than the version without bitshift. Can the below be faster? Feels like C programming now, btw…

```julia
hhh(x) = (unsafe_load(Ptr{UInt}(pointer(x))) << (8 - sizeof(x)))*8 >> (8- sizeof(x))*8
hh(x) = hhh.(x)
@time hh(svec1) # 9 seconds

```

I only just learned about memory recently, would this unsafe method cause segfault? In that it will try to access memory that was not assigned to it? Or is segfault not even the right term?

Based on my testing below `unsafe_load` 8 bytes at a time is almost as fast as unsafe\_load. But if I add the bit shift then it’s 3x slower. But still it’s an improvement over my original check length method already.

```julia
const M=100_000_000; const K=100
srand(1)
@time svec1 = rand([string(rand(Char.(1:255), rand(1:8))...) for k in 1:M÷K], M)

# loading the 8th byte
f(x) = unsafe_load.(pointer.(x) .+ 8)
@time f(svec1) # 3 seconds

# load all 8 bytes
hh(x) = unsafe_load.(Ptr{UInt}.(pointer.(x)))
@time hh(svec1) # 3 seconds

function codeunit_check_length(a_str, n)
    if n <= length(a_str)
        return codeunit(a_str,n)
    else
        return 0x00
    end
end

g(x) = codeunit_check_length.(x, 8)
@time g(svec1) # 19 seconds

```

---

<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:** [December 18, 2017, 8:49pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/27 "2017-12-18T20:49:32Z")

</div>

Thought about another way which is to mask it with `2^sizeof(string)-1)` which is of similiar speed to bitshift

```julia
bitshift(x) = (unsafe_load(Ptr{UInt}(pointer(x))) << (8 - sizeof(x)))*8 >> (8- sizeof(x))*8
rawload(x) = unsafe_load(Ptr{UInt}(pointer(x)))
masking(x) = unsafe_load(Ptr{UInt}(pointer(x))) & UInt(2^sizeof(x)-1)
using BenchmarkTools
@benchmark bitshift("abc") # 5-6 ns
@benchmark rawload("abc") # 1.5ns
@benchmark masking("abc") # 7ns

```

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 19, 2017, 8:50am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/28 "2017-12-19T08:50:37Z")

</div>

My result for bitshift is radically better! (0.7 ; linux ; intel i5)

```julia
julia> @btime bitshift("abc") # 5-6 ns
  2.082 ns (0 allocations: 0 bytes)
0x0000000000636261

julia> @btime rawload("abc") # 1.5ns
  1.741 ns (0 allocations: 0 bytes)
0x00007f1800636261

julia> @btime masking("abc") # 7 ns
  7.394 ns (0 allocations: 0 bytes)
0x0000000000636261

```

* * *

PS. You need to change a little these functions. You get `bitshift("abc") -> 0x0000000000000000` (8 outside of appropriate parenthesis) and `masking("abc") -> 0x0000000000000001` (8 factor is missing)…

Maybe to this:

```julia
julia> bitshift(x) = (unsafe_load(Ptr{UInt}(pointer(x))) << 8(8 - sizeof(x))) >> 8(8- sizeof(x));
julia> bitshift("abc")
0x0000000000636261

julia> masking(x) = unsafe_load(Ptr{UInt}(pointer(x))) & UInt(2^8sizeof(x)-1);
julia> masking("abc")
0x0000000000636261

```

---

<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:** [December 19, 2017, 9:00am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/29 "2017-12-19T09:00:33Z")

</div>

The faster string sort is up. Thanks to all for all the ideas and tips! The new string sort, `radixsort!`, is about 2~3 times than `Base.sort!`. It’s still slower than R but I guess it’s progress

```julia
# Pkg.clone("https://github.com/xiaodaigh/FastGroupBy.jl.git")
using FastGroupBy

const M=10_000_000; const K=100
srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M)
# using FastGroupBy.radixsort! to sort strings of length 8
@time radixsort!(svec1) # 3 seconds on 10m
issorted(svec1)

srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M)
# using Base.sort! to sort strings of length 8
@time sort!(svec1) # 7 seconds on 10m

srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:16))...) for k in 1:M÷K], M)
# using FastGroupBy.radixsort! to sort strings of length 16
@time radixsort!(svec1) # 4 seconds on 10m
issorted(svec1)

srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:16))...) for k in 1:M÷K], M)
# using Base.sort! to sort strings of length 16
@time sort!(svec1) # 8 seconds

```

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 19, 2017, 9:02am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/30 "2017-12-19T09:02:41Z")

</div>

I probably have to add that better performance is independent on my changes to function! It seems to be just other enverinment (maybe julia version, maybe OS, maybe HW)

Difference seems to be huge…

---

<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:** [December 19, 2017, 9:16am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/31 "2017-12-19T09:16:25Z")

</div>

BTW sorting length 1-8 or length 1-16 string vectors of size 10 million in R takes 1.1 second and 1.29 seconds 😲

So my Julia implementation is not even close to R’s performance yet, and maybe it’s unfair because R has this global pool concept which I haven’t been able to find out much about.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 19, 2017, 9:37am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/32 "2017-12-19T09:37:04Z")

</div>

I was also trying some research about Base.sort! and strcmp ccall…

Maybe you could find some improvements there too:

```julia
julia> strcmp(a::String, b::String) = ccall(:strcmp, Int32, (Cstring, Cstring), pointer(a), pointer(b))
strcmp (generic function with 1 method)

julia> @btime sort!(svec1, lt=(x,y)->strcmp(x,y)<0, alg=QuickSort)
  2.015 s (0 allocations: 0 bytes)

```

---

<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:** [December 19, 2017, 9:55am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/33 "2017-12-19T09:55:01Z")

</div>

I have switched to VScode and I get faster timings than in Juno already.

The `strcmp` is quite good as it’s performance only degrades a little when comparing long strings where as the radixsort solution will be bounded by O(ln) where `l` is the (average?) length of the strings. For longer strings I can see `strcmp` outperforming radixsort. I tried sorting length 1-8 strings of size 100 million the radix sort took 26 seconds and `strcmp` took 56 seconds; so in generally radixsort should still be faster. Perhaps the fastest radixsort is to call into a C implementation. But it would be great to not have to resort to C, cos Julia is meant to “solve” the two language problem. Perhaps this is one area where we have to admit defeat? Or Julia will come back with a much more performant way to rearrange the elements of string vectors.

```julia
using FastGroupBy

const M=10_000_000; const K=100
srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M)
# using FastGroupBy.radixsort! to sort strings of length 8
@time radixsort!(svec1); # 1.4 seconds
issorted(svec1)

srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M)
strcmp(a::String, b::String) = ccall(:strcmp, Int32, (Cstring, Cstring), pointer(a), pointer(b))
@time sort!(svec1, lt=(x,y)->strcmp(x,y)<0, alg=QuickSort); # 2.7 seconds
issorted(svec1)

srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M)
# using Base.sort! to sort strings of length 8
@time sort!(svec1); # 4 seconds on 10m
issorted(svec1)

srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:16))...) for k in 1:M÷K], M)
# using FastGroupBy.radixsort! to sort strings of length 8
@time radixsort!(svec1); # 2.3 seconds
issorted(svec1)

srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:16))...) for k in 1:M÷K], M)
strcmp(a::String, b::String) = ccall(:strcmp, Int32, (Cstring, Cstring), pointer(a), pointer(b))
@time sort!(svec1, lt=(x,y)->strcmp(x,y)<0, alg=QuickSort); # 2.7 seconds
issorted(svec1)

srand(1)
svec1 = rand([string(rand(Char.(32:126), rand(1:16))...) for k in 1:M÷K], M)
# using Base.sort! to sort strings of length 8
@time sort!(svec1); # 4.6 seconds on 10m
issorted(svec1)

```

---

<div class="post-metadata">

**Author:** ![nalimilan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nalimilan/32/147_2.png) [@nalimilan](https://discourse.julialang.org/u/nalimilan)\
**Post date:** [December 19, 2017, 10:05am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/34 "2017-12-19T10:05:00Z")

</div>

> [@xiaodai](#):
>
> But it would be great to not have to resort to C, cos Julia is meant to “solve” the two language problem. Perhaps this is one area where we have to admit defeat? Or Julia will come back with a much more performant way to rearrange the elements of string vectors.

I think you should define the target to reach if you want to assess how fast is your implementation. R is not a good reference as long as don’t know how it works exactly, and unless you can find a C implementation to compare to, it’s hard to know whether Julia can reach the same performance or not.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [December 19, 2017, 10:35am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/35 "2017-12-19T10:35:32Z")

</div>

You don’t really want to use `strcmp`, that is pretty much a legacy function that should be avoided, that doesn’t handle `\0` bytes inside strings.  
What you really want is `memcmp`, and don’t use `Cstring` either, directly use `Ptr{UInt8}`.

---

<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:** [December 19, 2017, 10:57am UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/36 "2017-12-19T10:57:23Z")

</div>

```julia
srand(1)

# memcmp("abc","def",3)
memcmp(a::String, b::String, sz) = ccall(:memcmp, Int32, (Ptr{UInt8}, Ptr{UInt8}, Int32), pointer(a), pointer(b), sz)

M = 10_000_000; K = 100
svec1 = rand([string(rand(Char.(32:126), rand(1:8))...) for k in 1:M÷K], M)
@time sort!(svec1, lt=(x,y)->memcmp(x,y,8)<0, alg=QuickSort); # 2.7 seconds
issorted(svec1) # 2.5 seconds

```

still slower than the radixsort but looks reasonable.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 19, 2017, 1:09pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/37 "2017-12-19T13:09:26Z")

</div>

> [@ScottPJones](#):
>
> You don’t really want to use `strcmp`, that is pretty much a legacy function that should be avoided, that doesn’t handle `\0` bytes inside strings.  
> What you really want is `memcmp`, and don’t use `Cstring` either, directly use `Ptr{UInt8}`.

IMHO in contrary it stop looking at memory after 0x00 is reached. Which is fine because we don’t to have memory access violation and it seems (although I agree it is probably not guaranted) that Julia add 0x00 after end of string. Memcpy solution has to find minimum of sizeofs which is not for free.

I agree that 0x00 could not be inside string (which will be problem or example with utf-16 encoding) but in UTF-8 and much other encodings it could be acceptable I think.

Does R support strings with 0x00 inside?

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [December 19, 2017, 1:20pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/38 "2017-12-19T13:20:34Z")

</div>

radixsort seems to bee good algorithm and we probably just need to find really quick function to calculate radix.

Could you test this conjecture and use some most primitive function for benchmark your algorithm? (maybe `radix(s) = s[1]` or maybe this one too: `radix(s) = 1`)

Maybe we could try to write something in C. (I don’t agree that it is losing war with 2 language problem - maybe just a battle 🙂 )

PS. Did you think about `RadixSort` as method which could be acceptable as `alg` parameter of `sort!`?

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [December 19, 2017, 1:21pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/39 "2017-12-19T13:21:03Z")

</div>

Most modern languages do accept strings with 0x00, even C does - it’s really just a _convention_, used by C literals and the `str*` family of functions, but having the length stored is also supported with the `mem*` functions, which can be faster than the `str*` ones using SIMD instructions, and don’t have the dangerous buffer overflow issues of using `\0` termination.

> **[Null-terminated string | History](https://en.wikipedia.org/wiki/Null-terminated_string#History)**
>
> Null-terminated strings were produced by the .ASCIZ directive of the PDP-11 assembly languages and the ASCIZ directive of the MACRO-10 macro assembly language for the PDP-10. These predate the development of the C programming language, but other forms of strings were often used.
> At the time C (and the languages that it was derived from) was developed, memory was extremely limited, so using only one byte of overhead to store the length of a string was attractive. The only popular alternative at t...

Also, about why it was really a bad choice: [http://queue.acm.org/detail.cfm?id=2010365](http://queue.acm.org/detail.cfm?id=2010365)

---

<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:** [December 19, 2017, 7:36pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/40 "2017-12-19T19:36:57Z")

</div>

yeah radixsort could be an alg. It is already the case if you load `SortingAgorithms.jl` but the radixsort there doesn’t sort strings hence the work here.

[Previous page](https://discourse.julialang.org/t/wip-faster-string-sort/7671.md?page=1)

[Next page](https://discourse.julialang.org/t/wip-faster-string-sort/7671.md?page=3)