# Ironic observation about \`sort\` and \`sortperm\` speed for "small integers" vs R

**URL:** <https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715>\
**Category:** Performance\
**Tags:** sort, sortperm, r\
**Created:** [January 31, 2018, 11:24am UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715 "2018-01-31T11:24:11Z")\
**Posts on this page:** 13\
**Page:** 2

<div class="post-metadata">

**Author:** ![Ralph\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ralph_smith/32/10344_2.png) [@Ralph\_Smith](https://discourse.julialang.org/u/Ralph_Smith)\
**Post date:** [February 2, 2018, 3:56am UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/22 "2018-02-02T03:56:17Z")

</div>

> [@xiaodai](#):
>
> Have you tried the sortperm\_int\_range4 function that I wrote?

`sortperm_int_range4` takes almost 7s for the standard problem on my systems. Let it be noted that my `sortperm_int_range_p1` is very similar in design. I thought that the difference in performance occurred because

1. I forced type-stability (partially true, more on this below)
2. there are fewer iterations of the radix mask loop (true, and possibly helpful for your project).

I noticed that `SortingAlgorithms.sort!(a::Vector{UInt},...,RadixSort,...)` is type-unstable and I assumed this was critical. (Fixing type stability **was** important for my version.) However, I recently found that making the `ca` variable in `sortperm_int_range4` a `Vector{Int}` instead of `Vector{UInt}` (which has no effect on the algorithm for this problem) **removes the type instability but does not fix the performance** , so there is something sick in the compilation of the method, hidden from the friendly tools I have used so far.

I need to mention that I am using v0.6.2. The type instability of radix `sort!` seems to be an inference bug which may be fixed in master.

---

<div class="post-metadata">

**Author:** ![Ralph\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ralph_smith/32/10344_2.png) [@Ralph\_Smith](https://discourse.julialang.org/u/Ralph_Smith)\
**Post date:** [February 2, 2018, 3:59am UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/23 "2018-02-02T03:59:57Z")

</div>

Regarding making my function type-stable

> [@foobar\_lv2](#):
>
> I’d be interested in the pitfalls you encountered.

I found it necessary to add extra type assertions and a function barrier, and to replace generators and broadcast expressions with `for` loops. Some day the compiler will presumably not need so much help.

---

<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:** [February 2, 2018, 4:12am UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/24 "2018-02-02T04:12:00Z")

</div>

> [@Ralph\_Smith](#):
>
> so there is something sick in the compilation of the method, hidden from the friendly tools I have used so far.

if this is true then it’s actually a good story and would confirm my hypothesis. And hopefully this will lead to an improvement in the compiler, and then everybody benefits!

---

<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:** [February 2, 2018, 4:14am UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/25 "2018-02-02T04:14:45Z")

</div>

> [@Ralph\_Smith](#):
>
> there are fewer iterations of the radix mask loop (true, and possibly helpful for your project)

totally. i actually implemented a version using the `sort32!` function in SortingLab.jl which only sorts the first 32 bits. That shaved 2 seconds off the benchmark so still slower than R, so I decided not to publish it. I actually got an idea for a modified counting sort that should be much faster if you radix sort benchmarks also holds on my machine. Will get to it once i get home.

---

<div class="post-metadata">

**Author:** ![bernhard](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bernhard/32/2619_2.png) [@bernhard](https://discourse.julialang.org/u/bernhard)\
**Post date:** [February 2, 2018, 7:46am UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/26 "2018-02-02T07:46:59Z")

</div>

For what it is worth, here are the numbers I get.  
I hope it is clear which algorithms I mean with p1 and p4.

I note that I get an error for the line which should save the pn

```julia
Main> savefig("julia_vs_r_sortandperm_integer.png")
ERROR: png output from the plotly backend is not supported. Please use plotlyjs instead.

```

![sorting_pic](https://global.discourse-cdn.com/julialang/original/3X/2/4/248f39ddeb15e9d7843386a3f16c2a5ba696e707.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:** [February 2, 2018, 10:41am UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/27 "2018-02-02T10:41:16Z")

</div>

> [@bernhard](#):
>
> Main\> savefig(“julia\_vs\_r\_sortandperm\_integer.png”)  
> ERROR: png output from the plotly backend is not supported. Please use plotlyjs instead.

You gotta run `gr()` use another backend.

---

<div class="post-metadata">

**Author:** ![bernhard](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bernhard/32/2619_2.png) [@bernhard](https://discourse.julialang.org/u/bernhard)\
**Post date:** [February 2, 2018, 12:38pm UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/28 "2018-02-02T12:38:12Z")

</div>

Thank you. Interestingly I had to `Pkg.add("GR")` which makes me wonder whether that package should be in any of the REQUIRE files. Admittedly I have absolutley no knowledge about Plots and so on.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [February 2, 2018, 4:52pm UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/29 "2018-02-02T16:52:56Z")

</div>

It’d probably be a little much to have every backend as a dependency, so I think it normally installs plotly by default, and lets you install any other back ends you would like to use.

---

<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:** [February 3, 2018, 10:56pm UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/30 "2018-02-03T22:56:43Z")

</div>

@Ralph_Smith and @foobar_lv2 The algorithms you helped write there will not only help `sortperm` for small integer ranges but also `sortperm` for any integer range. Is it ok if I incorporate your code into SortingLab.jl and then find a way to contribute them back to Base and/or SortingAlgorithms.jl?

---

<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:** [February 3, 2018, 11:15pm UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/31 "2018-02-03T23:15:14Z")

</div>

I have done a lot of testing and have read into [What every programmer should know about memory?](https://people.freebsd.org/~lstewart/articles/cpumemory.pdf). In particular, this quote from the paper made me realize how important understanding cache is

> A simple computation can show how effective caches can theoretically be. Assume access to main memory takes 200 cycles and access to the cache memory take 15 cycles. Then code using 100 data elements 100 times each will spend 2,000,000 cycles on memory operations if there is no cache and only 168,500 cycles if all data can be cached. That is an improvement of **91.5%**.

This is quite new to me and I assume to many other Julia programmers as well. Basically, the performance of counting sort beats radix sort up to around `2^11 = 2048` unique values. In counting sort, the size of the counting array is `# unqiues * sizeof(UInt32)` which is around 8192, so it’s getting close to maxing out the L1d-cache on most PCs. So perhaps @nalimilan’s point about the slowness of counting is “obvious” once you understand the importance of cache but not to beginners like me.

 ![Counting-sortperm%20vs%20Radix-sortperm%20(%20of%20elements%20%3D%20100m)](https://global.discourse-cdn.com/julialang/original/3X/8/6/8661ec2ccdf5927a2dcbabc0cc5d6dbb60cb69fe.png)

**code**

```julia
function counting_vs_radix(n)
    a = rand(1:n, 100_000_000)
    (@belapsed(sortperm_int_range2($a, $n, 1)), @belapsed(sortperm_int_range_p1($a, $n, 1, 10)))
end

tic()
res = [counting_vs_radix(n) for n in 2.^(2:20)]
toc()

using Plots
plot([r[1] for r in res], title="Counting-sortperm vs Radix-sortperm (# of elements = 100m)", label = "Counting-sortperm",
    ylabel = "seconds", xlabel = "log_2(n) unique values", ylim = (0, 15))
plot!([r[2] for r in res], label = "Radix-sortperm")
plot!(xticks = (2:20))
savefig("Counting-sortperm vs Radix-sortperm ( of elements = 100m).png")

```

---

<div class="post-metadata">

**Author:** ![Ralph\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ralph_smith/32/10344_2.png) [@Ralph\_Smith](https://discourse.julialang.org/u/Ralph_Smith)\
**Post date:** [February 4, 2018, 3:27am UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/32 "2018-02-04T03:27:09Z")

</div>

> [@xiaodai](#):
>
> Is it ok if I incorporate your code

Please do. I can think of at least one elaboration which I could propose as a PR.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [February 4, 2018, 12:25pm UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/33 "2018-02-04T12:25:42Z")

</div>

> [@xiaodai](#):
>
> Is it ok if I incorporate your code into SortingLab.jl and then find a way to contribute them back to Base and/or SortingAlgorithms.jl?

Don’t ask me, Ralph\_Smith did the work. (so this means “yes”, of course it is OK as far as I’m concerned, but I literally added two `@inbounds` to Ralph\_Smith’s cool thing and don’t deserve credit here)

Minor elaborations if you put this somewhere for general consumption: `cbin = cumsum(bin[:,j])`: The `cbin` can be re-used for all radices; the `cumsum` wants to be done via a `view` on 0.7 and by hand on 0.6.

---

<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:** [February 4, 2018, 1:48pm UTC](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715/34 "2018-02-04T13:48:42Z")

</div>

actually you dont need `cbin` just reuse `bin`

[Previous page](https://discourse.julialang.org/t/ironic-observation-about-sort-and-sortperm-speed-for-small-integers-vs-r/8715.md?page=1)