3 ms·

I think this technique also lies at the heart of the Cranelift project. https://cranelift.dev/ https://cranelift.dev/

aw1621107 1y ago
IIRC Cranelift doesn't use copy-and-patch. It uses e-graphs [0] as part of its optimization pipeline, though. Closest thing in (relatively) recent news that uses copy-and-patch I can think of is CPython's new JIT. [0]: https://github.com/bytecodealliance/rfcs/pull/27 https://github.com/bytecodealliance/rfcs/pull/27
- weinzierl 1y ago
  My understanding is that e-graphs take care of selecting the best patch (by examining many options in parallel) but fundamentally it is still copy-and-patch.
  - aw1621107 1y ago
    Could you elaborate more on "fundamentally it is still copy-and-patch"? From what I can recall when I had first read about copy-and-patch a not-uncommon comparison was against Cranelift, which to me would imply that different approaches were taken. I don't recall any discussion about Cranelift's use of the technique, either, so your claim that it's at the heart of Cranelift is new information to me. Has Cranelift adopted copy-and-patch (maybe for a specific compilation stage?) in the meantime?
    - weinzierl 1y ago
      You are right. Somehow I had in my mind that e-graphs worked with pre-compiled snippets of code but it seems Cranelift does not do that.
    - sestep 1y ago
      Indeed, the original copy-and-patch paper explicitly compares against Cranelift: https://fredrikbk.com/publications/copy-and-patch.pdf https://fredrikbk.com/publications/copy-and-patch.pdf
      - fikovnik 1y ago
        But not that is conceptually related, only that the copy-and-patch is faster than cranelift in that particular scenario.
    - quapster 1y ago
      [flagged]
      - PhilipRoman 1y ago
        You’re absolutely right —— it’s not just a trade-off between speed and optimization, it’s a balance between velocity and speed.
IainIreland 1y ago
Cranelift does not use copy-and-patch. Consider, for example, this file, which implements part of the instruction generation logic for x64: https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/codegen/src/isa/x64/inst/emit.rs https://github.com/bytecodealliance/wasmtime/blob/main/crane... Copy-and-patch is a technique for reducing the amount of effort it takes to write a JIT by leaning on an existing AOT compiler's code generator. Instead of generating machine code yourself, you can get LLVM (or another compiler) to generate a small snippet of code for each operation in your internal IR. Then codegen is simply a matter of copying the precompiled snippet and patching up the references. The more resources are poured into a JIT, the less it is likely to use copy-and-patch. You get more control/flexibility doing codegen yourself. But see also Deegen for a pretty cool example of trying to push this approach as far as possible: https://aha.stanford.edu/deegen-meta-compiler-approach-high-performance-vms-low-engineering-costb https://aha.stanford.edu/deegen-meta-compiler-approach-high-...

IIRC Cranelift doesn't use copy-and-patch. It uses e-graphs [0] as part of its optimization pipeline, though. Closest thing in (relatively) recent news that uses copy-and-patch I can think of is CPython's new JIT. [0]: https://github.com/bytecodealliance/rfcs/pull/27 https://github.com/bytecodealliance/rfcs/pull/27

weinzierl 1y ago
My understanding is that e-graphs take care of selecting the best patch (by examining many options in parallel) but fundamentally it is still copy-and-patch.
- aw1621107 1y ago
  Could you elaborate more on "fundamentally it is still copy-and-patch"? From what I can recall when I had first read about copy-and-patch a not-uncommon comparison was against Cranelift, which to me would imply that different approaches were taken. I don't recall any discussion about Cranelift's use of the technique, either, so your claim that it's at the heart of Cranelift is new information to me. Has Cranelift adopted copy-and-patch (maybe for a specific compilation stage?) in the meantime?
  - weinzierl 1y ago
    You are right. Somehow I had in my mind that e-graphs worked with pre-compiled snippets of code but it seems Cranelift does not do that.
  - sestep 1y ago
    Indeed, the original copy-and-patch paper explicitly compares against Cranelift: https://fredrikbk.com/publications/copy-and-patch.pdf https://fredrikbk.com/publications/copy-and-patch.pdf
    - fikovnik 1y ago
      But not that is conceptually related, only that the copy-and-patch is faster than cranelift in that particular scenario.
  - quapster 1y ago
    [flagged]
    - PhilipRoman 1y ago
      You’re absolutely right —— it’s not just a trade-off between speed and optimization, it’s a balance between velocity and speed.

IainIreland 1y ago

Cranelift does not use copy-and-patch. Consider, for example, this file, which implements part of the instruction generation logic for x64: https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/codegen/src/isa/x64/inst/emit.rs https://github.com/bytecodealliance/wasmtime/blob/main/crane... Copy-and-patch is a technique for reducing the amount of effort it takes to write a JIT by leaning on an existing AOT compiler's code generator. Instead of generating machine code yourself, you can get LLVM (or another compiler) to generate a small snippet of code for each operation in your internal IR. Then codegen is simply a matter of copying the precompiled snippet and patching up the references. The more resources are poured into a JIT, the less it is likely to use copy-and-patch. You get more control/flexibility doing codegen yourself. But see also Deegen for a pretty cool example of trying to push this approach as far as possible: https://aha.stanford.edu/deegen-meta-compiler-approach-high-performance-vms-low-engineering-costb https://aha.stanford.edu/deegen-meta-compiler-approach-high-...