Make ntuple(f, n) and ntuple(f, Val{n}) throw ArgumentError when n < 0 #21697

alyst · 2017-05-04T15:04:44Z

ntuple(i -> i, -1) returns an empty Tuple{}, but ntuple(i -> i, Val{-1}) sends Julia (both 0.5 and 0.6) into an endless type inference(?) loop consuming CPU and memory (I didn't dare to wait until the end).

The fix is to return an empty tuple immediately.

Probably should be backported to 0.5 and 0.6.

TotalVerb · 2017-05-04T15:37:46Z

I would personally prefer an error to an empty tuple.

timholy · 2017-05-04T15:44:51Z

This seems like a good idea. It looks like the branch gets elided by the compiler anyway, so there probably isn't any cost to checking this.

alyst · 2017-05-04T15:48:19Z

This could be an error, but for consistency it should also be an error for ntuple(f, N::Int), which would make it a breaking change w.r.t. 0.5.

TotalVerb · 2017-05-04T15:50:13Z

We could avoid backporting the error for that method to 0.5 and 0.6, tolerating an inconsistency for those releases.

tkelman · 2017-05-04T15:52:19Z

I had the same thought so tracked the non-Val version to see how long it's been that way. Apparently always 97b2e50.

alyst · 2017-05-04T16:03:31Z

So the consensus is to make it a DomainError, and add DomainError for ntuple(f, -1) to the master?

alyst · 2017-05-04T21:08:40Z

Changed it to throwing DomainError (plus separate commit for ntuple(f, -1)). AppVeyor x86 build timeout looks unrelated.

fredrikekre · 2017-05-04T21:18:23Z

base/tuple.jl

@@ -105,7 +105,8 @@ julia> ntuple(i -> 2*i, 4)
 ```
 """
 function ntuple(f::F, n::Integer) where F
-    t = n <= 0  ? () :
+    (n >= 0) || throw(DomainError())


Maybe ArgumentError? A quick search through base suggests DomainError is mostly used when the value is out of domain for mathematical functions (e.g. sqrt, log etc)

I would change it to ArgumentError if there would be more thumbs up than for DomainError (yours is counted) :)

I'd leave the check over _ntuple so the branch gets delayed after the small cases.

DomainError changed into ArgumentError.
I'd leave the n check where it is, because it's much cleaner than burying it inside another routine. Anyway, in performance-sensitive context one should use Val{N} alternative.

Seconding @pabloferz's recommendation. Using the Val{N} methods is not always possible, and ntuple's performance is important. Best!

I would be surprised if LLVM did not just hoist the branch to the end, but this change can't hurt.

I've benchmarked the early and the late n check variants with

@benchmark ntuple(identity, n) setup=(n = rand(0:10))

The late one (inside _ntuple()) was 1ns (~10%) faster, so I've updated the PR.

Sacha0 · 2017-05-04T21:54:22Z

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

nanosoldier · 2017-05-05T00:55:51Z

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

alyst · 2017-05-05T12:56:08Z

Probably the CI has to be rerun. Travis got stuck (no output for 10 minutes) in one configuration, AppVeyor failed to install the package in one configuration.

alyst · 2017-05-07T23:05:56Z

Travis failed for xcode8 in 1 test of "spawn", but it doesn't look like PR-related. All other test configurations were ok.

alyst · 2017-05-08T14:24:06Z

The CI tests pass from the 3rd attempt. 🎉

Sacha0 · 2017-05-08T16:47:42Z

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

Sacha0 · 2017-05-08T16:49:53Z

base/tuple.jl

@@ -142,6 +146,7 @@ ntuple(f, ::Type{Val{15}}) = (@_inline_meta; (f(1), f(2), f(3), f(4), f(5), f(6)

 function ntuple(f::F, ::Type{Val{N}}) where {F,N}
    Core.typeassert(N, Int)
+    (N >= 0) || throw(ArgumentError(string("tuple length should be ≥0, got ", N)))


I imagine this branch is handled at compile time where N is known at compile time?

Yes, that's the theory. That's also what I see with @code_llvm ntuple(identity, Val{-1})

And also I hope with e.g. @code_llvm ntuple(identity, Val{1})? :)

Sure. Actually, for each 0<=N<=15 there's explicit ntuple(identity, Val{N}) method. The check for N<0 is in a generic method.
In fact, ntuple(f, Val{N}) is substantially slower for N>=16. On the 11 days old master (b838f2e)

julia> @benchmark ntuple(identity, Val{15}) BenchmarkTools.Trial: memory estimate: 0 bytes allocs estimate: 0 -------------- minimum time: 3.365 ns (0.00% GC) median time: 3.379 ns (0.00% GC) mean time: 3.400 ns (0.00% GC) maximum time: 16.001 ns (0.00% GC) -------------- samples: 10000 evals/sample: 1000 julia> @benchmark ntuple(identity, Val{16}) BenchmarkTools.Trial: memory estimate: 288 bytes allocs estimate: 2 -------------- minimum time: 418.864 ns (0.00% GC) median time: 423.166 ns (0.00% GC) mean time: 448.653 ns (2.32% GC) maximum time: 6.745 μs (87.57% GC) -------------- samples: 10000 evals/sample: 199

Few nanoseconds could be explained by Base.@_inline_meta absence, but not hundreds.

Sure. Actually, for each 0<=N<=15 there's explicit ntuple(identity, Val{N}) method. The check for N<0 is in a generic method.

Ah, right! Wonseok's recent change. Thanks for reminding me. For @code_llvm ntuple(identity, Val{16}) then :).

Following up --- the branch gets handled at compile time for e.g. @code_llvm ntuple(identity, Val{16})? Assuming that holds (and perhaps even if it doesn't, if the marginal cost of the branch is low) the present incarnation lgtm! :)

Yes, apparently, LLVM understands that the check is a constant expression and eliminates it.
The nanosoldier regressions look like noise to me given their high variation between the runs.

alyst · 2017-05-08T17:21:03Z

Hmm, I was using the following benchmark to estimate the overhead of checking n in the most common situations (the test should never be triggered and _ntuple_xxx() never visited):

_ntuple_before(f, n) = (Base.@_noinline_meta; ([f(i) for i = 1:n]...))

function ntuple_before(f::F, n::Integer) where F
    (n >= 0) || throw(ArgumentError(string("tuple length should be ≥0, got ", n)))
    t = n == 0  ? () :
        n == 1  ? (f(1),) :
        n == 2  ? (f(1), f(2)) :
        n == 3  ? (f(1), f(2), f(3)) :
        n == 4  ? (f(1), f(2), f(3), f(4)) :
        n == 5  ? (f(1), f(2), f(3), f(4), f(5)) :
        n == 6  ? (f(1), f(2), f(3), f(4), f(5), f(6)) :
        n == 7  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7)) :
        n == 8  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8)) :
        n == 9  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9)) :
        n == 10 ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9), f(10)) :
        _ntuple_before(f, n)
    return t
end

function _ntuple_after(f, n)
    Base.@_noinline_meta
    (n >= 0) || throw(ArgumentError(string("tuple length should be ≥0, got ", n)))
    ([f(i) for i = 1:n]...)
end

function ntuple_after(f::F, n::Integer) where F
    t = n == 0  ? () :
        n == 1  ? (f(1),) :
        n == 2  ? (f(1), f(2)) :
        n == 3  ? (f(1), f(2), f(3)) :
        n == 4  ? (f(1), f(2), f(3), f(4)) :
        n == 5  ? (f(1), f(2), f(3), f(4), f(5)) :
        n == 6  ? (f(1), f(2), f(3), f(4), f(5), f(6)) :
        n == 7  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7)) :
        n == 8  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8)) :
        n == 9  ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9)) :
        n == 10 ? (f(1), f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9), f(10)) :
        _ntuple_after(f, n)
    return t
end

using BenchmarkTools

@benchmark ntuple_before(identity, n) setup=(n = rand(0:10))
@benchmark ntuple_after(identity, n) setup=(n = rand(0:10))

But the results behave reproducibly different in different Julia sessions.
Sometimes the early n>=0 check is faster:

Version 0.6.0-pre.beta.367 (2017-04-27 14:08 UTC)
Commit b838f2eec6 (11 days old master)

julia> @benchmark ntuple_before(identity, n) setup=(n = rand(0:10))
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     7.714 ns (0.00% GC)
  median time:      9.419 ns (0.00% GC)
  mean time:        9.758 ns (0.00% GC)
  maximum time:     63.276 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     999

julia> @benchmark ntuple_after(identity, n) setup=(n = rand(0:10))
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     8.712 ns (0.00% GC)
  median time:      10.426 ns (0.00% GC)
  mean time:        10.613 ns (0.00% GC)
  maximum time:     44.453 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     999

Sometimes the late one:

julia> @benchmark ntuple_before(identity, n) setup=(n = rand(0:10))
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     8.378 ns (0.00% GC)
  median time:      10.099 ns (0.00% GC)
  mean time:        10.364 ns (0.00% GC)
  maximum time:     66.474 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     999

julia> @benchmark ntuple_after(identity, n) setup=(n = rand(0:10))
BenchmarkTools.Trial: 
  memory estimate:  0 bytes
  allocs estimate:  0
  --------------
  minimum time:     8.044 ns (0.00% GC)
  median time:      9.738 ns (0.00% GC)
  mean time:        9.867 ns (0.00% GC)
  maximum time:     63.647 ns (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     999

Sacha0 · 2017-05-08T17:53:41Z

Perhaps benchmarking without dependence on random variables would be worthwhile, or at least worth excluding as a potential source of inconsistency?

Sacha0 · 2017-05-08T17:54:45Z

Thanks for going the distance by the way! :) Performance tuning of ntuple and friends is super finicky.

timholy · 2017-05-08T18:06:28Z

Few nanoseconds could be explained by Base.@_inline_meta absence, but not hundreds.

You're probably hitting

julia/base/inference.jl

Line 27 in 25f241c

tupletype_len::Int = 15,

. We may also want to introduce the Any16 fallback like we use for map, just to prevent compile time from exploding. (Try ntuple(identity, Val{1000}) to see what I mean.) That will, of course, slow down the runtime, but it prevents catastrophic behavior.

alyst · 2017-05-08T18:15:41Z

@timholy Yes, from @code_llvm output for the generic ntuple() it looks like this: f is not inlined anymore and there's jl_f_tuple() call for N>=16.

nanosoldier · 2017-05-08T19:38:59Z

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

alyst · 2017-05-10T16:43:04Z

It could be merged without squashing the commits. c6f458e (ntuple(f, Val{N}) fix) should be safe to backport to 0.5 and 0.6.

Sacha0

The present incarnation lgtm! :)

Perhaps @pabloferz could have another look?

pabloferz

LGTM too

Sacha0 · 2017-05-12T03:12:32Z

It could be merged without squashing the commits. c6f458e (ntuple(f, Val{N}) fix) should be safe to backport to 0.5 and 0.6.

@tkelman, squash or no? Best!

martinholters · 2017-05-12T08:12:40Z

The individual commits are all ok, so I'd say no squashing is necessary, and without squashing, we at least keep the option of an easy backport.

otherwise Julia would stuck in an endless type inference loop

alyst · 2017-05-12T23:43:51Z

Rebased to resolve conflicts with the updated NEWS.md (no julia code touched). 2b4bb1a (ntuple(f, Val{N}) fix) could be backported to 0.6.

alyst · 2017-05-13T08:18:56Z

@Sacha0 should be ready to go :)

Sacha0 · 2017-05-13T15:55:59Z

Following martinholters suggestion and merging without squash. Thanks for seeing this through @alyst! :)

otherwise Julia would stuck in an endless type inference loop (cherry picked from commit 2b4bb1a) ref #21697

kshyatt added the compiler:inference Type inference label May 4, 2017

alyst force-pushed the fix_ntuple_val branch from 7913cee to c37009f Compare May 4, 2017 19:08

alyst changed the title ~~Fix ntuple(i -> i, Val{-1})~~ Make ntuple(f, n) and ntuple(f, Val{n}) throw DomainError when n < 0 May 4, 2017

alyst force-pushed the fix_ntuple_val branch from c37009f to 55b79dc Compare May 4, 2017 19:19

fredrikekre reviewed May 4, 2017

View reviewed changes

alyst changed the title ~~Make ntuple(f, n) and ntuple(f, Val{n}) throw DomainError when n < 0~~ Make ntuple(f, n) and ntuple(f, Val{n}) throw ArgumentError when n < 0 May 5, 2017

alyst force-pushed the fix_ntuple_val branch from 55b79dc to 2c7dc16 Compare May 5, 2017 09:10

alyst force-pushed the fix_ntuple_val branch from 2c7dc16 to 31975bf Compare May 7, 2017 21:38

alyst closed this May 8, 2017

alyst reopened this May 8, 2017

Sacha0 reviewed May 8, 2017

View reviewed changes

JeffBezanson added breaking This change will break code error handling Handling of exceptions by Julia or the user bugfix This change fixes an existing bug and removed compiler:inference Type inference breaking This change will break code labels May 9, 2017

Sacha0 approved these changes May 10, 2017

View reviewed changes

pabloferz approved these changes May 12, 2017

View reviewed changes

alyst added 2 commits May 13, 2017 01:33

make ntuple(f, Val{-1}) throw ArgumentError

2b4bb1a

otherwise Julia would stuck in an endless type inference loop

ntuple(f, -1) throws ArgumentError

fc90413

alyst force-pushed the fix_ntuple_val branch from dabd474 to fc90413 Compare May 12, 2017 23:36

Sacha0 merged commit b51b42e into JuliaLang:master May 13, 2017

tkelman pushed a commit that referenced this pull request May 15, 2017

make ntuple(f, Val{-1}) throw ArgumentError

91d0f09

otherwise Julia would stuck in an endless type inference loop (cherry picked from commit 2b4bb1a) ref #21697

Make ntuple(f, n) and ntuple(f, Val{n}) throw ArgumentError when n < 0 #21697

Make ntuple(f, n) and ntuple(f, Val{n}) throw ArgumentError when n < 0 #21697

Conversation

alyst commented May 4, 2017

TotalVerb commented May 4, 2017

timholy commented May 4, 2017

alyst commented May 4, 2017

TotalVerb commented May 4, 2017

tkelman commented May 4, 2017

alyst commented May 4, 2017

alyst commented May 4, 2017

fredrikekre May 4, 2017 • edited Loading

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

Sacha0 commented May 4, 2017

nanosoldier commented May 5, 2017

alyst commented May 5, 2017

alyst commented May 7, 2017

alyst commented May 8, 2017

Sacha0 commented May 8, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

alyst May 8, 2017 • edited Loading

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

alyst commented May 8, 2017

Sacha0 commented May 8, 2017

Sacha0 commented May 8, 2017

timholy commented May 8, 2017

alyst commented May 8, 2017

nanosoldier commented May 8, 2017

alyst commented May 10, 2017

Sacha0 left a comment

Choose a reason for hiding this comment

pabloferz left a comment

Choose a reason for hiding this comment

Sacha0 commented May 12, 2017

martinholters commented May 12, 2017

alyst commented May 12, 2017

alyst commented May 13, 2017

Sacha0 commented May 13, 2017

fredrikekre May 4, 2017 •

edited

Loading

alyst May 8, 2017 •

edited

Loading