Mapreduce is 10x slower than loop.

[oscardssmith]

A slack conversation led me to the realization that currently the following two functions have very different speeds.

function f(x, y)
    return @inbounds mapreduce(==,+,x, y)
end

function f2(x, y)
	total=0
	@inbounds for i in 1:length(x)
		total += x[i]==y[i]
	end
	return total
end
x = randn(10240); y = similar(x)
@btime f2(x,y)
  1.255 μs (0 allocations: 0 bytes)

@btime f(x,y)
  9.207 μs (1 allocation: 10.19 KiB)

This is clearly unfortunate as the mapreduce version is much clearer. Is there any way we can make this case for mapreduce not have O(n) allocation? (or otherwise be faster)

[jishnub]

Perhaps this is because map allocates an intermediate array? The performance improves noticeably using MappedArrays:

julia> @btime f($x,$y);
  22.352 μs (1 allocation: 10.19 KiB)

julia> @btime f2($x,$y);
  2.178 μs (0 allocations: 0 bytes)

julia> using MappedArrays

julia> function f3(x,y)
           reduce(+, mappedarray(==, x, y))
       end
f3 (generic function with 1 method)

julia> @btime f3($x,$y);
  4.934 μs (0 allocations: 0 bytes)

Still not quite as good as the loop, but almost there.

[timholy]

If Generators were faster we could just delete the specialization for multiple arrays and use

julia/base/reduce.jl

Line 288 in 19b3ec5

mapreduce(f, op, itrs...; kw...) = reduce(op, Generator(f, itrs...); kw...)

Generators are like generalized MappedArrays, but unfortunately they never have quite gotten the same performance. Working on their performance might be the best way to tackle this issue.

[antoine-levitt]

Generators are like generalized MappedArrays, but unfortunately they never have quite gotten the same performance. Working on their performance might be the best way to tackle this issue.

Yes please. Generators are super useful and I use them all the time (much more than higher-order functions).

[JeffBezanson]

I get 1.3 us for the loop, 10.4 us for mapreduce, and 7.2 us for the generator version (no allocations). So generators are already faster in this case, but yes need to be faster still.

[timholy]

As a reasonable goalpost, here's one more timing comparison:

• Generator version: 5.969 μs (0 allocations: 0 bytes)
• MappedArrays version: 1.631 μs (0 allocations: 0 bytes)
• f2 version: 1.430 μs (0 allocations: 0 bytes)

For me the gap between the explicit loop and MappedArrays is very small.

[stevengj]

f4(x,y) = mapreduce(((x,y),)->x==y,+,zip(x,y)) also has no allocations and is faster, but it's still not as fast as the loop.

[oscardssmith]

That would be a pretty easy to do automatically, right?

[oscardssmith]

@timholy is there any good reason why Generators are slow? Is there low hanging fruit? If you have a place to point me, I'd be glad to take a look.