| Route | Moves | Frames | Time |
|---|---|---|---|
| baseline | 258 | 25139 | 6:58.98 |
| baseline+tweaks | 257 | 22848 | 6:20.80 |
| thief-based route | 236 | 20685 | 5:44.75 |
| alternative commands | 239 | 19759 | 5:29.32 |
| COFFIN last | 231 | 19263 | 5:21.05 |
| this | 222 | 18494 | 5:08.24 |
| Settings | Frames | Time |
|---|---|---|
| 80 columns, brief | 18494 | 5:08.24 |
| 40 columns, brief | 17299 | 4:48.32 |
| 80 columns, superbrief | 15096 | 4:11.60 |
| 40 columns, superbrief | 14454 | 4:00.90 |
>drop all in cage
huge diamond: Done.
brass lantern: Done.
screwdriver: Done.
>lift cage
The basket is raised to the top of the shaft.
>eaSt
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>EASt
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>gO up
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>go up
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>north
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>east
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>sOuth
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>NOrtH
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>gO up
You have moved into a dark place.
It is pitch black. You are likely to be eaten by a grue.
>south
Shaft Room
At the end of the chain is a basket.
The basket contains:
A screwdriver
A brass lantern (providing light)
A huge diamond
A histogram, "cycles per call to DOS in GETDSK". The horizontal axis is "cycles" from 0 to 300,000 and "frames" from 0 to about 18. The vertical axis is "count" from 0 to 350. There is a prominent mode, with a count of about 350, at about 40,000 cycles. There are many sparse bars above that and a few below, with counts usually below 50.
There's a prominent mode—about 20% of calls to DOS—that take around 40,000 CPU cycles, or 2 video frames, which is among the shortest times measured. But then there is a broad smear of times that extends up to 300,000 cycles, or 18 frames. Could this be the cause of the finicky timing of executing commands? No, I don't think so. To see why, understand that the DOS subroutine can be decomposed into a few blocks of code that take a fixed amount of time to execute, plus a call to SEEK and a GETADR loop that take variable amounts of time. The sums of these component timings is what gives rise to the distribution shown above.
SEEK moves the read head to the requested track. Timing SEEK alone yields the following timing distribution:
A histogram, "cycles per call to SEEK in DOSEEK". The horizontal axis is "cycles" from 0 to 250,000 and "frames" from 0 to about 15. The vertical axis is "count" from 0 to 600. There are 15 non-zero bins. The largest, with a count of about 600, is at approximately 0 cycles. The next is at 50,000 cycles with a count of 280. Then the bins are spaced roughly evenly at intervals of about 20,000 cycles, for the most part smoothly decreasing in count.
We see that only a few discrete timings are possible from SEEK. It turns out that the timing of SEEK depends entirely on how many tracks the read head has to travel over. Sometimes, the head is already over the right track; in that case the time required to seek is practically zero. The greater the absolute value of the difference between the current track (ctrack) and the desired track (ttrk), the more time it takes:
A scatterplot, "cycles per call to SEEK in DOSEEK, by distance". The horizontal axis is "ttrk − ctrk" from −30 to +30. The vertical axis is "cycles" from 0 to 250,000 and "frames" from 0 to about 15. The points are semitransparent but so heavily overplotted that all but the most extreme appear opaque. The plot is symmetrical about the middle. There is a point at (0, 0) at the bottom middle, and then the points increase smoothly on both sides.
So the timing of SEEK depends only on the current track and the sought track. It cannot be the cause of long-term drift. What about GETADR, then?
GETADR is a loop that repeatedly calls RDADDR until the disk drive reports that the sector currently being read is the right one. The timing distribution of the GETADR loop looks like this:
A histogram, "cycles per GETADR loop in DOS". The horizontal axis is "cycles" from 0 to 100,000 and "frames" from 0 to about 6. The vertical axis is "count" from 0 to 350. There are 16 main non-zero bins, evenly spaced at intervals of about 6,500 cycles starting from 0. The largest, with a count of about 350, is at about 20,000 cycles. The rest mostly have a count between 50 and 100. There are some shorter non-zero bins midway between some adjacent pairs of main bins.
Again we see a distribution that is highly discrete. There are 16 main peaks: this makes sense as the disk format has 16 sectors per track. The peak with the highest count is the 4th one from the left, and I think there is a good reason for that. The sectors are stored on disk, not in numerical order, but in an "interleaved" order that means that logical sector n + 1 is usually stored 4 physical sectors after logical sector n. In the common case of reading sectors sequentially, the GETADR loop has to skip over 3 physical sectors between consecutive logical sectors.
The Virtu emulator does not simulate continuous rotation of the disk. Instead, every time the track changes, it starts over with sector 0 of the track and serves the sectors to the application in order.
That does it for the floppy disk simulation hypothesis. Disk access times are variable, but the timing of any given disk access depends only on the current track and sector and and track and sector to be read. Making a change in the middle of a sequence of accesses does not have long-term effects.
The LRU page table that is not always LRU
The cause of the timing variations, I am convinced, is the implementation of the virtual memory page table in the Z-code interpreter.
The use of virtual memory by the Infocom interpreters is one of the most interesting facts about them, to me. The Zork I story file is about 83 KB, small enough to fit on a floppy disk but larger than the Apple II's 16-bit address space. (Even ignoring the space required for the interpreter itself.) So the interpreter inserts a virtualization layer between the program running in memory and the Z-code on disk. When a particular byte (at a particular address) is requested from the story file, the interpreter consults the page table to see if that page has been loaded into RAM; if it has, the interpreter looks up the address where the page is stored and reads the byte from there. If it has not, the interpreter reads the page from disk into RAM, updates the page table, then returns the requested byte.
The page table has a finite size. The question is what to do when a page is requested that is not in the page table, but every slot in the page table is already occupied. The interpreter needs to evict some other page to make room for the page that is now needed. If that evicted page is needed again later, it will have to be paged back in from disk.
This file apple/zip/npaging.h is a close match to the page table code that is present in the disk image I am using. (It's not an exact match: for example the code on the disk image lacks the EARLY2 subroutine and calls EARLY in its place; but it's closer than the files paging.asm and zpaging.asm in the same directory.) When the program fetches a byte of code (via NEXTPC) or data (via GETBYT), it calls the PAGE subroutine to find the necessary page in the page table, swapping it in if necessary.
The program code intends to implement a least recently used (LRU) cache eviction policy. This is evidenced in comments like "TIME-STAMP PAGING ROUTINE" and labels like LRUMAP. But, in fact, when the time comes to evict a page from the cache, the page chosen is not always the least recently used one. Frequently, the page that is evicted is actually one that was used recently and will be needed again in the near future. This is because of an integer overflow in the incrementing counter that serves as a timestamp. (Call it a bug—there's nothing in the source code, in the form of comments or otherwise, that indicates it's supposed to act the way it does.)
Here's how the page table is supposed to work. Each page table entry consists of two data fields: a 16-bit page ID and an 8-bit timestamp. There is a global 8-bit integer, STAMP, that increases by 1 every time any page is accessed. Whenever a page accessed, its timestamp is set to the current value of STAMP. The idea is that page table entries are brought up to date with the current STAMP whenever they are used, and unused pages' timestamps are left alone, so therefore you can find the least recently used page table entry by looking for the one with the oldest (lowest) timestamp.
This is the ideal state of the page table: every entry's timestamp is less than or equal to STAMP, and the least recently used page has the lowest timestamp. While these conditions hold, the page table is a true LRU cache, but they almost never do.
STAMP is an 8-bit counter—it can't keep increasing forever. What happens when STAMP overflows from 255 to 0? This is where things to go wrong. The page table code tries to do something to cope with the situation, but it does not really work, and STAMP very frequently ends up overflowing.
When STAMP overflows, the page table does an operation I'll call "discounting". What it tries to do is shift the whole table back in time to make room for STAMP to continue increasing. Specifically: find the entry with the minimum timestamp, then subtract that minimum from every entry's timestamp, and from STAMP itself. If the minimum timestamp in the page table is 10, for example, then that entry's timestamp becomes 0, all other entries' timestamps get decreased by 10, and STAMP gets reset from 0 to 246, now with room to continue growing.
The problem is, it's very very common for the minimum timestamp in the page table to be 0. When that happens, all timestamps and STAMP remain unchanged, and STAMP overflows from 255 to 0. To make matters worse, whatever page was just accessed gets marked with the new STAMP of 0—what should be the newest page in the table is instead tagged as being as old as it could possibly be! At the next page swap, the just-accessed page will be one of the leading candidates for eviction. (But it's not guaranteed to be the next page evicted: there can be ties between multiple entries with the same timestamp, and if the page continues to be accessed its timestamp will gradually increase as STAMP climbs back up from 0.)
In the course of a run, STAMP overflows many times, and each time it overflows, some page gets tagged with an ultra-low timestamp that makes it prone to eviction. This haphazard eviction is sometimes favorable, sometimes unfavorable—it is hard to control and predict. Below is a graph that shows what real memory pages are resident at what times throughout the 100%-80-brief run. The directory experiments/page contains code to reproduce the graph, and my rough notes on the subject start here. A round dot indicates that a page was accessed: ideally, this should make it the most recently used page. The vertical colored strips show the value of the timestamp field of each live page table entry: darker is older; brighter is newer.
A large wide graph, "pages loaded into virtual memory and LRU timestamp". The horizontal axis is "page" from 0x50 to 0x150. The vertical axis is "cycle" from 0 to 315,000,000 and "frame" from 1 to 18,575 (increasing downward). A continuous color axis "stamp" ranges from 0 (black) to 255 (light blue). Strips of varying blue and black run vertically downward from starting dots, with dots punctuating most of the strips more than once. Some ranges of pages—from 0x50 to 0x70, around 0x90, and around 0x100—are frequently accessed and are mostly continuous from top to bottom. Other pages are only occasionally accessed and the strips are sparser and shorter-lived.
When you see one of the vertical strips fade from bright blue to black, with no intervening dots, that's the discounting operation gradually decreasing that page table entry's timestamp. When you see a bright blue strip suddenly interrupted by a black dot, that's STAMP overflowing and a freshly accessed page being marked with a 0 timestamp. As you can see, STAMP overflows a lot—it's not at all an exceptional condition.
Look at page 0x50 (at the far left) around cycle 240,000,000. The page, which had been bright blue, indicating a recent timestamp, is accessed as STAMP overflows, and becomes black. Then page 0x50 is evicted around cycle 244,000,000. If the page table were a proper LRU cache, that eviction would not have happened, because it's easy to see other pages (e.g. 0x5c, 0x78, 0x80) that were resident at the time and that had been accessed less recently.
A demonstration of problems caused by anomalous page table eviction
This STAMP overflow phenomenon is what makes the page table sensitively dependent on initial conditions—why small, local changes in page accesses can have accumulating, far-reaching effects. I tried an experiment with modifying just the final thief fight. I constrained the remarks after hitting the thief to be faster ones, which should only speed up the fight. And speed up the fight it does—but then unfavorable page table evictions make it slower by the end. Here's the before-and-after diff of the transcript of the thief fight:
At first, the modified fight is faster by 3 frames; but it ultimately works out to be 32 frames slower.Language: diffYour sword has begun to glow very brightly. -You parry a lightning thrust, and the thief salutes you with a grim nod. +The thief tries to sneak past your guard, but you twist away. ->Hit man +>HIt mAn (with the sword) -A savage blow on the thigh! The thief is stunned but can still fight! -You parry a lightning thrust, and the thief salutes you with a grim nod. +Slash! Your stroke connects! This could be serious! +The thief tries to sneak past your guard, but you twist away. ->G +>g -A savage blow on the thigh! The thief is stunned but can still fight! -You dodge as the thief comes in low. +Slash! Your blow lands! That one hit an artery, it could be serious! +You parry a lightning thrust, and the thief salutes you with a grim nod. ->g +>G The thief takes a fatal blow and slumps to the floor dead.
Before frames | Before command | After frames | After command | Cumulative advantage | Per-command advantage |
|---|---|---|---|---|---|
15202 | s.u.w.w.u | 15202 | S.U.W.W.u | 0 | +1 |
15661 | Hit man | 15660 | HIt mAn | +1 | +2 |
15874 | G | 15871 | g | +3 | 0 |
15937 | g | 15934 | G | +3 | 0 |
16100 | drop old | 16097 | drop old | +3 | 0 |
16194 | get canary | 16191 | get canary | +3 | +7 |
16308 | temple | 16298 | temple | +10 | −5 |
16377 | d | 16372 | d | +5 | +11 |
16449 | get | 16433 | get | +16 | −26 |
16502 | u.s | 16512 | u.s | −10 | −4 |
16567 | pray | 16581 | Pray | −14 | +1 |
16653 | Wind canary | 16666 | wind canary | −13 | −16 |
16728 | get | 16757 | get | −29 | +12 |
16803 | e.s.e.w.w | 16820 | e.s.e.w.w | −17 | +1 |
17123 | drop all treasu in case | 17139 | drop all treasu in case | −16 | +12 |
17352 | w.w.u | 17356 | w.w.u | −4 | +11 |
17563 | drop all | 17556 | drop all | +7 | −39 |
17660 | Get all treasu | 17692 | get all treasu | −32 | −2 |
17821 | D | 17855 | d | −34 | +3 |
17887 | E | 17918 | E | −31 | −1 |
17935 | e | 17967 | e | −32 | 0 |
18041 | drop all in case | 18073 | drop all in case | −32 | 0 |
18280 | e.e.n.w.sw.w | 18312 | e.e.n.w.sw.w | −32 |
A 2-frame looping GIF animation, showing the lower left area of the page table graph: "cycles" from 265,000,000 to 315,000,000 and "pages" from 0x50 to 0xa4. The first frame is the same as in the graph above. The second frame shows the modified thief fight. There are places where the first frame has gaps and the second is connected, and vice versa. The dots (indicating page accesses) in the modified fight are shifted upward (indicating a time savings) until about cycle 280,000,000; but after that they are generally shifted downward, indicating a time loss.
Let's look at a particular case of STAMP overflow to see its effects on the page table. The left group of columns is the original thief fight; the right group is the modified (faster) thief fight. This table doesn't show every page access, only ones that resulted in a swap.
cycle | frame | zpage | page | STAMP | cycle | frame | zpage | page | STAMP | |
|---|---|---|---|---|---|---|---|---|---|---|
272337867 | 15991 | 16 | 0x78 | 228 | 272287738 | 15988 | 16 | 0x78 | 224 | |
272716133 | 16014 | 61 | 0xd7 | 254 | 272663464 | 16011 | 61 | 0xd7 | 254 | |
272811368 | 16019 | 24 | 0xd2 | 255 | 272758699 | 16016 | 24 | 0xd2 | 255 | |
273315572 | 16049 | 24 | 0x95 | 5 | 273262882 | 16046 | 12 | 0x95 | 0 | |
275050196 | 16151 | 12 | 0x76 | 219 | 274999096 | 16148 | 12 | 0x76 | 213 | |
275108188 | 16154 | 53 | 0x77 | 223 | 275057076 | 16151 | 1 | 0x77 | 217 | |
275255591 | 16163 | 24 | 0x92 | 225 | 275204491 | 16160 | 61 | 0x92 | 219 | |
276680776 | 16246 | 1 | 0x87 | 165 | 276629712 | 16243 | 60 | 0x87 | 161 | |
276881986 | 16258 | 25 | 0xf1 | 168 | 276830922 | 16255 | 37 | 0xf1 | 164 | |
277037566 | 16267 | 61 | 0x90 | 171 | 277153667 | 16274 | 43 | 0x54 | 188 | |
277384683 | 16288 | 37 | 0x100 | 218 | 277981061 | 16323 | 45 | 0x8a | 23 | |
278212278 | 16336 | 43 | 0x8a | 24 | 278140336 | 16332 | 22 | 0x93 | 25 |
| Settings | Version F frames | Version M frames | Ratio |
|---|---|---|---|
| 100%-80-brief | 18494 | 20860 | 112.79% |
| 100%-40-brief | 17299 | 19653 | 113.61% |
| 100%-80-superbrief | 15096 | 17538 | 116.18% |
| 100%-40-superbrief | 14454 | 16741 | 115.82% |
A large wide graph, "pages loaded into virtual memory and LRU timestamp". The horizontal axis is "page" from 0x50 to 0x150. The vertical axis is "cycle" from 0 to 360,000,000 and "frame" from 1 to 21,000 (increasing downward). A continuous color axis "stamp" ranges from 0 (black) to 255 (light blue). Strips of varying blue and black run vertically downward from starting dots, with dots punctuating most of the strips more than once. Compared to the corresponding version F graph, the strips under infrequently accessed pages are shorter, indicating quicker eviction. The dots that indicated memory access are generally bright blue in color, indicating that they are assigned a recent timestamp and not overflowing. There are, however, a few infrequently accessed pages—such as 0x78, 0xfa, 0x124, and 0x140—that persist for a long time with a strip that quickly turns black, indicating a timestamp of zero.
Compared to the version F graph, the most obvious difference is the generally shorter lifetimes of infrequently accessed pages. You see this in the graph as dots (which indicate when a page was accessed and swapped in if necessary) with a short strip under them (the end of the strip is when the page is evicted). There are, however, a few infrequently accessed pages that persist for a long time without being evicted, with a black strip that indicates a zero timestamp. Some examples are 0x78, 0xfa, 0x124, and 0x140. Another thing to notice is that the dots that indicate memory access are generally bright blue in color, which means they were assigned a recent timestamp that did not overflow. Finally, though it is not obvious visually, the version M page table has fewer live pages at its maximum. If you draw a horizontal line, you'll intersect at most 50 live pages in version M, while in version F the maximum is 62.
The key difference in the version M page table code is that when a page's timestamp decreases all the way to zero, it stays at zero until it is accessed or evicted. Pages with a zero timestamp are considered equally and maximally old: they are the first candidates for eviction. However, when there is a tie for the oldest page table entry (which is almost always the case, multiple pages having a zero timestamp), the one at the highest index is the one that is chosen for eviction.
Tie-breaking by index creates a bias in the selection of which page table entries get evicted. A page that lives at a higher index is more likely to get evicted than one at a lower index. The competition for eviction near the end of the page table is so fierce that 12 entries at the beginning go completely unused in this run; there's never a time when all higher indices have a non-zero timestamp. (This is clearly suboptimal on the part of the interpreter. It would do better to fill an unused page table entry rather than evict a live one.) This bias is what accounts for the entries that are infrequently accessed and yet persist in the page table for a long time: they happened to get placed at a low index. Here's a snapshot of the page table at the end of the run (corresponding to the lowest row in the graph). It shows the 12 unused entries (ptab = −1) at the lowest indices, as well as some of the long-lived entries I noted above (0x78, 0x140, 0xfa), which are also at relatively low indices:
zpage | ptab | STAMP |
|---|---|---|
0 | −1 | 0 |
1 | −1 | 0 |
2 | −1 | 0 |
3 | −1 | 0 |
4 | −1 | 0 |
5 | −1 | 0 |
6 | −1 | 0 |
7 | −1 | 0 |
8 | −1 | 0 |
9 | −1 | 0 |
10 | −1 | 0 |
11 | −1 | 0 |
12 | 0x78 | 0 |
13 | 0xff | 0 |
14 | 0x140 | 0 |
15 | 0xfa | 0 |
16 | 0xe1 | 0 |
17 | 0x50 | 0 |
18 | 0x91 | 0 |
19 | 0x67 | 0 |
20 | 0x60 | 0 |
21 | 0x8f | 85 |
22 | 0x66 | 0 |
23 | 0x64 | 0 |
24 | 0xfe | 0 |
25 | 0x6d | 142 |
26 | 0x6a | 0 |
27 | 0x8e | 84 |
28 | 0x147 | 0 |
29 | 0xf9 | 0 |
30 | 0xfc | 0 |
31 | 0x13d | 0 |
32 | 0x56 | 0 |
33 | 0x100 | 121 |
34 | 0x92 | 60 |
35 | 0x61 | 0 |
36 | 0x68 | 0 |
37 | 0x6e | 143 |
38 | 0x8d | 86 |
39 | 0x94 | 88 |
40 | 0x8c | 87 |
41 | 0x9f | 135 |
42 | 0x93 | 63 |
43 | 0x57 | 133 |
44 | 0x5a | 130 |
45 | 0x5b | 131 |
46 | 0x6c | 62 |
47 | 0x106 | 141 |
48 | 0x58 | 134 |
49 | 0x55 | 132 |
50 | 0x95 | 56 |
51 | 0x105 | 140 |
52 | 0x90 | 67 |
53 | 0xa2 | 138 |
54 | 0x8a | 58 |
55 | 0x54 | 123 |
56 | 0x59 | 129 |
57 | 0x8b | 89 |
58 | 0xa1 | 137 |
59 | 0xa0 | 136 |
60 | 0x11d | 74 |
61 | 0x11c | 73 |
Version F frames | Version F command | Version M frames | Version M command | Cumulative advantage | Per-command advantage |
|---|---|---|---|---|---|
521 | N.n.u | 521 | N.n.u | 0 | 0 |
761 | get egg | 761 | get egg | 0 | 0 |
920 | d.s.e | 920 | d.s.e | 0 | 0 |
1016 | open | 1016 | open | 0 | 0 |
1102 | w | 1102 | w | 0 | 0 |
1222 | open bag | 1222 | open bag | 0 | 0 |
1298 | get clove | 1298 | get clove | 0 | 0 |
1376 | w | 1376 | w | 0 | 0 |
1498 | light | 1498 | light | 0 | 0 |
1590 | get | 1590 | get | 0 | 0 |
1685 | tug rug | 1685 | tug rug | 0 | 0 |
1790 | open trap | 1790 | open trap | 0 | 0 |
1872 | d.n | 1872 | d.n | 0 | 0 |
2065 | hit nasty | 2065 | hit nasty | 0 | 0 |
2259 | drop old,egg | 2259 | drop old,egg | 0 | 0 |
2414 | e.n.ne.e.n.n | 2414 | e.n.ne.e.n.n | 0 | 0 |
2859 | push yellow | 2859 | push all but blue | 0 | −98 |
2973 | get all tool | 3071 | get all tool | −98 | −4 |
3086 | s.s | 3188 | s.s | −102 | −1 |
3196 | set bolt with wrench | 3299 | set bolt with wrench | −103 | +1 |
3308 | d | 3410 | d | −102 | 0 |
3381 | get | 3483 | get | −102 | −17 |
3441 | drop wrench | 3560 | drop wrench | −119 | −10 |
3516 | z | 3645 | z | −129 | 0 |
3562 | u.w.n.n | 3691 | u.W.n.n | −129 | −17 |
3846 | get | 3992 | get | −146 | +15 |
3962 | n.u.n.n.w.n.w.n | 4093 | n.u.n.n.w.n.w.n | −131 | −63 |
4452 | eat | 4646 | eat | −194 | +1 |
4561 | GEt jade,bat | 4754 | GET JADE,Bat | −193 | +3 |
4736 | d.s | 4926 | d.s | −190 | +15 |
4857 | get | 5032 | get | −175 | +9 |
4931 | N.u.u.n.e.s.n | 5097 | n.u.u.n.e.s.n | −166 | 0 |
5265 | get | 5431 | get | −166 | +1 |
5334 | u.s | 5499 | u.s | −165 | +12 |
5486 | drop lamp,screw,coal in cage | 5639 | drop lamp,screw,coal in cage | −153 | −25 |
5702 | lower cage | 5880 | lower cage | −178 | +9 |
5801 | drop All | 5970 | dRop aLl | −169 | −12 |
5884 | WeSt | 6065 | West | −181 | +1 |
5974 | wEst | 6154 | WeSt | −180 | 0 |
6029 | w | 6209 | w | −180 | −18 |
6138 | get all from cage | 6336 | get all from cage | −198 | +15 |
6258 | s | 6441 | s | −183 | 5 |
6346 | open lid | 6524 | open lid | −178 | +1 |
6410 | drop coal in lid | 6587 | drop coal in lid | −177 | +2 |
6503 | close lid | 6678 | close lid | −175 | +1 |
6565 | set switch | 6739 | set switch | −174 | 0 |
6669 | open lid | 6843 | open lid | −174 | +1 |
6733 | get | 6906 | get | −173 | +1 |
6795 | n | 6967 | n | −172 | 0 |
6846 | drop all in cage | 7018 | drop all in cage | −172 | +2 |
6950 | lift cage | 7120 | lift cage | −170 | +1 |
7010 | eaSt | 7179 | EAst | −169 | +1 |
7053 | EASt | 7221 | eAst | −168 | +1 |
7096 | gO up | 7263 | go up | −167 | +1 |
7143 | go up | 7309 | gO up | −166 | +1 |
7204 | north | 7369 | north | −165 | −9 |
7245 | east | 7419 | East | −174 | +1 |
7284 | sOuth | 7457 | SouTh | −173 | +1 |
7325 | NOrtH | 7497 | NOrth | −172 | −3 |
7375 | gO up | 7550 | go up | −175 | +1 |
7419 | south | 7593 | south | −174 | +26 |
7551 | get lamp,huge | 7699 | get lamp,huge | −148 | +2 |
7653 | get all | 7799 | get all | −146 | 0 |
7766 | w.s.d.s.e | 7912 | W.S.D.s.e | −146 | +4 |
8049 | get | 8191 | get | −142 | +51 |
8155 | w.n.n.w.s.e.u | 8246 | w.n.n.w.s.e.u | −91 | −12 |
8582 | get bag | 8685 | get bag | −103 | −7 |
8675 | sw.e.s.se | 8785 | Sw.e.s.se | −110 | +3 |
8923 | odysse | 9030 | odysse | −107 | +6 |
9023 | e.e | 9124 | e.e | −101 | 0 |
9124 | open case | 9225 | open case | −101 | 0 |
9211 | drop all treasu in case | 9312 | dRop all treasu in case | −101 | 0 |
9390 | w.W.U | 9491 | w.W.U | −101 | −8 |
9685 | temple | 9794 | temple | −109 | 0 |
9796 | get | 9905 | get | −109 | +1 |
9901 | d | 10009 | d | −108 | +1 |
10015 | open solid | 10122 | open solid | −107 | 0 |
10106 | get sharp | 10213 | get sharp | −107 | +1 |
10193 | u.n | 10299 | u.n | −106 | +2 |
10306 | get | 10410 | get | −104 | +1 |
10393 | s.s | 10496 | s.s | −103 | +1 |
10514 | get all | 10616 | get all | −102 | +1 |
10667 | d.d | 10768 | d.d | −101 | −2 |
10827 | drop pair | 10930 | drop pair | −103 | −2 |
10946 | ring bell | 11051 | ring bell | −105 | −5 |
11061 | get | 11171 | get | −110 | −2 |
11166 | read | 11278 | read | −112 | −2 |
11230 | s.n.u.n.n.n.e | 11344 | s.n.u.n.n.n.e | −114 | −7 |
11593 | echo | 11714 | echo | −121 | −2 |
11656 | e.e.s | 11779 | e.e.s | −123 | −7 |
11854 | drop pair,book,pump,boat | 11984 | drop pair,book,pump,boat | −130 | −10 |
12019 | inflat boat with pump | 12159 | inflat boat with pump | −140 | −8 |
12148 | drop sharp in boat | 12296 | drop sharp in boat | −148 | −6 |
12313 | enter boat | 12467 | enter boat | −154 | −5 |
12421 | launch | 12580 | launch | −159 | −5 |
12564 | get red | 12728 | get red | −164 | −2 |
12710 | e | 12876 | e | −166 | 0 |
12780 | disemb | 12946 | disemb | −166 | −1 |
12851 | open red | 13018 | open red | −167 | −2 |
12927 | get large,sharp | 13096 | get large,sharp | −169 | −3 |
13036 | n | 13208 | n | −172 | −4 |
13119 | get all | 13295 | get all | −176 | −1 |
13186 | ne | 13363 | ne | −177 | −5 |
13247 | dig sand with shovel | 13429 | dIg sand with shovel | −182 | −8 |
13376 | g | 13566 | g | −190 | −3 |
13466 | g | 13659 | g | −193 | −3 |
13517 | g | 13713 | g | −196 | −2 |
13569 | get | 13767 | Get | −198 | −3 |
13645 | sw.s.s | 13846 | sw.s.s | −201 | −1 |
13801 | wave sharp | 14003 | wave sharp | −202 | −2 |
13882 | w.w | 14086 | w.w | −204 | 0 |
14036 | get | 14240 | get | −204 | −2 |
14097 | Sw.u.u.nw.w.w.w | 14303 | sw.u.u.nw.w.w.w | −206 | 0 |
14573 | drop all but lamp in case | 14779 | drop all but lamp in case | −206 | 0 |
14842 | open trap | 15048 | open trap | −206 | −4 |
14961 | d.n | 15171 | d.n | −210 | −3 |
15098 | get old | 15311 | Get old | −213 | −3 |
15202 | s.u.w.w.u | 15418 | S.u.w.w.U | −216 | −8 |
15661 | Hit man | 15885 | hIt man | −224 | −9 |
15874 | G | 16107 | g | −233 | −12 |
15937 | g | 16182 | g | −245 | +5 |
16100 | drop old | 16340 | drop old | −240 | −6 |
16194 | get canary | 16440 | get canary | −246 | −5 |
16308 | temple | 16559 | temple | −251 | 0 |
16377 | d | 16628 | d | −251 | −2 |
16449 | get | 16702 | get | −253 | −4 |
16502 | u.s | 16759 | u.s | −257 | 0 |
16567 | pray | 16824 | pray | −257 | −1 |
16653 | Wind canary | 16911 | wind canary | −258 | −2 |
16728 | get | 16988 | get | −260 | −3 |
16803 | e.s.e.w.w | 17066 | e.s.e.w.w | −263 | +2 |
17123 | drop all treasu in case | 17384 | drop all treasu in case | −261 | −2 |
17352 | w.w.u | 17615 | w.w.u | −263 | −6 |
17563 | drop all | 17832 | drop all | −269 | −1 |
17660 | Get all treasu | 17930 | gEt all treasu | −270 | −7 |
17821 | D | 18098 | d | −277 | −3 |
17887 | E | 18167 | E | −280 | −4 |
17935 | e | 18219 | e | −284 | 0 |
18041 | drop all in case | 18325 | drop all in case | −284 | −8 |
18280 | e.e.n.w.sw.w | 18572 | e.e.n.w.sw.w | −292 |
Version F frames | Version F command | Version M frames | Version M command | Cumulative advantage | Per-command advantage |
|---|---|---|---|---|---|
522 | n.n.u | 522 | n.n.u | 0 | 0 |
762 | get egg | 762 | get egg | 0 | 0 |
931 | d.s.e | 931 | d.s.e | 0 | 0 |
1039 | open | 1039 | open | 0 | 0 |
1127 | w | 1127 | w | 0 | 0 |
1248 | open bag | 1248 | open bag | 0 | 0 |
1355 | get clove | 1355 | get clove | 0 | 0 |
1445 | w | 1445 | w | 0 | 0 |
1559 | light | 1559 | light | 0 | 0 |
1632 | get | 1632 | get | 0 | 0 |
1730 | tug rug | 1730 | tug rug | 0 | 0 |
1842 | open trap | 1842 | open trap | 0 | 0 |
1932 | d.n | 1932 | d.n | 0 | 0 |
2168 | hIT nasty | 2168 | hIT nasty | 0 | 0 |
2401 | drop old,egg | 2401 | drop old,egg | 0 | 0 |
2529 | e.n.ne.e.n.n | 2529 | e.n.ne.e.n.n | 0 | 0 |
3022 | push yellow | 3022 | push all but blue | 0 | −111 |
3132 | get all tool | 3243 | get all tool | −111 | +13 |
3250 | s.s | 3348 | s.s | −98 | −9 |
3400 | set bolt with wrench | 3507 | set bolt with wrench | −107 | 0 |
3538 | d | 3645 | d | −107 | 0 |
3624 | get | 3731 | get | −107 | +13 |
3717 | drop wrench | 3811 | drop wrench | −94 | −3 |
3802 | z | 3899 | z | −97 | 0 |
3857 | u.w.n.n | 3954 | U.w.n.n | −97 | −7 |
4162 | get | 4266 | get | −104 | +3 |
4254 | n.u.n.n.w.n.w.n | 4355 | n.u.n.n.w.n.w.n | −101 | +1 |
4761 | eat | 4861 | eat | −100 | 0 |
4836 | GET Jade,bat | 4936 | Get jade,bat | −100 | +15 |
5050 | d.s | 5135 | d.s | −85 | −6 |
5170 | get | 5261 | get | −91 | 0 |
5238 | n.u.U.n.e.s.n | 5329 | n.u.u.n.e.s.n | −91 | +11 |
5618 | get | 5698 | get | −80 | 0 |
5690 | u.s | 5770 | u.s | −80 | −4 |
5841 | drop lamp,screw,coal in cage | 5925 | drop lamp,screw,coal in cage | −84 | +3 |
6084 | lower cage | 6165 | lower cage | −81 | 0 |
6194 | dROP All | 6275 | droP all | −81 | −10 |
6281 | WESt | 6372 | weST | −91 | −4 |
6406 | west | 6501 | west | −95 | 0 |
6461 | w | 6556 | w | −95 | 0 |
6594 | get all from cage | 6689 | get all from cage | −95 | +1 |
6769 | s | 6863 | s | −94 | 0 |
6885 | open lid | 6979 | open lid | −94 | 0 |
6980 | drop coal in lid | 7074 | drop coal in lid | −94 | 0 |
7122 | close lid | 7216 | close lid | −94 | 0 |
7186 | set switch | 7280 | set switch | −94 | 0 |
7302 | open lid | 7396 | open lid | −94 | 0 |
7380 | get | 7474 | get | −94 | 0 |
7456 | n | 7550 | n | −94 | 0 |
7544 | drop all in cage | 7638 | drop all in cage | −94 | 0 |
7717 | lift cage | 7811 | lift cage | −94 | 0 |
7790 | east | 7884 | eAst | −94 | 0 |
7859 | east | 7953 | east | −94 | 0 |
7904 | go Up | 7998 | Go Up | −94 | 0 |
7952 | go up | 8046 | go up | −94 | 0 |
8013 | North | 8107 | north | −94 | 0 |
8055 | east | 8149 | eAst | −94 | 0 |
8094 | sOuth | 8188 | sOUth | −94 | 0 |
8136 | norTh | 8230 | NOrth | −94 | 0 |
8187 | gO up | 8281 | go up | −94 | 0 |
8232 | south | 8326 | south | −94 | 0 |
8364 | get lamp,huge | 8458 | get lamp,huge | −94 | 0 |
8517 | get all | 8611 | get all | −94 | 0 |
8639 | W.S.D.s.e | 8733 | w.s.d.s.e | −94 | 0 |
8964 | get | 9058 | get | −94 | 0 |
9067 | w.N.n.w.s.e.u | 9161 | w.n.n.w.s.e.u | −94 | 0 |
9519 | get bag | 9613 | get bag | −94 | 0 |
9680 | sw.e.s.se | 9774 | sw.e.s.se | −94 | 0 |
9940 | odysse | 10034 | odysse | −94 | 0 |
10041 | e.e | 10135 | e.e | −94 | 0 |
10170 | open case | 10264 | open case | −94 | 0 |
10264 | drop all treasu in case | 10358 | Drop all treasu in case | −94 | 0 |
10495 | w.W.u | 10589 | w.W.u | −94 | 0 |
10828 | temple | 10922 | temple | −94 | 0 |
10958 | get | 11052 | get | −94 | 0 |
11071 | d | 11165 | d | −94 | 0 |
11160 | open solid | 11254 | open solid | −94 | 0 |
11275 | get sharp | 11369 | get sharp | −94 | 0 |
11384 | u.n | 11478 | u.n | −94 | 0 |
11516 | get | 11610 | get | −94 | 0 |
11621 | s.s | 11715 | s.s | −94 | 0 |
11748 | get all | 11842 | get all | −94 | 0 |
11919 | d.d | 12013 | d.d | −94 | 0 |
12093 | drop pair | 12187 | drop pair | −94 | 0 |
12240 | ring bell | 12334 | ring bell | −94 | 0 |
12332 | get | 12426 | get | −94 | 0 |
12454 | read | 12548 | read | −94 | 0 |
12520 | s.N.u.n.n.n.e | 12614 | s.n.u.n.n.n.e | −94 | 0 |
12967 | echo | 13061 | echo | −94 | 0 |
13031 | E.e.s | 13125 | e.e.s | −94 | 0 |
13245 | drop pair,book,pump,boat | 13339 | drop pair,book,pump,boat | −94 | 0 |
13470 | inflat boat with pump | 13564 | inflat boat with pump | −94 | 0 |
13641 | drop sharp in boat | 13735 | drop sharp in boat | −94 | 0 |
13808 | enter boat | 13902 | enter boat | −94 | 0 |
13901 | launch | 13995 | launch | −94 | 0 |
14084 | get red | 14178 | get red | −94 | 0 |
14282 | e | 14376 | e | −94 | 0 |
14378 | disemb | 14472 | disemb | −94 | 0 |
14449 | open red | 14543 | open red | −94 | 0 |
14542 | get large,sharp | 14636 | get large,sharp | −94 | 0 |
14673 | n | 14767 | n | −94 | 0 |
14782 | get all | 14876 | get all | −94 | 0 |
14853 | ne | 14947 | ne | −94 | 0 |
14919 | dig sand with shovel | 15013 | Dig sand with shovel | −94 | 0 |
15058 | G | 15152 | g | −94 | 1 |
15140 | G | 15233 | G | −93 | 0 |
15195 | g | 15288 | G | −93 | 0 |
15259 | get | 15352 | Get | −93 | 0 |
15356 | sw.s.s | 15449 | sw.s.s | −93 | 0 |
15527 | wave sharp | 15620 | wave sharp | −93 | 0 |
15600 | W.w | 15693 | w.w | −93 | 0 |
15783 | get | 15876 | get | −93 | 0 |
15875 | sw.u.u.nw.w.w.w | 15968 | sw.u.u.nw.w.w.w | −93 | 0 |
16365 | drop all but lamp in case | 16458 | drop all but lamp in case | −93 | 0 |
16689 | open trap | 16782 | open trap | −93 | 0 |
16817 | d.n | 16910 | d.n | −93 | 0 |
16957 | get old | 17050 | get old | −93 | 0 |
17065 | s.u.W.w.u | 17158 | S.U.w.W.u | −93 | 0 |
17567 | hiT maN | 17660 | HiT Man | −93 | 0 |
17833 | G | 17926 | g | −93 | −1 |
17899 | G | 17993 | g | −94 | +1 |
18043 | drop old | 18136 | drop old | −93 | 0 |
18181 | get canary | 18274 | get canary | −93 | 0 |
18293 | temple | 18386 | temple | −93 | 0 |
18357 | d | 18450 | d | −93 | 0 |
18420 | get | 18513 | get | −93 | +1 |
18476 | u.s | 18568 | u.s | −92 | 0 |
18542 | Pray | 18634 | pray | −92 | 0 |
18644 | Wind canary | 18736 | wind canary | −92 | 0 |
18769 | get | 18861 | get | −92 | 0 |
18840 | E.s.e.w.w | 18932 | e.s.e.w.w | −92 | 0 |
19167 | drop all treasu in case | 19259 | drop all treasu in case | −92 | 0 |
19381 | w.w.u | 19473 | w.w.u | −92 | 0 |
19595 | drop all | 19687 | drop all | −92 | 0 |
19738 | Get all treasu | 19830 | Get all treasu | −92 | 0 |
19931 | D | 20023 | D | −92 | 0 |
20027 | E | 20119 | e | −92 | 0 |
20084 | e | 20176 | e | −92 | 0 |
20227 | drop all in case | 20319 | drop all in case | −92 | 0 |
20571 | e.e.n.w.sw.w | 20663 | e.e.n.w.sw.w | −92 |
