Skip to content

Implement mapreduce_impl for IndexCartesian.#45651

Open
N5N3 wants to merge 2 commits intoJuliaLang:masterfrom
N5N3:CartReduce
Open

Implement mapreduce_impl for IndexCartesian.#45651
N5N3 wants to merge 2 commits intoJuliaLang:masterfrom
N5N3:CartReduce

Conversation

@N5N3
Copy link
Copy Markdown
Member

@N5N3 N5N3 commented Jun 12, 2022

On master, mapreduce calls mapfoldl for inputs with IndexCartesian style, which brings performance pain if the 1st dimension is long enough for vectorlization.

This PR implements pairwise mapreduce_impl for better performance by cutting the highest splitable dimension in half.
(As we can't reorder the inputs, and CartesianPartition has much higher overhead)

Test added.

A simple benchmark

julia> a = randn(100, 100);

julia> slow(a) = view(a, axes(a)...)
slow (generic function with 1 method)

julia> @btime reduce(+, slow($a))
  1.870 μs (0 allocations: 0 bytes)
88.67608098492965

julia> @btime foldl(+, slow($a))
  9.700 μs (0 allocations: 0 bytes)
88.67608098492977

@N5N3 N5N3 added the performance Must go faster label Jun 12, 2022
@adienes adienes added the fold sum, maximum, reduce, foldl, etc. label May 5, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

fold sum, maximum, reduce, foldl, etc. performance Must go faster

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants