One thing I might do is check whether there is a version of the revision 88 interpreter that has a less finicky implementation of virtual memory, because that will be more satisfying to optimize.
I have seen reference to different versions of Infocom interpreters, indicated by letters of the alphabet. For example, there is a “revision 88, interpreter B” and a “revision 88, interpreter F”. But I don’t know what the difference is, or how you can tell which one is being used. The game itself doesn’t seem to output such a letter, only the revision number. Can someone explain what these lettered versions are?
This is the disk image I am now using. It doesn’t say what version of the interpreter it may be.
Here are a few more disk images from the Internet Archive. To judge by the item identifiers, there are at least revisions B, F, and K, though I don’t know how the uploader knew that.
The interpreter writes its version letter into the header at VM address $1F. (Possibly only in version 4+?) It’s also embedded in the interpreter code. If you browse the disk image for the ASCII string Apple II Version or INTERPRETER VERSION you should see it.
% strings Zork_I_r88.dsk | grep -i version
Apple II Version F
…I see it also appears (at least in Zork) if you type $VERIFY.
Thank you! That information is really helpful. I see now that the version string is in the interpreter source code: "Apple II Version G" in io.g and "Apple II Version L" in io.l. zip.l has a brief changelog that mentions versions J, K, and L.
I extracted the version strings from the disk images I mentioned in post 21. Some of the disk images are in WOZ2 format, which is not directly searchable for strings, so I converted them to .dsk format using woz2dsk. The conversion failed in two cases.
One of them is version M, which I think is the latest version I’ve seen mentioned. I compared the virtual memory paging code of version F, which I have been using, against version M. I have not verified it yet, but there’s a difference that I think may make the page swapping code more well-behaved.
Procedure
Open .dsk file in BizHawk and run to the “80-COLUMN DISPLAY?” prompt.
Pause the emulator and open Tools→Hex Editor.
In the Hex Editor, File→Save as binary…. (This puts the memory image in linear order, as opposed to the interleaved ordering of sectors on disk.)
Open the resulting .bin file in Rizin, specifying 6502 as the architecture.
/x a2ff to search for the LDX #$FF instruction in NEXTPC and GETBYT, to put you in the vicinity of the paging code.
The only difference between the PAGE routine in version F and version M is that version M uses the EARLY2 function to find the page table entry with the minimum timestamp for the “discounting” operation, where version F uses EARLY (as I noted in post 19). The difference between EARLY and EARLY2 is that EARLY2 ignores timestamps that are zero. This could make a world of difference. EARLY2 always returns a nonzero timestamp, so STAMP is always decreased by at least 1 during discounting, and hence does not overflow.
If I am reading the code right, the use of EARLY2 means that page table entries (as long as they are not accessed) age until they reach a timestamp of zero, then they remain at zero. It is as if all the page table entries with a timestamp of zero are “infinitely old”: once they get that far in the past, we stop trying to track which is the oldest; they are all considered equally old for the purposes of eviction. The page table is still not truly an LRU cache, because we do not have the ability to compare timestamps after they get sufficiently old. But the page that gets evicted, if it is not the oldest page, is at least one of the oldest pages. This should avoid the pathological behavior of evicting recently accessed pages (that are likely to be needed again soon). The EARLY2 code is more eager to evict pages (I saw that it starts evicting pages even before the page table is full, which the EARLY code does not), but the pages it evicts are old ones.
Updating to version M of the interpreter is worth doing for its own sake. (Unless one of you knows of a later and/or more appropriate version.) So I’ll plan on doing that, and then I’ll be able to check whether my interpretation of how the paging code works is correct. It will be great if it lets route optimization have more to do with the game and less with the interpreter.