5 ms·

I wrote a new JIT compiler for PostgreSQL

290 points by mattashii 3y ago

pinaraf 3y ago
Author here. Thanks for submitting my article on hackernews. I'll do my best to answer any question.
- frizlab 3y ago
  Not a question, but I love this. I’m eager to see its evolution.
- deleted 3y ago
  [deleted]
- pgaddict 3y ago
  Would be a great topic for pgconf.eu in June (pgcon moved to Vancouver). Too bad the CfP is over, but there's the "unconference" part (but the topics are decided at the event, no guarantees).
  - mattashii 3y ago
    Did you mean pgconf.dev in May (which has the unconference), or pgconf.eu in October (which doesn't have an unconference, but the CfP will open sometime in the - hopefully near - future)?
    - pgaddict 3y ago
      Yeah, I meant May. Sorry :-( Too many conferences around that time, I got confused. That being said, submitting this into the pgconf.eu CfP is a good idea too. It's just that it seems like a nice development topic, and the pgcon unconference was always a great place to discuss this sort of stuff. There are a couple more topics in the JIT area, so having a session or two to talk about those and how to move that forward would be beneficial.
- can3p 3y ago
  Nice post, thanks! Do I read it right that using jit results in the worst max times? What could be a reason in your opinion?
  - pinaraf 3y ago
    Two parts: I did the benchmark on a laptop and didn't spend enough time forcing its runtime PM in a fixed state, I'll run a real pgbench on my desktop once I implement all required opcodes for it. And since JIT requires a minimum amount of time (about 300us on my tests), on such small runtimes this can quickly overcome the benefits.
- winternewt 3y ago
  Is there a fundamental difference between copy and patch with C and what compilers do when they target intermediate representations? It seems to me that traditional compilation methods are also "copy and patch" but with another intermediate language than C.
  - tetha 3y ago
    I think conceptually, there is no real difference. In the end, a compiler outputting machine code uses very small stencils, like "mov _ _", which are rather simple to patch. Practically though, it's an enormous difference, as the copy and patch approach re-uses the years of work going into clang / gcc supporting platforms, optimizations for different platforms and so on. The approach enables a much larger pool of people ("People capable of writing C" vs "People capable of writing assembly / machine code") to implement very decent JIT compilers.
    - pinaraf 3y ago
      The real difference is in the possible optimizations. If you consider the full scope of JIT compilation in for instance a web browser or the JVM, you could use copy and patch as a tier 0 compiler, and once really hot paths are identified, trigger a complete compiler with all the optimizer steps. Some optimizations are more complicated to implement with copy-patch, esp. if you can't use all the tricks described in the paper (for instance they use the ghccc calling convention to get a much finer register allocation, but from the documentation I don't think it's going to make it for PostgreSQL). But as you say, yes, this enables people capable of writing C and reading assembly (or you have to be perfect and never have to go into gdb on your compiled code), and it makes the job so much faster and easier... Writing several machine code emitters is painful, and having the required optimization strategies for each ISA is quickly out of reach.
- o11c 3y ago
  Is copy-and-patch really a new idea, or just a new name for an old idea? When I learned programming (and interpreters particularly) around 2010, I thought it was well-known that you could memcpy chunks of executable code that your compiler produced if you were careful ... the major gotcha was that the NX bit was just starting to take off at the time (Even on Linux, most people still assumed 32-bit distros and might be surprised that their CPUs even supported 64-bit. At some point I ended up with a netbook that didn't support 64-bit code at all ...). Unfortunately I ended up spending too much time on the rest of the code to actually look deeply enough into it to build something useful.
  - aengelke 3y ago
    It is an old idea with a new name. For example, QEMU orginally worked like this [1] and they already used relocations to patch in constants, before they later moved to TCG for higher-quality code. [1]: https://www.usenix.org/legacy/event/usenix05/tech/freenix/full_papers/bellard/bellard.pdf https://www.usenix.org/legacy/event/usenix05/tech/freenix/fu...
- aengelke 3y ago
  Thanks for the blog post, it's always nice to see performance improvements in Postgres! I'm curious: how much time is spent for LLVM on some real queries and how is LLVM configured (i.e., which passes, which back-end optimization, etc.)? In our experience [1], LLVM can be reasonably fast when optimized for compile time without optimizations and the -O0 back-end pipeline, but obviously still 10-20x slower compared to other approaches. Also, in our experience, copy-and-patch-generated code tends to be quite slow and hard to optimize (we tried some things [2; Sec. 5], but there's still quite a gap (see Fig. 3 for a database evaluation)). Do you have some numbers on the run-time slowdown compared to LLVM? Any future plans for implementing multi-tiering, so dynamically switching from the quickly compiled code to LLVM-optimized code? [1]: https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf [2]: https://home.in.tum.de/~engelke/pubs/2403-cc.pdf https://home.in.tum.de/~engelke/pubs/2403-cc.pdf
deleted 3y ago
[deleted]
adzm 3y ago
I'm still surprised there isn't a query/plan cache for PostgreSQL. I could easily see these two approaches working in harmony once it does, as frequent queries could end up being cached and more aggressively optimized with a cache to offset the compilation cost. Of course that adds a whole new layer of complexity and trouble.
- pinaraf 3y ago
  Honestly I thought the same as you, then I wrote this, and I now understand it's going to be really hard to do. To make it very simple: there are pointers to query parts "leaking" everywhere across the execution engine. Removing them will require a significant overall of the execution engine, the planner and who knows what else. Even in a single session, two compiled queries will have different compiled code because of that (both llvm and my copyjit have to inject the adresses of various structs in asm code)
  - adzm 3y ago
    Just going to say, I'm blown away by how simple this JIT is though. Really quite a beautiful JIT approach.
    - pinaraf 3y ago
      Same for me, that's why I did this after finding out this research paper. With the proper compiler settings and small tricks you can remove some parts and already end up faster than the interpreter (because you remove some branches and a few memory accesses) and it's even possible to create "super-stencils" covering typical opcodes series and optimizing them further. Or the opposite, "sub-stencils" in order to do some loop unrolling for instance.
- williamdclt 3y ago
  (The article goes a bit above my head so my excuses if I am a bit off-topic) There is a form of query plan caching in PG: for prepared statements, if PG determines that the actual value of parameters won't affect the query plan much, it uses a "generic plan" so that it reuses the same query plan for every execution of the prepared statement (https://www.postgresql.org/docs/current/sql-prepare.html https://www.postgresql.org/docs/current/sql-prepare.html, see "notes")
weliveindetail 3y ago
> There is one way to make the LLVM JIT compiler more usable, but I fear it’s going to take years to be implemented: being able to cache and reuse compiled queries. Actually, it's implemented in LLVM for years :) https://github.com/llvm/llvm-project/commit/a98546ebcd2a692e0634c5b1a7e77471316ab6e0 https://github.com/llvm/llvm-project/commit/a98546ebcd2a692e...
- pinaraf 3y ago
  Yeah, well, sorry, I should have been more explicit here: the issue is with PostgreSQL, not LLVM. The JIT compiler has to inject direct memory addresses, making the generated code specific to your query and process.
  - weliveindetail 3y ago
    Interesting, because we store relocatable objects. And process symbols can be resolved by name if you really want. It might be yet another performance trade-off though.
- SigmundA 3y ago
  Since PG uses one process per connection and the LLVM JIT code is process specific the code can't be shared amongst all connections to the DB. Plans themselves suffer from this since they are in memory data structures not designed to be shared amongst different processes. DB's like MSSQL don't have this issue since they use a single process with threads which is also why it can handle more concurrent connections without an external pooler. Although MSSQL can also serialize plans to a non process specific representation and store them in the DB for things like plan locking.
  - hans_castorp 3y ago
    > Plans themselves suffer from this since they are in memory data structures not designed to be shared amongst different processes. Oracle uses a process-per-connection model as well (at least on Linux), and they are able to share execution plans across connections. They put all the plans into the "global" shared memory.
OhNoNotAgain_99 3y ago
[dead]
miohtama 3y ago
Back in 386 era, there was a concept of self-modifying code (assembly). A similar like stencils presented here, but because code was a singleton, rarely a copy was made. E.g. Doom on DOS used this optimisation techique, because otherwise you could not cram out enough performance from tight rendering loops on old CPUs.
HackerThemAll 3y ago
Interesting work, please continue it. Great times ahead. Thanks!

290 points by mattashii 3y ago

pinaraf 3y ago

Author here. Thanks for submitting my article on hackernews. I'll do my best to answer any question.

frizlab 3y ago
Not a question, but I love this. I’m eager to see its evolution.
deleted 3y ago
[deleted]
pgaddict 3y ago
Would be a great topic for pgconf.eu in June (pgcon moved to Vancouver). Too bad the CfP is over, but there's the "unconference" part (but the topics are decided at the event, no guarantees).
- mattashii 3y ago
  Did you mean pgconf.dev in May (which has the unconference), or pgconf.eu in October (which doesn't have an unconference, but the CfP will open sometime in the - hopefully near - future)?
  - pgaddict 3y ago
    Yeah, I meant May. Sorry :-( Too many conferences around that time, I got confused. That being said, submitting this into the pgconf.eu CfP is a good idea too. It's just that it seems like a nice development topic, and the pgcon unconference was always a great place to discuss this sort of stuff. There are a couple more topics in the JIT area, so having a session or two to talk about those and how to move that forward would be beneficial.
can3p 3y ago
Nice post, thanks! Do I read it right that using jit results in the worst max times? What could be a reason in your opinion?
- pinaraf 3y ago
  Two parts: I did the benchmark on a laptop and didn't spend enough time forcing its runtime PM in a fixed state, I'll run a real pgbench on my desktop once I implement all required opcodes for it. And since JIT requires a minimum amount of time (about 300us on my tests), on such small runtimes this can quickly overcome the benefits.
winternewt 3y ago
Is there a fundamental difference between copy and patch with C and what compilers do when they target intermediate representations? It seems to me that traditional compilation methods are also "copy and patch" but with another intermediate language than C.
- tetha 3y ago
  I think conceptually, there is no real difference. In the end, a compiler outputting machine code uses very small stencils, like "mov _ _", which are rather simple to patch. Practically though, it's an enormous difference, as the copy and patch approach re-uses the years of work going into clang / gcc supporting platforms, optimizations for different platforms and so on. The approach enables a much larger pool of people ("People capable of writing C" vs "People capable of writing assembly / machine code") to implement very decent JIT compilers.
  - pinaraf 3y ago
    The real difference is in the possible optimizations. If you consider the full scope of JIT compilation in for instance a web browser or the JVM, you could use copy and patch as a tier 0 compiler, and once really hot paths are identified, trigger a complete compiler with all the optimizer steps. Some optimizations are more complicated to implement with copy-patch, esp. if you can't use all the tricks described in the paper (for instance they use the ghccc calling convention to get a much finer register allocation, but from the documentation I don't think it's going to make it for PostgreSQL). But as you say, yes, this enables people capable of writing C and reading assembly (or you have to be perfect and never have to go into gdb on your compiled code), and it makes the job so much faster and easier... Writing several machine code emitters is painful, and having the required optimization strategies for each ISA is quickly out of reach.
o11c 3y ago
Is copy-and-patch really a new idea, or just a new name for an old idea? When I learned programming (and interpreters particularly) around 2010, I thought it was well-known that you could memcpy chunks of executable code that your compiler produced if you were careful ... the major gotcha was that the NX bit was just starting to take off at the time (Even on Linux, most people still assumed 32-bit distros and might be surprised that their CPUs even supported 64-bit. At some point I ended up with a netbook that didn't support 64-bit code at all ...). Unfortunately I ended up spending too much time on the rest of the code to actually look deeply enough into it to build something useful.
- aengelke 3y ago
  It is an old idea with a new name. For example, QEMU orginally worked like this [1] and they already used relocations to patch in constants, before they later moved to TCG for higher-quality code. [1]: https://www.usenix.org/legacy/event/usenix05/tech/freenix/full_papers/bellard/bellard.pdf https://www.usenix.org/legacy/event/usenix05/tech/freenix/fu...
aengelke 3y ago
Thanks for the blog post, it's always nice to see performance improvements in Postgres! I'm curious: how much time is spent for LLVM on some real queries and how is LLVM configured (i.e., which passes, which back-end optimization, etc.)? In our experience [1], LLVM can be reasonably fast when optimized for compile time without optimizations and the -O0 back-end pipeline, but obviously still 10-20x slower compared to other approaches. Also, in our experience, copy-and-patch-generated code tends to be quite slow and hard to optimize (we tried some things [2; Sec. 5], but there's still quite a gap (see Fig. 3 for a database evaluation)). Do you have some numbers on the run-time slowdown compared to LLVM? Any future plans for implementing multi-tiering, so dynamically switching from the quickly compiled code to LLVM-optimized code? [1]: https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf [2]: https://home.in.tum.de/~engelke/pubs/2403-cc.pdf https://home.in.tum.de/~engelke/pubs/2403-cc.pdf

deleted 3y ago

[deleted]

adzm 3y ago

I'm still surprised there isn't a query/plan cache for PostgreSQL. I could easily see these two approaches working in harmony once it does, as frequent queries could end up being cached and more aggressively optimized with a cache to offset the compilation cost. Of course that adds a whole new layer of complexity and trouble.

pinaraf 3y ago
Honestly I thought the same as you, then I wrote this, and I now understand it's going to be really hard to do. To make it very simple: there are pointers to query parts "leaking" everywhere across the execution engine. Removing them will require a significant overall of the execution engine, the planner and who knows what else. Even in a single session, two compiled queries will have different compiled code because of that (both llvm and my copyjit have to inject the adresses of various structs in asm code)
- adzm 3y ago
  Just going to say, I'm blown away by how simple this JIT is though. Really quite a beautiful JIT approach.
  - pinaraf 3y ago
    Same for me, that's why I did this after finding out this research paper. With the proper compiler settings and small tricks you can remove some parts and already end up faster than the interpreter (because you remove some branches and a few memory accesses) and it's even possible to create "super-stencils" covering typical opcodes series and optimizing them further. Or the opposite, "sub-stencils" in order to do some loop unrolling for instance.
williamdclt 3y ago
(The article goes a bit above my head so my excuses if I am a bit off-topic) There is a form of query plan caching in PG: for prepared statements, if PG determines that the actual value of parameters won't affect the query plan much, it uses a "generic plan" so that it reuses the same query plan for every execution of the prepared statement (https://www.postgresql.org/docs/current/sql-prepare.html https://www.postgresql.org/docs/current/sql-prepare.html, see "notes")

weliveindetail 3y ago

> There is one way to make the LLVM JIT compiler more usable, but I fear it’s going to take years to be implemented: being able to cache and reuse compiled queries. Actually, it's implemented in LLVM for years :) https://github.com/llvm/llvm-project/commit/a98546ebcd2a692e0634c5b1a7e77471316ab6e0 https://github.com/llvm/llvm-project/commit/a98546ebcd2a692e...

pinaraf 3y ago
Yeah, well, sorry, I should have been more explicit here: the issue is with PostgreSQL, not LLVM. The JIT compiler has to inject direct memory addresses, making the generated code specific to your query and process.
- weliveindetail 3y ago
  Interesting, because we store relocatable objects. And process symbols can be resolved by name if you really want. It might be yet another performance trade-off though.
SigmundA 3y ago
Since PG uses one process per connection and the LLVM JIT code is process specific the code can't be shared amongst all connections to the DB. Plans themselves suffer from this since they are in memory data structures not designed to be shared amongst different processes. DB's like MSSQL don't have this issue since they use a single process with threads which is also why it can handle more concurrent connections without an external pooler. Although MSSQL can also serialize plans to a non process specific representation and store them in the DB for things like plan locking.
- hans_castorp 3y ago
  > Plans themselves suffer from this since they are in memory data structures not designed to be shared amongst different processes. Oracle uses a process-per-connection model as well (at least on Linux), and they are able to share execution plans across connections. They put all the plans into the "global" shared memory.

OhNoNotAgain_99 3y ago

[dead]

miohtama 3y ago

Back in 386 era, there was a concept of self-modifying code (assembly). A similar like stencils presented here, but because code was a singleton, rarely a copy was made. E.g. Doom on DOS used this optimisation techique, because otherwise you could not cram out enough performance from tight rendering loops on old CPUs.

HackerThemAll 3y ago

Interesting work, please continue it. Great times ahead. Thanks!