for loop over char type runs forever

[AdrianV]

var tab: array[char, int]
for i in tab.low .. tab.high: tab[i] = -1

[reactormonk]

var tab: array[char, int]
echo int(tab.low)
echo int(tab.high)

Gives me

0
255

[AdrianV]

that's not the problem. The loop is translated into:

var res: char = tab.low # 0
while res <= tab.high : 
  yield res
  inc(res) # since res is a char 255 +1 = 0

[Araq]

'inc' lacks overflow checking for now; known issue, I was lazy ... However, I suppose it shouldn't yield an overflow error but instead a specialized 'count' for 'char' should be provided.

[AdrianV]

I think the for loop is flawed, because you cannot loop until the T.high of any integral type.

proc bugLoop[T] () =
  var count = 0
  try :
    for i in T.high -2 .. T.high:
      echo i
      inc count
      if count > 3 :
        echo "should not happen - compiled with overflow checks of ?"
        break
  except EOverflow:
    echo("should not happen - error overflow! ")  

bugLoop[int64]()
bugLoop[int]()
bugLoop[int32]()
bugLoop[int16]()
bugLoop[int8]()

either they throw when overflow checks are on - which is wrong, because it should be legal to loop until the highest value of a type, or even worse when compiled with -d:release they loop forever

[AdrianV]

wouldn't this be better ? - I used 3 dots to test !

iterator `...`[T] (a, b: T): T {.inline.} =
  var i = a
  if i < b :
    while true :
      yield i
      if i == b : break
      inc(i)

[Araq]

Yeah, of course this would be better. Could you please check that performance is not affected in microbenchmarks?

[AdrianV]

on 32 bit I can't measure any differences, but on 64bit its huge. The standard loop is about 80% faster. I guess it's the branch prediction. Therefore I suggest the following iterator (a bit weird) which is as fast as the standard in my tests:

  iterator `..`[T] (a, b: T): T {.inline.} =
    var res: T = T(a)
    while res < b:
      yield res
      inc res
    if res == b : yield res

[Araq]

Interesting but your suggested iterator is unacceptable: Due to the inlining implementation multiple 'yield' statements will duplicate the 'for' loop body! This should blow up the compiler's exe size tremendously; with all its bad effects for the caches. I think we need to live with this limitation and add an 'assert b != high(T)' at the start of the iterator. For 'char' or other smallish types we could make the iteration variable an 'int', but this doesn't work for int64 so it's not a general solution ... Hm, as I guess we should use specialization for 'char' and any enum and live with the limitation for other ordinal types.

[AdrianV]

Ok - I see it when I look at the generated source.

I have tested many different patterns now. The solution which I have now is also weird but as fast as the standard loop. It seems that at least my CPU does the calculation in parallel - while it yields yres it can inc(res) and test if there is an overflow - the inc should be compiled without overflow checks

  iterator `...`[T] (a, b: T): T {.inline.} =
    var res: T = T(a)
    while res <= b:
      var yres = res
      yield yres
      inc(res)
      if res < yres : break

[AdrianV]

BTW I think that an iterator (at least an iterator released under system) should be a promise that it either runs or fails (assert doesn't help here), but never fails with obscure reasons - one thing that holds me back from using c, c++ and others is that. I had never a problem with a for loop in pascal - a for loop in c is a va banque game. If you look at D, it is never able to create a proper for/in loop over an enum or so, because the upper bound is outside of the scope of the range. When I first saw nimrod I saw that the for loop range is sane - one reason for me to look deeper into the language.

[Araq]

Intel Atom doesn't do OOE afaik, so I still don't like it. ;-) Seriously what's so bad about low(int32)..high(int32) failing with an overflow error? Who iterates over 4 billion numbers anyway? It's only useful for full coverage testing and the workaround then is easy enough ... I agree it should work for enums and char and perhaps int16 ... Btw does int32 iteration even work in FPC?

[AdrianV]

Intel Atom is useful only for 32 bit. But yes, widening to int32 is ok. An overflow error at int32.high is pragmatic but not in the spirit ( if I might to say so) - but unless you work in CERN the question who needs to iterate over 2^32 is academic at the moment - but might depend on the algorithm you have in mind - someones code might depend on the logic that a for loop doesn't fail if she/he loops from 2^32 -2 to 2^32-1.
And I remember one guy who said 640kB is all you need in the future. - I have to stop now, otherwise I will quote that a soccer game takes 90 min. ;-)

[AdrianV]

I did some test with different compilers now (gcc, clang, vcc, icl) and the results really, really differ. But the general direction is, that the standard loop is always on top. So one reason more to stay with the default behavior and have a solution for smaller types like char. The problem that is not possible to loop until int.high should be mentioned in the docs and since it is dead easy to introduce your own, safe, but slower iterator, I can't see a real problem for now.

[Araq]

Sure, I was about to add that behaviour to the docs. But then people don't read any docs anyway ... ;-)

[AdrianV]

I would put it more positive - they read the docs, but forget the important facts they have read ;-)