4 ms·

One interesting thing about at least some versions of the Oberon system is that they found that it was faster to store programs as compressed abstract syntax tr

by KMag 4y ago

One interesting thing about at least some versions of the Oberon system is that they found that it was faster to store programs as compressed abstract syntax trees on disk and compile them at load time instead of storing them on disk as native code. This was largely due to 2 factors: (1) the ratio of disk I/O bandwidth to CPU speed on the ETH Zurich workstations and (2) Wirth-style compilers generating code very quickly (with relatively few optimizations). Wirth's graduate student Michael Franz took this a bit further and adapted to storing Java programs as compressed SSA control flow graphs, called SafeTSA. Franz's research group modified the Jalapeno (now JikesRVM) JVM to be able to load SafeTSA files as well as regular Java class files. They found that the time to JIT code was reduced, and the performance of the generated native code was faster when using SafeTSA. The downside is that SafeTSA isn't well suited to interpretation in a HotSpot style hybrid JIT. So, program start-up time would likely suffer unless using AoT compilation. Last time I played around with A2/Bluebottle/AOS, I believe compressed syntax trees were the on-disk program format.

vidarh 4y ago
Huge fan of Franz' work on this, his PhD thesis on it[1] is a thing of beauty for it's simple, accessible description. Beyond that, I just wanted to add a couple of things: It doesn't require keeping the generated datastream at the level of the AST per see. You can generate as high- or low-level data as suitable where e.g. a lower level representation requires additional computation but remains independent of hardware architectures. The key is just that what you generate should fit a tree structure. So you can do any number of optimisation steps on the tree prior to applying the semantic dictionary encoding step if you choose. The extension to e.g. serialising SSA forms was pretty natural - there was work at ETHZ on generating SSA form around the same time as well [2] The real beauty of the method is that the encoder and decoder each generates a dictionary the same way e.g. LZW does (and the dissertation cites Welch; Lempel-Ziv style variable length dictionary entries is achieved by simply variable length encoding all integers stored), but where the encoder uses it to compress and flatten the tree, the decoder does not reconstitute the original tree, but uses it to generate machine code fragments directly, and either copy it straight into the code being generated or stores it as a template to reuse for generation of other occurrences of that dictionary element. The compression/decompression and serialization/code-generation are one and the same, and avoiding a separate layer is a key reason why it achieved the speed it did. [1] Code-Generation On-the-Fly: A Key to Portable Software, M. Franz (1994): https://oberoncore.ru/_media/library/franz_m.code-generation_on-the-fly_a_key_to_portable_software.en.pdf https://oberoncore.ru/_media/library/franz_m.code-generation... [2] Single-pass generation of static single-assignment form for structured languages, M. Brandis, H. Mössenböck (1994)
pjmlp 4y ago
As info for others, since Oberon System 3, there is the option of AOT or JIT compile the modules, depending on the use cases. It is done as part of the compiler settings when compiling a module, if it ends up in pure binary or abstract syntax trees format. Some flags depend on the compilation mode.

by KMag 4y ago

vidarh 4y ago

Huge fan of Franz' work on this, his PhD thesis on it[1] is a thing of beauty for it's simple, accessible description. Beyond that, I just wanted to add a couple of things: It doesn't require keeping the generated datastream at the level of the AST per see. You can generate as high- or low-level data as suitable where e.g. a lower level representation requires additional computation but remains independent of hardware architectures. The key is just that what you generate should fit a tree structure. So you can do any number of optimisation steps on the tree prior to applying the semantic dictionary encoding step if you choose. The extension to e.g. serialising SSA forms was pretty natural - there was work at ETHZ on generating SSA form around the same time as well [2] The real beauty of the method is that the encoder and decoder each generates a dictionary the same way e.g. LZW does (and the dissertation cites Welch; Lempel-Ziv style variable length dictionary entries is achieved by simply variable length encoding all integers stored), but where the encoder uses it to compress and flatten the tree, the decoder does not reconstitute the original tree, but uses it to generate machine code fragments directly, and either copy it straight into the code being generated or stores it as a template to reuse for generation of other occurrences of that dictionary element. The compression/decompression and serialization/code-generation are one and the same, and avoiding a separate layer is a key reason why it achieved the speed it did. [1] Code-Generation On-the-Fly: A Key to Portable Software, M. Franz (1994): https://oberoncore.ru/_media/library/franz_m.code-generation_on-the-fly_a_key_to_portable_software.en.pdf https://oberoncore.ru/_media/library/franz_m.code-generation... [2] Single-pass generation of static single-assignment form for structured languages, M. Brandis, H. Mössenböck (1994)

pjmlp 4y ago

As info for others, since Oberon System 3, there is the option of AOT or JIT compile the modules, depending on the use cases. It is done as part of the compiler settings when compiling a module, if it ends up in pure binary or abstract syntax trees format. Some flags depend on the compilation mode.