4 ms·

Hm 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 eff

by chubot 9y ago

Hm 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 ago
Isn't WebAssembly arguably a kind of "slim binary"? It's basically a binary form AST, no?
- vidarh 9y ago
  I 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 ago
There'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.
- vanderZwan 9y ago
  I'm actually exploring something "spiritually" related: currently, I have a project where I store the state of an app in the URL, by compressing trees of JavaScript objects by first putting them through a pre-compression "filter" step to make the data more compressible (not going into that now, but see [0]), then apply JSON.stringify, and finally put the resulting string through lz-string to create an URI-safe string[1]. lz-string is basically a wonderful, wonderful hack to Lempel-Ziv compress strings to a bitstream, which is then turned back into a string. I'm basically looking at ways to cut out the JSON.stringify step. So basically, first turn a JSON-friendly object into a binary representation, which is then compressed into a bytestream, and stored in a URI-safe string. This might lead to something generally usable, and faster/smaller than lz-string. I know JSON alternatives like flatpack and messagepack exist, but this would be a much simpler, lighter JS library, single-digit kilobytes in size before gzipping. It also would probably be backwards compatible all the way to IE6. [0] https://github.com/linnarsson-lab/loom-viewer/blob/master/client/js/state-compressor.js https://github.com/linnarsson-lab/loom-viewer/blob/master/cl... [1] http://pieroxy.net/blog/pages/lz-string/index.html http://pieroxy.net/blog/pages/lz-string/index.html
  - vidarh 9y ago
    That's interesting. Yes, I'd encourage looking at how SDE functions there, as SDE is ultimately using Lempel-Ziv-Welch that operates directly on a tree instead of a serialized string, and where the heuristics for what to add to the dictionary can include templated tree subsets. That part of it is really independent of the code generation aspect, and could easily be adapted to serialize arbitrary types of tree structures. Basically what you need is a general mechanism that takes a possibly templated rule, and adds to the dictionary. Then you need a mechanism that looks at a JS object and instead of spitting out JSON, matches the current node to one of the dictionary items and spits out a bit pattern and then recursively spits out the bit pattern for the template arguments. The decoder can basically be very simple recursive descent: Identify the dictionary entry, look it up, find the template rule, recursively call itself to retrieve the template patterns, and reconstitute the object. The "magic" then lies in the heuristics, which can be very generic (e.g. suitable for any JSON) or very specific (e.g. embedding domain knowledge of what the trees are likely to be shaped like, or at least code to be able to recognize and encode complex shapes when seen).

by chubot 9y ago

vanderZwan 9y ago

Isn't WebAssembly arguably a kind of "slim binary"? It's basically a binary form AST, no?

vidarh 9y ago
I 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 ago

There'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.

vanderZwan 9y ago
I'm actually exploring something "spiritually" related: currently, I have a project where I store the state of an app in the URL, by compressing trees of JavaScript objects by first putting them through a pre-compression "filter" step to make the data more compressible (not going into that now, but see [0]), then apply JSON.stringify, and finally put the resulting string through lz-string to create an URI-safe string[1]. lz-string is basically a wonderful, wonderful hack to Lempel-Ziv compress strings to a bitstream, which is then turned back into a string. I'm basically looking at ways to cut out the JSON.stringify step. So basically, first turn a JSON-friendly object into a binary representation, which is then compressed into a bytestream, and stored in a URI-safe string. This might lead to something generally usable, and faster/smaller than lz-string. I know JSON alternatives like flatpack and messagepack exist, but this would be a much simpler, lighter JS library, single-digit kilobytes in size before gzipping. It also would probably be backwards compatible all the way to IE6. [0] https://github.com/linnarsson-lab/loom-viewer/blob/master/client/js/state-compressor.js https://github.com/linnarsson-lab/loom-viewer/blob/master/cl... [1] http://pieroxy.net/blog/pages/lz-string/index.html http://pieroxy.net/blog/pages/lz-string/index.html
- vidarh 9y ago
  That's interesting. Yes, I'd encourage looking at how SDE functions there, as SDE is ultimately using Lempel-Ziv-Welch that operates directly on a tree instead of a serialized string, and where the heuristics for what to add to the dictionary can include templated tree subsets. That part of it is really independent of the code generation aspect, and could easily be adapted to serialize arbitrary types of tree structures. Basically what you need is a general mechanism that takes a possibly templated rule, and adds to the dictionary. Then you need a mechanism that looks at a JS object and instead of spitting out JSON, matches the current node to one of the dictionary items and spits out a bit pattern and then recursively spits out the bit pattern for the template arguments. The decoder can basically be very simple recursive descent: Identify the dictionary entry, look it up, find the template rule, recursively call itself to retrieve the template patterns, and reconstitute the object. The "magic" then lies in the heuristics, which can be very generic (e.g. suitable for any JSON) or very specific (e.g. embedding domain knowledge of what the trees are likely to be shaped like, or at least code to be able to recognize and encode complex shapes when seen).