I didn’t even try the byte-by-byte comparison because it wasn’t clear to me where the string to be analyzed was coming from, and I didn’t want to have to try to store each string’s contents. I had the vague idea that if the source code is available in memory in its entirety while compilation is going on, maybe the hash-to-marker storage could also record start and end points for the slice representing the string in question. However, from what little I’ve seen and understood so far, it seems like the lexer is supposed to throw away source code that it has already processed (which makes sense to me but could be a misinterpretation).
I’m in over my head looking at lexer.c, but I think maybe a lextext is created that holds the contents of the string literal to be processed before compile_string() is called. If that lextext persists (or a copy of it can be made to persist, as one of the comments suggests might be happening for dictionary words), it seems like it would be pretty easy to associate that to the hash value and marker value to make the previous string’s contents available for a byte-by-byte comparison.
FYI, I ran advent.inf as seen in the 6.44 r7 release ZIP file, which I think is the one you meant (and which doesn’t use abbreviations):
The code is fascinating. I didn’t know the i6 source was available. It is neat that it uses a Huffman encoding scheme for its compression. I’ve always really liked that algorithm.
I think it must be the case that forcing every inlined string out of routine space and into string space is creating double negative hits (both extra byte code for the print calls and wasted alignment space as you describe), and that for mid-sized strings (say 10-32 chars long, short phrases and sentences) there is enough variation that coalescing them doesn’t make up for that on average.
So I was wrong about when coalescing strings would be most useful – the benefit isn’t dependent on eliminating inlined strings, it comes more from de-duplicating strings that are already being placed into string space.
If I understand correctly, inlining can only happen for printing opcodes. (Is that right?) If so, then coalescing would ensure that string literals in any other context are not duplicated. And that would mean that a comparion "foo" == "foo" should always evaluate true if strings are coalesced, even though the lengths of the literals are below $ZCODE_MAX_INLINE_STRING?
Yes, inlining is only done with printing. All other strings are stored as packed pointers to high memory (well except character arrays, but that isn’t strings). “foo” == “foo” compares pointers.
Of course I was just speaking generally. It was obvious that the code only uses Huffman encoding in glulx mode. It was neat to see it. I wrote an assembly version of Huffman. I’ve used it in many projects and it is inline in C source code. It makes such a difference in assembly.
edit - For the ask, are the identical packed strings the strings that aren’t common enough for the common string lookup table? These then are the strings that are duplicates but not enough to be common duplicates? Would there perhaps be a few alternate options for determining duplicates to examine if one scheme performs better than another for a certain title?
You really have to have read the Z-Machine specifications to make a lot of sense out of this conversation (probably at least twice, based on my own misapphrensions after having read through it once).
The basics:
The Z-Machine memory map includes different dedicated spaces for storing routines versus strings.
All Z-machine strings are fixed with respect to their contents at compile time.
When string literals are part of a routine, the compiler decides (in the case of printing operations only) whether to put that string data in the dedicated string space or keep it inlined within the logic of the routine in the dedicated routine space. There is a length parameter (default 32 characters) that it uses to make the decision.
The compiler currently doesn’t make any effort to save space in the case of a non-inlined string that is identical to another one which already exists; it just creates another string with the same content. This will waste an amount of storage dependent on the size and frequency of duplicate strings in the source code.
I was under the mistaken impression that the decision to inline was based only on the string length, regardless of context. In fact, even literals short enough to be under the inline limit parameter will be moved to the dedicated string space when they are not attached to a print operation. (See the explanation by heasm66 above.)
I was also under the mistaken impression that it would be necessary to prevent all inlining to see the benefit from coalescing strings. Tests so far suggest that the typical author can get a significant amount of space savings (where “significant” means a few K) from coalescing strings without changing the default inline limit. Tests so far also suggest that preventing all inlining will usually require more space than coalescing the moved strings will gain back. (Again, see the explanation by heasm66 above.)
I’m not sure whether or not that answers your questions, because many assumptions about how I6 works based experience with other languages don’t really hold, and some of the terms used in the discussion (e.g. “packed”) have very specific meanings that aren’t easily translated outside of this domain. (At least, not by me.)
If the suggested compiler option is implemented, an author would have control of both whether that option was active and the already-existing inline length limit, so there would be room to experiment with different combinations to find what works best for a given project.
Does this mean the 5-bit string that was referenced in the previous comment? I found that Infocom used a middle of the road solution to pack 3 bytes into 2 bytes for space saving of the string and that the algorithm was chosen because it could perform well enough on a 1 MHz machine.
“Packed” in Z-machine terminology usually refers to packed addresses. This is a way to store addresses for a 128-512 KB address space as 16-bit numbers (by lowering the resolution, thus introducing the need for padding).
But yes, a string is encoded into a number of five-bit codes, and each pair of bytes hold three five-bit codes, plus a bit saying if this is the last byte-pair of the string.
Or in other words—“packed strings” are strings stored in the strings area of high (non-byte-addressable) memory, where they have to be referenced via packed addresses. The alternatives are “inline strings” stored in the routine area (which don’t have an accessible address at all) and “low strings” stored in low (byte-addressable) memory, where they’re referenced via raw byte addresses.