I need a `sortperm!`

function which returns the number of comparisons actually performed to sort an array. I thought I could do this by intercepting and counting the calls to `isless`

.

After a few trials I identified two possible solutions, implemented in the `mysortperm1!`

and `mysortperm2!`

functions shown below. Questions are:

- why
`mysortperm1!`

is much slower than `mysortperm2!`

?
- is there a better (i.e. faster) way to solve this problem?

```
function mysortperm1!(p, v)
counter = 0
sortperm!(p, v, lt=(a,b) -> (counter += 1; a < b))
return counter
end
function mysortperm2!(p, v)
counter = [0]
sortperm!(p, v, lt=(a,b) -> (counter[1] += 1; a < b))
return counter[1]
end
using BenchmarkTools
n = 100_000
v = rand(n);
p = zeros(Int, length(v));
@btime sortperm!(p, v);
@btime mysortperm1!(p, v)
@btime mysortperm2!(p, v)
```

Thanks

I’m not sure if I understand it fully myself, but I think it’s because the anonymous function `(a,b) -> (counter += 1; a < b)`

is reaching outside it’s scope to modify an immutable, which being immutable it can’t, so it instead gets boxed.

```
let counter = 0
(a,b) -> (counter += 1; a<b)
end |> dump
-> getfield(Main, Symbol("##83#84"))(Core.Box(0)) (function of type getfield(Main, Symbol("##83#84")))
counter: Core.Box
contents: Int64 0
```

Taking a look at the anonymous function, `counter`

is captured and boxed, and a box is of type `Any`

so the function is not type stable.

```
function mysortperm1!(p, v)
counter = Ref(0)
sortperm!(p, v, lt=(a,b) -> (counter[] += 1; a < b))
return counter[]
end
```

As an alternative, you can make a reference to an immutable, and modify it by reference. Although someone may know of a better solution. Your `mysortperm2!`

is modifying an array which is mutable and thus type stable, but has the unnecessary bounds checking overhead.

1 Like

I think the `Ref`

way is the standard way to do it.

1 Like