RFC: Make `any` and `all` always short-circuit #19543

ararslan · 2016-12-09T02:07:59Z

Fixes #19151

This implements @JeffBezanson's suggested simplification. With this change, any and all will short circuit in all circumstances. Currently they short circuit for arrays (we even have a test for that) but not for generators.

StefanKarpinski

I enjoy that this code is much simpler. Honestly, I think I'd much rather move all of our reduction code back to this sort of simple definition unless there's a really compelling reason. It's gotten pretty hairy and out of control.

fcard · 2016-12-09T23:39:56Z

This code here could be removed also: base/reduce.jl#L561-L569

ararslan · 2016-12-10T04:28:42Z

Good catch, @fcard, thanks!

ararslan · 2016-12-10T04:56:40Z

These changes make me wonder whether mapreduce_sc and mapreduce_no_sc are necessary...

Side note: The 32-bit Windows build failure looks like one of those intermittent Git issues

fcard · 2016-12-10T09:56:44Z

@ararslan Do you mean that as "mapreduce should always short-circuit as well" or "mapreduce should never short-circuit and just leave that to any/all"? Tbh I should have just left that function alone but back in the day it was hip to reduce everything to mapreduce. (or map everything to it, eh? eh?)

pabloferz · 2016-12-10T16:32:17Z

base/reduce.jl

-    eltype(itr) <: Bool ?
-        mapreduce_sc_impl(f, |, itr) :
-        reduce(or_bool_only, false, itr)
+function any(f::Predicate, itr)


You could also change mapreduce_sc_impl in terms of these for now and leave the cleaning of the rest of the reduce code for another PR. That is

mapreduce_sc_impl(f, ::typeof(|), itr) = any(f, itr) mapreduce_sc_impl(f, ::typeof(&), itr) = all(f, itr)

It looks as though if I change mapreduce to do that directly, there's no need for any of the other mapreduce_*sc* functions.

ararslan · 2016-12-10T19:13:00Z

@fcard I mean that—assuming I'm following all the logic correctly—the mapreduce_*sc* functions are only being used for any, all, and mapreduce where the function is a predicate and the reduction operator is | or &. All of these cases short circuit. mapreduce for | and & could just use any/all, rendering all of the mapreduce_*sc* functions unused.

or map everything to it

groan 🙂

ararslan · 2016-12-10T19:39:10Z

As an aside, I just realized that in the linked issue, the reason why the generator wasn't being short circuited was because the eltype wasn't being inferred as Bool. It was being inferred as Any, so mapreduce_no_sc was called instead.

fcard · 2016-12-10T20:38:15Z

The only thing that short-circuits other than any and all is reduce(|/&, itr) where eltype(itr) == Bool, which indeed isn't a very impressive case for keeping this in Base. My intention when initially adding those was to eventually extend the number of cases where short-circuiting happens safely, which could be accomplished generically with traits like so:

function mapreduce{R}(f::PureFunction, op::ShortCircuiting{R}, init::R, itr)
  local r::R = init
  local terminal = terminal_values(op,R)
  for x in itr
    r = op(r, f(x))
    r in terminal && return r
  end
  return r
end

ShortCircuiting{R} being a subtrait of PureFunction (explains itself) that requires the function type Op=typeof(op) to be in a terminal_values(op::Op, ::Type{R}) method, which returns a S::Collection{R} such that ∀(x∈S, y)(op(x,y) == x).

...But that's not happening any time soon is it? Even if it eventually becomes possible and is something wanted in Base (it could also go in a package), it's not going to reuse any of the code here. (my original code looked a bit more like this, but really I shouldn't have based it in a dream so far in the future)

What I am trying to say is that unless anyone cares about short-circuiting reduce(|/&, itr) despite there already existing any/all, there is indeed no point in keeping the mapreduce_sc definitions.

... Goodbye, my beautiful children. I hope you served your purpose well 😢>

This is the third or fourth reason that I give for making the code like this, but they were all true in different ways:

The reason I didn't go for the simple algorithm was that back then anonymous functions were slow and also there were so many optimizations for mapreduce that I felt like I needed to fall back to that (plus it was hip and cool and everybody in ~~town~~reduce.jl was doing it)
The reason I made short-circuiting so restrictive was because if an f in any/all (f, itr) 1) caused side-effects or 2) was type unstable and returned a non-bool at any point that caused any/all to throw an error, then it would mean that short-circuiting could alter the behavior of the program, and that's terrible.
After the goal was set to both extend short-circuiting to mapreduce and filter out anything that could make short-circuiting a behavior-altering property, I came up with this totally uber cool algorithm that could ensure that not only for any and all but anything passed to mapreduce, but I couldn't write it just yet so I made a restricted prototype, which is what is being put to rest here. (back then I thought arrow functions were the way to go, but eventually I concluded traits were more doable and simpler)

Sorry if I am being long-winded and over-explaining myself, I am trying to cope, it was my first big contribution to anything... But I still wholeheartedly approve this simplification.

ararslan · 2016-12-11T20:16:11Z

@fcard You have every reason to be proud of your children, for they have served valiantly. You've made an invaluable contribution to Julia through them, and they will live eternally in Julia versions past.

@StefanKarpinski Would you mind taking another look at this? It's changed a fair bit since you submitted your review.

Edit: ~~Oops! Ambiguities galore. Will fix.~~ Fixed.

fcard · 2016-12-11T21:41:07Z

base/reduce.jl

-mapreduce(f, op::ShortCircuiting, n::Number) = n
-mapreduce(f, op::ShortCircuiting, itr::AbstractArray) = mapreduce_sc(f,op,itr)
-mapreduce(f, op::ShortCircuiting, itr::Any)           = mapreduce_sc(f,op,itr)
+mapreduce(f, op::Union{typeof(&), typeof(|)}, n::Number) = n


This actually should be

mapreduce(f, op::Union{typeof(&), typeof(|)}, n::Number) = f(n) ^^^^

I just now noticed this dumdum mistake of mine (thankfully calling mapreduce(f, rand([&,|]), x::Number) instead of f(x) never took off, it had all the potential to be the new x |> f)

But maybe you should just remove all short-circuiting mapreduce methods all together for now, since the only thing using Predicate is any/all and nothing else will short-circuit. You could also test to see if thePredicate thing still has any performance advantages and remove that as well if it doesn't.

Or you could just focus on the any/all part and leave me to clean up after my own mess in a followup PR, all valid options in my book :P

Haha yeah, I noticed the f(n) thing as I was going through here. I've simplified things in this PR but if people end up wanting me to undo stuff here, I'll leave the rest to you. 😉

martinholters · 2016-12-12T07:53:02Z

Can't we get rid of Predicate altogether? If we make the API that any and all always short-circuit, while mapreduce never does, that seems pretty usable and also allows for the simplest implementation, I guess.

Presently, Predicate is used to annotate a function to mark it as pure and returning a bool by hand. So the current logic only allows optimization for mapreduce(p::Predicate, f::Function, ...) where, when the code is being written, the programmer knows that the p is a valid predicate (hence he has wrapped it in a Predicate), while he cannot know what f is, hence cannot use any or all. Then, in case f is & or |, short-circuiting would happen automatically. Seems to be a rare situation, probably not worth all the code complexity. Or am I missing something?

ararslan · 2016-12-12T18:03:36Z

@martinholters Sounds excellent to me! I'll make those changes later today. We should probably run Nanosoldier afterward as well, just in case.

Sacha0 · 2016-12-13T03:36:45Z

@nanosoldier runbenchmarks(ALL, vs = ":master")

nanosoldier · 2016-12-13T06:53:07Z

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here. cc @jrevels

martinholters · 2016-12-13T07:30:58Z

Those regressions look unrelated. Is your branch missing the commits from #19512/#19491? That might be the reason.

KristofferC · 2016-12-13T07:58:34Z

Nanosoldier benchmarks on the merge commit if I recall correctly. However, these benchmarks have popped up before so I think they are a bit noisy.

ararslan · 2016-12-13T18:14:25Z

Those regressions look unrelated

That's what I was thinking but I'm never sure...

Is your branch missing the commits from #19512/#19491? That might be the reason.

Quite possibly, though I thought I had rebased from master before the most recent push. And if Nanosoldier benchmarks on the merge commit that should make it irrelevant anyway.

It this okay then?

Also: Does this warrant a news item? It changes the behavior such that mapreduce never short circuits whereas any and all always do. Previously mapreduce would sometimes short circuit and any/all would do so when the element type of the iterator was inferrable as Bool.

tkelman · 2016-12-13T19:28:55Z

yes, should go in news

ararslan · 2016-12-14T01:50:12Z

And gone in NEWS it has. 🙂 Thanks, @tkelman.

martinholters · 2016-12-14T07:37:40Z

NEWS.md

@@ -74,6 +74,10 @@ Library improvements

  * New `titlecase` function, which capitalizes the first character of each word within a string ([#19469]).

+  * `any` and `all` now always short-circuit, and `mapreduce` never short-circuits ([#19543]).


Could also mention reduce here, since it is equally affected by the change.

Good call, added. Thanks!

simonbyrne · 2016-12-15T11:55:26Z

base/reduce.jl

-or_bool_only(a::Bool, b::Bool) = a|b
-and_bool_only(a, b) = nonboolean_error(:all, :&)
-and_bool_only(a::Bool, b::Bool) = a&b
-
 """
    any(p, itr) -> Bool


Maybe mention short-circuiting behaviour in the docs?

with an example, e.g.:

any(i -> (println(i); i > 3), 1:10)

Done. Look okay? Thanks!

[ci skip]

tkelman · 2016-12-15T19:46:17Z

base/reduce.jl

@@ -524,6 +476,7 @@ end
    any(itr) -> Bool

 Test whether any elements of a boolean collection are `true`.
+Not all items in `itr` will be visited if a `true` value is found.


maybe "Returns true as soon as the first true value is found in itr (short circuiting)." ?

The mix of imperative ("test whether") and non-imperative ("returns true") seems a little odd to me but maybe it's fine. How about something like

Test whether any elements of a boolean collection are true, returning true as soon as the first true value in itr is encountered (short-circuiting).

?

Cool, went with that then. Thanks!

ararslan · 2016-12-15T22:10:06Z

I just now realized that any! and all! exist. They call mapreduce! with | and & as the reducer, respectively. mapreduce! doesn't have the short-circuiting methods that its cousin mapreduce had, so any! and all! have never short-circuited AFAICT. Assuming I correctly understanding what those functions are supposed to do, those shouldn't change, right? It seems like if you short circuit then you may not fill the destination array entirely. Just want to make sure...

ararslan · 2016-12-16T23:39:41Z

Is this good to go then?

tkelman · 2016-12-17T06:41:17Z

any! and all! are only defined for reducing across a given dimension, right? so they could short circuit in that dimension but still have to fill each element in the orthogonal dimensions. That's probably best left to a separate PR if we decide we want to change that though.

ararslan · 2016-12-17T18:37:09Z

Kind of? any!(r, A) detects true values in A along the singleton dimensions in r and overwrites r; there's no dimension specification as such. Disclaimer: I don't fully understand what that means or what the function actually does.

Agreed regarding those changes being a separate PR, if they're necessary.

tkelman · 2016-12-27T16:01:53Z

We should probably put back Predicate and ShortCircuiting as non-exported deprecated bindings, since removing them broke several packages.

ararslan · 2016-12-27T20:48:36Z

If you can point me to which packages in particular broke I can submit PRs. I've done so for Lazy.jl and ColorVectorSpace.jl so far.

tkelman · 2016-12-27T23:31:54Z

Grepping registered packages, it looks like ColorVectorSpace was the only user of ShortCircuiting, and aside from Lazy the only package that uses Base.Predicate is DistributedArrays. Several packages define their own type called Predicate, but they won't notice this.

ararslan · 2016-12-28T06:14:42Z

Cool, I just submitted a PR to DistributedArrays, so I think I've got everything covered now.

ararslan force-pushed the aa/all-short-circuit branch from 089e5a9 to 83071d0 Compare December 9, 2016 03:05

StefanKarpinski approved these changes Dec 9, 2016

View reviewed changes

fcard mentioned this pull request Dec 9, 2016

Add tests for more permissive any/all with non-boolean collections #18969

Merged

pabloferz reviewed Dec 10, 2016

View reviewed changes

fcard reviewed Dec 11, 2016

View reviewed changes

ararslan force-pushed the aa/all-short-circuit branch 2 times, most recently from e0e7fe1 to e59a277 Compare December 13, 2016 00:54

Sacha0 mentioned this pull request Dec 13, 2016

last(::Tuple) should be type stable #19571

Closed

ararslan force-pushed the aa/all-short-circuit branch from e5a4417 to 6a346b5 Compare December 14, 2016 01:51

martinholters reviewed Dec 14, 2016

View reviewed changes

Sacha0 approved these changes Dec 14, 2016

View reviewed changes

simonbyrne reviewed Dec 15, 2016

View reviewed changes

Make any and all always short-circuit

cd230e1

ararslan added 3 commits December 15, 2016 10:23

Remove Predicate and short-circuiting mapreduce

8d40662

Add NEWS item

55f7a1c

[ci skip]

Mention short circuiting behavior in the docstrings

df560dd

ararslan force-pushed the aa/all-short-circuit branch from cb2532a to df560dd Compare December 15, 2016 18:23

tkelman reviewed Dec 15, 2016

View reviewed changes

Update wording in any/all docstrings

5df0dce

tkelman merged commit ded2259 into JuliaLang:master Dec 17, 2016

ararslan deleted the aa/all-short-circuit branch December 17, 2016 20:21

vtjnash mentioned this pull request Dec 23, 2016

Load failing in latest 0.6.0 - "UndefVarError: ShortCircuiting not defined" JuliaGraphics/ColorVectorSpace.jl#63

Closed

		@@ -74,6 +74,10 @@ Library improvements

		* New `titlecase` function, which capitalizes the first character of each word within a string ([#19469]).

		* `any` and `all` now always short-circuit, and `mapreduce` never short-circuits ([#19543]).

RFC: Make any and all always short-circuit #19543

RFC: Make any and all always short-circuit #19543

Conversation

ararslan commented Dec 9, 2016

StefanKarpinski left a comment

Choose a reason for hiding this comment

fcard commented Dec 9, 2016

ararslan commented Dec 10, 2016

ararslan commented Dec 10, 2016 • edited Loading

fcard commented Dec 10, 2016 • edited Loading

pabloferz Dec 10, 2016 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ararslan commented Dec 10, 2016 • edited Loading

ararslan commented Dec 10, 2016

fcard commented Dec 10, 2016 • edited Loading

ararslan commented Dec 11, 2016 • edited Loading

fcard Dec 11, 2016 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

martinholters commented Dec 12, 2016

ararslan commented Dec 12, 2016

Sacha0 commented Dec 13, 2016

nanosoldier commented Dec 13, 2016

martinholters commented Dec 13, 2016

KristofferC commented Dec 13, 2016 • edited Loading

ararslan commented Dec 13, 2016 • edited Loading

tkelman commented Dec 13, 2016

ararslan commented Dec 14, 2016

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ararslan commented Dec 15, 2016

ararslan commented Dec 16, 2016

tkelman commented Dec 17, 2016

ararslan commented Dec 17, 2016 • edited Loading

tkelman commented Dec 27, 2016

ararslan commented Dec 27, 2016 • edited Loading

tkelman commented Dec 27, 2016

ararslan commented Dec 28, 2016

RFC: Make `any` and `all` always short-circuit #19543

RFC: Make `any` and `all` always short-circuit #19543

ararslan commented Dec 10, 2016 •

edited

Loading

fcard commented Dec 10, 2016 •

edited

Loading

pabloferz Dec 10, 2016 •

edited

Loading

ararslan commented Dec 10, 2016 •

edited

Loading

fcard commented Dec 10, 2016 •

edited

Loading

ararslan commented Dec 11, 2016 •

edited

Loading

fcard Dec 11, 2016 •

edited

Loading

KristofferC commented Dec 13, 2016 •

edited

Loading

ararslan commented Dec 13, 2016 •

edited

Loading

ararslan commented Dec 17, 2016 •

edited

Loading

ararslan commented Dec 27, 2016 •

edited

Loading