I6: Compiler option to coalesce identical packed strings?

Technical Development Development Systems
1

The new(ish) ZCODE_MAX_INLINE_STRING setting is useful for ensuring that strings of at least a certain size get an address. By setting it to zero, it seems like every string will get an address.

This is just a stone’s throw away from a space optimization of ensuring that all duplicate strings are coalesced into the same address by the compiler. I know there was a thread about this once, and the space savings for doing so wasn’t huge but wasn’t negligible, either (around 1%, if I recall correctly?).

I’m no expert on the compiler, but it seems like something that could be done without too much trouble, though at some overhead due to the need to analyze strings’ contents. Any chance of this option being put on the roadmap?

2

This has come up many times over the years. It’s never happened because the standard I6 library has some places (the list_together property) where strings are compared for equality. String coalescing could in theory change a game’s behavior. Although it would be an unusual game.

I don’t know if PunyLib works the same way. Still, it’s a trap waiting to happen, and defining your own string constants is easy enough if you want to avoid duplicated strings manually.

3

Well, Lazy Larry[1] would be safe if this were a compiler option instead of default behavior.

The way that list_together works, I don’t see this as a significant concern, anyway. If I’m understanding your point, the theoretical change would be that two objects sharing “lookalike” strings (i.e. identical strings that are nonetheless given separate addresses by the compiler) in their list_together property actually would be listed together if strings were coalesced, where in the current state they would not. Seems like chances are that the naive author would want and/or expect that behavior?

  1. my nickname for the hypothetical user who won’t touch code while insisting on using a newer version of the compiler ↩︎

4

Just piping in here…

You could argue that it’s coming up repeatedly because it’s something worth considering. Even if it’s a compiler option, off by default, any theoretical issues with the standard/puny libraries would suddenly gain visibility and could therefore become targets to address.

5

It does.

6

I found the previous discussion I was thinking of. As I understood it, the major objection then was that in-line strings constitute their own subproblem that makes the situation more complicated. (And I agree with that.)

This feature would be most useful (and be most predictable in its effect) when disallowing in-line strings entirely – that was the use case I was imagining when I said it seems like it’s only a stone’s throw away from current state. Maybe the hypothetical compiler option could require having set $ZCODE_MAX_INLINE_STRING to zero? Or could force it to zero with a warning?

7

It’s come up repeatedly because it’s easy to think of, but that doesn’t mean it would be a big benefit.

8

I don’t understand the compiler code very well, but I was looking at text.c to see what I could understand.

It looks like somewhere in the action of compile_string() and/or translate_text() is the main place where modifications would be needed? My uninformed idea would be to have translate_text() compute a hash value for each string that compile_string() could check against a list of previous values (perhaps also making a byte-by-byte comparison if the hash value is found to guard against hash collision?) before deciding that the literal represents an actually new string.

If I’m understanding the interface with the backpatching system (and I’m not sure that I am), it looks like it’s compile_string()'s return value that determines the actual marker value used. The way the return value is computed looks different for Z-Machine vs. Glulx (relative packed address vs sequential value, respectively?), but maybe the storage structure for checking existing string literal values could be the same in both cases (using an integer to store the marker value associated with the hash).

I think the logic to search for previous strings could go right after the following block in compile_string():

i = translate_text(-1, b, strctx);
if (i < 0) {
    error("text translation failed");
    i = 0;
}

which would be before the function does housekeeping tasks like padding for packed address spacing and making sure the total text limit hasn’t been exceeded (neither of which would be necessary if the string is not actually new).

9

So I went ahead and tried to implement a quickie prototype of this, which isn’t doing double-checking on hash collisions but seems to be working as a proof-of-concept. Some example compilation debugging output:

duplicate string detection 
Inform 6.44 for Linux (11th September 2025)
String 0 / RUINS had 5 chars with hash 3126239...
Adding new string for marker value 0...
String 2 / ^An Interactive Worked Example^Copyright (c) 1999 by Angela M. Horns^ had 69 chars with hash 4307736...
Adding new string for marker value 2...
String 17 / 040227 had 6 chars with hash 8177346...
Adding new string for marker value 17...
String 19 / 6/11 had 4 chars with hash 5438310...
Adding new string for marker value 19...
String 21 / a had 1 chars with hash 3399299...
Adding new string for marker value 21...
String 22 / --- had 3 chars with hash 2949274...
Adding new string for marker value 22...
String 23 / the had 3 chars with hash 9876454...
Adding new string for marker value 23...
String 24 / The  had 4 chars with hash 2238807...
Adding new string for marker value 24...
String 25 / the  had 4 chars with hash 516103...
Adding new string for marker value 25...
String 26 / a  had 2 chars with hash 5591919...
Adding new string for marker value 26...
String 27 / The  had 4 chars with hash 2238807...
Existing string marker found at index 24
Returning pre-existing marker 24 for string The ...
String 27 / the  had 4 chars with hash 516103...
Existing string marker found at index 25
Returning pre-existing marker 25 for string the ...

As would be expected, it doesn’t save space when all of the coalesced strings are below the ZCODE_MAX_INLINE_STRING limit, but when this is forced to zero there is about 1% reduction in file size, as seen in vaporware’s previous analysis. (Forcing it to zero does expand the file size more than the savings, though. I’m not sure why unless the bytecode overhead to print a packed string is so much larger on average than for an inline string that you lose on balance.)

However, it does solve the naive author’s list_together problem. Sample source:

uses strings for list_together 
Constant Story "Testing List Together";
Constant Headline "^(works as naively expected with coalesced strings)^";

Include "Parser";
Include "VerbLib";
Include "Grammar";

Class Room
	has light;

Room Start "Starting Point"
	with    description
	            "An uninteresting room.";

Object key1 "brass key" Start
	with    name 'brass' 'key' 'keys//p',
	        list_together "keys";

Object key2 "steel key" Start
	with    name 'steels' 'key' 'keys//p',
	        list_together "keys";

[ Initialise ;

	location = Start;

];

yielding:

Testing List Together
(works as naively expected with coalesced strings)
Release 1 / Serial number 260920 / Inform v6.44 Library 6/11 S

Starting Point
An uninteresting room.

You can see two keys (a brass key and a steel key) here.

>

as opposed to (with the normal compiler):

Starting Point
An uninteresting room.

You can see a brass key and a steel key here.

>

EDIT: For the benefit of anyone coming across this thread because it mentions list_together being set to a string, it’s worth noting that the pattern shown above (in which each object declares its own list_together) is actually not a great way to do it.

If instead a parent class is declared that includes the relevant list_together string, then this problem goes away even if strings aren’t coalesced because all instances of the class inherit the same string instance (which has the same address). So:

revised key example 
Class Key
	with    name 'key' 'keys//p',
	        list_together "keys";

Key key1 "brass key" Start
	with    name 'brass';

Key key2 "steel key" Start
	with    name 'steel';

which is just better coding practice all around.

10

Here’s the patch file for text.c (6.44 version), for anyone interested.

coalesce-strings-poc-6.44.patch.zip (1.0 KB)

This is very hacked-together, since I’m not a proper C programmer, and not suitable for anything other than a demonstration of the concept. Specific advisories include:

  • It’s not hooked up to a compiler option and spews progress/debugging data that can’t be turned off.
  • It allocates a large fixed array and assumes no more than 32K unique strings will be encountered.
  • The hash function is simple to the point of suspicion but had the advantage of being easy to implement.
  • Hashing is based on pre-encoded strings as seen in the user-provided source file.
  • The deduplication logic assumes that a hash collision means the strings were identical and does not double-check this.

A better programmer than me can surely do a better job.

On the plus side, in basic testing it works for both Z-Machine and Glulx.

I happen to know that Yoon Ha Lee’s Moonlit Tower was a bit careless about duplicating large strings in the source, so I ran some tests to see how well space savings might work in the wild.

moonlit.inf w/ 6.44  + StdLib 6/11 -> 163840 bytes
moonlit.inf w/ 6.44X + StdLib 6/11 -> 157184 bytes

That’s a bit over 4% reduction with the default ZCODE_MAX_INLINE_STRING value, over 15,552 strings.

moonlit.inf w/ 6.44  + StdLib 6/11 + no in-line -> 166912 bytes
moonlit.inf w/ 6.44X + StdLib 6/11 + no in-line -> 158720 bytes

That’s just shy of 5% reduction with ZCODE_MAX_INLINE_STRING set to zero, over 17,109 strings, and this time the coalesced string version is actually smaller than the default size with the current compiler.

11

It’s easy to think of because many people assume there are lots of identical strings floating around in their works. And… maybe?

Agreed. But “big” is subjective. I’d think the benefits could be established empirically. Of course, that probably would mean implementing said feature and running a collection of use cases through it. So… kinda moot, I guess, if you have to build the feature to decide if its worth building.

12

Ok, here’s my question.

The abbreviation feature also works by coalescing duplicated string content. Obviously it works at a different level and it’s a nuisance to use. (You have to precalculate a list of string fragments.) On the up side, it works on parts of strings.

So, how does this patch’s size reduction compare to -e mode, using Inform’s current best attempt at an abbreviation list?

13

(Forcing it to zero does expand the file size more than the savings, though. I’m not sure why unless the bytecode overhead to print a packed string is so much larger on average than for an inline string that you lose on balance.)

For zmachine there are a couple of strings (pun intended) pulling in different directions.

  1. The print opcode use fewer bytes than print_paddr.
  2. Every routine and high string waste a couple of bytes between then due to alignment in high memory. For example 10 inline strings in one routine is only subjected to one alignment but if you extract them to 10 high strings they are subjected to 10 alignments. You often save more memory by compiling as much strings as possible as inline. The drawback is that the routines gets bigger and on retro hardware you can get more swapping of memory.

The optimal solution would be to extract all strings from the game and identify identical ones and assign those to constants, thereby putting them among high strings. In code you will need to only move the identical strings to high memory and keep the unique ones as inline.

Edit: There are tools that help with this (nudge, nudge - zabbrev) but if you produce abbreviations and get unusually long sentences as suggestion for abbreviate, they are prime candidates for constants.

14 
moonlit.inf w/ 6.44  + StdLib 6/11 + I6 abbrevs -> 153088 bytes
moonlit.inf w/ 6.44X + StdLib 6/11 + I6 abbrevs -> 147968 bytes

A bit over 3.3% reduction with coalesced strings when using I6-generated abbreviations.

EDIT: I note that inspection of the debugging output shows the abbreviation markers, so it’s not the case that hashing is based on “pre-encoded strings as seen in the user-provided source file” when abbreviations are used. I guess the compiler globally replaces those in the source text prior to string compilation?

15

It’s also possible for a single routine to get so large (16kb) that branch instructions can’t get from one end to the other. I think this is what inspired the original MAX_INLINE_STRING check in the compiler. Retro games wouldn’t run into this but a big v8 game might.

16 
moonlit.inf w/ 6.44  + StdLib 6/11 -> 163840 bytes
moonlit.inf w/ 6.44X + StdLib 6/11 -> 157184 bytes

moonlit.inf w/ 6.44  + StdLib 6/11 + I6 abbrevs -> 153088 bytes
moonlit.inf w/ 6.44X + StdLib 6/11 + I6 abbrevs -> 147968 bytes

So abbreviations do better than string coalescing, which is what I sort of expected. But you can use both together for a small improvement (3.3% over abbrevations alone). I didn’t expect that part.

I want to do a few tests on games other than Moonlit Tower. (Advent.inf has a fair number of longish strings used twice. As always, these are cases where the author could use a string constant but it’s extra work.)

But I see there is an argument that this is at least worth a more serious look.

I don’t remember the exact code flow around string compilation. It’s very messy! Which is one reason that I am so hesitant to add any more features here.

17

The DM4 is clear that the language does not work the way the way the naive author expects.

(In particular, the actual text should only be written out in one place in the source code. Otherwise two or more different strings will be made, which just happen to have the same text as each other, and Inform will consider these to be different values of list_together.)

If we go through with this option, it will have a big warning that it can make list_together work wrong and that’s the author’s problem.

18

Some more examples from the wild…

Risorgimento Represso (source includes author-provided abbreviations):

risorg.inf w/ 6.44  + StdLib611 + orig abbrevs -> 476160 bytes
risorg.inf w/ 6.44X + StdLib611 + orig abbrevs -> 468480 bytes

About 1.6% reduction with coalesced strings.

Augmented Fourth (source includes author-provided abbreviations):

Aug4.inf w/ 6.44  + StdLib611 + orig abbrevs -> 407552 bytes
Aug4.inf w/ 6.44X + StdLib611 + orig abbrevs -> 395264 bytes

About 3.0% reduction with coalesced strings.

Blue Chairs (source includes author-provided abbreviations):

bluechairs.inf w/ 6.44  + StdLib611 + orig abbrevs -> 269824 bytes
bluechairs.inf w/ 6.44X + StdLib611 + orig abbrevs -> 269312 bytes

About 0.2% reduction with coalesced strings.

Spider and Web (source includes author-provided abbreviations):

tangle.inf w/ 6.44  + StdLib611 + orig abbrevs -> 253440 bytes
tangle.inf w/ 6.44X + StdLib611 + orig abbrevs -> 249856 bytes

About 1.4% reduction with coalesced strings.

Vespers (source does NOT include author-provided abbreviations):

vespers.inf w/ 6.44  + StdLib611 -> 335360 bytes
vespers.inf w/ 6.44X + StdLib611 -> 320000 bytes

About 4.6% reduction with coalesced strings.

None of these tests changed the default setting for $ZCODE_MAX_INLINE_STRING.

Blue Chairs is an unusually small difference, and this is true even when ignoring abbreviations. Glancing over the source code, it looks like quite a lot of the responses are very short (e.g. “That wouldn’t really help.”, “You hop a little, just because.”, “You’re not very good at singing.”) so an unusually large fraction of strings may be being inlined with default settings.

That is the real reported total for Vespers with strings coalesced, just lucky to be divisible by 10,000. Since the source doesn’t include abbreviations, it’s not surprising that it shows the largest space savings.

With a random set of spot tests it seems like the change is usually beneficial at a level comparable to or better than other space savings optimizations (e.g. stripping the unused dict_par3 byte).

19

For what it’s worth, my crappy patch is about 80 lines of code for a handful of functions. Changes to the original code are limited to the compile_string() function, which simply aborts and returns the previously-recorded marker value when a hash collision is detected. Doing leaves the marker value enumeration and target output game text storage unchanged.

A better version might use a more advanced hash routine (or use two different simple ones as a cross-check, or actually byte-by-byte compare when a collision is detected), and make better use of the compiler’s existing memory management subsystems to hold the array linking hash values to backpatch marker values.

20

The byte-by-byte check is mandatory. Can’t rely on probabilistic results for compile behavior. (Looking at Claude Code meaningfully…)

make better use of the compiler’s existing memory management subsystems

Sure.