Doubt about nested functions and scopes

General Usage
1

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

2

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
3

I think the Ref way is the standard way to do it.

1 Like