Assembler Optimizer

Cool! Did you do any more progress on this @Grauw?

As for the "program is a DAG" or not, @pgimeno, if I understand correctly, this is a particular case, where the idea is to first linearize a program (or a section of the program). So, there are no loops here, etc. Then you want to find the way to recreate the same sequence using the minimum possible space, identifying subroutines, etc. Hence the DAG.

@santiontanon I made some fuzz tests for the suffix tree algorithm that I implemented and it didn’t do very well in those . That StackOverflow explanation gives a nice intuition but it misses some specifics. So I spent some time reading a chapter from a book by Gusfield (1997) that this explanation referenced (and more or less copies), gained some more understanding and now it’s working.

I think this weekend I’ll try to process a couple of test suffix trees to extract some useful data. E.g. first challenge would be to convert something simple like XXXXXXXX to bb / b = aa / a = XX.

@pgimeno, thanks for those links :). The case I’m looking into this for is even simpler since I’m dealing with a fully linear stream of commands that I want to “subroutinise” to compress it. But the paper that I found that describes pretty much what I want to do actually applied the techniques to entire programs.

Cool, still busy with other projects/work these days, but will follow your updates for when I go back to MDL

I also have a question: imagine that you have a sequence ABCDEFGHIJ for which you want to build the suffix tree in order to generate a more efficient way to express this code. Now, until now we have been assuming that the order of the tokens in ABCDEFGHIJ is fixed, but in reality there might be some instructions that can be executed in arbitrary order, e.g. it might be that ABCD and ABDC are equivalent. Do you think that if in addition to the sequence you have all the dependencies between the tokens, so you know which can be reordered, there is an easy way to exploit this to compress even more?

Interesting! I like the canonical order idea! And actually it could be useful in another way too! In my MSXDev entry, many parts of the code were compressed, and only decompressed to RAM when needed, in order to pack as much as I could into the cartridge. I am sure compression would work best if instructions were re-ordered in my source code according to some canonical order, and thus maximize the chance of similar bytes sequences when compressing. Maybe it'd only save a few bytes here and there, but still, every byte counts!

Another nice paper found: Procedural Abstraction with Reverse Prefix Trees. It reverses the operations pushed into the suffix tree to also identify cases where you can jump into subroutines at different locations, whilst keeping the single return at the end. Additionally it has a detailed description of the fragment discard criteria that I was missing from the other papers, both for regular suffix trees and reversed ones. The paper also references other research in the same space.

I found that using the search term “suffix tree functional abstraction” in Google Scholar gives several relevant results.

I’m not also able to read Ukkonen’s suffix tree paper. After going through the descriptions from stack overflow and Gusfield’s book, and implementation experience, I was finally able to understand it :).