4 ms·

Tangent: I wish more (any?) high-level languages were capable of expressing self-modifying code safely. A lot of values are variable at compile time but constan

by blt 11y ago

Tangent: I wish more (any?) high-level languages were capable of expressing self-modifying code safely. A lot of values are variable at compile time but constant within a significant block of computation at runtime. If compilers were designed to emit self-modifying code, they could propagate constants through the block and replace register/register instructions with register/immediate instructions, freeing up registers for other variables. This is the promise of JIT compilers but in practice the popular jit-compiled languages have too many other performance issues to be popular for serious CPU-bound work. Plus the jitter has to do a lot of analysis at runtime. It would be cool if you could mark a block of C code with `#pragma jit`, making the compiler emit a binary that contains some compiler IR and a peephole optimizer to make the code as tight as possible given the conditions at runtime.

gfody 11y ago
I can't think of any language that has this as a feature. But there are some nice libraries for assembling machine code at runtime - there was one I used called "softwire" that seems to have disappeared. I just found this one on github: https://github.com/kobalicek/asmjit https://github.com/kobalicek/asmjit
ChrisLomont 11y ago
C# (Microsoft stack, probably other stack, probably other .NET languages) lets you generate or input C# code at runtime, compile it, and run it through the jitter as desired. It's nearly trivial to do it. The Regex classes for example create code at runtime to do compiled regular expressions, but I think they do it with emitted IL instead of C# code directly. All the pieces are there.
- dx211 11y ago
  .Net provides a couple of different ways to dynamically emit IL, but that's not quite the same as being able to emit your own native machine instructions, though. I think the challenge would be that you'd need to work out a calling convention between the jitted code and the emitted native code, at which point you might as well stick the native code in its own library function and compile or assemble it with a native tool.
  - ChrisLomont 11y ago
    People have done this if you dig around. The basic idea is you can assemble arbitrary code into a byte array, then use an unsafe cast and use PInvoke to execute. The calling convention for many platforms has been reverse engineered, but I don't have a link handy. I've used it before to see if it works, and you can do it.
- dsharlet 11y ago
  The LINQ expression compiler also lets you generate expressions at runtime and compile them, it's an amazingly powerful feature: https://msdn.microsoft.com/en-us/library/bb397951.aspx https://msdn.microsoft.com/en-us/library/bb397951.aspx
- yaur 11y ago
  Have you ever seen the jiter use SIMD? Having written some test code that was the simplest use case (multiply an array of floats by a float constant iirc) I have not. C# is a great language, but not for compute bound problems.
  - ChrisLomont 11y ago
    Yes, I have seen that. Of course the JITer will not perform the same level of optimizations as the fullblown code generator, but then you can just call that if you like. The new JIT engine does support SIMD [1]. And C# can generate SIMD code using various libraries (I think MS has one, and I know Mono does). And various people have shown how to do fullblown x86 assembly code generation and execution from within C#, but it's fragile. [1] http://blogs.msdn.com/b/dotnet/archive/2014/04/07/the-jit-finally-proposed-jit-and-simd-are-getting-married.aspx http://blogs.msdn.com/b/dotnet/archive/2014/04/07/the-jit-fi...
  - jj10 11y ago
    Actually, I just tried it: float[] floats = new float[1000]; float factor = 1.01f; int index = 0; while (index < 1000) { floats[index++] *= factor; } ...becomes... 00007ff8`80a804a9 488d549010 lea rdx,[rax+rdx*4+10h] 00007ff8`80a804ae c4e17a1002 vmovss xmm0,dword ptr [rdx] 00007ff8`80a804b3 c4e17a590524000000 vmulss xmm0,xmm0,dword ptr [00007ff8`80a804e0] 00007ff8`80a804bc c4e17a1102 vmovss dword ptr [rdx],xmm0 This is in VS 2013, compiled with DEBUG off, prefer x86 off, and 'any cpu' as the target.
    - tbirdz 11y ago
      Those are scalar instructions, not the SIMD instructions. With x86_64 the fpu stack operations are basically for legacy purposes only, and normal floating point operations are expected to be done with the SSE/AVX scalar instructions. SIMD instruction used the packed variants of the commands allowing you to multiple say 4 floats in a single instruction.
  - pjmlp 11y ago
    Yes, you just need to fulfil three conditions: - Use the new RyuJIT - Make use of 64 bits CPU - Use the vector and matrix classes from System.Numerics
gdwatson 11y ago
Selectively using code generation to implement closures over immutable variables could get you part of the way there while allowing a lot of the work to be done at compile time and avoiding the need for a full JIT. How much it would help performance in practice I couldn't say.
deleted 11y ago
[deleted]
kazinator 11y ago
> If compilers were designed to emit self-modifying code ... then the high-level language isn't expressing self-modifying; the compiler is doing it to optimize the code while preserving the abstract meaning that is free of self-modifying.
mbrock 11y ago
Maybe you know that Common Lisp makes it easy to compile and recompile functions at runtime. http://clhs.lisp.se/Body/f_cmp.htm http://clhs.lisp.se/Body/f_cmp.htm In fact, with the package system ASDF, you can recompile (incrementally) an entire package at runtime. This is a single blocking function call; something like: (asdf:operate 'asdf:compile-op :my-package) I have a web project where any request in dev mode triggers a system recompilation only if the git revision of the working tree is new. (my-handler :did-recompile (when (revision-is-new) (recompile) t)) That recompiles the system including MY-HANDLER, and right after RECOMPILE returns, the new version of MY-HANDLER from the working tree will be active. The way Common Lisp lets me do that as a ten minute hack feels like living in the future... except of course it's pretty old technology! Edit: I realize this is not really what you are talking about as "self-modifying code." Having full access to the compiler at runtime is a good first step for doing some of what you want, though. And with S-expressions, constructing and manipulating "ASTs" is ridiculously straightforward.
swolchok 11y ago
Modern processors don't handle self-modifying code efficiently. https://en.wikipedia.org/wiki/Self-modifying_code#Interaction_of_cache_and_self-modifying_code https://en.wikipedia.org/wiki/Self-modifying_code#Interactio...
- userbinator 11y ago
  short sections of self-modifying code execute more slowly Unless you're optimising for size, SMC'ing little pieces is definitely going to be slower. But e.g. in loops that do a few hundred iterations, saving a cycle or two by getting rid of some opaque predicates quickly adds up and the cache/pipeline-flushing overhead (few hundred cycles at most) becomes insignificant. After all, as the parent comment says, a JIT is basically SMC'ing huge blocks of code, and it's definitely faster than the equivalent alternative of a bytecode interpreter.
  - wyager 11y ago
    Modern branch predictors handle opaque predicates (assuming you mean branches that don't change). Jump instructions in tight, repetitive loops on superscalar out-of-order processors are basically free.
easytiger 11y ago
> It would be cool if you could mark a block of C code with `#pragma jit`, making the compiler emit a binary that contains some compiler IR and a peephole optimizer to make the code as tight as possible given the conditions at runtime. Even if that remotely made any sense, which i don't think it does... c code compiles to the end target of all jits anyway, you just have some if statements or use pointers to other executable code that you swap around. Not only do you get the executable code as efficable as any jit, its constant with no jit cost. Its called c programming.
- creshal 11y ago
  When you have variable types (say, you're deserializing foreign data, always fun), typical C code will end up having a huge switch() block do determine the type (expensive, e.g. due to branch prediction) and do something with it (trivial). Ahead-of-time compilation cannot optimize away the switch(), JIT can, by evaluating the data fed to the function at runtime. What OP wants is a way to get the advantage of ahead-of-time compilation for the 99% of the code that benefit from it, and the advantages of JIT for the remaining 1% (or even less). However, I'm not sure how feasible that would be.
exDM69 11y ago
Probably doesn't count as "high level" but you can embed the LLVM compiler backend to your project and compile and optimize code at runtime. See the LLVM "Kaleidoscope" tutorials from the LLVM docs. They implement a simple toy compiler with a JIT-based REPL. Basically you use the LLVM framework to build a program and then run it through the compiler pipeline and get a callable function pointer to your newly compiled function(s), optimized for the CPU architecture you're running on.
- eru 11y ago
  I've seen people use that for compiling regular expressions to LLVM assembly at run time.
mgraczyk 11y ago
I wrote up a small module to do this in C on x86 platforms. I called it a predicate replacer, but it can replace any integer constant. https://github.com/mgraczyk/fast_check_once https://github.com/mgraczyk/fast_check_once

by blt 11y ago

gfody 11y ago

I can't think of any language that has this as a feature. But there are some nice libraries for assembling machine code at runtime - there was one I used called "softwire" that seems to have disappeared. I just found this one on github: https://github.com/kobalicek/asmjit https://github.com/kobalicek/asmjit

ChrisLomont 11y ago

C# (Microsoft stack, probably other stack, probably other .NET languages) lets you generate or input C# code at runtime, compile it, and run it through the jitter as desired. It's nearly trivial to do it. The Regex classes for example create code at runtime to do compiled regular expressions, but I think they do it with emitted IL instead of C# code directly. All the pieces are there.

dx211 11y ago
.Net provides a couple of different ways to dynamically emit IL, but that's not quite the same as being able to emit your own native machine instructions, though. I think the challenge would be that you'd need to work out a calling convention between the jitted code and the emitted native code, at which point you might as well stick the native code in its own library function and compile or assemble it with a native tool.
- ChrisLomont 11y ago
  People have done this if you dig around. The basic idea is you can assemble arbitrary code into a byte array, then use an unsafe cast and use PInvoke to execute. The calling convention for many platforms has been reverse engineered, but I don't have a link handy. I've used it before to see if it works, and you can do it.
dsharlet 11y ago
The LINQ expression compiler also lets you generate expressions at runtime and compile them, it's an amazingly powerful feature: https://msdn.microsoft.com/en-us/library/bb397951.aspx https://msdn.microsoft.com/en-us/library/bb397951.aspx
yaur 11y ago
Have you ever seen the jiter use SIMD? Having written some test code that was the simplest use case (multiply an array of floats by a float constant iirc) I have not. C# is a great language, but not for compute bound problems.
- ChrisLomont 11y ago
  Yes, I have seen that. Of course the JITer will not perform the same level of optimizations as the fullblown code generator, but then you can just call that if you like. The new JIT engine does support SIMD [1]. And C# can generate SIMD code using various libraries (I think MS has one, and I know Mono does). And various people have shown how to do fullblown x86 assembly code generation and execution from within C#, but it's fragile. [1] http://blogs.msdn.com/b/dotnet/archive/2014/04/07/the-jit-finally-proposed-jit-and-simd-are-getting-married.aspx http://blogs.msdn.com/b/dotnet/archive/2014/04/07/the-jit-fi...
- jj10 11y ago
  Actually, I just tried it: float[] floats = new float[1000]; float factor = 1.01f; int index = 0; while (index < 1000) { floats[index++] *= factor; } ...becomes... 00007ff8`80a804a9 488d549010 lea rdx,[rax+rdx*4+10h] 00007ff8`80a804ae c4e17a1002 vmovss xmm0,dword ptr [rdx] 00007ff8`80a804b3 c4e17a590524000000 vmulss xmm0,xmm0,dword ptr [00007ff8`80a804e0] 00007ff8`80a804bc c4e17a1102 vmovss dword ptr [rdx],xmm0 This is in VS 2013, compiled with DEBUG off, prefer x86 off, and 'any cpu' as the target.
  - tbirdz 11y ago
    Those are scalar instructions, not the SIMD instructions. With x86_64 the fpu stack operations are basically for legacy purposes only, and normal floating point operations are expected to be done with the SSE/AVX scalar instructions. SIMD instruction used the packed variants of the commands allowing you to multiple say 4 floats in a single instruction.
- pjmlp 11y ago
  Yes, you just need to fulfil three conditions: - Use the new RyuJIT - Make use of 64 bits CPU - Use the vector and matrix classes from System.Numerics

gdwatson 11y ago

Selectively using code generation to implement closures over immutable variables could get you part of the way there while allowing a lot of the work to be done at compile time and avoiding the need for a full JIT. How much it would help performance in practice I couldn't say.

deleted 11y ago

[deleted]

kazinator 11y ago

> If compilers were designed to emit self-modifying code ... then the high-level language isn't expressing self-modifying; the compiler is doing it to optimize the code while preserving the abstract meaning that is free of self-modifying.

mbrock 11y ago

Maybe you know that Common Lisp makes it easy to compile and recompile functions at runtime. http://clhs.lisp.se/Body/f_cmp.htm http://clhs.lisp.se/Body/f_cmp.htm In fact, with the package system ASDF, you can recompile (incrementally) an entire package at runtime. This is a single blocking function call; something like: (asdf:operate 'asdf:compile-op :my-package) I have a web project where any request in dev mode triggers a system recompilation only if the git revision of the working tree is new. (my-handler :did-recompile (when (revision-is-new) (recompile) t)) That recompiles the system including MY-HANDLER, and right after RECOMPILE returns, the new version of MY-HANDLER from the working tree will be active. The way Common Lisp lets me do that as a ten minute hack feels like living in the future... except of course it's pretty old technology! Edit: I realize this is not really what you are talking about as "self-modifying code." Having full access to the compiler at runtime is a good first step for doing some of what you want, though. And with S-expressions, constructing and manipulating "ASTs" is ridiculously straightforward.

swolchok 11y ago

Modern processors don't handle self-modifying code efficiently. https://en.wikipedia.org/wiki/Self-modifying_code#Interaction_of_cache_and_self-modifying_code https://en.wikipedia.org/wiki/Self-modifying_code#Interactio...

userbinator 11y ago
short sections of self-modifying code execute more slowly Unless you're optimising for size, SMC'ing little pieces is definitely going to be slower. But e.g. in loops that do a few hundred iterations, saving a cycle or two by getting rid of some opaque predicates quickly adds up and the cache/pipeline-flushing overhead (few hundred cycles at most) becomes insignificant. After all, as the parent comment says, a JIT is basically SMC'ing huge blocks of code, and it's definitely faster than the equivalent alternative of a bytecode interpreter.
- wyager 11y ago
  Modern branch predictors handle opaque predicates (assuming you mean branches that don't change). Jump instructions in tight, repetitive loops on superscalar out-of-order processors are basically free.

easytiger 11y ago

> It would be cool if you could mark a block of C code with `#pragma jit`, making the compiler emit a binary that contains some compiler IR and a peephole optimizer to make the code as tight as possible given the conditions at runtime. Even if that remotely made any sense, which i don't think it does... c code compiles to the end target of all jits anyway, you just have some if statements or use pointers to other executable code that you swap around. Not only do you get the executable code as efficable as any jit, its constant with no jit cost. Its called c programming.

creshal 11y ago
When you have variable types (say, you're deserializing foreign data, always fun), typical C code will end up having a huge switch() block do determine the type (expensive, e.g. due to branch prediction) and do something with it (trivial). Ahead-of-time compilation cannot optimize away the switch(), JIT can, by evaluating the data fed to the function at runtime. What OP wants is a way to get the advantage of ahead-of-time compilation for the 99% of the code that benefit from it, and the advantages of JIT for the remaining 1% (or even less). However, I'm not sure how feasible that would be.

exDM69 11y ago

Probably doesn't count as "high level" but you can embed the LLVM compiler backend to your project and compile and optimize code at runtime. See the LLVM "Kaleidoscope" tutorials from the LLVM docs. They implement a simple toy compiler with a JIT-based REPL. Basically you use the LLVM framework to build a program and then run it through the compiler pipeline and get a callable function pointer to your newly compiled function(s), optimized for the CPU architecture you're running on.

eru 11y ago
I've seen people use that for compiling regular expressions to LLVM assembly at run time.

mgraczyk 11y ago

I wrote up a small module to do this in C on x86 platforms. I called it a predicate replacer, but it can replace any integer constant. https://github.com/mgraczyk/fast_check_once https://github.com/mgraczyk/fast_check_once