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

General Usage Performance
1

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.

2

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
3

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

4

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.

5

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.