regression in performance of counting loops

[mlubin]

I was playing around with an example for the class I'm preparing and noticed a 30% performance regression in the following code from 0.2 to master:

function normAndMin(x)
    n = 0.0
    m = Inf
    for i in 1:length(x)
        n += x[i]*x[i]
        if x[i] < m
            m = x[i]
        end
    end
    return sqrt(n),m
end

x = rand(100_000_000)
normAndMin(x) # throw away
n,m = @time normAndMin(x)

Julia 0.2:
elapsed time: 0.101895311 seconds (6912 bytes allocated)

Julia master:
elapsed time: 0.135729463 seconds (6812 bytes allocated)

[JeffBezanson]

This is certainly due to 0860767.

[mlubin]

Any hope for improvement?

[JeffBezanson]

Yes, this can be fiddled with, and we might overhaul integer ranges partly for this purpose.

[JeffBezanson]

I have been digging deeply into this today. The way we lower iteration may be interfering with LLVM's ability to recognize loop idioms. The following code is slow:

    state = 1
    while state != l+1
        i = state
        state += 1
        n += x[i]*x[i]
        if x[i] < m
            m = x[i]
        end
    end

And simply moving state += 1 to the end is faster:

    state = 1
    while state != l+1
        i = state
        n += x[i]*x[i]
        if x[i] < m
            m = x[i]
        end
        state += 1
    end

[simonster]

It looks like, with state += 1 at the beginning, the if is a branch, whereas with state += 1 at the end, it is optimized into a select. And indeed with:

    state = 1
    while state != l+1
        i = state
        state += 1
        n += x[i]*x[i]
        m = ifelse(x[i] < m, x[i], m)
    end

I seem to get the same performance as with state += 1 at the end.

[mlubin]

Cool!

[JeffBezanson]

Please verify. Worryingly, this varies a bit by machine, but it's either the same or faster on both machines I've tried so far.

[mlubin]

Confirmed back to 0.2 timings on my machine.

[timholy]

Very nice.