[bjourne]

> Another point with the above loop, is that ideally, even if it can't be optimized/memoized down to a constant - it really shouldn't have to be much slower than its C counterpart. Except for handling bignums in some way or other (perhaps on overflow only).

Sadly, bignum handling is very expensive even with type hinting. Essentially, every time two numbers is added or subtracted you have to check for overflow:

    int z = hw_add(x, y);
    if (over/under-flowed?()) {
      bignum* bn = new bignum();
      bignum_add(to_bignum(x), to_bignum(y), &bn);
      return bn;
    }
    return z;

So most modern statically typed languages (none named, none forgotten!) actually cheat and use modular arithmetic instead. For example, the straightforward way of computing 9223372036854775807 + 1 on a 64bit system in one of those languages is likely to yield an incorrect result.

Which imho is complete bullshit because there is no reason to sacrifice correctness for performance other than to win benchmarking contests.

[rurban]

This overflow check is extremely cheap. Just check the overflow flag on the cpu. jo +4; jmp bignum; 6 byte. C compilers didn't support it until last year, so everyone just used inline assembly. Now we have it in gcc 5 and clang 3.4

One good trick started by lua is to use double for everything and check the mantissa of the normalized result for overflows. A double can represent the whole int32 range. With double and nan-tagging you have a unique fast representation of all primitives and can use a double word stack. Which is the biggest win. Look at how python, perl and ruby are doing this. Horrible. And then look how a fast dynamic language is doing it.

[bjourne]

Everything is relative. :) Compared to the add instruction itself, the overflow check is very expensive. But the big problem is that your types widen. E.g:

    // x and y are hardware integers >= 0
    var z = x + y
    for (var i = 0; i < z; i++) {
        ...
    }

If your language used modular arithmetic, 'z' would also be a hardware integer and the induction variable 'i' could be kept in a cpu register. But with real arithmetic using bignums you can't assume that anymore and each iteration of the loop must do a relatively expensive comparison of 'i' against 'z'. In pseudo code:

    var z = x + y
    var i = 0
    if (!hw_int(z)) i = new_bignum(0)
    while (true) {
      // i < z
      if (hw_ints?(i, z)) {
        if (i >= z) break
      } else {        
        if (bignum_gte(i, z)) break
      }        
      ... body ...
      // i++
      if (hw_int?(i)) {
        i++;
      } else {
        i = bignum_add(i, 1)
      }
    }

[rurban]

No, it's super cheap. overflows happen <1%, so you mark it as UNLIKELY, and the branch prediction units just don't care about all those bignum branches.

If you know to use bigints or bignums, just type it and use their variants from the beginning.

Most better dynamic languages already use tagged ints, so they have only say ~30bits for an int and do a lot of those overflow checks and still beat the hell out of the poorly designed dynamic languages with full boxed ints or nums.