4 ms·

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 for

• tonyedgecombe 3y ago
  I wonder if switching to byte code rather than using the visitor pattern would give you a big enough performance improvement.
  • DylanSp 3y 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.
    • secondcoming 3y ago
      Well, my thoughts are that if a C compiler can do all the heavy lifting I may as well take advantage of that. Transpiling to C also reduces, if not eliminates, any internal recursion in the expression evaluation. You also get decades of optimisations too, although I don't see there being much of that.
      • DylanSp 3y ago
        Compiling to C introduces the complexity of loading/unloading a shared library at runtime, though, as you and other folks in this thread have been talking about. A bytecode compiler + VM could just be built into your main program.
      • afiori 3y ago
        This looks like one of the perfect application of wasm. You could do ruleset -> C -> wasm and run the wasm in process with wasmer/wasmtime. From my understanding wasmer might be easier to use. It sounds like this should solve the immediate problem, the main downside I can see is that it might be a new significant dependency whose cost can be hard to judge.
• naasking 3y ago
  JIT it with GNU lightning.
• mike_hearn 3y 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.
  • secondcoming 3y 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.
    • mike_hearn 3y ago
      Try looking at dlmopen.
    • aardvark179 3y ago
      That is okay, your libs can be uniquely named, and have unique symbols. I would echo the suggestions that you may be better off going for a byte code interpreter, at least as a first stage. If interpreting rules is expensive enough to worry about compiling then it’s probably expensive enough to be thinking about resource limits, interruption, and maybe profiling, and that stuff will be easier to experiment with if you have an interpreter.
• JonChesterfield 3y 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.
  • secondcoming 3y 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.
    • JonChesterfield 3y ago
      If you want to keep the call into a C compiler, you might want to go with freestanding (no calling into glibc by accident) and position independent, see if you can get everything statically resolved. Nothing in the loader relocation tables. Then mmap the entire elf. That gives you tables of constant data and removes all the edge cases that come from carving .text out. If you're partly looking for a easy and sufficient answer, and are building an elf anyway, much like the sibling post, I'd think dlopen is probably the way to go. Beware that dlclose might be a no-op, in which case eventually the address space leak will sink you.
    • noelwelsh 3y ago
      Maybe libgccjit, then? https://gcc.gnu.org/onlinedocs/jit/ https://gcc.gnu.org/onlinedocs/jit/
  • samsquire 3y ago
    I wrote the beginnings of a JIT compiler here (with help from Martin Jacob) https://GitHub.com/samsquire/compiler https://GitHub.com/samsquire/compiler See jitcompiler.c The code might be helpful.
  • pritambaral 3y 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.
• DylanSp 3y ago
  Aside from the bytecode approach that other people have mentioned, is there a way you could leverage a SAT solver like Z3?
• xavxav 3y 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.
• DylanSp 3y 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.
  • secondcoming 3y 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.
    • DylanSp 3y ago
      So it sounds like the rules themselves aren't recursive, just your current strategy for evaluating them; is that correct? Given that, I'm more inclined towards the currently upvoted reply about translating them to JS/Lua and just calling eval(). [1] It'd be very simple and _should_ be fast enough, though you might need to worry a little bit about security (especially depending on whoever's providing the rule sets and how much validation there is around them). [1] https://news.ycombinator.com/item?id=37136272 https://news.ycombinator.com/item?id=37136272
• mamcx 3y ago
  Exist 2 "better/easier" options: - Compile to WASM - Compile to closures: https://blog.cloudflare.com/building-fast-interpreters-in-rust/ 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.
• amno 3y 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 3y ago
  You could also check out libjit: https://www.gnu.org/software/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.
• chubot 3y 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 3y ago
  I can highly recommend libtcc (https://github.com/TinyCC/tinycc.git 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.