That's interesting. I think where SDE goes further is that you can go full lzw with it. The "dictionary" here is not a static dict, but a dynamically built dictionary as with lzw compression that is expanded as you parse the stream.

That makes it harder to traverse - you can't jump to arbitrary locations without decoding everything before it, because you need to look at everything to apply the heuristics to build the dictionary. But it makes it likely to be far more compressed - e.g. you can have dictionary entries shorter than a byte, and you can build dictionary entries that represents whole subtrees, and in SDE's case those subtrees can be templated.

Hm, but if compression ratio is the only difference, then I don't see that as a bottleneck in most language systems?

I think that overall startup time for example is a more interesting goal, not just the amount of data transferred over the network or streamed off disk.

Startup time can be saved by doing parsing and semantic analysis on one side of the network. And if you know your target architecture, you can do code generation there too, although that doesn't seem to be the way any systems have evolved -- even Android was doing native code generation on the device recently.

I guess I am having trouble seeing situations where both of these are true:

1) A compression algorithm specific to a file format is say 50% or 100% better than gzip or xz.

2) That 50% or 100% results in a big user-perceived improvement.

Most bytecode formats are "lazily" decoded, although they can be somewhat large. I sort of like the scheme I proposed because it's both compact and can be lazily decoded. You could make it more compact, but then you would have to decompress the whole thing up front.

It's not just compression ratio, but that it's exploiting the nature of the compression mechanism so that the decompression step effectively translates to a depth first traversal of the tree, during which it generates the code.

> I think that overall startup time for example is a more interesting goal, not just the amount of data transferred over the network or streamed off disk.

I agree, but to that end size is a major factor, and if the tree is structured properly nothing stops you from being able to start executing the code during generation ("just" generate stubs for missing functions that will wait for or trigger generation of the missing function)

> Startup time can be saved by doing parsing and semantic analysis on one side of the network. And if you know your target architecture, you can do code generation there too, although that doesn't seem to be the way any systems have evolved -- even Android was doing native code generation on the device recently.

Agreed, and SDE will do the parsing and semantic analysis on the other end too.

> I guess I am having trouble seeing situations where both of these are true:

But that is not the goal. The goal is to generate architecture independent code in a format that is very fast to generate code for. The compression and reduced load time is just a happy side-effect of speeding up the code generation by structuring it for reusability of code fragments during generation.

As such the decompression is "free", as it's nothing more than very lightweight dictionary lookups and insertion during the code generation.

> Most bytecode formats are "lazily" decoded, although they can be somewhat large. I sort of like the scheme I proposed because it's both compact and can be lazily decoded. You could make it more compact, but then you would have to decompress the whole thing up front.

Lazy decoding is possible as described above, though I agree that ability to do "random access" when generating the code is a benefit. Systems like SDE certainly do depend on outputting the code in a sensible order. Though incidentally you can get a lot of that simply by carefully deciding on how to traverse the AST to generate the output. E.g. traverse outer definitions, then the main entrypoint and output any obvious dependencies first.