# 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:** 1
**Showing post:** 65

<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 9, 2018, 2:03pm UTC](https://discourse.julialang.org/t/wip-faster-string-sort/7671/65 "2018-01-09T14:03:59Z")

</div>

Before going to sleep I tried these two ideas, expecting nothing but…

**String sorting performance vs R is only marginally (within 1.x-1.3x) slower now!** In my benchmarks sorting 10m records where 100k of them are distinct yields 1.31secs (Julia) vs 1.1secs (R) (for 100m it’s around 25-27 seconds vs 18 -21 seconds).

![sort_perf_10m100_u](https://global.discourse-cdn.com/julialang/original/3X/4/0/4050e47b3f72d499726b7e6fe6c36aa5187da95d.png)

I made these 3 changes

1. Use my own sort function instead of `Base.sort` which is hard to overload as `Base.sort` doesn’t dispatch on `alg`, or more generally on named arguments. Some how `Base.sort(svec, alg = StringRadixSort)` is running some code which probably wasn’t all that necessary.
2. Change the `SortingAlgorithms.RADIXSIZE` to 16 from 11. This means sort 16 bits in one go instead of 11 bits. After getting comfortable with radixsort, I was curious why `SortingAlgorithms.jl` chose 11 as the `RADIXSIZE`, the most common types are probably multiples of 16 bits, e.g. UInt32 is 32 bits and UInt64 is 64 bits. Sorting 11 bits in one go, we need 3 passes over the data to sort 32 bit type and 6 passes over the data for a 64 bit type vs 2 and 4 passes if we just choose a `RADIXSIZE` of 16 bits. From benchmarking, increasing the `RADIXSIZE` results in faster sorting too.
3. Do not load underlying bits into `UInt128` and instead use `UInt64` as the maximum. I found that it’s quicker to sort twice using `UInt64` instead of sorting once `UInt128`. When I said sort “once” the data has been gone through 4 times when sorting the underlying bytes as 64bit; so really the number of passes over the data is the same whether you use `UInt128` or `UInt64` but it seems Julia can handle 64bit data better which makes sense given that I am running on a 64bit machine.

---

_[View the full topic](https://discourse.julialang.org/t/wip-faster-string-sort/7671)._