Today Sebastian Tepper submitted a solution to the “draw black” challenge. He wrote:
I think this is much faster and avoids unnecessary SETs. Instruction 100 will do the POKE only once per character block.– Sebastian Tepper, 7/5/2022
The routine he presented (seen in lines 100 and 101) looked like this:
20 FOR A=0 TO 31
30 X=A:Y=A:GOSUB 100
50 GOTO 50
100 IF POINT(X,Y)<0 THEN POKE 1024+Y*16+X/2,143
It did see the criteria of the challenge, correctly drawing a diagonal line from (0,0) down to (31,31) on the screen. And, it was fast.
POINT() will return -1 if the location is not a graphics character. On the standard CLS screen, the screen is filled with character 96 — a space. (That’s the value you use to POKE to the screen, but when printing, it would be CHR$(32) instead.) His code would simply figure out which screen character contained the target pixel, and POKE it to 143 before setting the pixel.
So I immediately tried to break it. I wondered what would happen if it was setting two pixels next to each other in the same block. What would RESET do?
I added a few lines to the original test program so it drew the diagonal line in both directions PLUS draw a box (with no overlapping corners). My intent was to make it draw a horizontal line on an even pixel line, and odd pixel line, and the same for verticals. It looks like this (and the original article has been updated):
10 CLS 20 FOR A=0 TO 15 30 X=A:Y=A:GOSUB 100 31 X=15-A:Y=16+A:GOSUB 100 32 X=40+A:Y=7:GOSUB 100 33 X=40+A:Y=24:GOSUB 100 34 X=39:Y=8+A:GOSUB 100 35 X=56:Y=8+A:GOSUB 100 40 NEXT 50 GOTO 50
And this did break Sebastian’s routine… and he immediately fixed it:
100 IF POINT(X,Y)<0 THEN POKE 1024+INT(Y/2)*32+INT(X/2),143 101 RESET(X,Y):RETURN
I haven’t looked at what changed, but I see it calculates the character memory location by dividing Y by two (and making sure it’s an integer with no floating point decimals — so for 15 becomes 7 rather than 7.5), and then adds half of X. (Screen blocks are half as many as the SET/RESET pixels).
And it works. And it works well — all cases are satisfied.
And if that wasn’t enough, some optimizations came next:
And for maximum speed you could change line 100 from:
100 IF POINT(X,Y)<0 THEN POKE 1024+INT(Y/2)*32+INT(X/2),143
100 IFPOINT(X,Y)<.THEN POKE&H400+INT(Y/2)*&H20+INT(X/2),&H8F
To time the difference, I added these extra lines:
45 PRINT TIMER
This lowers execution time from 188 to 163 timer units, i.e., down to 87% of the original time.– Sebastian Tepper, 7/5/2022
Any time I see TIMER in the mix, I get giddy.
Spaces had been removed, 0 was changed to . (which BASIC will see a much faster-to-parse zero), and integer values were changed to base-16 hex values.
Also, in doing speed tests about the number format I verified that using hexadecimal numbers was more convenient only when the numbers in question have two or more digits.– Sebastian Tepper, 7/5/2022
Perhaps final improvement could be to change the screen memory location from 1024/&H400 to a variable set to that value, the multiplication value of 32/&h20, as well as the 143/&H8F. Looking up a variable, if there are not too many of them in the list before the ones you’re looking up, can be even faster.
Using the timer value of 163 for our speed to beat, first I moved that extra space just to see if it mattered. No change.
Then I declared three new variables, and used DIM to put them in the order I wanted them (the A in the FOR/NEXT loop initially being the last):
11 DIM S,C,W,A 12 S=1024:W=32:C=143 ... 100 IFPOINT(X,Y)<.THENPOKES+INT(Y/2)*W+INT(X/2),C 101 RESET(X,Y):RETURN
No change. I still got 163. So I moved A to the start. A is used more than any other variable, so maybe that will help:
11 DIM A,S,C,W
No change — still 163.
Are there any other optimizations we could try? Let us know in the comments.
Thank you for this contribution, Sebastian. I admire your attention to speed.
Until next time…