Julia: uncaught iterate overflow for StepRange

[johnnychen94]

I believe this overflow is unwanted.

julia> I = 1:2:typemax(Int)
1:2:9223372036854775807

julia> iterate(I, last(I))

julia> iterate(I, last(I)-1)
(-9223372036854775808, -9223372036854775808)

julia> iterate(I, last(I)-2)
(9223372036854775807, 9223372036854775807)

Another behavior that might be related to this:

julia> iterate(Base.OneTo(5), 6)
(7, 7)

Should this return nothing or (7, 7)?

Related lines are:

https://github.com/JuliaLang/julia/blob/9392bbe347226fb6686d5ddb77717b0ab5142902/base/range.jl#L651-L664

[haampie]

iterate(x, i) shouldn't be seen as indexing x at index i; i is the iterator state, and valid iterator states are obtained through calling iterate(x) and iterate(x, curr_state) successively. In iterate(Base.OneTo(5), 6) you are using an invalid iterator state, so the resulting value shouldn't really matter.

The same holds for iterate(I, last(I)-1): last(I) - 1 is an invalid iterator state.

[johnnychen94]

Thanks for the explanation, this makes sense to me.

This issue was raised when I try to add overflow test cases and I was a bit confused about how overflow should be checked.

Another aspect of not doing such eager checking, IMO, is that this terribly hurts the performance. For example, in https://github.com/JuliaLang/julia/pull/37829#discussion_r498691929 the loop without such eager overflow checking takes about 15ns and the one with takes 37ns, which is something we don't want to pay.

[haampie]

Hm, what change would you propose to improve performance generally? One issue to keep in mind is you can't assume you have a sentinel value in ranges like typemax(Int)-1:typemax(Int) and typemin(Int):typemax(Int), that's why this iterator uses i == last(r).

I don't immediately see issues in simple loops:

julia> function steprange_iter(a, k)
         x = 0.0
         for i = 1:k:length(a)
           @inbounds x += a[i]
         end
         x
       end

julia> function manual_iter(a, k)
         x = 0.0
         i = 1
         while i <= length(a)
           @inbounds x += a[i]
           i += k
         end
         x
       end

julia> @code_native debuginfo=:none steprange_iter(rand(100), 3)
...
L80:
    vaddsd  (%rcx,%rdx,8), %xmm0, %xmm0
    addq    %rbx, %rdx
    cmpq    %rdx, %rax
    jne L80
...

julia> @code_native debuginfo=:none manual_iter(rand(100), 3)
...
L32:
    vaddsd  -8(%rcx,%rdx,8), %xmm0, %xmm0
    addq    %rsi, %rdx
    cmpq    %rax, %rdx
    jle L32
...

So yeah, you can see there's a jne in the one and a jle in the other, otherwise the inner loop is identical.

[johnnychen94]

Sorry for the confusing word choices, I meant to say "by removing those eager checks in my PR, the performance can be improved quite significantly"

The eager cheks, though, is specific in my PR https://github.com/JuliaLang/julia/pull/37829/commits/4b47f634241b22e01bd8bbd3084d272033cf56dc#diff-89e97f67f8058d32eac8d917db5bbdbfR407-R433 where I did a lot of checks on boundary and steps. Those checks can be possibily simplified into i == last(r) just like ranges.

[haampie]

Oh, so you're saying adding a bunch of checks improves performance? That's interesting :p

[johnnychen94]

😂 the opposite.

Adding a bunch of checks increases the time from 15ns to 37ns, which is not very acceptable for such basic operations.

[haampie]

Ok, then I got it right the first time :laughing:.