AST vs. Bytecode: Interpreters in the Age of Meta-Compilation [pdf]

https://stefan-marr.de/downloads/oopsla23-larose-et-al-ast-vs-bytecode-interpreters-in-the-age-of-meta-compilation.pdf

by mpweiher • 3 years ago

99 47 3 years ago

stefan-marr.de

punnerud• 3 years ago

Fun fact, Python give you access to AST: https://docs.python.org/3/library/ast.html

You can easily check that Python Dict is just keys and pointers to values: Dict(expr* keys, expr* values)

sottol• 3 years ago

These features are always nice for meta-magic and monkey-patching but those are usually exactly the reasons why a language can only be optimized so much. It's often a worthwhile tradeoff but needs to be carefully considered.

amno5• 3 years ago

Is "meta-magic" and "monkey-patching" what we mortals call code generation and which is an useful technique to automate coding and which can both save time and generate safer and more correct code or is it something else?

nabla9• 3 years ago

These features with the option to declare not to use them in a piece of code that are the reasons why language don't have to make trade-offs.

Common Lisp has good balance in this regard.

progval• 3 years ago

This is a grammar: stars mean they are repeated, not pointers.

chubot2• 3 years ago

Yes, the language there is Zephyr ASDL [1]. I actually changed this:

    Dict(expr* keys, expr* values)

    Dict(List[expr] keys, List[expr] values)

in our fork for https://oilshell.org/ , and it made a lot more sense to contributors.

It's funny how "sticky" syntax is -- two contributors ALSO read * as "pointer" ! So I changed it to be consistent with MyPy syntax earlier this year, and now I think I should have done that a long time ago.

(It would also make sense to change it to keys: List[expr], as that's the Python 3 syntax for types)

---

The funny thing is that while the web page says "Abstract Grammar", I would not call Zephyr ASDL a grammar.

Python has a separate Grammar/Grammar file, that is distinct from this file Python/Python.asdl.

A grammar describes a set of strings, and that's not what ASDL does.

It describes the data structure that the valid strings get transformed to after parsing, and there is not a 1:1 correspondence (e.g. due to the difference between a CST and AST, and other post-parsing validation).

I mentioned that here: https://www.oilshell.org/blog/2016/12/11.html#it-describes-a...

(Pretty sure "ungrammar" from rust-analyzer is nodding at this -- https://rust-analyzer.github.io//blog/2020/10/24/introducing... -- it's "ASDL for concrete syntax trees", i.e. it's not a grammar because it doesn't describe strings; it describes trees)

[1] https://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL

secondcoming5• 3 years ago

I am experimenting with runtime generation of shared libs.

We have a database of rules in the form 'A OR (B AND C)' stored just like that in human readable form. The current implementation creates an AST of the expression and executes it via the visitor pattern. The problem with this is it's slow and there can be recursion problems if the expression is too complex.

I've shown it's actually quite easy to translate these expressions to C code, and then compile that to machine code. My only real concern is around loading and unloading shared libs at runtime. These expressions are updated every hour or so.

It is possible to strip the .text section from a binary and then mmap() it to executable memory, which has the advantage of not having to deal with reference counts in shared libs. The disadvantage is that the generated C code must just be code, no state of its own.

I'm still unclear on which option is best.

mike_hearn2• 3 years ago

What's the problem with dlopen and dlclose? Or LoadLibrary/FreeLibrary on Windows? Loading and unloading shared libraries is a perfectly normal thing to do, there's no issue with it. Where it may get complex is if you want to have new and old versions active simultaneously - then you'd need to be careful about namespacing and symbol scoping.

But you didn't mention what language the rest of your server is written in. If you read the paper, it talks about Truffle/Graal, which is a compiler system that JIT compiles AST interpreters. So if you're working on the JVM, you could instead write (or reuse) a simple interpreter for your expression language that uses the Truffle annotations, and switch to the GraalVM as your JDK. Then it'd get faster automatically and you don't have to think about compilers, shared libraries or whatnot. Of course you don't need Truffle. For a simple language you could also generate bytecode and load that into a classloader. It's not particularly complex.

But if you want to stick with C then I'd just go ahead and load/unload shared libs on the fly. Just make sure you don't unload one whilst a thread is still inside it.

secondcoming5• 3 years ago

The rest of the server is C++. And yes, the problem is that there will temporarily be two libs active simultaneously for a few seconds. I'll need to think it through. Sounds like a debugging nightmare if things go wrong.

JonChesterfield2• 3 years ago

It might be best to emit machine code directly to memory. Template JIT style.

Removes hazards like the C compiler putting jump tables in .rodata, has some nice properties like you can emit calls to functions in the address space as literal address instead of using a loader to patch them from relocation tables.

secondcoming5• 3 years ago

That's interesting about jump tables in .rodata. That would break everything indeed.

I really want the C compiler to do all the work. If I was to emit the machine code myself it would end up just being stack based anyway, I think.

samsquire• 3 years ago

I wrote the beginnings of a JIT compiler here (with help from Martin Jacob)

https://GitHub.com/samsquire/compiler

See jitcompiler.c

The code might be helpful.

pritambaral• 3 years ago

... you can emit calls to functions in the address space as literal address instead of using a loader to patch them from relocation tables.

Technically, dlopen can do this too, except it'd make dlopen() slower.

My toy compiler's C backend does just that: emit ELF files with relocation tables but load them and patch all relocations to direct addresses instead of PLT/GOT jump.

tonyedgecombe• 3 years ago

I wonder if switching to byte code rather than using the visitor pattern would give you a big enough performance improvement.

DylanSp5• 3 years ago

I had the same thought; a simple bytecode VM shouldn't be too bad to implement (famous last words...), and the improvement in cache locality might help a lot.

xavxav• 3 years ago

Compiling to C is definitely an option, but there are also plenty of low-hanging fruit that could come before. You could invest in a better interpreter or even some bytecode compilation first.

I don't know where your rules are coming from but I would personally not be super happy with the introduction of a c compiler running user-provided strings in the middle of my application.

DylanSp5• 3 years ago

Aside from the bytecode approach that other people have mentioned, is there a way you could leverage a SAT solver like Z3?

DylanSp5• 3 years ago

I'm curious about a few things: - How many rules are there, and how complex do they get? It sounds pretty substantial if you're running into performance issues (and/or you're working with highly demanding performance requirements) - What do your rules look like? I'm having a bit of trouble understanding how you'd get recursion if there's just AND/OR operators. I can imagine an AST getting fairly big/deep, but the only way I can think of to get recursion would be if you're calling external functions multiple times, with different values over the course of processing a single request.

secondcoming5• 3 years ago

Hundreds at the moment, but it will need to scale to thousands.

Complexity varies, it's usually a bunch of ORs but technically the complexity can be arbitrary as they're created by humans.

Recursion comes from the AST structure. For example, for an AND operation it's essentially

    bool execute(ANDNode n) { return execute(n->left) && execute(n->right); }

In reality it's the visitor pattern using variants. That's what I want to get away from.

mamcx• 3 years ago

Exist 2 "better/easier" options:

- Compile to WASM

- Compile to closures: https://blog.cloudflare.com/building-fast-interpreters-in-ru...

And something else to consider: Compact the representation/user "arena-like" storage.

Also, if you already have the rules stored, you can compile them, save that, and reuse the compilation.

amno5• 3 years ago

I am experimenting with runtime generation of shared libs.

Sure, you can produce an executable or a shared library at runtime; after all, that is what compilers and linkers do, those are also just programs, aren't they :). But do you really need to do that? As others said, you can also dlopen and rename your symbols, put them in an array and what not, but your problem seems quite simple, unless you need to transport that library somewhere or keep it for later use, I don't see reason why would you bother with generating a file just to load it after into your program again?

We have a database of rules in the form 'A OR (B AND C)' stored just like that in human readable form.

That sounds like you could construct a "bottom-up" parser, i.e. an operator precedence parser, and just evaluate that directly, or emit the assembly code directly to a page memory and mark that as an executable page? Unless you are doing some optimizations, do you really need an explicit AST?

Anyway, if your AST is slow, it may depend of course on the size, but also on how you create your AST in the memory and how you use it. If you are doing some linked structure with pointers pointing all over the memory and accessing it randomly you can be trashing your cache which should be slow. But if you put it in some vector and can access it sequentially, it might help performance. I don't know, just thinking loud, no idea what you are really doing.

I suggest look at a good Lisp compiler like SBCL or CCL. They generate code at runtime which is than mark as executable and call that code. They can also save themselves into an executable (or a shared library in the case of sbcl). Writing a read-macro that transforms your human readable strings into compiled Lisp functions would be trivial exercise in Common Lisp. Perhaps you should try to solve your problem with that tool instead of C++? If you are going to generate code dynamically every now and than as you describe, than pick a tool that already has infrastructure to do that in-place so you don't have to do everything from the scratch; albeit you could do something similar based on llwm or libgccjit too.

openasocket• 3 years ago

You could also check out libjit: https://www.gnu.org/software/libjit/ . I've not used it before but know it exists. Essentially you pass your bytecode in and the library handles turning that into machine code and everything. So that library would handle the loading and unloading of executable memory for you, you would just have to handle translating your rules into the libjit bytecode.

chubot2• 3 years ago

What are A and B? Are they expressions over integers, floats, or strings?

I would simply try translating them to JavaScript / Lua and use v8 / LuaJIT (LuaJIT is probably much smaller and easier to embed)

And just do

    eval('A || (B && C)')

Or there is probably a way to store the parsed and compiled representation.

v8 and LuaJIT are slower than C/C++ in general, but for that specific simple case, they are likely about the same speed, or within a factor of 2.

And WAY easier to implement and deploy!

raible• 3 years ago

I can highly recommend libtcc (https://github.com/TinyCC/tinycc.git) for this kind of thing. I recently ported the code developed in linux on an ARM chromebook to a generic windows box in 20 minutes.

naasking• 3 years ago

JIT it with GNU lightning.

hgs3• 3 years ago

The authors implemented a stack-based virtual machine for their benchmarks, but as they briefly alluded a register-based virtual machine should perform better. With a register-based VM there is no excessive stack fiddling and fewer instructions to perform the same task. Consider the instructions for adding two integers and storing the result in a variable. In a stack machine this requires four instructions: 'push int', 'push int', 'add', and 'pop to variable' but in a register machine it could be done with a single instruction: 'add $r1, $r2, $r3'.

For further reading, there is an excellent paper [1] by the authors of Lua discussing the practical benefits of implementing the language using a register machine.

[1] https://www.lua.org/doc/jucs05.pdf

AST vs. Bytecode: Interpreters in the Age of Meta-Compilation [pdf]

Related Stories