# Progress towards faster \`sortperm\` for Strings

**URL:** <https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505>\
**Category:** Data\
**Tags:** performance, sortperm\
**Created:** [January 21, 2018, 2:04pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505 "2018-01-21T14:04:42Z")\
**Posts on this page:** 17\
**Page:** 1

<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 21, 2018, 2:04pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/1 "2018-01-21T14:04:42Z")

</div>

I have just implemented an idea I had to make `sortperm` faster for Strings. It is implemented in `SortingLab.jl`’s `fsortperm`; and I got the performance on a particular benchmark to be 7x faster than `Base.sortperm`, see [code here](https://gist.github.com/xiaodaigh/376f4be78aaeecdc0bcb501629814262)

 ![sortperm_perf](https://global.discourse-cdn.com/julialang/original/3X/8/b/8b1062cf4d1927d32e49c891e21c5efb93fe9691.png)

Here is a **rough sketch** of how it works

1. For each value in a string vector, load the last 4 bytes of the string into x::`UInt64` where the last 32 bits are all 0 and only the first 32 bits are populated with 4 bytes of the string
2. Populate the last 32 bits of `x` with the string’s position in the array
3. use a modified LSD radix sort that only sorts on the first 32 bits; but note that the position of the string is also being permuted at the same time
4. Obtain the last 4 bytes of each of the elements in the sorted `x`’s and store them in `ss`; note that `ss` is the original index position permuted
5. Create a view of the string vector permuted by `ss`, i.e `@view(orig_string_vector[ss])`
6. repeat from step 1, but instead of loading the last 4 bytes from the string vector, load the next 4 bytes (counting in reverse) in the string vector view from step 5, and populate the last 32 bits of each `x` with the corresponding `ss` values; this is the iterative sorting step in LSD radixsort

Basically, I found that it’s less expensive to pack 4 bytes of a string and its array position into one 64 bit value and sort that instead of sorting the strings and keeping another vector of permuted indexes (as in [this SortingAlgorithms’s unmerged PR](https://github.com/JuliaCollections/SortingAlgorithms.jl/pull/27)).

However, R’s string performance is another total beast due to data.table’s optimization ideas and clever user of the global cache and string interning. But Julia’s getting closer even without string interning.

Slow sorting performance in Julia has been [documented before](https://github.com/JuliaLang/julia/issues/939). But I feel that my approach is too low-level to be a long term solution, but it’s a worthy experiment.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 21, 2018, 2:38pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/2 "2018-01-21T14:38:50Z")

</div>

String interning only makes sense if there’s repeated values though, right? So this chart is missing a crucial detail that you’re sampling in a way that has each string repeated about 100 times, but the 7x and chart don’t make reference to the case it’s in. But that’s kind of misleading since it’s not about a `7x`, it’s about whether this particular way of optimizing makes sense in most cases, and what case that is.

The better question is, how does this performance difference very and the change of repeats is changed? I would assume from these details that your Julia implementation does better when everything is unique, and somewhere between 0 and 100 there’s a cutoff where it begins to make sense to intern. That would be a nice line chart, change of uniqueness vs relative performance against R. If the cutoff is like 50, then maybe it’s something that only makes sense to assume is better on certain data applications (which R was designed for, while Julia was not necessarily designed to be just for data), requiring an alternative method for this specific application. On the other hand, if the cutoff is low enough then maybe it’s a good thing to always do by default? Just spitballing but you see where I am heading.

Also:

> [@xiaodai](#):
>
> However, R’s string performance is another total beast due to data.table’s optimization ideas and clever user of the global cache and string interning.

Is that thread-safe?

---

<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:** [January 21, 2018, 2:49pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/3 "2018-01-21T14:49:25Z")

</div>

Also string interning incurs a cost when creating strings which may or may not be worth it depending on the number of times you perform grouping/sorting on the data. To take this into account one would need to include the time needed to create strings from raw bytes, or to read a text file.

In [the previous thread](https://discourse.julialang.org/t/wip-faster-string-sort/7671/65) you showed a graph where Julia was as fast as R. What’s the difference with the new graph? Is it just `sort` vs. `sortperm`?

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [January 21, 2018, 3:51pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/4 "2018-01-21T15:51:39Z")

</div>

At some point I played around with a hybrid representation where strings up to 15 bytes were stored inline with one byte of length in such a way that they integer sort in correct string sort order (store the length in the low byte, pad string data with zeros) and as a pointer to string data otherwise. This not only means that short strings can fit in a single register but also that when comparing two short strings the compare is just an integer comparison. This _flew_ for sorting and basically eliminates any advantage of interning (since interning still requires a pointer to the interned string, which is strictly more storage _and_ more indirection). The problem was that making garbage collection work with this representation was beyond our ability at the time. We may be able to explore such an approach in the future again, however.

---

<div class="post-metadata">

**Author:** ![Keno](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/keno/32/285_2.png) [@Keno](https://discourse.julialang.org/u/Keno)\
**Post date:** [January 21, 2018, 7:21pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/5 "2018-01-21T19:21:42Z")

</div>

> [@StefanKarpinski](#):
>
> The problem was that making garbage collection work with this representation was beyond our ability at the time. We may be able to explore such an approach in the future again, however.

I don’t think that would be much of a problem now anymore. We’ve significantly cleaned up the the way the GC stuff works on the codegen side and the union work has led to some better factoring of abstractions. Would be good to try again once 0.7 is out the door.

---

<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 21, 2018, 8:50pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/6 "2018-01-21T20:50:12Z")

</div>

> [@ChrisRackauckas](#):
>
> The better question is, how does this performance difference very and the change of repeats is changed

That’s a great insight actually and in my previous posts I have been careful to mention those but just slip my mind this time. But there’s a reason and that is I have to come realise that datasets with repeated strings is the majority case; from my banking example the most common string columns that i need to sort are always the Customer ID or the Account ID which always has repeats. But I will detail the non repeat case for a comparison later. The other key case is skewwd distribution with repeats; think retailer, some 20% of cusomters are responsible for 80% of purchases, so in the transactions table there is a skewed distribution of IDs

---

<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 21, 2018, 8:55pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/7 "2018-01-21T20:55:26Z")

</div>

> [@nalimilan](#):
>
> To take this into account one would need to include the time needed to create strings from raw bytes, or to read a text file

I have to think about how to measure this; I can’t think of a perfect way. I have seen that Julia can generate the test data 3x faster than R. But generating synthetic data is not exactly a real life use case.

> [@nalimilan](#):
>
> What’s the difference with the new graph? Is it just sort vs. sortperm?

Yes. For `sort` Julia is still 20%-30% slower than R from my testing. The `sort` chart was from 10m length vector with 100k unique values

---

<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 21, 2018, 8:58pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/8 "2018-01-21T20:58:33Z")

</div>

> [@ChrisRackauckas](#):
>
> I would assume from these details that your Julia implementation does better when everything is unique, and somewhere between 0 and 100 there’s a cutoff where it begins to make sense to intern. That would be a nice line chart, change of uniqueness vs relative performance against R

This will be a great piece of analysis! I will look into it.

> [@ChrisRackauckas](#):
>
> that thread-safe?

Another great question. Interested to find out…

---

<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 21, 2018, 9:19pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/9 "2018-01-21T21:19:11Z")

</div>

> [@Keno](#):
>
> Would be good to try again once 0.7 is out the door.

That would be awesome!

I am writing an R package that can manipulate large amount of data on disk. I really wanted to do it in Julia (design is a different to JuliaDB.jl so can’t just use that), but I choose R mainly because data.table is so much faster on grouping/sorting/reading in data etc. Hopefully, DataFrames and JuliaDB can catch up soon! Of course string sorting/grouping is key.

Btw I think that Julia’s string hashing can also be faster.

---

<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:** [January 22, 2018, 2:52am UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/10 "2018-01-22T02:52:20Z")

</div>

> [@xiaodai](#):
>
> Btw I think that Julia’s string hashing can also be faster.

You could also use `Base.crc32c` instead of `hash` for a string hash table, it’s almost twice as fast, and unless you have a huge hash table, will probably give as good results as `hash` for spreading things out.

---

<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 22, 2018, 12:46pm UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/11 "2018-01-22T12:46:29Z")

</div>

Thanks to @ChrisRackauckas’s great suggestion, the best known Julia implementation for string sort actually beats R when the ratio of unique values to vector length is greater than 3:10 in this particular setup-10m id strings with common prefix with variouz number of unique strings

As can be seen Julia’s radix sort outperforms R’s when the number of unique values is large. For this particular case I have 10m-length vector and the cross over point is at 3m unique values.

It is also true that R takes significantly longer to generate the synthetic data, possibly due to the building of global cache for string interning; or it could just be naturally slower, but it’s hard to separate out the two effects.

 ![string_sort_vs_r_10m](https://global.discourse-cdn.com/julialang/original/3X/5/5/55e6fbcad9ed5bd4668a49022fa592134db3c7ad.png)

---

<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 28, 2018, 2:32am UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/12 "2018-01-28T02:32:20Z")

</div>

A faster `sortperm` for strings has been published as part of `SortingLab.jl`. The function is `fsortperm`

 ![sortperm_vs_fsorperm_1m](https://global.discourse-cdn.com/julialang/original/3X/f/0/f068c2f969f9bb617291c196a1965e72a7fcec44.png)

**example code below**

```julia
Pkg.add("SortingLab") # run once
sv = [randstring(8) for i=1:Int(1e6)];
svs = radixsort(sv) # faster than sort
svsp = fsortperm(sv) .|> Int # faster than sortperm
issorted(sv[svsp])

```

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 28, 2018, 2:59am UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/13 "2018-01-28T02:59:37Z")

</div>

Nice work. One thing I want to move other here is our Twitter conversation. I noted that small numbers of unique values is something that would show up a lot in general computing, like sorting filenames in a folder of a webserver, while lots of repeats are found in datasets. You suggested that DataFrames.jl or other data readers could use interned strings so that way the performance is specialized to both domains. I think that’s a really great idea and would be a great use of Julia’s type system since most/all algorithms should work no matter what string type is internally used, and that context switch is a great way to get performance. I would be interested in seeing that investigated in more depth.

---

<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:** [January 28, 2018, 9:48am UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/14 "2018-01-28T09:48:32Z")

</div>

> [@ChrisRackauckas](#):
>
> You suggested that DataFrames.jl or other data readers could use interned strings so that way the performance is specialized to both domains. I think that’s a really great idea and would be a great use of Julia’s type system since most/all algorithms should work no matter what string type is internally used, and that context switch is a great way to get performance. I would be interested in seeing that investigated in more depth.

We kind of do this already since CSV.jl creates `CategoricalArray` vectors for columns with a small proportion of unique values. I think it makes sense to use `CategoricalArray`/`PooledArray` to represent values with lots of duplicates, and arrays of strings for “real” strings which are almost all different from one another.

---

<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 28, 2018, 9:58am UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/15 "2018-01-28T09:58:09Z")

</div>

yep. R mostly don’t bother with storing strings as factors much anymore probably due to string interning. it would be good to have finer control over these type of things.

---

<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 28, 2018, 11:23am UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/16 "2018-01-28T11:23:32Z")

</div>

> [@StefanKarpinski](#):
>
> a hybrid representation where strings up to 15 bytes were stored inline with one byte of length

I have implemented the short string representation at [ShortStrings.jl](https://github.com/xiaodaigh/ShortStrings.jl), and yes it’s blazing fast! I hope that it will make it to Base soon, or at least DataFrames.jl should take note and implement this. It will lead to much faster sorting and group-by operations.

On a side note, I found that being able to define my own types in Julia that is also fast to be such an awesome feature! Definitely a selling point for Julia.

 ![readme_string_sort](https://global.discourse-cdn.com/julialang/original/3X/2/3/23c86fb761c50a5cc2966e0255a2673a83d9ec04.png)

---

<div class="post-metadata">

**Author:** ![jameson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jameson/32/23_2.png) [@jameson](https://discourse.julialang.org/u/jameson)\
**Post date:** [January 29, 2018, 4:45am UTC](https://discourse.julialang.org/t/progress-towards-faster-sortperm-for-strings/8505/17 "2018-01-29T04:45:39Z")

</div>

> [@Keno](#):
>
> I don’t think that would be much of a problem now anymore

Seems like this could be a pretty massive headache when trying to enable stack allocation / inline allocation of reference objects. It’s still probably worth investigating in the future though, just not sure about priority.

Also, now that we store string bytes inline always, doesn’t that get us pretty far towards making this like a fat-pointer (and we just need to get aforementioned stack-allocation)?