Fun Challenge - Smallest possible code for fill.asm

[dolomiti7]

While working on a different project, I created an optimized version of Fill.asm as a spin-off. I then got hooked on optimizing it even further and managed to squeeze the entire logic down to exactly 16 instructions (excluding labels). It passes the FillAutomatic test flawlessly.

How does it work?

There is no initialization code, all 16 instructions are inside the loop. The only variable is the screen pointer which is kept inside the range of the video RAM inside the loop (regardless of its initial state). One trick that I use is to hard-wire this variable to address 8191...
In the spirit of nand2tetris, I don't publish the code here, but this is the basic structure:
(loop)
6 instructions update the screen pointer (increased by 1 and kept inside the range 16384-24575),
5 instructions to read the keyboard and load the D register with the color,
3 instructions to write the color to the screen pointer address and
2 instructions to jump back to the loop start.

I'm curious: has anyone managed to go even lower, or is 16 the absolute theoretical limit for the Hack CPU? Can you beat 16? :-)

[WBahn]

I don't know what I eventually got it down to, but it was right in that ballpark.

I used Fill.asm as an introductory example in my Comp Org course as it is a nice intro to assembly language programming in general and how to convert a high-level algorithm into assembly language and then progressively optimize it in a number of ways. The direct translation had something like 50 instructions and required over 300,000 clock cycles to turn the screen completely from one color to the other. It leads to an interesting discussion of which optimizations are easy to implement in a compiler and which would be far more difficult, relying on an understanding of the underlying goal of the program to see and exploit.

It also allows an exploration of the time/space tradeoffs that are common in program implementation. The space-optimized version did it in ~100,000 clock cycles (3x the speed with ~1/3 the code) while the speed-optimized version did it in just over 16,000 cycles (~19x the speed but over 650x the code).

[dolomiti7]

Sounds logical. For speed optimization, the whole write process can be unrolled (init, then 8192 times M=D, A=A+1). That must be the fastest possible way with a program size of 16k instructions plus a small overhead for reading the keyboard and initialising. Btw, if your factor of 650x size is correct, that would indicate a size of ~25 instructions for the size optimized version.

The execution speed of my length 16 version depends on the color, it is either 15x8192=123k or 16x8192=131k cycles. It is slower than the 100k cycles of your size optimized version - which is the trade-off for having all the code in a single loop and avoid "wasting" instructions for Initialization...

[WBahn]

dolomiti7 wrote

Sounds logical. For speed optimization, the whole write process can be unrolled (init, then 8192 times M=D, A=A+1). That must be the fastest possible way with a program size of 16k instructions plus a small overhead for reading the keyboard and initialising. Btw, if your factor of 650x size is correct, that would indicate a size of ~25 instructions for the size optimized version.

The 650x was relative to the original ~50 instruction version, which was the reference for all of the optimized versions. It was ~2000x (IIRC) times the tightest space-optimized version (which know was no more than 19 instructions, but I don't recall is that was the final version or not).

The execution speed of my length 16 version depends on the color, it is either 15x8192=123k or 16x8192=131k cycles. It is slower than the 100k cycles of your size optimized version - which is the trade-off for having all the code in a single loop and avoid "wasting" instructions for Initialization...

My code also had a significant difference between black and white. Also, IIRC, I might have tweaked the requirement such that the program had to be more responsive with the color starting to change as soon as a key was pressed or released instead of just "eventually". I did a few iterations of this demo over a few semesters and I know that I added this at some point as it allowed me to start off with a version that seemed to be unresponsive, with nothing happening right away which could lead the user to think something was wrong, so that I could point that out and discuss whether that was something that should be a requirement, how to go about getting it, and what the tradeoffs might be.

[WBahn]

I found an early draft of my PPT slides on this machine. It included the following:

// fillbrute.asm

// INSTRUCTIONS.............. 50
// INNER WHITE/BLACK cycles..      37 /      36
// FRAME OVERHEAD cycles.....       4 /       4
// FRAME WHITE/BLACK cycles.. 303,108 / 311,300



The ultimate tradeoff of space for speed:

// INSTRUCTIONS.............. 32,778
// INNER WHITE/BLACK cycles..       2 /       2
// FRAME OVERHEAD cycles.....       4 /       6
// FRAME WHITE/BLACK cycles..  16,388 /  16,390

Nearly 19x the speed, but nearly 656x the size.

How was this done?

Do you see the problem?

What kind of compromises could be made?

So my recollection of most of the numbers was pretty good, but there was one important thing that I forget. The speed-optimized version was thrown out with malice aforethought to try to stimulate a discussion of whether they could both figure out how it was done and whether they could spot that it was unobtainable in the Hack's ROM size limit.

One thing that I thought about doing, but didn't actually do, was to have the students do a plot of number of cycles (best case to change the screen from one color to the other and back (so as to capture the black/white differences)) as a function of code size. The intent was for them to see that the very fastest programs would typically take a huge amount of space, but that huge space-savings can be gained for almost no speed penalty until you start getting to pretty small code sizes, at which point you start incurring significant speed penalties for further code-size reductions. I never got around to doing this myself, so I don't know where the knee would end up. It might be something that I explore at some point for grins and giggles.

[pm100]

Is this a documented challenge somewhere. I didn't see it in the book

[WBahn]

pm100 wrote

Is this a documented challenge somewhere. I didn't see it in the book

No, this is something I came up with for the Computer Organization and Design course that I taught a number of times.

[dolomiti7]

Nice — I wish I had had the opportunity to join one of your classes; I find challenges like this inspiring. I quickly created several versions with different levels of unrolling, and also experimented with handling responsiveness either per cell or per frame. The results show the expected diminishing returns.

In the chart below, I used a logarithmic scale for the code size. The red data points represent polling the keyboard for each cell, while the black ones always draw a full frame. As far as I can tell, this is more or less the optimal result you can achieve.

As you can see on the far right, you can reach the same cycle count with only half the code size of your example by using shared code for drawing black and white (setting D upfront). In fact, the black case is even one cycle faster. Of course, this approach removes the educational aspect of demonstrating how the code size can exceed the available ROM space.

[dolomiti7]

Never say something is optimal until there is proof... As limited as the Hack ISA is, it is often surprising what you can squeeze out of it to optimize your code. So I was able to further improve the code on fill.asm. This time I'm really really sure, that the graph shows the optimal pareto frontier - as far as I can tell ;-) If anyone can show me code that is breaking the frontier (faster at same size or smaller at same speed), I will invite you for a virtual paypal drink!

The smallest version with 16 instructions is now faster. The code has now 2 instructions of initialization, but the loop is only 14 instructions long (with 1 instruction skipped in the white case). The initialization is not even required to pass the FillAutomatic test as long as cell [8191] doesn't point to an illegal memory address. So technically you can fullfill the test with even 14 instructions, however that would be cheating :-)
The structure is now:
2 instructions to init [8191]
(loop)
3 instructions to write the color to the screen pointer address (that's why the init is required)
6 instructions update the screen pointer (increased by 1 and kept inside the range 16384-24575),
5 instructions to read the keyboard and load the D register with the color and jump back to loop

The version drawing a full frame is now only 20 instructions long. Looking at it now, the code is so simple that I'm wondering why I didn't do it like that right from the start...
It has 2 separate blocks for the black and white case and the keyboard poll just in between the blocks, either falling through or looping back to the first block. The structure is:
(white)
2 instructions init loop counter
5 instructions loop through 16384-24575 and write 0
(poll)
4 instructions poll keyboard and conditionally jump to white
// black fall-through
2 instructions init loop counter
5 instructions loop through 16384-24575 and write -1
2 instructions jump to poll

Pretty simple, the real challenge is how to make the loop with just 5 instructions...

The graph now distinguishes clearly between the versions polling the keyboard after every cell vs once per frame.

[dolomiti7]

Admittedly, I’ve had a bit too much free time during my holidays to sink into these rather useless micro‑optimizations. Still, I enjoy the process, and I genuinely think it sharpens creative problem‑solving. Long story short: I’ve managed to push the Pareto frontier a bit further again. After I had re-introduced initialization instructions, I overlooked that the sequence to update the screen pointer can be simplified because it can now rely on the fact that the current pointer always points to a valid screen address. That reduced the update sequence from 6 to 5 instructions and the overall code is now only 15 instructions long - and thus also faster.

I also found a way to pack a version that polls the keyboard only once per frame into 16 instructions. As expected it is slower than my previous 20 instruction solution (but faster than similar size code that polls after every cell). The main reason for the loss of speed is that the code actually writes 0 or -1 to the whole memory, not only the video RAM, but in return the loops are only 3 instructions long... and yes, it is possible to write a 3 instruction long loop. A few hints if you want to try to recreate the code yourself: It won't work in the original Java-based CPU Emulator since you have to use set-on-jump code like A...=...;J... (this is a known bug in the Java CPU Emulator), it will work however in the web-based Emulator where this bug has been corrected. There is no loop counter stored in memory (and that is the reason why this 3 instruction loop has to write the whole memory - except [0]). And of course you need 2 of these loops, one for black and one for white.

The paypal drink challenge is still on if you can provide better solutions. Below is the updated chart. The red curve looks a bit bumpy, mainly because I only use the cycles for the slower color in the chart and as you can see some of them have significant differences in speed between black and white (at least the major differences are shown). It would look smoother if I used the average cycles of black and white. Btw, I hereby bow out of this challenge, I promise :-)