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:

julia/base/range.jl

Lines 651 to 664 in 9392bbe

	function iterate(r::Union{LinRange,StepRangeLen}, i::Int=1)
	@_inline_meta
	length(r) < i && return nothing
	unsafe_getindex(r, i), i + 1
	end
	iterate(r::OrdinalRange) = isempty(r) ? nothing : (first(r), first(r))
	function iterate(r::OrdinalRange{T}, i) where {T}
	@_inline_meta
	i == last(r) && return nothing
	next = convert(T, i + step(r))
	(next, next)
	end

[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 #37829 (comment) 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 4b47f63#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 😆.