5 ms·

I've been thinking along these lines as well. One of my dirty secrets is that I'm jealous of Rust's zero cost iterators. I want those in JS and Lua. One way to

by shawn 8y ago

I've been thinking along these lines as well. One of my dirty secrets is that I'm jealous of Rust's zero cost iterators. I want those in JS and Lua. One way to get them is to write an interpreter for a specialized subset of the language, and generate traces for each part of your program that uses e.g. map and reduce. It seems possible to specialize the generated code so that the overhead is essentially zero cost, but I haven't thought about it deeply enough yet. There must be a way to get Rust's zero cost abstractions without the steep penalty of static typing plus borrow checking annotations.

ufo 8y ago
Macros, perhaps? Tracing JITs actually can have a hard time with map and reduce because they can't always tell that different calls to map should be compiled with different traces. If you try to use the same trace for map(f) and map(g) you are going to fall out of the trace often. For an example of this issue coming up see https://github.com/luafun/luafun/issues/32 https://github.com/luafun/luafun/issues/32
- shawn 8y ago
  Whoa. Why does that happen? The first call does indeed compile down to a tight loop of around 10 instructions. However, the second call compiles down to around 62 instructions - even though it is exactly the same code! That seems like a bug rather than a consequence of tracing JITs, isn't it? Macros are one possibility, but they require global knowledge at compile time, which is at odds with the dynamic nature of scripting languages. Suppose you want to write a function `f` which takes some object `x` and calls `str(x)` on it. If you know the type of `x` at compile time, it's a simple matter to substitute `str(x)` with `x.str()`, if you know it contains a `str()` method. The other code would look like this: (define-global str (x) (if (and (obj? x) (get x 'str)) (call (get x 'str)) ... else stringify `x` as normal )) i.e. you'd have to write a `str` function that checks the type of `x` at runtime, incurring a cost. A strongly typed language is one possibility, but it seems like we could do better by tracing at runtime. When you know that `x` has a method `.str()`, shouldn't it be possible to replace all instances of `str(x)` with `x.str()` at the call sites themselves? Just recompile all the functions that call `str(x)`. Then you can even inline the str() method's code directly into the call site.
  - sabauma 8y ago
    This is indeed a consequence of tracing. The problem is that traces are associated to loops in the program, and since the map function contains only one loop, all traces for map are associated to the loop in its implementation. When you manually write a loop, there is only one 'body', so a tracing JIT turns that into a single or small number of traces. For the loop inside of map, you need to produce side exits and new traces for each function passed in. The more times map is used, the slower it gets. This is made worse by the fact that traces out of side exits tend to not be optimized nearly as well. Pycket has this same issue with its builtin (or hand written) looping _functions_ like map. Fortunately, Racket provides many useful looping macros which allows Pycket to generate unique traces for each loop, ameliorating this problem somewhat in Pycket.
    - shawn 8y ago
      For the loop inside of map, you need to produce side exits and new traces for each function passed in. Is it true to say that if two functions have the same body and arglist, and capture no variables, then you should be able to reuse the same traces? This doesn’t happen very often in real code, but it’s useful to understand the problem.
      - akiselev 8y ago
        I think in the case of a JITed function in a dynamic language, whether the body is the "same" or not depends on how the interface used by the function is monomorphized - which in turn depends on the trace.
      - ufo 8y ago
        In theory if you call map again with an identical function it should still fall inside the original trace. Tracing JITs effectively inline all function calls that happen inside the trace so if two functions contain the same body they would be indistinguishable. But there are all sorts of reasons why this might not be happening in that bug report I linked to. It might be due to the definition of the map and reduce functions (luafun adds lots of features to them, so its not just a simple straightforward loop) or it could be due to something about luajit (it is a complex piece of software after all). The only way to know for sure would be to examine the traces with "luajit -jdump"

by shawn 8y ago

ufo 8y ago

Macros, perhaps? Tracing JITs actually can have a hard time with map and reduce because they can't always tell that different calls to map should be compiled with different traces. If you try to use the same trace for map(f) and map(g) you are going to fall out of the trace often. For an example of this issue coming up see https://github.com/luafun/luafun/issues/32 https://github.com/luafun/luafun/issues/32

shawn 8y ago
Whoa. Why does that happen? The first call does indeed compile down to a tight loop of around 10 instructions. However, the second call compiles down to around 62 instructions - even though it is exactly the same code! That seems like a bug rather than a consequence of tracing JITs, isn't it? Macros are one possibility, but they require global knowledge at compile time, which is at odds with the dynamic nature of scripting languages. Suppose you want to write a function `f` which takes some object `x` and calls `str(x)` on it. If you know the type of `x` at compile time, it's a simple matter to substitute `str(x)` with `x.str()`, if you know it contains a `str()` method. The other code would look like this: (define-global str (x) (if (and (obj? x) (get x 'str)) (call (get x 'str)) ... else stringify `x` as normal )) i.e. you'd have to write a `str` function that checks the type of `x` at runtime, incurring a cost. A strongly typed language is one possibility, but it seems like we could do better by tracing at runtime. When you know that `x` has a method `.str()`, shouldn't it be possible to replace all instances of `str(x)` with `x.str()` at the call sites themselves? Just recompile all the functions that call `str(x)`. Then you can even inline the str() method's code directly into the call site.
- sabauma 8y ago
  This is indeed a consequence of tracing. The problem is that traces are associated to loops in the program, and since the map function contains only one loop, all traces for map are associated to the loop in its implementation. When you manually write a loop, there is only one 'body', so a tracing JIT turns that into a single or small number of traces. For the loop inside of map, you need to produce side exits and new traces for each function passed in. The more times map is used, the slower it gets. This is made worse by the fact that traces out of side exits tend to not be optimized nearly as well. Pycket has this same issue with its builtin (or hand written) looping _functions_ like map. Fortunately, Racket provides many useful looping macros which allows Pycket to generate unique traces for each loop, ameliorating this problem somewhat in Pycket.
  - shawn 8y ago
    For the loop inside of map, you need to produce side exits and new traces for each function passed in. Is it true to say that if two functions have the same body and arglist, and capture no variables, then you should be able to reuse the same traces? This doesn’t happen very often in real code, but it’s useful to understand the problem.
    - akiselev 8y ago
      I think in the case of a JITed function in a dynamic language, whether the body is the "same" or not depends on how the interface used by the function is monomorphized - which in turn depends on the trace.
    - ufo 8y ago
      In theory if you call map again with an identical function it should still fall inside the original trace. Tracing JITs effectively inline all function calls that happen inside the trace so if two functions contain the same body they would be indistinguishable. But there are all sorts of reasons why this might not be happening in that bug report I linked to. It might be due to the definition of the map and reduce functions (luafun adds lots of features to them, so its not just a simple straightforward loop) or it could be due to something about luajit (it is a complex piece of software after all). The only way to know for sure would be to examine the traces with "luajit -jdump"