5 ms·

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

by 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"
ufo 8y ago
The macro and type issues are orthogonal. As sabauma pointed out, the tricky bit is that you need one while statement per trace.
bjoli 8y ago
Racket's loops are almost always zero cost, and that is done by specifying the type you are iterating over (in-list, in-string etc). This is generally fine, since when you want to iterate over something you probably already know it's type. That is done by macros and inlining. I wrote similar macros for guile, which has a very handy source to source optimiser.

by shawn 8y ago

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"

ufo 8y ago

The macro and type issues are orthogonal. As sabauma pointed out, the tricky bit is that you need one while statement per trace.

bjoli 8y ago

Racket's loops are almost always zero cost, and that is done by specifying the type you are iterating over (in-list, in-string etc). This is generally fine, since when you want to iterate over something you probably already know it's type. That is done by macros and inlining. I wrote similar macros for guile, which has a very handy source to source optimiser.