Here’s the result of a recent build of my IFComp entry, made with the latest ifcomp2025 compiler for z8 format.
Debug: Heap: 2500 words
Debug: Auxiliary heap: 500 words
Debug: Long-term heap: 750 words
Debug: Registers used: 118 of 240* (49%)
Debug: Properties used: 0 of 63 (0%)
Debug: Dynamic flags used: 7 of 48 (14%)
Debug: Total flags used: 45 native
Debug: Objects used: 340 of 8190 (4%)
Debug: Dictionary words used: 1420 of 7679 (18%)
Debug: Extended ZSCII characters used: 76 of 97 (78%)
Debug: Addressable memory used: 25520 of 65536 bytes (38%)
Debug: Object table: 7612
Debug: Object vars: 1360
Debug: Wordmaps: 8147
Debug: Unicode data: 161
Debug: Main heap: 5000
Debug: Auxiliary heap: 1000
Debug: Long-term heap: 1500
Debug: Total filesize used: 497248 of 524288 bytes (94%)
Debug: Routines: 16080
Debug: Strings: 62432
In this case at least, objects and dictionary words are not in short supply, and RAM is not much of an issue now that the $8000 bug is fixed. The most pressing limitation is ROM space. (And the only other metric that’s over 50% is ZSCII characters, which are easy to get more of via the --no-default-unicode option.)
This suggests that we shouldn’t be worried about saving RAM, and optimization efforts should be focused on more efficiently compiling strings and routines. Using abbreviations in the string encoding, for example, would help much more than my previous dictionary optimizations.
I assume that routines and strings are the number of each, not the size in bytes of them?
Abbreviations are relatively easy to implement. Both encoding (optimal parse) and decoding algorithm are straight forward, and zabbrev can be used externally to calculate them (algorithm can of course be included in Dialog too).
Are the compiling done in one or two stages? If it is two, then the abbreviations could be calculated in the first stage and encoded in the second.
Interesting. This is the opposite of Inform 6, which uses property tables and global variables heavily.
We usually think of abbreviation calculation as a slow process, but also one that doesn’t have to be redone on each compile. You can manually generate an abbrevation table, and then maybe regenerate it once a week as you work, with a final rebuild at release time.
There’s actually already a way to calculate abbreviations for Dialog games, but it is a bit cumbersome. One can use UnZ to extract the text from the compiled file and then run zabbrev on the extracted text. Pretty useless at the moment when Dialog lacks means for encoding and decoding them, but anyway.
Should be bytes, unless I’ve got something wrong in the diagnostic code.
Two stages. First it compiles the Dialog code to an intermediate representation that lives in memory (and this is what the debugger executes); then it compiles that intermediate representation into either Z-code or Å-code.
It’s not trivial, because the IR doesn’t really have a concept of strings the same way Inform does, but the IR-to-Z process also has several stages, and you could do the abbreviation calculation after generating the strings but before saving them into the file. That’s where dictionary words are currently analyzed to put non-ASCII characters into the Unicode translation table, for example.
Excellent! I think this would be the next big step forward for the Dialog compiler, if you’re interested in implementing it. (Or even if you can just give me a writeup of the algorithms; classes are about to start, but I do a bit of compiler work when I have time for it.)
The thing with Dialog is that its philosophy is “keep the language and compiler high-level and do as much optimization as possible automatically”, so there’s no easy way to have it generate an abbreviation table once and then use that later when compiling. The ideal, philosophically, would be to calculate abbreviations during each compilation.
So how slow are we talking? Right now, when I run regression tests on my IFComp entry, compiling takes a split second but running the full game through dumbfrotz takes about ten to twenty seconds.
Yeah, Dialog is extremely efficient at using Z-machine RAM. It turns as many object properties into attributes as possible, and when it runs out of attributes, it compiles arrays of bytes where each bit represents one “extended attribute” (so that an “extended attribute” lookup is just @loadb array object -> sp; @test sp bit). It avoids property tables entirely, and compiles Dialog “properties” as big arrays indexed by object.
The drawback of this is that it’s impossible to have a property only apply to certain objects. Every dynamic property costs one word per object in the game. So the manual encourages authors to avoid these if possible and use global variables instead. This game has only two per-object properties, one used by the standard library, the other by the automap code.
It’s also very efficient at compiling global flags (that is, single-bit globals), packing sixteen of them to a register, which is why an almost-500kB game uses only 118 of the 240 Z-machine registers. (77 of those are used by the compiler for its own purposes, so 41 of them are used for game flags and variables.)
It’s fun having these diagnostics now! All along I’d thought RAM would be the most precious resource, but it turns out the compiler is good enough at optimizing that it doesn’t become an issue at all.
A custom alphabet would be easy to implement, because it already uses a custom Unicode translation table. The tricky part would be making it apply to inline strings in the veneer, since some of those are compiled very early, but the timing shouldn’t be impossible.
The abbreviations are the hard part, mostly because I don’t know any good algorithms for calculating those without building my own new data structures (since C doesn’t provide anything beyond arrays).
@jxself converted my zabbrev from C# to C, so the algorithm is there with a suffix array and all. Doing the first suffix array stage (~95% of the saving) would take a couple of seconds, I guess.
So the total file size is right, but I’ve messed something up in calculating how much space is used by routines and strings. Routines should be 278,424 bytes and strings should be 193,648.
The other side of this, which I forgot to mention, is that Dialog generally compiles static data into routines rather than tables—the exits from each room, for example, are compiled into one big routine that takes a source and a direction and returns the room in that direction, and a second big routine that takes a source and a destination and returns the direction to that destination. This is rather less efficient in terms of space, but since high memory is cheaper than addressable memory by a factor of 8, it generally ends up being a pretty good tradeoff.
Unfortunately, both versions of ZAbbrev are GPL-licensed, which means they can’t be used in Dialog. So I’m going to avoid looking at the code for them, just in case. But the reference in your ZAbbrev repository will still be very helpful for this!
I think a good first step will be coming up with a set of abbreviations that’s generally effective for English, and hardcoding that into the compiler. This should get moderate savings for most projects, and doesn’t require analyzing the text to find good abbreviations in and of itself—it just requires the Wagner optimal-parse algorithm.
Once that’s in place, we could start looking at generating new abbreviations.
It’s definitely a pain! I think if you just state somewhere in the repository (e.g. in the README) that you also allow use under the MIT license (or your favorite permissive license), either to the Dialog project or to everyone in the world more generally, that’s enough.
(Really, since you’re the author, it wouldn’t be a problem in practice unless you decided to sue us over it. But an explicit “you’re allowed to do this, I won’t sue you for it” is always better than an informal agreement when it comes to licensing!)
I’ll do that, I may even write a suggestion as a code snippet.
Design-wise I don’t think a compiler switch that imports abbreviations from an externally created file isn’t totally wrong. You then don’t need to invent Dialog-syntax for specifying abbreviations or slowing down the compilation every time because abbreviations are calculated. At least as a first step. Implement encoding and decoding and you’re good to go.
Yeah; I’m on the fence about it philosophically, but I think if the compiler’s default behavior is pretty good (either generating its own abbreviations or using a built-in “usually good enough” set), then letting the user tweak the settings further isn’t the end of the world. Then future versions of the compiler can get smarter about the default behavior until manual intervention is no longer needed.
Okay, yeah, this should be doable. I’ll make an issue to discuss it further. But basically:
There’s a routine called generate_output_from_utf8 in backend_z.c that takes strings of source text and turns them into Z-machine instructions.
Near the top of the routine, it calls utf8_to_zscii to convert the array of UTF-8 bytes into an array of ZSCII bytes. (This is where a custom alphabet table would happen.)
Shortly after that, it calls find_global_string to store the resulting string in a hash-set.
In between the two of those, we could call a new abbreviate_zscii routine to transform one array of ZSCII into another, applying the abbreviations per Wagner’s algorithm.
There’s also a routine called init_abbrev called during compiling, which compiles the abbreviation strings and abbreviation table into the Z-code file. This would be rewritten to insert our own table instead.
So if we make a new data structure to store the abbreviations (probably just an array for now?), and write two new routines (one for Wagner’s algorithm and one to compile the abbreviations), that should be enough for the first pass, and that should save a significant (hopefully!) amount of ROM.
out of curiosity, what is the license of your new version of dialogc ?
The logic behind GPL is about ensuring that the “licensed” code will never be put under the hood for profit.
but OTOH, under a serious OS, isn’t difficult piping out to Zabbrev the entire vocabulary and piping in to dialogc the resulting set of abbreviation… of, course this will slow down the compilation, but if you for what strange reason don’t want to release your version of dialogs under GPL, perhaps is a feasible alternative…
Linus’s original versions of Dialog were released under an MIT license, so our continuation has also stuck to an MIT license. Legally speaking, nothing stops us from switching to the GPL, but (1) I’m not a big fan of the GPL personally, and (2) I don’t want to unilaterally declare to all the other contributors that the project license is becoming more restrictive going forward, so they’ll need to fork the whole thing if they want to keep working under the previous terms.
We’d also need to put exceptions in the license, because the Dialog compiler includes a certain amount of “veneer” Z-machine code that’s copied verbatim into every Z-code file it produces (e.g. routines written in Z-machine assembly to traverse lists and consult wordmaps), and I really don’t want to tell every user that any of their projects compiled with new versions of Dialog are now suddenly under the GPL. So we would need to release the veneer under one license and the compiler proper under another, and it’s just a headache I don’t want to deal with.