4 ms·

I'm amused by the "Lift" naming trend for code generators. Mozilla's next gen code generator for wasm will be called "Cranelift" [1]. Probably coincidence. [1]

• tlb 8y ago
  "lifting" is a common optimization -- moving a computation from inside a loop to outside. It can make a huge difference in numerical functions. For instance, consider the JS code: for (let i=0; i<a.length; i++) { a[i] = a[i]*2 } Without lifting, every time through the loop it has to check that a is an array and (i >= 0 && i < a.length). Lifting lets the compiler move all the checks before the loop and do them once. It's nontrivial to check that the truth value of the check can't possibly change during the loop.
  • otras 8y ago
    I may be missing something here. Given that i is incremented in the loop, wouldn't the truth value of (i < a.length) change? Or do you mean the two other checks (a is an array and i>= 0)?
    • Jasper_ 8y ago
      For a[i] to be valid, i has to be < a.length. This invariant is never invalidated during the loop body itself.
      • otras 8y ago
        I think I'm following, but I'm not sure I completely understand. From the GP: > Without lifting, every time through the loop it has to check that a is an array and (i >= 0 && i < a.length). It sounds like these checks are being performed once. Does that mean that instead of it checking in the loop, it's checked prior to and outside of the loop body? Otherwise, I'm not sure how the value of (i < a.length) wouldn't change as the loop is performed multiple times, as the increment expression is called after every loop. Thanks for your help!
        • kiriakasis 8y ago
          I think it is that since the length is never mutated in the body the check can be simplified. From a generic dictionary lookup to comparison to a constant int.
        • codefined 8y ago
          for (let i = 0; i < a.length; i++) { a[i] = a[i]*2 } Has to be converted into something that can be run onto a machine that won't cause a fatal error if the array `a` doesn't have an item at index `i` (e.g. negative index). It can be converted to the following by a naive compiler: for (let i = 0; i < a.length; i++) { if (i > 0 && a < a.length) { // safe to access a[i] = a[i] * 2 } else { throw('in a safe way') } } Or, to avoid repetitive checks to a.length: const temp = a.length for (let i = 0; i < temp; i++) { if (i > 0 && a < temp) { // safe to access a[i] = a[i] * 2 } } A more advanced compiler might realise that the if statement is irrelevant, we've defined it in the loop that we'll never have a negative `i` or one above the length of the array, so we can just avoid those checks entirely and actually revert back to the original code to compile. This is not always the case: const temp = a.length for (let i = 0; i < temp; i++) { a[i] = a[i]*2 } This comes up in interesting places, like why it is faster to go through an array backwards than forwards[0]. [0] https://stackoverflow.com/questions/8689573/why-is-iterating-through-an-array-backwards-faster-than-forwards https://stackoverflow.com/questions/8689573/why-is-iterating...
        • lomnakkus 8y ago
          If the array structure itself were being modified, the "i < a.length" check would have to be done every iteration, but in this case there's no mutation of the array itself, so it's OK to move "a.length" to a constant outside the loop... and from there it's trivial to move bounds checks outside the loop (and from there: eliminate them entirely)
  • kodablah 8y ago
    "Lifting" is also a common term for disassembling from assembly code back to a workable IR, though probably not an intended use here of course.