Programming : Code optimisation

peteI started programming when I was around 10 years old, after my dad showed me how to program on the Atari 800XE. I remember progressing on from that to QBASIC when we got our first PC. It was QBASIC that stayed with me for a good few years on from that until I believe I moved on to PHP. Whilst using QBASIC, three very important things happened. 1) I started college, 2) I met a guy called Alan O, and 3) I learnt about the elegance and beauty of code reduction and optimisation.

When starting any class in computing it’s usually apparent after the first few lectures, who the real geeks are and who the rest of the class are. I don’t know why, and I guess I never will, but there is always a group of people in computing classes that enjoy laughing at the guys who really do want to learn. Reminding them that they’re in the computing class too usually brings them down to earth for a while, but it’s this leveling effect I enjoyed because it usually meant I was about to make some new friends who were as eager to code and learn about computing as I was.

“He looked at the screen and then the mouse, picked up the mouse and spoke rather bluntly, gesturing to the screen. ‘What the heck do I do with this?’„

In my A level Computing class at college I met a guy who changed my outlook of programming forever. I’d had no real external input from anyone else before then, apart from the small amount of Visual Basic that we were taught at the end of school. This was the first time I’d met someone else who was better than me at programming, Alan O. I almost overlooked this guy after our first lecture in the computing lab. We’d been sat down in front of Win 95 machines and instructed to run up MS Access. Alan sat there and looked rather bewildered. Curious as to his problem I leaned over and asked him what was the matter. He looked at the screen and then the mouse, picked up the mouse and spoke rather bluntly, gesturing to the screen. “What the heck do I do with this?” I looked at him and then the mouse and then him again. “What’dya mean?” I asked?

verticesAs it turned out, Alan had never used Windows at all, he’d lived entirely in the land of DOS and had never even used a mouse. I knew this guy coded, but at this point I was seriously wondering if he “really” coded or not. A few days later, I took in a program to show him, the code for which is displayed below in it’s entirety. I had programmed a clone of the “Mystify Your Mind” screensaver from Windows 95. Essentially four vertices or points, joined by lines bounced around the screen. See Figure 1. Alan, looked genuinely impressed and asked to see the code. Had I know what he would show me the next day, I would certainly never have bothered to show it to him at all. His creation was not just breathtaking, it was utterly astounding. He suddenly became my mentor overnight. Alan had programmed a full screen scrolling RPG framework in QBASIC. He had transparent menu overlays, double buffered graphics and well, I can’t even begin to describe what else. I remember him talking about interfacing directly with the graphics card, through what I believe was Assembler. I’d never seen anything like it. Not in QBASIC. Forget Nibbles, forget Gorillas. Alan was da bomb.

Rewinding back to my own submission to the coding genius, Alan sparked off something in me that I’d never had before; A quest to optimise and reduce my code as much as possible. Naively, I had always been under the impression that more code lines meant I was more elite. Come on, I was only young. Alan showed me that the real key to everything was reduction and optimisation. It was the first time that I’d seen code as an art form, as something elegant to strive towards perfection; The most optimised, reduced code possible.

verticesI was pretty pleased with the code below. The first section sets up two arrays g and h. I then set the screen to mode 11. g and h were actually x and y, and you can see the next set of lines set up the initial coordinates for the 4 points of the of the traveling polygon. After that comes something interesting. There are five lines that set up the status for the vertices of the lines. Note the inconsistencies in my early programming. I declare coordinate arrays with 10 points, I set up initial coordinates for only 4 points, and I define a status for 5 points. As a side note, QBASIC was a language that had line numbers optionally. Note the ’10’ on it’s own that I used as a line identifier.

The lines of code after that do the drawing of the lines. You’ll notice at the end of the line draw, there is a for-next loop on every other line, and a 0 on the in between lines. Here I would draw the first line, wait for 100 cycles, then draw a black line over the top to blank it out ready for the next frame then lather, rinse and repeat for the remaining lines. In retrospect I should have drawn all four lines, then waited 100 cycles and blanked them all in one go. This would have probably given a better frame rate, and looked a lot nicer too. The reason for the loop wait was because if I cleared immediately after I drew, you ended up either seeing a very flickery image, or not much at all.

The next statements were REM’d or commented out. I can’t quite recall what the PSET commands were for. Looking at it now I’m suprised it didn’t throw an error as they were arrays after all and PSET required a single x,y value. The GOSUB 5000 was almost a function call, because at the time I was unaware of how to do functions at all in QBASIC. After that you see the GOTO 10. When the program had finished in the pseudo-function or subroutine, it would return and go to line 10, essentially performing a loop that would keep redrawing each frame.

The “function” at line 50000 actually did do some optimisation. This part of the code deals with checking if a point of the polygon has hit the edge of the screen, and if it has, “bounces” it back. Either I couldn’t be bothered to copy and paste the code, or I actually had a clue, but the FOR loop, loops through each vertex. Notice here I loop through 5 points, even though there are only ever 4 used in the draw sequence.

verticesAn interesting thing now, is to talk about the vertex states. Think about this, my code was very simple, a point could only move diagonally at 45 degrees because I was either adding or subtracting one pixel from each axis. Taking this into account, a vertex could only be in one of four possible states. These were, moving top left to bottom right, moving bottom right to top left, moving top right to bottom left, or moving bottom left to top right. I thought I had been clever here. You can see four sub routines, defining what to do for each state and above it some IF statements telling the code where to jump depending which state the vertex is in. Each of these routines does four things. It checks one axis to see if it has exceeded a limit, if it has, it changes the state. Then it checks the other axis. Finally it increments or decrements the coordinates of the point in both axis, depending on the state of the vertex in question. You may be wondering why the limits are set to 1 for the lower limit, but the upper limit is the actual edge of the canvas. In QBASIC, you could draw past the upper limits, but not below zero. It would mean that the drawing was off the screen, but it was still legal, if I remember correctly.

In essence, that was the entire program. The sub routines would move the points around and then the draw statements would create the lines on the screen. After looking at it, and I’m positive that both he and others could have optimised it even more – double buffering for instance – Alan said to me, “Can I make a suggestion?” I said yes and what follows is a brief summary of our discussion.

He asked me, in a nut shell, what the subroutines were doing. Of course he _knew_ the answer, he was just trying to get me to think. So I replied that they incremented or decremented based on the direction of the vertex. “I can reduce that code for the subroutines to about four to six lines,” he said. I was shocked and I certainly didn’t believe him. He asked me what was happening at each edge. So I replied that essentially the speed for the vertex at a specific zxis was getting flipped from positive to negative. I could see his mind turning, but mine certainly wasn’t.

“What’s an easy way of flipping positive to negative?” he asked. “Store a flag and based on that flag either increment or decrement,” I told him, smugly. Unphased, he turned to me and simply said, “What if the flag could be the incrementor and the decrementor at the same time?” I just stood there like a dummy. I had no idea how. “What’s one times minus one?” he asked. “Duh, minus one,” I replied. On to my next mathematical challenge. “What’s minus one times minus one?” Again with the easy questions I thought. “One” I replied. Then it hit me. By starting with the number one, and multiplying by minus one each time, I was oscillating from positive to negative. Each time my vertex hit an edge, I just needed to multiply the speed by minus one and the direction would be reversed.

“The elegance of Alan’s solution is something I don’t think I will ever forget. It led me to change my entire way of thinking.„

It was genius, but it was something I had never ever thought of. He also slimmed down the conditional statements. If we’d simplified the core idea down to the flipping of the polarity of the direction, we didn’t need to know which edge it had hit, just that it _had_ hit an edge. By doing this, we only had to do two things. 1) Add two more small arrays, gspeed and hspeed, to hold the speed for each vertex in it’s associated axis, set up initial conditions and 2) Replace the lines from “REM LOCATE 5, 1: PRINT n” to the last “RETURN 59000” with this.

IF g(n) 640 THEN gspeed = gspeed * -1
IF h(n) 480 THEN hspeed = hspeed * -1
g(n) = g(n) + gspeed
h(n) = h(n) + hspeed

To this day I still find the way in which Alan reduced and optimised 25 lines of my code, to just 4 in the loop, 2 more declarations, and a set of initial conditions, absolutely staggering. Not only was the code cleaner, but it was more optimised. Doing comparisons takes CPU cycles, doing memory writes takes CPU cycles. The elegance of Alan’s solution is something I don’t think I will ever forget. It led me to change my entire way of thinking. Years later at university, whenever there was a computing assignment, we would always challenge each other to try to do it in as few lines as possible. Most people didn’t care, but there were five or six of us that always pushed to the limit.

Hand in hand with this memory is a very fond one whilst mentoring for GSoC. My student had shown me some code he’d written and had a few problems with it. After looking at it, I saw what Alan must have seen that day, a huge number of repeated sections of code. “Why not put the names of the labels in an array and step through it using the same routine, instead of copying and pasting all those lines?” I asked. A short silence was broken by a gasp of excitement as what I had suggested was finally understood. Hearing the excitement in my students voice was something I’ll never forget and all in all, we must have removed 60 to 70 lines down to about 10.

Sadly, optimisation seems to be a dying art. People are so used to having abundant memory and cpu cycles that many coders just don’t seem to bother optimising anymore. The trouble is, if no one optimises, programs bloat and run slow. Get several of these running on the same machine and you have a recipe for running through treacle. I hope this article has instilled some of the optimiser in you. It was this defining moment that made me see that coding isn’t just about getting a job done, it can be down in an incredibly artistic way, leading to something elegant and sometimes almost beautiful. Happy Coding.

DIM g(10)
DIM h(10)
g(1) = 100
h(1) = 100
h(2) = 100
g(2) = 200
h(3) = 200
g(3) = 100
h(4) = 200
g(4) = 200
stat(1) = 1
stat(2) = 4
stat(3) = 3
stat(4) = 2
stat(5) = 3

LINE (g(1), h(1))-(g(2), h(2)): FOR i = 1 TO 100: NEXT i
LINE (g(1), h(1))-(g(2), h(2)), 0
LINE (g(2), h(2))-(g(3), h(3)): FOR i = 1 TO 100: NEXT i
LINE (g(2), h(2))-(g(3), h(3)), 0
LINE (g(3), h(3))-(g(4), h(4)): FOR i = 1 TO 100: NEXT i
LINE (g(3), h(3))-(g(4), h(4)), 0
LINE (g(4), h(4))-(g(1), h(1)): FOR i = 1 TO 100: NEXT i
LINE (g(4), h(4))-(g(1), h(1)), 0
REM LOCATE 1, 1: PRINT g(1); h(1); stat(1)
REM LOCATE 2, 1: PRINT g(2); h(2); stat(2)
REM LOCATE 3, 1: PRINT g(3); h(3); stat(3)
REM LOCATE 4, 1: PRINT g(4); h(4); stat(4)

PSET (g, h)
PSET (g, h), 0
GOSUB 50000

FOR n = 1 TO 5

50008 IF stat(n) = 0 THEN GOSUB 55000
50009 IF stat(n) = 1 THEN GOSUB 51000
50010 IF stat(n) = 2 THEN GOSUB 52000
50020 IF stat(n) = 3 THEN GOSUB 53000
50030 IF stat(n) = 4 THEN GOSUB 54000

51000 IF g(n) < 1 THEN stat(n) = 2
51010 IF h(n) < 1 THEN stat(n) = 4
51020 g(n) = g(n) - 1
51030 h(n) = h(n) - 1
RETURN 59000

52000 IF h(n) 640 THEN stat(n) = 1
52020 g(n) = g(n) + 1
52030 h(n) = h(n) - 1
RETURN 59000

53000 IF g(n) > 640 THEN stat(n) = 4
53010 IF h(n) > 480 THEN stat(n) = 2
53020 g(n) = g(n) + 1
53030 h(n) = h(n) + 1
RETURN 59000

54000 IF h(n) > 480 THEN stat(n) = 1
54010 IF g(n) < 1 THEN stat(n) = 3
54020 g(n) = g(n) - 1
54030 h(n) = h(n) + 1
RETURN 59000

55000 RETURN 59000

59000 NEXT n


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: