It seems like all I’m doing lately is regurgitating things that Robin of 8-Bit Show and Tell has already done.

So let’s do that again.

Don’t blame me. Blame YouTube!

YouTube did what YouTube does and it showed me another of Robin’s well-done videos. This one caught my attention because it dealt with the Commodore VIC-20 and its Super Expander cartridge.

The main thing that pulled me away from Commodore was seeing the TRS-80 Color Computer’s Extended Color BASIC. The CoCo had simple commands to play music and draw lines, boxes and circles. It also had this wondrous ELSE command I’d only heard rumors about.

On the VIC-20, it seemed you needed to use POKE and PEEK for just about anything graphics or sound related. Thus I gave up a computer with programmable characters and a hardware sound chip for a machine that had neither. On my new CoCo, at least I could draw a circle and play music without needing pages of DATA statements and cryptic PEEKS and POKEs.

Commodore was aware of this shortcoming, and they sold the Super Expander as a way to make up for it. Not only did it provide an extra 3K of memory (giving a whopping 6.5K for BASIC), it also added new commands to do “high resolution” graphics including drawing lines and circles, as well as ways to PRINT music using simple notation.

I used the Super Expander to do TV titles for fishing videos my father shot and edited. It was a thrill to see my VIC-20 graphics on TV screens at the Houston Boat Show.

But no one else could run my programs unless they had purchased the Super Expander as well.

But I digress.

(And besides, the Commodore 64 was $600 when it came out, and I was able to get a 64K CoCo 1 for $300 at the time.)

Don’t blame YouTube. Blame Twitter.

Robin’s video was making use of the Super Expander to let the VIC-20 solve a challenge initiated by Twitter user Dataram_57. On June 8th, 2019, they wrote:

This was, more or less, a classic bouncing ball program very much like the ones I have been writing about lately. But, all mine certainly made use of IF. Here’s how mine started:

0 REM bounce.bas
10 CLS:X=0:Y=0:XM=1:YM=1
20 PRINT@Y*32+X,"O";
30 X=X+XM:IF X<1 OR X>30 THEN XM=-XM
40 Y=Y+YM:IF Y<1 OR Y>13 THEN YM=-YM
50 GOTO 20

That’s not a very good example. It doesn’t erase itself, nor does it use the bottom line to avoid screen scrolling when the ball hits the bottom right position. It does show how I would use X and Y coordinates then an XM (X movement) and YM (Y movement) variable to increment or decrement them based on if they hit an edge.

The parameters of Dataram_57’s challenge were as follows:

• Width: 90
• Height: 80
• Starting Position: 0,0
• Time: ???

I wrote a quick graphical program do do this using my X/Y/XM/YM method:

0 REM dataram_57 twitter challenge
1 POKE 65495,0
10 W=89:H=79:X=0:Y=0:T=0:XM=1:YM=1
20 PMODE0,1:PCLS0:SCREEN1,1
30 LINE(0,0)-(89,79),PSET,BF
40 PSET(X,Y,0)
50 X=X+XM:IF X<0 THEN XM=1:GOTO 50 ELSE IF X>=W THEN XM=-1:GOTO 50
60 Y=Y+YM:IF Y<0 THEN YM=1:GOTO 60 ELSE IF Y>=H THEN YM=-1:GOTO 60
70 T=T+1:IF T=7031 THEN END
80 GOTO 40

The first thing to notice is that I draw a filled box from 0,0 to 89,79 and then set black pixels in it. This lets me visually verify my line is going all the way to the edge of the 90×80 target area. Also, I am using the CoCo 1/2 double speed poke since this is time consuming. If you do this on a CoCo 3, feel free to use POKE 65497,0 instead.

Eventually the area should be entirely black when every dot has been erased.

How long has this been going on?

I did some tests and figured out that it takes 7032 iterations (0-7031) for the dot to cycle through the entire 90×80 area before it has erased all the other dots.

With that in mind, I propose we turn this into both a logic and optimization challenge. On the CoCo, let’s see if we can use the PMODE 0 screen (128×96 resolution with 1 color). We can put this in a modified version of benchmark framework for 7032 cycles and see how fast we can do it. (By modified, I am removing the outer “try this three times and average the results” loop.)

My example, using IFs, looks like this:

0 REM dataram_57 twitter challenge 2
1 POKE 65495,0
5 DIM TM,A
10 TIMER=0:TM=TIMER

15 W=89:H=79:X=0:Y=0:XM=1:YM=1
16 PMODE0,1:PCLS0:SCREEN1,1
17 LINE(0,0)-(89,79),PSET,BF

20 FORA=0TO7030

30 PSET(X,Y,0)
40 X=X+XM:IF X<0 THEN XM=1:GOTO 40 ELSE IF X>=W THEN XM=-1:GOTO 40
50 Y=Y+YM:IF Y<0 THEN YM=1:GOTO 50 ELSE IF Y>=H THEN YM=-1:GOTO 50

80 NEXT
90 PRINTTIMER:END

Mine, running in Xroar, displays 9808 at the end. And it’s not the correct way to meet the requirements of the challenge, so … the real versions may be faster, or slower.

Your challenge, should you decide to accept it…

Our challenge is to:

1. Rewrite this to work WITHOUT using any “IFs”.
2. Try to make it as fast as possible while keeping the benchmark code (lines 5, 10, 20, 80 and 90) intact. You can add variables to the DIM, but otherwise leave those lines alone.

What says you?

Credit where credit is due…

And lastly, for those who want to cheat, here is the solution that Robin came up with using the VIC-20 Super Expander cartridge…

Is his the only way? The best way? The fastest way?

Let the regurgitated challenge begin!

Until next time…

See also: part 1

My original “nicer to read, slower to run” version took 25.28 seconds to run. Here are some things that can speed it up.

RENUMber by 1

Renumbering the program by 1 can save program memory (since “GOTO 77” takes less space than “GOTO 1500”, and if the program is large enough, you get a slight speed increase since it’s also less work to parse shorter line numbers. But this program is too small for this to matter.

Remove comments / avoid comments at the end of lines

Removing comments, in general, is a good way to make a program smaller (and thus, a bit faster since BASIC will have less lines to skip). But, as I found out, comments at the end of lines are a real problem, since BASIC cannot just skip the entire line like it can if the line starts with a comment:

10 X=42:REM SET X TO THE ANSWER.

10 REM SET X TO THE ANSWER. 
20 X=42

The second version is faster, since even though BASIC has to scan an extra line, it can immediately skip it, while the first example must be parsed, character-by-character, to find the end of that line. But for this example, this did not help. It would have, if there were more GOTOs to earlier line numbers, since they would have to parse through a few lines with end comments, which would be slower. Since our looping was done with a FOR/NEXT, we didn’t have to do that.

Remove unnecessary spaces

Spaces are great for readability, but bad for code size and speed. There are only a few times when a space is needed, such as when BASIC can’t tell if the next character is a keyword or part of a variable:

10 IF A=B THEN 100

BASIC must have the space between the variable and the keyword THEN, else the parser isn’t sure if the variable is “B” or “BT” followed by the characters HEN. BUT, if it’s a number, it can figure it out:

10 IFA=42THEN100

Removing all other spaces reduces the amount of code BASIC has to parse through. My program had plenty of spaces. Removing them in this tiny program only reduced it to 25.15 seconds, but it can have a bigger impact on larger programs.

Combine lines

This one is easy. The less lines BASIC has to scan through, the quicker it will run. But, there are exceptions to this. Any time BASIC has to do more work at the end of a line, such as checking an ELSE, if that condition is not satisfied, BASIC has to scan forward character-by-character to get to the end of the line:

10 IF X=42 THEN 100 ELSE PRINT "I DON'T KNOW THE ANSWER"

Above, if X is 42, the ELSE code will not be ran. BUT, before the program can find 100, it has to scan through all the rest of the bytes in that line to find the end of it, then it continues scanning a line at a time looking for 100. Based on line lengths, sometime it might be faster to do:

10 IF X=42 THEN 100
20 IF X<>42 THEN PRINT "I DON'T KNOW THE ANSWER"

Combining lines in the program reduced the speed slightly to 25.13 seconds. The more code, the more you save by doing this (and it makes the program smaller, since every line number takes up space).

NEXT without variable

Unless you are doing really weird stuff with FOR/NEXT loops, it’s faster to leave off the variable in the NEXT. For example:

10 FOR A=1 TO 10:NEXT A

…will be slower than:

10 FOR A=1 TO 10:NEXT

NEXT without a variable will go to the most recent FOR anyway, so this works fine:

10 FOR A=1 TO 10
20 FOR B=1 TO 20
30 PRINT A,B
40 NEXT
50 NEXT

For this program, just removing the variables from NEXT A and NEXT Z increased the speed to 24.66 seconds.

Use HEX instead of decimal

It takes much more work to convert base-10 (i.e., “normal”) decimal numbers than it does to convert base-16 (hex) values. Every time a number is encountered, time can be saved by simply changing the number to a HEX — even though a hex digit has to start with “&H”. It will make the program larger, since 15 takes less bytes than &HF. For this example, it reduced time down to 21.66 seconds!

Pre-render strings

If you have to PRINT a generated string more than once, you are better off pre-rendering that string first so it only gets generated one time. This includes using things like STRING$, CHR$, etc. For example:

10 PRINT CHR$(128);"HELLO";CHR$(128)

Each time BASIC has to print that, it allocates a new string a few times and copies things over. See my string theory article for more details. For this program, I use STRING$() to generate a repeating block of characters. But, since it’s in a loop to print the block, it generates the same string over and over for each line of the block. Instead of this:

10 FOR A=1 TO 10
20 PRINT STRING$(10,128)
30 NEXT A

…I could generate that string ahead of time and just print it in the loop:

5 LN$=STRING$(10,128)
10 FOR A=1 TO 10
20 PRINT LN$
30 NEXT A

In this program, doing this trick reduces the time to 20.98 seconds! String are slow, you see…

The time savings so far…

Combining all of these (the ones that matter, at least), reduces time taken down to 18.45 seconds – saving 6.83 seconds overall.

Here is what it looks like, with the stuff outside of the benchmark timing loop left alone:

0 REM scale.bas
10 SW=32/4 ' SCALE WIDTH
20 SH=16/3 ' SCALE HEIGHT
30 SM=.1   ' SCALE INC/DEC
40 S=.5    ' SCALE FACTOR
70 TM=TIMER:FOR Z=1 TO 100
80 W=INT(SW*S):H=INT(SH*S):P=&HF-INT(W/&H2)+(&H7-INT(H/&H2))*&H20:LN$=STRING$(W,&HAF):CLS:FORA=&H1 TOH:PRINT@P+A*&H20,LN$:NEXT:S=S+SM:IFH<&H1 ORH>&HF THEN SM=-SM:S=S+(SM*&H2)
170 NEXT
180 ' 60=NTSC 50=PAL
190 PRINT:PRINT (TIMER-TM)/60;"SECONDS"

If we’d done any GOTO/GOSUBing to earlier lines, that would have to scan through those lines with ending REMarks, so cleaning all that up would be useful. If this was a larger program, RENUMbering by 1s might also squeak out a bit more speed.

But wait! There’s more!

I originally wrote this follow-up the evening that I wrote the original article. However, several folks have contributed their own optimizations. Let’s see what they did…

First, we go to the comments of the original article…

George Phillips – inner loop optimization

My current best effort is going full strength reduction on the inner loop. Replace lines 120 to 170 with:

120 L$=STRING$(W,175):FORA=P+32TOP+H*32STEP32:PRINT@A,L$;:NEXT
150 IFH<1ORH>15THEMSM=-SM
170 S=S+SM:NEXT

The STRING$ requires Extended Color Basic which starts at a baseline of 20.4 seconds and those changes get it down to 13.

George Phillips

George pre-rendered the string, removed spaces, and vastly sped things up by simplifying the math. On Xroar, it reports 16.15 – faster than any of my efforts. Nice job!

I took his updated code and converted the integers to HEX and that dropped it to 15.1 seconds! Even faster.

Jason Pittman – hex and start row calculation

Interestingly, changing the blue square value on line 130 to hex (“&HAF”) saves about 11.5% for me (27.55 to 24.33). Then, moving the row start calculation out of the print statement takes it down to 22.87.

120 FOR A=32 TO H*32 STEP 32
130 PRINT@P+A,STRING$(W,&HAF)
140 NEXT A

Jason Pittman

Ah, the magic of hex! Jason did a similar trick with the row calculation. I tried Jason’s updates, and it was 20.28 on my Xroar. George is still in the lead.

Adam – DIM, reductions and variable substituion

So I was able to cut out 5 seconds doing the following:
– DIM all variables
– Adding variables for constants (2, 32, etc.) for lines 130, 160.
– Removing the math in lines 10, 20.
– Removing the variables after NEXT.
– Removing all remarks.

No change to the original algorithm or PRINT line.

Coco3 (6309): Original code = 27.15s. Optimized code 22.13s.
With high speed poke: 11.05s. :D

I’m intrigued with the post that mentioned using HEX values. I may have to try that.

Adam

Ah! Using a variable rather than a constant can be significantly faster. I didn’t think about that, even though I’ve previously benchmarked and tested that. He adds:

I just put the STRING$ statement into a variable as suggested by George Phillips. That took out another 2 seconds! I also ran RENUM 1,,1. Run time is down from 27.2 s to 20.1 s.

L$=STRING$(W,C)
FORA=1TO H
PRINT@P+A*B,L$
NEXT

Adam

It looks like George has gotten us all thinking. I don’t have Adam’s code to test, but I am going to experiment with replacing the constants with variables and see what that does.

Ciaran Anscomb – uh… not really sure!

The author of Xroar chimes in:

So I cheated and read the comments on your page and combined some of those techniques (and replace /2 with  *1/2, forgot about that…).

13.1s?  Not quite double speed, but not bad :)

0 REM scale.bas
1 GOSUB100:TM=TIMER:FORZ=1TO M:CLS:A$=STRING$(E-INT(W*B),L)+STRING$(W,C):PRINT@(8-INT(H*B))*L,””;:FORA=1TOH:PRINTA$:NEXT:IFH<1ORH>=&H10 THENQ=-Q:R=-R
2 W=W+Q:H=H+R:NEXT
3 ‘ 60=NTSC 50=PAL
4 T=TIMER:PRINT:PRINT (T-TM)/60;”SECONDS”
5 END
100 DIMW,H,A$,A,B,C,L,Q,R,E,M,Z
110 I=32/4 ‘ SCALE WIDTH
120 J=16/3 ‘ SCALE HEIGHT
130 D=.1   ‘ SCALE INC/DEC
140 S=.5   ‘ SCALE FACTOR
150 W=I*S:H=J*S
160 Q=I*D:R=J*D
170 L=32:M=&H64
180 B=1/2:C=&HAF:E=15
190 RETURN

..ciaran

Ciaran Anscomb

Ciaran reorganized the code, placing initialization at the end. This is a habbit I need to get into since GOTO/GOSUB to an earlier line number have to start at the FIRST line of the program and scan forward EVERY TIME. Code that only needs to run once, if placed at the top, slows down every GOTO to an earlier line number.

I just ran this and got 13.13 seconds!

There is alot to dissect here. Numbers are replaced with variables. Stuff is pre-calculated. And he’s using a variable for the end of a FOR/NEXT, for some reason. I’m going to have to dig in to that one.

Twice as fast, indeed!

I feel like there were a few more responses, but I can’t locate them at the moment, so maybe there will be a second attempt article down the line.

Until next time, kudos to all of you for giving me new things to consider — especially Ciaran with that amazing improvement. Very impressive.

Prerequisite: Optimizing Color BASIC series

Here is a simple Color BASIC program that will scale blue box on the screen from small to large then back, going through the scaling processes 100 times.

0 REM scale.bas
10 SW=32/4 ' SCALE WIDTH
20 SH=16/3 ' SCALE HEIGHT
30 SM=.1   ' SCALE INC/DEC
40 S=.5    ' SCALE FACTOR
70 TM=TIMER:FOR Z=1 TO 100
80 W=INT(SW*S)
90 H=INT(SH*S)
100 P=15-INT(W/2)+(7-INT(H/2))*32
110 CLS
120 FOR A=1 TO H
130 PRINT@P+A*32,STRING$(W,175)
140 NEXT A
150 S=S+SM
160 IF H<1 OR H>15 THEN SM=-SM:S=S+(SM*2)
170 NEXT Z
180 ' 60=NTSC 50=PAL
190 PRINT:PRINT (TIMER-TM)/60;"SECONDS"

After this runs, it will report the approximate number of seconds it took. It does this by resetting the TIMER at the start, then printing the current TIMER value divided by 60 (since the CoCo timer is based on the NTSC video interrupt that happens 60 times a second).

NOTE: If you run this on a PAL system, you will need to change the 60 to a 50 in line 190. (edit: thanks, George P., for catching my typo.)

On the Xroar emulator running on my Mac it reports 25.25 seconds.

Your challenge, should you decide to accept it, is to take this code and make it run faster.

Rules

1. You must leave the basic algorithm intact (the SW, SH, S and SH stuff with all the math). You can rename variables, change the representation of values, speed up PRINTing, etc. but the core program flow should remain the same.
2. For bonus points, you are welcome to rewrite the program (in BASIC) to improve upon the algorithm in any way that makes sense, provided it achieves the same results (including the 1 to 100 benchmark loop).

There are some very (very!) simple things that can be done to dramatically improve the speed to his code.

Feel free to share your efforts in the comments. If you post your code, be sure to post the resulting time, too.

Good luck!