# Sorting seems to have some low hanging speed fruit for sorting by single column
**URL:** https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568
**Category:** Data
**Tags:** performance, sort, dataframes
**Created:** [December 6, 2017, 1:18pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568 "2017-12-06T13:18:24Z")
**Posts on this page:** 8
**Page:** 1
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 6, 2017, 1:18pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568/1 "2017-12-06T13:18:24Z")
I was doing some benchmarking of data.table vs DataFrames.jl. Of course, `data.table` is still way faster on sorting. But I found a low hanging fruit for sorting performance; it could be the backbone of a PR. Here is an MWE: basically I found that if there is only one column in the `cols` argument of `sort`, then I can simply do a `sortperm` on the one column vector and then apply to the rest of the Dataframe for a 4x speed up; this is implemented in `fsort`. Btw, this is still 10x slower than `data.table` so there must be other efficiencies we can find.
```julia
using DataFrames
const N = Int(1e8)
testdf = DataFrame(large_n_grps = rand(1:Int32(N/100), N), small_n_grps = rand(1:100, N), v1 = rand(1:5, N))
function fsort(df::DataFrame, cols)
x = df[cols]
df[sortperm(x),:]
end
@time fsort(testdf, :small_n_grps) #10.5 seconds
@time sort(testdf, cols = [:small_n_grps]) # 40.4 seconds
```
---
### Author:  [@nalimilan](https://discourse.julialang.org/u/nalimilan)
#### Post date: [December 6, 2017, 1:53pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568/2 "2017-12-06T13:53:33Z")
Thanks for continuing your investigations. However, I’m not sure it’s a good idea to improve speed for special cases, especially since you note that the improvement is still not enough to get close to data.table. I’d rather try to improve the general algorithm.
Indeed it’s not clear to me why an algorithm accepting multiple columns should be slower when passed a single column than your specialized algorithm. The overhead due to looping over the sorting columns (in this case, a single column) should be negligible. There may be low-hanging fruits in the general algorithm too.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 6, 2017, 1:54pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568/3 "2017-12-06T13:54:55Z")
Maybe that’s my christmas project if no one beats me to it.
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [December 6, 2017, 3:05pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568/4 "2017-12-06T15:05:24Z")
`@time sort(testdf, cols = :small_n_grps)`
instead of
> @time sort(testdf, cols = [:small\_n\_grps]) # 40.4 seconds
recovers some performance on my machine.
---
### Author:  [@piever](https://discourse.julialang.org/u/piever)
#### Post date: [December 6, 2017, 3:42pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568/5 "2017-12-06T15:42:41Z")
Not sure if it is related, but DataFrames `sort!` uses `Base.permute!!` (which is `permute!` minus a copy) and when looking for it I get the following:
```julia
help?> permute!
search: permute! ipermute! permutedims! permute permutedims PermutedDimsArray
permute!(v, p)
Permute vector v in-place, according to permutation p. No checking is done
to verify that p is a permutation.
To return a new permutation, use v[p]. Note that this is generally faster
than permute!(v,p) for large vectors.
```
Instead IndexedTables does something similar but instead of `permute!(v, p)` they use:
```julia
copy!(v, v[p])
```
I don’t know if this is the cause of the performance difference but maybe it’s a relevant thing to keep in mind.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 6, 2017, 8:06pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568/6 "2017-12-06T20:06:44Z")
The documenter on indexedtable is a bit sparse atm. Will look into it once
its more stable.
---
### Author:  [@piever](https://discourse.julialang.org/u/piever)
#### Post date: [December 6, 2017, 8:44pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568/7 "2017-12-06T20:44:08Z")
I’ve tested the implementation in [this PR](https://github.com/JuliaComputing/IndexedTables.jl/pull/104/files) in IndexedTables: it is more or less as fast as yours in this specific case and it indeed does very similar things. The surprising part is that most of the time is actually spent in:
`df[p, :]`
That is to say, getting the rearreanged version of the vectors. I really don’t understand how data.table could speed that up so much. I would expect that `v[p]` with `v` a vector and `p` a vector of integers is reasonably fast in Julia. Do you know what data.table’s algorithm does differently?
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [December 6, 2017, 10:21pm UTC](https://discourse.julialang.org/t/sorting-seems-to-have-some-low-hanging-speed-fruit-for-sorting-by-single-column/7568/8 "2017-12-06T22:21:31Z")
Perhaps it’s `df[p,:]` that’s inefficient? R’s `data.table` is formidably optimised in many cases I find but I am not sure exactly what’s going.
I tried to do the group by `:large_n_grps` and data.table advantage is now only 2x.
```julia
using DataFrames
const N = Int(1e8)
testdf = DataFrame(large_n_grps = rand(1:Int32(N/100), N), small_n_grps = rand(1:100, N), v1 = rand(1:5, N))
function fsort(df::DataFrame, cols)
x = df[cols]
df[sortperm(x),:]
end
@time fsort(testdf, :large_n_grps)
@time sort(testdf, cols = [:large_n_grps])
```