[VB] For-Loop Overflow and Underflow

[AdamSpeight2008]

Issue in VB Repo
The follow will throw a System.OverflowException due to the underlying implementation details.

For value = Byte.MinValue To Byte.MaxValue
   Console.Write($"{value}  ")
Next

We should consider changing the lowering to better handle the cases which approach the numerical type's MIn or Max values.

suggested lowering form, which should all current allowed for-loop forms.

Dim __Value__ = StartValue
While True
  Body( __Value__)
  Dim __delta__ = Math.Abs( __EndValue__ - __Value__ )
  If __delta__ <= Math,Abs(__Step__) Then Exit While
  __Value__ += __Step__
End While

[rskar-git]

@AdamSpeight2008 I'm concerned that any attempt to address this design flaw in today's For ... Next is going to hurt performance, not to mention flub-up those (perhaps foolish) souls who depended on the final value after the last iteration in their code.

Wouldn't it be better to somehow make specialized "lowered code" for Byte/SByte/Short/UShort, pretty much in the style that @ericmutta already does in his work-around (using an Integer then casting to Byte)? I think the work-around might even be slightly faster, since conversion of Integer to Byte is cheap, and it's generally better to use a CPU's native-size int. (In my own testing, using VS 2015, the work-around runs about the same as the pure-Byte approach, and maybe slightly faster.)

[AdamSpeight2008]

@rskar-git It being a Byte as nothing to do with the issue. All of the Integer types suffer from the same problem.

[rskar-git]

@AdamSpeight2008 Yep, I got that. Yet Byte has everything to do with how this issue came to light in the first place. Whether For ... Next or for(;;), this several-decades old approach to looping has the fatal flaw of when the loop's arithmetic takes it outside of T.MinValue..T.MaxValue.

However, this approach is now, and has been for quite a long time, the "devil we know." And, for good or ill, people have made use of the side-effect. Hence one of my worries about the possibility of a breaking change (the other being performance).

[AdamSpeight2008]

What are the current workarounds?

• Use larger integer type, and cast back down.
  • At some point there going no more larger type.
• Try ... Catch o As OverflowException
  • Using executions for control flow.
  • Slow
• Special case the last value and repeat the code inside the loop.

We could enable the safety via an option Option NoOverflowLoops.

[rskar-git]

@AdamSpeight2008 The suggested lowering form above won't work with signed types (it can overflow at fourth line, __EndValue__ - __Value__). (Also, minor bug at fifth line, should be If __delta__ < Math.Abs(__Step__) Then Exit While - otherwise it could skip final value.)

Another proposal to consider:

' For v As T = r0 To r1 Step dv
Dim IsDownTo As Boolean = dv < 0
Dim vEdgeLo As T = If(IsDownTo, T.MinValue - dv, T.MinValue)
Dim vEdgeHi As T = If(IsDownTo, T.MaxValue, T.MaxValue - dv)
Dim v As T = r0
While If(IsDownTo, v >= r1, v <= r1)
    Body(v)
    If If(IsDownTo, v < vEdgeLo, v > vEdgeHi) Then Exit While
    v += dv
End While

When possible, it preserves the legacy side effect; otherwise by design it won't suffer overflow/underflow. (I suspect that if unchecked integer arithmetic/converision was more readily available in VB, we could make a much better alternative.)

I should still point out that employing a 32-bit integer type and then casting back down works well for the 8-bit and 16-bit integer types, and runs efficiently for both Debug and Release compiles. In Release, its performance is the same as a pure 8-bit/16-bit implementation. In Debug, even though it runs about 15% slower versus a pure 8-bit/16-bit implementation, the performance nonetheless beats both "suggested lowering form above" and "another proposal" by a wide margin (they are each like >70% slower).

Employing a 64-bit integer type and then casting back to 32-bit works OK too. However, at this point in time, people would have already made their own specialized work-arounds for their Int32.MinValue to Int32.MaxValue use cases. I really don't think we need to make a fix for the 32-bit case.

I can't imagine anyone doing Int64.MinValue to Int64.MaxValue (2^64 is mind-bogglingly hugh!), but I think they would use the same code pattern as they did for the 32-bit situation. And a super computer, like maybe a Cray.

Anyway, I'm still of the opinion of leaving For...Next as-is, unless there is some way we could select an optimized lowering form based on certain discernable characteristics.

For example, I would suppose that if the Step is a constant of 1, and that the scope of the indexing variable was restricted to the code block of the For (i.e. For v As T = ...), then we could select the lowering form specialized for this case:

If __Start__ <= __End__ Then
    __Value__ = __Start__
    While True
        Body(__Value__)
        If __Value__ >= __End__ Then Exit While
        __Value__ += 1
    End While
End If

[AdamSpeight2008]

It would be nice to have compile-time verified templates so we can optimise the generated code.

Template Templated_ForLoop(
                            _Start_ As ConstExpr,
                            _End_   As ConstExpr,
                            _Step_  As ConstExpr,
                            Body    As Expression,
                            Cmp     As Operator.Comparision,
                            deltaFunc As ...,
                            op      As Operatior.Binary
                          )
  Dim _Value_ = %{ _Start_ }%
  While True
    Body(_Value_)
    If _Value_ %{Cmp}% %{_End_}% Then Exit While
    Dim _delta_ = %{ deltaFunc }%
    If _delta_ > Abs( %{ _Step_ }% ) Then Exit While
    _Value_ = _Value_ %{ op }% %{ _Step_ }% 
  End While
End Template

' Ascending
Templated_ForLoop( _Start_ , _End_ , _Step_ , Body , Operator.Comparision.GE, ${ %{ _End_ } - %{ _Value_ }%, Operator.Binary.Addition )
' Descending
Templated_ForLoop( _Start_ , _End_ , _Step_ , Body , Operator.Comparision.LE , ${ %{ _Value_ } - %{ _End_ }%, Operator.Binary.Subtraction )

[rskar-git]

Yep, compile-time verified templates do seem like a very nice thing.

However, I've been experimenting on this for much of yesterday, and have come to the conclusion that today's CPU is optimized around the idiomatic for(v=r0; v<=r1; v+=dv){ ... }, and any attempt to stray from that idiom comes at a performance price. The Debug compile is the first indication of trouble. The Release compile sometimes repairs the performance loss, but along with whatever optimizations it may make, there are also the CPU tricks such as caching and branch predictions that will certainly hide performance issues that may happen for lesser CPUs.

The Option NoOverflowLoops concept might be a fair compromise, as it allows one to opt-in or opt-out, but it would be an all-or-nothing choice for a module, which will make for performance trouble again if not every loop needs the overflow protection. I suppose nobody cared for the For n As T In RangeOf(...) idea. How about something like this, then:

For(Of Integer) n As Byte = Byte.MinValue To Byte.MaxValue
    UseByteValue(n)
Next

This indicates to the compiler to use Integer for the indexing, but to then cast back to Byte into n. This concept may be interesting for other kinds of number crunching:

For(Of Decimal) x As Single = CDec(-1000.0) To CDec(+1000.0) Step CDec(+0.000001)
    UseSingleValue(x)
Next

[AnthonyDGreen]

Hey guys, I think it's premature to split this discussion off from the language repo. We still haven't made a decision there and having people discuss across two threads is a pain. We'll discuss execution on this repo when and if we decide to do anything.