4 ms·

I don't understand why there can't be a type of "dynamic analysis " done on higher level languages that analyzes them and tries to substitute lower level code t

by Timmah 8y ago

I don't understand why there can't be a type of "dynamic analysis " done on higher level languages that analyzes them and tries to substitute lower level code that does the same thing. Like an AI agent that says "hmm this behavior is very map-like, I'll try replacing it with a std::map" or "80 / 100 of these functions are never called. I'll just remove them from the program image to save load time and locality of reference". And in before "it'll just crash". Have the agent throw an exception that is picked up and dynamically loads the old program image, resulting in a one time delay.

austin_y 8y ago
What you described sounds to me like a just-in-time (JIT) compiler! https://en.wikipedia.org/wiki/Just-in-time_compilation https://en.wikipedia.org/wiki/Just-in-time_compilation
friday99 8y ago
Note, "80 / 100 of these functions are never called. I'll just remove them from the program image to save load time and locality of reference" is already an optimization compilers apply: dead code elimination. https://en.wikipedia.org/wiki/Dead_code_elimination https://en.wikipedia.org/wiki/Dead_code_elimination
- Timmah 8y ago
  I know that for a language like c++, the compiler can prune dead code. But I mean for the often-lamented "4gb-electron text editor" something that could nibble away at the redundancy gradually during runtime, dynamically reducing and refactoring. Until it approaches the efficiency of a native compiled application.
jcranmer 8y ago
Compilers do that a lot already. The question is at what level we can do stuff, particularly in a compile-time issue. Instruction-level (peephole) optimizations are omnipresent. You're not going to beat a compiler in register allocation (at least, not by enough to actually be worth the time writing in assembly), and optimizing for microarchitecture is generally within reach of the compiler, when the compiler is made aware of these details. Superoptimization means that automatic tools can write better patterns than you can for loop-free code, and maybe even small loops (although most compilers don't incorporate superoptimization for compile-time reasons). The next level of optimization is loop nest. Compilers already do loop idiom recognition (if you write a memcpy as a loop, LLVM will recognize it as a memcpy and convert it to faster memcpy idioms). But recognition is of course limited to known kernels; we don't have good general-purpose tools. Automatic optimization for parallelization, vectorization, cache hierarchy (block loops out so everything sits in L1 cache, for example) are all well-known, but they tend to turn out to be extremely problematic to work in practice because languages suck, and many of the core kernels can be wrapped up in autotuned libraries (e.g., FFTW, ATLAS). Whole-function optimization, interprocedural, and whole-program optimization are much less mature. Whole-function is used for many microoptimizations (dead code and various kinds of partial redundancy elimination), but it's not really feasible for higher-level algorithm analysis. Interprocedural optimization is largely limited to figuring out if inlining functions would help reduce code size or dead function analysis, and whole-program is used to improve the quality of these kinds of analyses. The frontier of compiler research (and in terms of shifting research prototypes to product compilers) is in moving our techniques to larger and larger program slices. Program synthesis can already automatically generate specialized data structures from the queries you will make on them, for example. As the original paper points out, making these techniques easier and more readily available is likely going to the main program here for the next two decades or so.
- Timmah 8y ago
  Thank you for the thorough reply

by Timmah 8y ago

austin_y 8y ago

What you described sounds to me like a just-in-time (JIT) compiler! https://en.wikipedia.org/wiki/Just-in-time_compilation https://en.wikipedia.org/wiki/Just-in-time_compilation

friday99 8y ago

Note, "80 / 100 of these functions are never called. I'll just remove them from the program image to save load time and locality of reference" is already an optimization compilers apply: dead code elimination. https://en.wikipedia.org/wiki/Dead_code_elimination https://en.wikipedia.org/wiki/Dead_code_elimination

Timmah 8y ago
I know that for a language like c++, the compiler can prune dead code. But I mean for the often-lamented "4gb-electron text editor" something that could nibble away at the redundancy gradually during runtime, dynamically reducing and refactoring. Until it approaches the efficiency of a native compiled application.

jcranmer 8y ago

Compilers do that a lot already. The question is at what level we can do stuff, particularly in a compile-time issue. Instruction-level (peephole) optimizations are omnipresent. You're not going to beat a compiler in register allocation (at least, not by enough to actually be worth the time writing in assembly), and optimizing for microarchitecture is generally within reach of the compiler, when the compiler is made aware of these details. Superoptimization means that automatic tools can write better patterns than you can for loop-free code, and maybe even small loops (although most compilers don't incorporate superoptimization for compile-time reasons). The next level of optimization is loop nest. Compilers already do loop idiom recognition (if you write a memcpy as a loop, LLVM will recognize it as a memcpy and convert it to faster memcpy idioms). But recognition is of course limited to known kernels; we don't have good general-purpose tools. Automatic optimization for parallelization, vectorization, cache hierarchy (block loops out so everything sits in L1 cache, for example) are all well-known, but they tend to turn out to be extremely problematic to work in practice because languages suck, and many of the core kernels can be wrapped up in autotuned libraries (e.g., FFTW, ATLAS). Whole-function optimization, interprocedural, and whole-program optimization are much less mature. Whole-function is used for many microoptimizations (dead code and various kinds of partial redundancy elimination), but it's not really feasible for higher-level algorithm analysis. Interprocedural optimization is largely limited to figuring out if inlining functions would help reduce code size or dead function analysis, and whole-program is used to improve the quality of these kinds of analyses. The frontier of compiler research (and in terms of shifting research prototypes to product compilers) is in moving our techniques to larger and larger program slices. Program synthesis can already automatically generate specialized data structures from the queries you will make on them, for example. As the original paper points out, making these techniques easier and more readily available is likely going to the main program here for the next two decades or so.

Timmah 8y ago
Thank you for the thorough reply