5 ms·

Basic Block Versioning – My Best Result Yet

75 points by dmit 11y ago

ndesaulniers 11y ago
The author has done some really cool talks as a guest speaker at Mozilla HQ before: https://air.mozilla.org/higgs-jit/ https://air.mozilla.org/higgs-jit/ I think about meta-circular interpreters, IIRC. The JIT being discussed is written in D.
nwmcsween 11y ago
Hmm I'm guessing the BBV is going to have an impact on code size and cache misses due to versioning. BBV sounds like a great mix with an effects system.
- maximecb 11y ago
  The ECOOP 2015 paper examines the code size issue. The bottom line is that code is often smaller because it's better optimized, has less type checks and boxing/unboxing. What kind of information do you think it would be useful to propagate about effects?
FullyFunctional 11y ago
This is very interesting. My immediate thought was what this could do for languages with arbitrary sized integer. Those are generally implemented using tagged pointers for small integers and "changes types" when arithmetic on them overflows. If BBV can determine type operands are tagged integers then arithmetic only have to worry about overflow and not the type checking. I don't know if anyone has tried to do anything similar.
- maximecb 11y ago
  JavaScript is typically implemented with small integers that overflow into doubles. Higgs is very effective at eliminating type tests on numerical values. It's difficult to eliminate overflow checks in general, but Higgs uses BBV to do some primitive overflow check elimination that can take care of the "for (i=0;i<n;i++)" case.
  - FullyFunctional 11y ago
    I'll take that as a confirmation of feasibility. Among the languages who integer types default to unbounded, I can think of Python, Erlang, and Scheme (Others? Haskell has both Int and Integer), but it doesn't appear that BBV has been tried outside of Higgs. I guess I could get close by changing something like https://github.com/peterolson/BigInteger.js https://github.com/peterolson/BigInteger.js to use native JavaScript numbers for small integers. One of these days.
rwmj 11y ago
I prefer static typing because it finds more bugs at compile time. However my statically typed code (in OCaml) still contains occasional runtime type checks, and inefficiencies because polymorphic functions can't be specialized. I wonder if BBV or similar techniques could be used to improve that?

75 points by dmit 11y ago

The author has done some really cool talks as a guest speaker at Mozilla HQ before: https://air.mozilla.org/higgs-jit/ https://air.mozilla.org/higgs-jit/ I think about meta-circular interpreters, IIRC. The JIT being discussed is written in D.

nwmcsween 11y ago

Hmm I'm guessing the BBV is going to have an impact on code size and cache misses due to versioning. BBV sounds like a great mix with an effects system.

maximecb 11y ago
The ECOOP 2015 paper examines the code size issue. The bottom line is that code is often smaller because it's better optimized, has less type checks and boxing/unboxing. What kind of information do you think it would be useful to propagate about effects?

FullyFunctional 11y ago

This is very interesting. My immediate thought was what this could do for languages with arbitrary sized integer. Those are generally implemented using tagged pointers for small integers and "changes types" when arithmetic on them overflows. If BBV can determine type operands are tagged integers then arithmetic only have to worry about overflow and not the type checking. I don't know if anyone has tried to do anything similar.

maximecb 11y ago
JavaScript is typically implemented with small integers that overflow into doubles. Higgs is very effective at eliminating type tests on numerical values. It's difficult to eliminate overflow checks in general, but Higgs uses BBV to do some primitive overflow check elimination that can take care of the "for (i=0;i<n;i++)" case.
- FullyFunctional 11y ago
  I'll take that as a confirmation of feasibility. Among the languages who integer types default to unbounded, I can think of Python, Erlang, and Scheme (Others? Haskell has both Int and Integer), but it doesn't appear that BBV has been tried outside of Higgs. I guess I could get close by changing something like https://github.com/peterolson/BigInteger.js https://github.com/peterolson/BigInteger.js to use native JavaScript numbers for small integers. One of these days.

rwmj 11y ago

I prefer static typing because it finds more bugs at compile time. However my statically typed code (in OCaml) still contains occasional runtime type checks, and inefficiencies because polymorphic functions can't be specialized. I wonder if BBV or similar techniques could be used to improve that?