aengelke

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).)

> 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.)

[1]: https://www.vldb.org/pvldb/vol4/p539-neumann.pdf

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.

> 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).

> 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.

I'm a bit late, but: Umbra doesn't use AsmJIT anymore since many years, it was too slow.

That's not generally correct. Compile-time is a concern for several databases.

> 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.

[1]: https://umbra-db.com/

> What's the rationale?

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.

I fully agree, but:

> 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.

[1]: https://github.com/aengelke/instrew

Actually, nowadays Arm describes the ISA as a load-store architecture. The RISC vs. CISC debate is, in my opinion, pretty pointless nowadays and I'd prefer if we'd just stop using these words to describe ISAs.

The same site hosts [1], but that's not nearly as nice as the 32-bit version. It's also a bit outdated.

[1]: https://www-user.tu-chemnitz.de/~heha/hs/chm/x86.chm/x64.htm

> I’d suggest starting with arm

I agree: AArch64 is a nice instruction set to learn. (Source: I taught ARMv7, AArch64, x86-64 to first-year students in the past.)

> how simple instruction encoding is on arm64

Having written encoders, decoders, and compilers for AArch64 and x86-64, I disagree. While AArch64 is, in my opinion, very well designed (also better than RISC-V), it's certainly not simple. Here's some of my favorite complexities:

- Many instructions have (sometimes very) different encodings. While x86 has a more complex encoding structure, most encodings follow the same structure and are therefore remarkably similar.

- Huge amount of instruction operand types: memory + register, memory + unsigned scaled offset, memory + signed offset, optionally with pre/post-increment, but every instruction supports a different subset; vector, vector element, vector table, vector table element; sometimes general-purpose register encodes a stack pointer, sometimes a zero register; various immediate encodings; ...

- Logical immediate encoding. Clever, but also very complex. (To be sure that I implemented the decoding correctly, I brute-force test all inputs...)

- Register constraints: MUL (by element) with 16-bit integers has a register constraint on the lowest 16 registers. CASP requires an even-numbered register. LD64B requires an even-numbered register less than 24 (it writes Xt..Xt+7).

- Much more instructions: AArch64 SIMD (even excluding SVE) has more instructions than x86 including up to AVX-512. SVE/SME takes this to another level.

TPDE co-author here. Nice work, this was easier than expected; so we'll have better upstream ORC support soon [1].

The benchmark is suboptimal in multiple ways:

- Multi-threading makes things just slower. When enabling multi-threading, LLJIT clones every module into a new context before compilation, which is much more expensive than compilation. There's also no way to disable this. This causes a ~1.5x (LLVM)/~6.5x (TPDE) slowdown (very rough measurement on my laptop).

- The benchmark compares against the optimizing LLVM back-end, not the unoptimizing back-end (which would be a fairer comparison) (Code: JTMB.setCodeGenOptLevel(CodeGenOptLevel::None);). Additionally, enabling FastISel helps (command line -fast-isel; setting the TargetOption EnableFastISel seems to have no effect). This gives LLVM a 1.6x speedup.

- The benchmark is not really representative, as it causes FastISel fallbacks to SelectionDAG in some very large basic blocks -- i24 occurs rather rarely in real-world code. This is the reason why the speedup from the unoptimizing LLVM back-end is so low. Replacing i24 with i16 gives LLVM another 2.2x speedup. (Hint: to get information on FastISel fallbacks, enable FastISel and pass the command line options "-fast-isel-report-on-fallback -pass-remarks-missed=sdagisel" to LLVM. This is really valuable when optimizing for compile times.)

So we get ~140ms (TPDE), ~730ms (LLVM -O0), or 5.2x improvement. This is nowhere near the 10-20x speedup that TPDE typically achieves. Why? The new bottleneck is JITLink, which is featureful but slow -- profiling indicates that it consumes ~55% of the TPDE "compile time" (so the net compile time speedup is ~10x). TPDE therefore ships its own JIT mapper, which has fewer features but is much faster.

LLVM is really powerful, and despite being not particularly fast, the JIT API makes it extremely difficult to make it not extra-slow, even for LLVM experts.

[1]: https://github.com/tpde2/tpde/commit/29bcf1841c572fcdc75dd61...

> but typically a change to the preprocessed output implies a change to the IR (e.g., it's a functional change and not just a variable name change or something). Otherwise, why would I recompile it?

For C++, this could happen more often, e.g. when changing the implementation of an inline function or a non-instantiated template in a header that is not used in the compilation unit.

Or rather: There are 2 hard problems in computer science: cache invalidation, naming things, and off-by-1 errors.

(source: https://martinfowler.com/bliki/TwoHardThings.html)

Template instantiation caching is likely to help -- in an unoptimized LLVM build, I found that 40-50% of the compiled code at object file level is discarded at link-time as redundant.

Another thing I'd consider as interesting is parse caching from token to AST. Most headers don't change, so even when a TU needs to be recompiled, most parts of the AST could be reused. (Some kind of more clever and transparent precompiled headers.) This is likely to need some changes in the AST data structures for fast serialization and loading/inserting. And that makes me think that maybe the text book approach of generating an AST is a bad idea if we care about fast compilation.

Tangentially, I'm astonished that they claim correctness while a large amount of IR is inadequately (if at all) captured in the hash (comdat, symbol visibility, aliases, constant exprs, block address, calling convention/attributes for indirect calls, phi nodes, fast math flags, GEP type, ....). I'm also a bit annoyed, because this is the type of research that is very sloppily implemented, only evaluates projects where compile time is not a big problem and then only achieves small absolute savings, and papers over inherent difficulties (here: capturing the IR, parse time) that makes this unlikely to be used in practice.

In AoT compilation, unoptimized code is primarily useful for debugging and short compile-test round trips. Your point on C++ is correct, but test workloads are typically small so the cost is often tolerable and TPDE also supports -O1 IR -- nothing precludes using an -O0 back-end with optimized IR, so if performance is relevant for debugging/testing, there's still a measurable compile-time improvement. (Obviously, with -O1 IR, the TPDE-generated code is ~2-3x slower than the code from the LLVM-O1-back-end; but it's still better than using unoptimized IR. It might also be possible to cut down the -O1 pass pipeline to passes that are actually important for performance.)

In JIT compilation, a fast baseline is always useful. LLVM is obviously not a great fit (the IR is slow to generate and inspect), but for projects that don't want to roll their own IR and use LLVM for optimized builds anyway, this is an easy way to drastically reduce the startup latency. (There is a JIT case study showing the overhead of LLVM-IR in Section 7/Fig. 10 in the paper.)

> And if a project is not large one then build times should not be that much of a problem.

I disagree -- I'm always annoyed when my builds take longer than a few seconds, and typically my code changes only involve fewer compilation units than I have CPU cores (even when working on LLVM). There's also this study [1] from Google, which claims that even modest improvements in build times improve productivity.

[1]: https://www.computer.org/csdl/magazine/so/2023/04/10176199/1...

The paper is rather selective about the used benchmarks and baselines. They do two comparisons (3 microbenchmarks and a re-implementation of a few (rather simple) database queries) against LLVM -- and have written all benchmarks themselves through their own framework. These benchmarks start from their custom AST data structures and they have their own way of generating LLVM-IR. For the non-optimizing LLVM back-end, the performance obviously strongly depends on the way the IR is generated -- they might not have put a lot of effort into generating "good IR" (=IR similar to what Clang generates).

The fact that they don't do a comparison against LLVM on larger benchmarks/functions or any other code they haven't written themselves makes that single number rather questionable for a general claim of being faster than LLVM -O0.

There's a longer paragraph on that topic in Section 8. We also previously built an LLVM back-end using that approach [1]. While that approach leads to even faster compilation, run-time performance is much worse (2.5x slower than LLVM -O0) due to more-or-less impossible register allocation for the snippets.

[1]: https://home.cit.tum.de/~engelke/pubs/2403-cc.pdf

In terms of runtime performance, the TPDE-generated code is comparable with and sometimes a bit faster than LLVM -O0.

I agree that front-ends are a big performance problem and both rustc and Clang (especially in C++ mode) are quite slow. For Clang with LLVM -O0, 50-80% is front-end time, with TPDE it's >98%. More work on front-end performance is definitely needed; maybe some things can be learned from Carbon. With mold or lld, I don't think linking is that much of a problem.

We now support most LLVM-IR constructs that are frequently generated by rustc (most notably, vectors). I just didn't get around to actually integrate it into rustc and get performance data.

> The 10-20x improvement described here doesn’t work yet for clang

Not sure what you mean here, TPDE can compile C/C++ programs with Clang-generated LLVM-IR (95% of llvm-test-suite SingleSource/MultiSource, large parts of the LLVM monorepo).

The documentation has a list of currently unsupported features: https://docs.tpde.org/tpde-llvm-main.html

Storing the string length explicitly as an 8-byte integer does have a measurable cost. Consider llvm::Twine as an example, it supports storing a null-terminated string and a ptr+len string (among other options). I once changed the implementation to store string literals (length known at compile-time) as ptr+len instead of a pointer to a C string, with the intention of avoiding the strlen in the callee on constant strings. However, this change made things slower, because of the cost of storing the length everywhere. (That's why I never proposed such a change upstream.)

The critical (data) path of the null-terminated loop, however, does not include the load -- the actually loaded value is not a loop-carried dependency in your example. The re-steering of the branch at the end of the loop might happen much later, however.

Vectorization with null-terminated strings is possible and done, but requires alignment checking, which adds some cost.

It's probably worth noting that TySan currently only catches aliasing violations that LLVM would be able to exploit. For some types, e.g. unions, Clang doesn't emit accurate type-based aliasing information and therefore TySan won't catch these.

These are tests that use some more LLVM tools (llvm-objdump, llvm-dwarfdump, not). Could you try after building these tools in addition to FileCheck? Do the TPDE-LLVM tests, which use the same tools, pass with this setup?

> Also there are processors with larger vector length

How do these fare in terms of absolute performance? The NEC TSUBASA is not a CPU.

> Do you have more examples of this?

I ported some numeric simulation kernel to the A64Fx some time ago, fixing the vector width gave a 2x improvement. Compilers probably/hopefully have gotten better in the mean time and I haven't redone the experiments since then, but I'd be surprised if this changed drastically. Spilling is sometimes unavoidable, e.g. due to function calls.

> Anyway, I know of one comparison between NEON and SVE: https://solidpixel.github.io/astcenc_meets_sve

I was specifically referring to dynamic vector sizes. This experiment uses sizes fixed at compile-time, from the article:

> For the astcenc implementation of SVE I decided to implement a fixed-width 256-bit implementation, where the vector length is known at compile time.

Thanks, I misremembered. However, the microarchitecture is a bit "weird" (really HPC-targeted), with very long latencies (e.g., ADD (vector) 4 cycles, FADD (vector) 9 cycles). I remember that it was much slower than older x86 CPUs for non-SIMD code, and even for SIMD code, it took quite a bit of effort to get reasonable performance through instruction-level parallelism due to the long latencies and the very limited out-of-order capacities (in particular the just 2x20 reservation station entries for FP).

> if we didn't settle on executing compiled machine code exactly as-is, and had a instruction-updating pass (less involved than a full VM byte code compilation)

Apple tried something like this: they collected the LLVM bitcode of apps so that they could recompile and even port to a different architecture. To my knowledge, this was done exactly once (watchOS armv7->AArch64) and deprecated afterwards. Retargeting at this level is inherently difficult (different ABIs, target-specific instructions, intrinsics, etc.). For the same target with a larger feature set, the problems are smaller, but so are the gains -- better SIMD usage would only come from the auto-vectorizer and a better instruction selector that uses different instructions. The expectable gains, however, are low for typical applications and for math-heavy programs, using optimized libraries or simply recompiling is easier.

WebAssembly is a higher-level, more portable bytecode, but performance levels are quite a bit behind natively compiled code.