4 ms·
Compulsory Michael Franz (author of the linked paper) fanboy-ing: Prof Franz did his PhD under Niklaus Wirth. His thesis was on Semantic Dictionary Encoding -
by vidarh 9y ago
Compulsory Michael Franz (author of the linked paper) fanboy-ing:
Prof Franz did his PhD under Niklaus Wirth. His thesis was on Semantic Dictionary Encoding - a method for storing a compact semantic tree representation of a program in what is effectively a prefix code (e.g. similar to Huffman coding) that it exploits beautifully to both compress the tree and to use heuristics (the same on the encoder and decoder) to generate templated code fragments to allow the code generator on load time to do less work. Published in '94, it unfortunately was totally overshadowed by Java.
It's still one of my favorite papers, and one day I still want to go down the route of actually implementing SDE properly (there are implementations for Oberon - one of the early remarkable feats was that because of the more compact representation, on MacOberon it was on some hardware faster to load and generate code from these "slim binaries" than it was to just load a native binary, because the code generator was fast enough to beat the disk IO cost of loading a larger binary...)
One of Franz' PhD students was Andreas Gal, who wrote the paper on trace trees and applied it to JIT'ing Javascript, and worked as CTO at Mozilla.
- Someone 9y agoThanks for the pointer. It led me to a few useful links. Michael Franz has a personal web page at http://www.michaelfranz.com http://www.michaelfranz.com. His thesis is at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1424 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1.... I think http://hokstad.com/semantic-dictionary-encoding http://hokstad.com/semantic-dictionary-encoding is your work, so I assume it is a good description of what I can expect from reading that thesis.
- vidarh 9y agoThanks, that's useful. I totally forgot to include any links even though I was meaning to (and yes, that's my page at the end)
- vanderZwan 9y agoI'm a bit sad to see that it's the only article tagged: http://hokstad.com/semantic-dictionary-encoding http://hokstad.com/semantic-dictionary-encoding Did you ever get around to exploring SDE's in a Ruby context?
- vidarh 9y agoUnfortunately not yet. My compiler project has stagnated a bit, though I still work on it occasionally (most recently I've now come to the point where I have to implement GC - the compiler racks up 2GB of mostly garbage while trying to compile itself...). I do want to eventually retarget it to SDE, but it's unlikely to happen this year...
- vanderZwan 9y ago> MacOberon it was on some hardware faster to load and generate code from these "slim binaries" than it was to just load a native binary, because the code generator was fast enough to beat the disk IO cost of loading a larger binary...) The CPU/Memory/Disk gap has only grown since then - even with SSD drives it is still a lot bigger than twenty years ago. So this is probably even more true today than back then, no? Reminds me of blosc, which uses data compression algorithms that are so fast that the cost of spending CPU cycles on it is lower than the savings in terms of reduced time to read/write to disk[0]. [0] http://www.blosc.org/ http://www.blosc.org/
- vidarh 9y agoIt very well might be that gap has grown, though I think the expectations of optimizations of the code has grown too. On the other hand, we now have more cores than we know what to do with, so an interesting approach would be to start generating code, and inserting calls to the code generator for pieces that hasn't been generated yet, and farm out generation to multiple cores. If the code is structured right, and you could certainly try to sort the code based on a dependency graph, you don't even need to load the entire file before you can start generating code from SDE (but you'd need to be prepared to stub out forward jumps so they point to something that'll generate or wait for generation of the rest where necessary).
- vanderZwan 9y agoWell, after quickly skimming through at the PDFs linked here, it looks like SDE are a good data structure for IR, and that one could compile one SDE into another. So it looks like you could do some kind of heavy "portable optimisation" pass first, then distribute the resulting SDE of that, and do a second, lighter pass of "local" optimisations targeting the local architecture.
- vidarh 9y agoThat's true. There's also always the option of treating SDE as an "installation format" rather than "runtime format" and generate optimized code for a given architecture at installation time. Optionally it opens the door for funky things such as generating code instrumented for profile guided optimization first, and in the background/offline continue to optimize the code. (in fact, I believe quite a lot of Franz' subsequent research has been in areas like that, though mostly JVM focused)
- useranme 9y agoI'm going through the paper on "slim binaries". They compress the abstract syntax tree at a semantic level and are smaller than compressed source code. ftp://ftp.cis.upenn.edu/pub/cis700/public_html/papers/Franz97.pdf
- chubot 9y agoHm very interesting. But to play devil's advocate, what's wrong with the Java approach or the v8 approach? Is it just that they are suboptimal in terms of efficiency, or is there something that SDE can accomplish that they can't? The Java approach is to do parsing, semantic analysis, and compilation to bytecode on one side of the network. Then JIT compilation is done on the other side. The v8 / "modern JS" approach is to do gzip compression of source code on one side of the network. Then decompression, lazily parse, and lazily generate native code on the other side. Now I recently look at v8's parser, and it's fiendishly complex [1] and somewhere north of 20K lines of code -- and yes that's just the parser. So there are downsides. SDE might be more elegant and efficient overall (?) But when you are dealing with networked code, you can't change both sides of the wire at once. So we are sort of stuck with suboptimal interfaces and brute force on both sides. That said, I do think there is a good argument to be made for shipping plain text source code and using brute force to make parsing and analysis in the browser fast. (That is, writing ridiculous amounts of hand-tuned C++ code.) [1] https://www.youtube.com/watch?v=Fg7niTmNNLg&t=2s https://www.youtube.com/watch?v=Fg7niTmNNLg&t=2s
- vanderZwan 9y agoIsn't WebAssembly arguably a kind of "slim binary"? It's basically a binary form AST, no?
- vidarh 9y agoI was actually thinking the same. WebAssembly certainly brings us a step closer to the SDE approach, though I haven't looked at it enough to be able to say how close.
- vidarh 9y agoThere's nothing "wrong" with the Java or V8 approach per se. It's not even a given that SDE would do better today. Note that most of Franz' own work has since been on the JVM. I just think SDE is worth more exploration. It lost out not because it failed to compete on merits with the JVM but because the JVM basically cut short any hope of it getting mindshare at the time. It's possible the JVM or V8 approaches are simply superior designs. But we don't really know, because such huge resources have gone into making the JVM or v8 approaches work, and not just SDE but most other approaches from that time became near instant dead ends. > The v8 / "modern JS" approach is to do gzip compression of source code on one side of the network. Then decompression, lazily parse, and lazily generate native code on the other side. The interesting part of this is that you could treat SDE simply as a way to short-circuit the parsing and compression step by using it to serialize the AST and still retain exactly the same code generation. You can lazily generate native code from it, as long as you apply the heuristics to build the dictionary on load time (necessary to rebuild the correct tree). Whether it'd be worth it is an open question, but I wish I had time to explore it.