Yeah, modern CPUs are great at executing garbage code reasonably fast. Getting binary-translated code to come close to native performance is still difficult.
Apple obviously had an advantage as they also control the hardware (and Arm helped by adding some extensions to simplify translation); significantly easing two difficult parts of translating from x86: TSO and status flags. AVX is somewhat annoying (256-bit regs -> 128-bit regs, frequent merging of scalar values), but manageable.
> You would like to be able to precisely handle exceptions (especially ones caused by invalid memory accesses) while presenting a userspace exception handler with an architecturally valid state for the source program.
This is absolutely annoying and makes many optimizations much more difficult as a lot of additional state needs to be kept around, either for real or in metadata for reconstruction (including weird status flags, fun with partially written flags (inc/dec), maybe-written flags (shift/rotate), etc.). Does Rosetta 2 always have precise status flags (including PF/AF) at every possibly-faulting memory access? (This should be rarely needed in practice, so I've never implemented flag recovery in my own binary translators (primarily for research, Instrew but also non-public).)
Not sure where the idea comes from that Cranelift is much faster than LLVM -O0, at least in our experiments in 2024 it wasn't, see [1] Fig. 6.
Template-based code generators suffer from bad code quality due to missing register allocation.
Our TPDE-based compilers compile a bit slower than template-based code generation but the generated code is much smaller and faster ([2] Fig. 2). Also for database workloads ([2] Fig. 6).
All that said, Postgres' main limitation is that it (IIRC) only compiles single expressions from operators, not pipelines. This fundamentally limits the achievable performance improvement compared to databases that perform more extensive query compilation.
Always good to have proper researchers in the thread.
> Not sure where the idea comes from that Cranelift is much faster than LLVM -O0
Cranelift describes itself as a fast, secure, relatively simple and innovative compiler backend. [0] Interesting that LLVM can compete there, with its optimisations dialed down.
> Postgres' main limitation is that it (IIRC) only compiles single expressions from operators, not pipelines. This fundamentally limits the achievable performance improvement compared to databases that perform more extensive query compilation.
That sounds pretty limiting. That's separate from query optimisation though, right? The query optimiser is presumably able to reason 'broadly' and not just at the level of individual expressions? High-level query-plan optimisation must be much more consequential than effective use of JIT compilation.
> That's separate from query optimisation though, right? The query optimiser is presumably able to reason 'broadly' and not just at the level of individual expressions? High-level query-plan optimisation must be much more consequential than effective use of JIT compilation.
Yes, yes, and yes. For databases, query optimization (esp. join ordering for larger queries, which heavily depends on estimates) is fundamental. Query optimization happens at the level of the query plan, JIT compilation is only relevant afterwards. A bad query plan leads to asymptotically worse performance (e.g., bad join ordering with huge intermediate results).
On query plan execution: The "classical" model as used in e.g. Postgres is a pull-based iterator model, where operators implement a next() method yielding the next tuple and in there recursively call next() on their child operators (e.g., a next() of a select operator calls next() on its child operator, then applies the predicate [what Postgres JIT-compiles], and returns the tuple if the predicate was true). This can happen one tuple at a time (Postgres) or "vectorized" where multiple tuples are processed at once (e.g. DuckDB). A query-compiling database will split the tree into pipelines and compile each pipeline as one function (e.g., a pipeline will iterate over all the tuples from a source (e.g. tablescan) and a select operator then becomes an if statement inside that loop). This results in pretty tight loops, avoids per-tuple dispatch overhead, and enables more optimizations inside the JIT-ted code (e.g., tuple values don't need to be reloaded from memory all the time). (I find the original paper on query compilation [1] to be well readable.)
> But you will not find multiple different CPUs that decode valid instructions differently. If I run your weird old x86 code, either it will run correctly or it will fault.
Oh, that's not completely true. Intel 64 and AMD64 are not identical and they certainly have encodings that behave differently. As an example: f3 41 90 is pause on Intel, but xchg r8d, eax on AMD (granted, this is not a canonical instruction encoding). 66 e9 xx xx yy yy is a unconditional jump to a 32-bit relative offset on Intel, but on AMD, the offset is 16-bit only (yy yy are the start of the next instruction). x86-64 is typically used to refer to the very large common subset, but this doesn't mean the implementations behave identically.
There are also some weird corner cases where CPUs aren't 100% backwards compatible, just backwards compatible enough for the software that matters.
For those less familiar with x86, the example instruction encodings that are interpreted differently on Intel and AMD are not base encodings, but instruction encodings modified with prefixes.
The x86 ISA includes a great number of bytes that are used as instruction prefixes, many of which are obsolete. The problem is that the effect of prefixes upon instructions has never been completely defined in any Intel or AMD documentation. The prefix effects have been documented for some instructions, but they were left unspecified for most other instructions.
This has lead to divergent implementations in the unspecified cases. Well-behaved compilers should not generate such undocumented combinations of instruction prefixes with base encodings.
> The problem is that the effect of prefixes upon instructions has never been completely defined in any Intel or AMD documentation.
In case of the jump example, the effects are documented by Intel and AMD and they still differ. Point of the GP was that all CPUs don't decode valid instructions differently, which is not fully accurate as shown by the examples; and some of these differences are also explicitly documented.
It's also not accurate that most prefixes are obsolete when most see regular use today (66 size override for 16-bit operations, f2/f3 for string operations, 66/f2/f3 mandatory prefix for many (e.g. SSE) instructions, 64/65 fs/gs override for thread-local storage access and per-thread kernel storage, f0 lock for atomic operations, 3e (again) for branch-taken hint, 4x REX prefix for r8-r15 and 64-bit operand size; one can argue that the 67 address-size override is useless, and only the 26, 2e, and 36 are ignored; I don't count VEX/EVEX/REX2 as prefixes but more as opcode escapes).
Pretty sure 3DNow's instruction space has been repurposed too. There are a few like that, or worse extremely similar but ever so slightly different between vendors or even generations of the same vendor. I won't claim to be an expert, this is all in IIRC territory for me.
No, the 0f 0f opcode (most of 3DNow was encoding-wise a single RMI-encoded opcode where the immediate specified the operation) and the 0f 0e opcode (FEMMS) were not repurposed by either Intel or AMD.
Most systems submit many of the same queries over and over again.
Ad-hoc one off queries usually can accept higher initial up-front compile cost because the main results usually take much longer anyway, vs worrying about an extra 100ms of compile.
Maybe it was too strong to say its not a concern at all, but nothing like PG where every single request needs to replan and potentially jit unless the client manually prepares and keeps the connection open.
> It's very difficult to do low-latency queries if you cannot cache the compiled code
This is not too difficult, it just requires a different execution style. Salesforce's Hyper for example very heavily relies on JIT compilation, as does Umbra [1], which some people regard as one of the fastest databases right now. Umbra doesn't cache any IR or compiled code and still has an extremely low start-up latency; an interpreter exists but is practically never used.
Postgres is very robust and very powerful, but simply not designed for fast execution of queries.
Disclosure: I work in the group that develops Umbra.
If I recall research papers regarding Umbra it's also using AsmJit as a JIT backend, which means that theoretically the compilation times would be comparable if you only consider code emitting overhead.
The problem will always be queries where the compilation is orders of magnitude more expensive than the query itself. I can imagine indexed lookup of 1 or few entries, etc... Accessing indexed entries like these are very well optimized by SQL query engines and possibly make no sense JIT optimizing.
Interesting... AsmJit is pretty fast for compilation, but about 3x than sljit. The only way I can see how to make it fast enough, in theory (i.e. without slowing down point-lookup queries and such) would be to fuse planning with code generation - i.e. a single pass plan builder + compiler essentially. Not sure if Umbra tries to do that, and AsmJit is not the best choice for it anyway, but with sljit it could be on par with interpreter even for fastest queries I believe. Pretty hard (likely impossible) to implement though, planning is inherently a non-linear process...
Because pg_jitter uses AsmJit's Compiler, which also allocates registers. That's much more work than using hardcoded physical registers in SLJIT case. There is always a cost of such comfort.
I think AsmJit's strength is completeness of its backends as you can emit nice SIMD code with it (like AVX-512). But the performance could be better of course, and that's possible - making it 2x faster would be possible.
There are other issues with that auto-allocation. I tested all 3 backends on very large queries (hundreds of KBs) per query. Performance of all of them (+LLVM, but -sljit) was abysmal - the compiler overhead was in seconds to tens(!) of seconds. They have some non-linear components in their optimization algorithms. While sljit was scaling linearly and almost as fast as for smaller queries. So yes, it gives higher run-time performance but the cost of that performance grows non-linearly with code size and complexity. While you still can have good performance with manual allocations. I also don't believe you can make AsmJit 2x faster without sacrificing that auto-allocation algorithm.
AsmJit has only one place where a lot of time is spent - bin-packing. It's the least optimized part, which has quadratic complexity (at the moment), which starts to show when you have like hundreds of thousands of virtual registers. There is even a benchmark in AsmJit called `asmjit_bench_regalloc`, which shows that a single function that has 16MB alone, with 65k labels and 200k virtual registers takes 2.2 seconds to generate (and 40ms of that is time to just call `emit()`).
If this function is optimized, or switched to some other implementation when there is tens of thousands of virtual registers, you would get orders of magnitude faster compilation.
But realistically, which query requires tens of megabytes of machine code? These are pathological cases. For example we are talking about 25ms when it comes to a single function having 1MB of machine code, and sub-ms time when you generate tens of KB of machine code.
So from my perspective the ability to generate SIMD code that the CPU would execute fast in inner loops is much more valuable than anything else. Any workload, which is CPU-bound just deserves this. The question is how much the CPU bound the workload is. I would imagine databases like postgres would be more memory-bound if you are processing huge rows and accessing only a very tiny part of each row - that's why columnar databases are so popular, but of course they have different problems.
I worked on one project, which tried to deal with this by using buckets and hashing in a way that there would be 16 buckets, and each column would get into one of these, to make the columns closer to each other, so the query engine needs to load only buckets used in the query. But we are talking about gigabytes of RAW throughput per core in this case.
I have a test of 200Kb query that AsmJit takes 7 seconds to compile (that's not too bad both LLVM and MIR take ~20s), while sljit does it in 50ms. 200Kb is a pathological case, but it's not unheard of in the area I'm working on. It's realistic, although a rare case.
Last 10-15 years most OLTP workloads became CPU bound, because active datasets of most real databases fully fit in memory. There are exceptions, of course.
That's interesting - 200kB should not be a big deal for it - maybe it uses something that I usually don't, like many function calls, or insane number of branches, etc... I would be interested in that case, but I'm not sure whether I would be able to blindly improve AsmJit without a comprehensive test.
Definitely good to know though. When it comes to low-latency compilation my personal goal is to make it even faster when generating small functions.
SLJIT is a bit smarter than just to use hardcoded registers. It's multi-platform anyway, so it uses registers when they are available on the target platform, if not it will use memory, that's why performance can differ between Windows and Linux on x64 for example - different number of available registers.
Indeed, but this also means that you would get drastically different performance on platforms that have more physical registers vs on platforms that have less. For example x86_64 only has 16 GP registers, while AArch64 has 32 - if you use 25 registers without any analysis and just go to stack with 10 of them, the difference could be huge.
But... I consider SLJIT to be for a different use-case than AsmJit. It's more portable, but its scope is much more limited.
It's definitely different, and for Postgres specifically, they may complement each other. SLJit can be used for low latency queries where codegen time is more important than optimizations, also for other platforms like s390x / PPC / SPARC, etc. AsmJit can be used for SIMD optimizations for x86_64 and ARM64. MIR is kinda in the middle - it does auto-allocations of registers, doesn't support SIMD, but also it's multiplatform. The only thing that doesn't fit well here is LLVM :). It has some advantages in some edge cases, but... It really needs a separate provider, the current one is bad. I'll probably create another LLVM backend for pg_jitter in the future to utilize it properly...
Gift cards are used by phishers. In our institution, we routinely get personalized spam mails (in the name of the corresponding group lead of the recipient, sent via GMail -- this is not low-effort) that ask whether they are available and, when (accidentally) responding, ask for Apple gift cards.
> these are the string instructions like REP MOVSB
AArch64 nowadays has somewhat similar CPY* and SET* instructions. Does that make AArch64 CISC? :-) (Maybe REP SCASB/CMPSB/LODSB (the latter being particularly useless) is a better example.)
> LEA happens to be the unique instruction where the memory operand is not dereferenced
Not quite unique: the now-deprecated Intel MPX instructions had similar semantics, e.g. BNDCU or BNDMK. BNDLDX/BNDSTX are even weirder as they don't compute the address as specified but treat the index part of the memory operand separately.
Been there, done that during my PhD (code: [1]). Works reasonably well, except for compile times (for which I implemented a caching strategy). However, due to calling conventions, using LLVM isn't going to give the best possible performance. Some features like signal handling are extremely hard to implement with LLVM (I didn't, therefore). Although the overall performance results have been good, it's not an approach that I could strongly recommend.
Apple obviously had an advantage as they also control the hardware (and Arm helped by adding some extensions to simplify translation); significantly easing two difficult parts of translating from x86: TSO and status flags. AVX is somewhat annoying (256-bit regs -> 128-bit regs, frequent merging of scalar values), but manageable.
> You would like to be able to precisely handle exceptions (especially ones caused by invalid memory accesses) while presenting a userspace exception handler with an architecturally valid state for the source program.
This is absolutely annoying and makes many optimizations much more difficult as a lot of additional state needs to be kept around, either for real or in metadata for reconstruction (including weird status flags, fun with partially written flags (inc/dec), maybe-written flags (shift/rotate), etc.). Does Rosetta 2 always have precise status flags (including PF/AF) at every possibly-faulting memory access? (This should be rarely needed in practice, so I've never implemented flag recovery in my own binary translators (primarily for research, Instrew but also non-public).)
reply