Why is this numerical scheme so much faster when using `collect()` than a for loop?

Consider a toy algorithm that finds the maximum of a vector, then removes it and alters the other entries of the vector in a way that depends on whether they are located at a lower or higher index.

In the code below, why is the function foo() so much slower than baz()?

function foo(a::Vector)
    for j in 1:length(a)
        b, k = findmax(a)

        for i in 1:k-1
            a[i] = (a[i] + b) / 2
        end
        for i in k+1:length(a)
            a[i] = (a[i] + 1) / 2
        end

        deleteat!(a, k)
    end
end


function bar(a::Vector)
    for j in 1:length(a)
        b, k = findmax(a)

        deleteat!(a, k)

        a[:] = collect(
            i < k ? (a[i] + b) / 2 : (a[i] + 1) / 2
            for (i, c) in enumerate(a)
        )
    end
end


function baz(m::Int)
    a = rand(m)

    t_foo = @time foo(a)    #  10.415122 seconds  
    t_bar = @time bar(a)    #   0.000000 seconds
end


baz(100000)

I expected foo() to be faster, because it works individually on the indices as they come up, whereas baz() has to collect an entire new vector.

If your measure claims that something that should take quite some time happens in basically no time, assume that your benchmarking is broken. In this case foo(a) mutates a and removes all elements. The call to bar(a) operates on an empty vector, which indeed is very fast.

3 Likes

Indeed you are right. Which makes it all the more mysterious why the for loop version is so much slower in my real application.

When I’m faced with that kind of scenario I commit all my current changes, then start to aggressively cut down my code, while making sure the problem remains, until it’s small enough to explain itself or generate a Julia bug report. The latter outcome has become increasingly rare over time.

I was able to create an example that (I think) is benchmarked correctly. I created a new thread here: Why is `collect()` faster than a for loop in this numerical scheme? (corrected!)

I’d be very grateful if you could take a look.