Add mapreduce_single function by simonbyrne · Pull Request #25051 · JuliaLang/julia

simonbyrne · 2017-12-12T23:48:28Z

Since the demise of r_promote in #22825, there is now a type-instability in mapreduce if the operator does not give an element of the same type as the input. This arose during my implementation of Kahan summation using a reduction operator, see: JuliaMath/KahanSummation.jl#7

This adds a mapreduce_single function which defines what the result should be in these cases.

simonbyrne · 2017-12-13T01:08:03Z

This has the benefit of being able to get rid of the funny composition behaviour to get the widening behaviour of sum/prod.

simonbyrne · 2017-12-13T20:20:26Z

Okay, I think this should be ready. I tried to avoid touching the reducedim code too much, but I suspect something like this could help clean up that as well.

simonbyrne · 2017-12-13T20:28:02Z

@TotalVerb You did the last deep dive into this code: would you mind having a quick look over it?

TotalVerb · 2017-12-13T20:42:31Z

base/reduce.jl

+reduce_single(op, x) = x
+reduce_single(::typeof(+), x::Bool) = Int(x)
+
+reduce_single(::typeof(add_sum), x) = reduce_single(+, x)


Although adding + zero(x) for add and * one(x) was ugly, I think it is more general. There are theoretically other types than Bool that are not the type of their "additive monoid" or "multiplicative monoid". Char is now one of these for multiplication. Of course, Irrational is one of these, but that doesn't support zero either. The extra add or multiply should be easily optimized by LLVM for all types except already-slow ones like BigInt, anyway.

zero(pi) and one('a') both currently throw errors, so they won't work either.

Well, let's leave it as is then. one('a') should theoretically return "" though.

Yeah, I'll add a fix for that.

TotalVerb · 2017-12-13T20:44:36Z

base/reduce.jl

 overflow results in -128.
 """
-sum(f::Callable, a) = mapreduce(promote_sys_size_add ∘ f, +, a)
+sum(f, a) = mapreduce(f, add_sum, a)


Good catch: it looks like this Callable is not necessary for avoiding ambiguity any more. The same change should apply for prod.

TotalVerb · 2017-12-13T20:51:52Z

base/reducedim.jl

-        reducedim_initarray(A, region, real(zero(eltype(A))))
-    global reducedim_init(f::Union{typeof(abs),typeof(abs2)}, op::typeof(*), A::T, region) =
-        reducedim_initarray(A, region, real(one(eltype(A))))
+    global reducedim_init(f, op::Union{typeof(+),typeof(add_sum)}, A::T, region) =


I think it's not safe to generalize this to f ∉ [identity, abs, abs2] because we need the reduction operator to be type stable over whatever is produced by the f used for mapreduce. Nevertheless, it's a nice simplification to have, but I think we will need to continue hardcoding the list of acceptable map functions.

Won't mapreduce_single(f, op, zero(eltype(A))) should handle that?

In general, for some choices of f, this assumes that mr_single(f, +, 0) + f(0), etc., will be of the same concrete type of mr_single(f, +, 0), which one can design f to make it fail (for example, in the case of *, if f return a dimensionful quantity, like 1m, which has different concrete type than 1m^2). This seems to be where _reducedim_init is more general and guards against. Of course it is also possible to thwart _reducedim_init with badly behaving f, so 😕.

Although I'm not actually sure _reducedim_init does what it should in these type unstable cases, so maybe it's best to leave cleanup of _reducedim_init to later.

TotalVerb · 2017-12-13T20:55:23Z

base/reduce.jl

+prod(a) = mapreduce(identity, mul_prod, a)

 ## maximum & minimum



It might be worth changing the f(a1) in the below function to mapreduce_single(f, op, a1) for consistency, although no reasonable types I can think of should have a lattice structure outside the type itself.

TotalVerb · 2017-12-13T20:57:56Z

base/reduce.jl

@@ -133,7 +141,7 @@ function mapfoldr(f, op, itr)
    if isempty(itr)


Unrelated comment, which can be done as part of this PR or in a later one: Since we have #24187 Iterators.Reverse now, I think we can write these mapfoldr functions generically. As it stands it only works with arrays, and this generalization may allow it to work with arbitrary reversible iterators.

StefanKarpinski · 2017-12-13T21:08:40Z

How about calling this reduce1? Terrible name? Somehow I like it better than reduce_single.

simonbyrne · 2017-12-13T21:12:46Z

How about calling this reduce1? Terrible name? Somehow I like it better than reduce_single.

Because it deals with singleton case, in the same way that reduce_empty deals with the empty case.

Perhaps it would be best to change it to reduce_first, since it is used in a couple of places to get the first element of the reduction.

StefanKarpinski · 2017-12-14T22:02:39Z

I would say go with mapreduce_first then, seems like a clearer name.

simonbyrne · 2017-12-14T22:33:21Z

Okay done.

One question: should reduce/foldl/foldr always call reduce_first on the first element when more than 1 element? This is not true currently (some just unwind the loop of the first 2 elements).

simonbyrne · 2017-12-14T22:34:46Z

Also, I didn't touch accumulate, cumsum, etc., as that is way beyond most mere mortals.

JeffBezanson · 2017-12-30T19:28:25Z

LGTM.

Rebase?

Since the demise of `r_promote` in #22825, there is now a type-instability in `mapreduce` if the operator does not give an element of the same type as the input. This arose during my implementation of Kahan summation using a reduction operator, see: JuliaMath/KahanSummation.jl#7 This adds a `mapreduce_single` function which defines what the result should be in these cases.

The promotion machinery for reduction in sum/prod was changed in JuliaLang/julia#25051. This updates the use.

simonbyrne force-pushed the sb/reduce branch from 2553673 to e120c61 Compare December 13, 2017 01:07

simonbyrne force-pushed the sb/reduce branch from e120c61 to 937b954 Compare December 13, 2017 01:14

ararslan requested a review from stevengj December 13, 2017 06:53

simonbyrne changed the title ~~Add mapreduce_single function~~ WIP: Add mapreduce_single function Dec 13, 2017

simonbyrne changed the title ~~WIP: Add mapreduce_single function~~ Add mapreduce_single function Dec 13, 2017

simonbyrne added the arrays [a, r, r, a, y, s] label Dec 13, 2017

simonbyrne added the triage This should be discussed on a triage call label Dec 13, 2017

TotalVerb reviewed Dec 13, 2017

View reviewed changes

StefanKarpinski removed the triage This should be discussed on a triage call label Dec 14, 2017

StefanKarpinski added this to the 1.0 milestone Dec 14, 2017

StefanKarpinski assigned simonbyrne Dec 14, 2017

simonbyrne force-pushed the sb/reduce branch from eae9a54 to 982c833 Compare December 14, 2017 22:31

simonbyrne force-pushed the sb/reduce branch from 982c833 to 4c19973 Compare January 3, 2018 20:23

JeffBezanson merged commit e422547 into master Jan 4, 2018

JeffBezanson deleted the sb/reduce branch January 4, 2018 16:22

simonbyrne mentioned this pull request Jan 11, 2018

accumulate(op, v0, x) fails on arrays of non-numeric types #25506

Closed

jw3126 mentioned this pull request Jan 12, 2018

fix non numeric accumulate(op, v0, x) (#25506) #25515

Closed

simonbyrne added a commit to JuliaMath/FixedPointNumbers.jl that referenced this pull request Jan 16, 2018

Update reduction machinery for 0.7

94ae245

The promotion machinery for reduction in sum/prod was changed in JuliaLang/julia#25051. This updates the use.

simonbyrne mentioned this pull request Jan 16, 2018

Update reduction machinery for 0.7 JuliaMath/FixedPointNumbers.jl#100

Merged

mbauman mentioned this pull request Apr 28, 2025

Whole-array reductions always use init to start each reduction chain #58241

Open

		prod(a) = mapreduce(identity, mul_prod, a)

		## maximum & minimum

		@@ -133,7 +141,7 @@ function mapfoldr(f, op, itr)
		if isempty(itr)

Uh oh!

Conversation

simonbyrne commented Dec 12, 2017

Uh oh!

simonbyrne commented Dec 13, 2017

Uh oh!

simonbyrne commented Dec 13, 2017

Uh oh!

simonbyrne commented Dec 13, 2017

Uh oh!

TotalVerb Dec 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

TotalVerb Dec 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

TotalVerb Dec 13, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

StefanKarpinski commented Dec 13, 2017

Uh oh!

simonbyrne commented Dec 13, 2017

Uh oh!

StefanKarpinski commented Dec 14, 2017

Uh oh!

simonbyrne commented Dec 14, 2017

Uh oh!

simonbyrne commented Dec 14, 2017

Uh oh!

JeffBezanson commented Dec 30, 2017

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

TotalVerb Dec 13, 2017 •

edited

Loading

TotalVerb Dec 13, 2017 •

edited

Loading

TotalVerb Dec 13, 2017 •

edited

Loading