Optimization: lambda lifting

[splitice]

I've seen talk about RaptorJIT as LuaJIT's successor so I figured I'd cross post this issue from LuaJIT.

LuaJIT/LuaJIT#499

[lukego]

Is it reasonable to say that lambda-lifting would be a feature of the bytecode compiler rather than the JIT? Since the bytecode compiler is a single-pass C program I am not sure how much fun it is to add new features and optimizations there.

Seems there are options for how to handle this kind of optimization moving forward...

• Document the limitations of the compiler (e.g. can't lambda-lift) and write DSLs accordingly (do it while generating Lua code.)
• Implement these kind of optimizations in the current bytecode compiler which is a single-pass C program.
• Write a new bytecode compiler and do these optimizations there e.g. using Lua instead of C (Idea: Write Lua parser and bytecode compiler in Lua #248.)

btw the example code errors for me when I test it with luajit v2.1:

48: attempt to call upvalue '_a2' (a string value)

[lukego]

Generally there should be a disclaimer somewhere the the current compiler is quite simple and literal. If you are using it as an intermediate representation for a compiler you should really know that ahead of time.

For example if you write this in your source code:

for i = 1, 1000000 do end

then what you will get is a program that counts to one million, whether that is bytecode compile or JITed, because that is the "what ask for is what you get" approach that the compiler takes in these cases.

Mike Pall highlighted this as a deliberate choice when he gave his talk about LuaJIT in Zurich some years back.

[splitice]

Alright I re-tested and fixed the example code (and benchmark). It's what I get for doing a quick fix to the posted code, I made it worse.

I'm certain this kind of work won't be "fun" but this pattern is so very common from my observation.

Another example where lambda lifting would help is in logging. Currently our developers have to weigh up the cost of:

function log(exec_or_print)
if DEBUG then
-- ... exec then print
end
end

log(function() return "this is a test message "..with_an_element_of_dynamic(errno_or_something) end)
-- vs
log("this is a test message "..with_an_element_of_dynamic(errno_or_something))

The cost of the closure being rather high normally means that the second form is more optimal (unless with_an_element_of_dynamic is particularly high cost). With inlining it's possible the cost could be only the conditional check.

Last year we wrote a pre-processor for removing log statements from production builds of one project, it shaved almost 10% off our execution while eliminating less than half the calls to the logger (reliably post-processing via regex is difficult).

I assumed that in-lining like this would be best done at the JIT level. The only other JIT I've played with is C#/dotnet and it's JIT is certainly state of the art. From what I remember it does inlining at both compile time based on method size and during JIT.

It might be wise if attempting an implementation to initially restrict the feature only to pure closures that do not modify their upvalues.

Documentations on the what the optimizer is capable of would certainly be a good idea. Knowing what I know now I would have certainly put more effort into the DSL with the hopes of eliminating some of the closures.

[splitice]

On a related note this has been attempted by @katlogic in his LuaJIT fork before. I don't believe he got it stable in the end however.

https://github.com/katlogic/ljx/blob/14f276b34cc7afc4d221ca6d638730a254d53dc7/src/lj_func.c

[hippi777]

hi there! :)

Mike Pall highlighted this as a deliberate choice when he gave his talk about LuaJIT in Zurich some years back.

wow! ive thought that Mike is invisible, i didnt find the talk, does it have a record? id like to see the legend! :D

thx and bests! :)

[lukego]

wow! ive thought that Mike is invisible, i didnt find the talk, does it have a record? id like to see the legend!

Here's the only historical record that I can find now: https://www.meetup.com/en-AU/zhgeeks/events/141272252/

Somebody should invite him to give another talk and get a recording of that.

[hippi777]

thx! :)

ive found that, and the notes as well, however i believe its intentional. :D there are ppl out there who simply dont like reflector lights, but thats fine... :) just think about Tesla, and im not saying if would be necessarily my image about Mike, get it only as a wild guess, or better said, just a probability of many that i can think and nothing more than that... otherwise this makes much harder to resolve issue 45 for lj... :D (checklist for resolving starts with: "Obtain DNA/RNA and create a viable cloning method.")

have a nice day and stuffs like that! :)