See also: part 1, part 2, part 3, part 4 and part 5.
Math versus DATA: FIGHT!
In the previous post, I showed the simple way I would bounce a ball around the screen by using X and Y coordinates and converting them to PRINT@ screen position, and then using an X Movement and Y Movement variable to control where the ball went next.
But, since this is a demo, we don’t actually need to calculate anything realtime. We could have all the positions stored in DATA statements, and just READ them as the program ran. This would also allow fancier movement patterns, such as bouncing with gravity.
Yes, it’s cheating. But is it faster? Let’s find out. Here is some code that repeatedly reads a location from DATA statements then displays an “*” at that position.
6 P=0 30 READP:IFP=&HFFF THENRESTORE:GOTO30 31 PRINT@P,"*"; 1000 DATA&H1,&H2,&H3,&H4,&H5,&H6,&H7,&H8,&HFFFF
The above code is inserted in to my BENCH.BAS program.
In line 30, we read a value from the DATA statements. If that value is &HFFFF (65535), RESTORE is used to rewind the READ so the next time it happens it looks for the first DATA statement. The GOTO causes it to try the READ again (thus, restarting with the first bit of data when it runs out of DATA).
Line 31 just prints our ball at whatever position was in the DATA statement.
Pretty simple.
Running this shows that reading 8 data values then rewinding over and over again (1000 times total) takes about 768. That’s a huge improvement of calculating the X and Y each time (1842). Thus, we should be able to pre-calculate the ball positions and go from there.
Writing code that generates code
We can write some code that writes an ASCII (text) file to disk (or tape) that contains numbers lines of BASIC which could be loaded (or MERGED from disk) later. Let’s start by just PRINTing out the lines we’d want to generate:
5 X=0:Y=0:XM=1:YM=1 10 LN=1000 20 LN$=STR$(LN)+" DATA" 30 P=X+Y*32 40 IF LEN(LN$)<240 THEN LN$=LN$+"&H"+HEX$(P) 50 IF LEN(LN$)<239 THEN LN$=LN$+"," ELSE PRINTLN$:LN=LN+10:GOTO 20 60 X=X+XM:IFX<1ORX>30THENXM=-XM 70 Y=Y+YM:IFY<1ORY>14THENYM=-YM 80 GOTO30
When you run that, it starts printing out lines of DATA statements containing hex values:
1000 DATA&H0,&H21,&H42,&H63,&H84,&HA5,&HC6, &HE7,&H108,&H129,&H14A,&H16B,&H18C,&H1AD, &H1CE,&H1EF,&H1D0,&H1B1,&H192,&H173,&H154, &H135,&H116,&HF7,&HD8,&HB9,&H9A,&H7B,&H5C, &H3D,&H1E,&H3F,&H5E,&H7D,&H9C,&HBB,&HDA, &HF9,&H118,&H137,&H156,&H175,&H194 1010 DATA&H194,&H1B3,&H1D2,&H1F1,&H1D0,&H1AF, &H18E,&H16D,&H14C,&H12B,&H10A,&HE9,&HC8, &HA7,&H86,&H65,&H44,&H23,&H2,&H21,&H40, &H61,&H82,&HA3,&HC4,&HE5,&H106,&H127, &H148,&H169,&H18A,&H1AB,&H1CC,&H1ED, &H1CE,&H1AF,&H190,&H171,&H152,&H133,&H114
All we’d have to do is figure out how many positions we want, and then print these lines to an ASCII file on disk or tape instead of to the screen. For instance, if we start at position 0, maybe we generate values until we bounce back to position 0. (To make things easier, I’m going to start at 1,1 and end when it gets back to 0).
0 CLEAR1000 5 X=1:Y=1:XM=1:YM=1 10 LN=1000 15 OPEN "O",#1,"DATA.ASC" 20 LN$=STR$(LN)+" DATA" 30 P=X+Y*32 31 PRINTP; 35 IF P=0 THEN CLOSE#1:END 40 IF LEN(LN$)<240 THEN LN$=LN$+"&H"+HEX$(P) 50 IF LEN(LN$)<239 THEN LN$=LN$+"," ELSE PRINT#1,LN$:LN=LN+10:GOTO 20 60 X=X+XM:IFX<1ORX>30THENXM=-XM 70 Y=Y+YM:IFY<1ORY>14THENYM=-YM 80 GOTO30
This program will produce a text file called DATA.ASC containing all the positions the ball will be in until it loops back to the top left corner of the screen. This can then be loaded (LOAD”DATA.ASC”) into BASIC. (Disk BASIC allows MERGE”DATA.ASC” to merge those lines in with whatever BASIC program is already there, just as if they were typed in by hand.)
With this pre-calculated data, all we have to do is just read a position, then display the ball there.
10 CLS 20 READP:IFP=&HFFFF THENRESTORE:GOTO20 30 PRINT@P,"*";:GOTO20 5000 DATA&HFFFF
Note I needed to add the final &HFFFF, but I should have made the DATA generator program add that before closing the file.
Those lines and all the generated DATA statements make a blazing fast bouncing ball with no math involved – just the time it takes to READ a value from DATA statements.
With this proof-of-concept, the next step will be seeing if this can speed up printing a large block of text for a huge ball.
To be continued…
A qualified guess is that the RESTORE or the first READ after a restore or after RUN might run noticeably faster if you place the DATA statements early in the program.
Side track: Don’t know if something is wrong on my side, but it seems like I didn’t get any RSS notifications of this and the following post (part 4). Only saw this thanks to the RSS feed notifying me on part 5 where you thankfully have linked to all previous parts.
Excellent observation, and one I have indeed tested. Yes, very true. With a large enough program, there might be a slight delay each time the DATA needs to recycle to start the pattern over.
But, since GOTO/GOSUB to earlier line numbers has to start at the beginning and skip through all the lines, the seek time for that in a main loop probably well outweighs the DATA seek.
What I really wish we had was a true BASIC OPTIMIZER that could take source, then profile it (somewhat) and move things around. It’s hard to know the program flow without a runtime profiler of some sort, but just being able to click on blocks of BASIC and drag them around and have it renumber would allow for quick experimentation.
Making an optimizer for basic sounds like a great idea. As it seems like at least most of the 6809 and 6502 versions of Microsoft Basic are rather similar the optimizer could be common for both. I don’t know much about the 8080/8085/Z80 version though. I think the original basics for the PC also are rather similar so some stuff might be common for that one too. At least for a rather advanced optimizer it might be necessary to have some way to feed metadata to the optimizer. Like for example if you combine BASIC with assembler you might want certain stuff to not be optimized out even though it from a pure BASIC perspective seems meaningless or inefficient. What really needs to be fine tuned for each “target” is what the actual speed is for various stuff. We can be fairly certain that any part of the BASIC program that doesn’t do any I/O would run at the same relative speed on any computer with the same version of BASIC. But any I/O like PRINT or similar might take different time, which means that the optimizer must have knowledge to be able to know what speed difference it would make to do two separate PRINTs instead of one. (Say for example that the optimizer is about to run out of max line length and splitting a PRINT statement could reduce the number of lines by one, or so).
A more or less dirty trick could be done to remove the speed penalty of doing a RESTORE to DATA statements near the end of the program, and that is to poke the DATA pointer to point to the first DATA statement instead of actually doing a RESTORE. Not sure if that would be faster though. I assume that it would be two POKEs. As POKEs are faster using variables than constants (at least unless you have too many variables that the interpreter has to traverse to find the right one) the values might aswell be PEEKed at the program initialization (and just to be sure a RESTORE statement (and a CLR) could be inserted in the beginning of the initialization, as some kind of protection against starting the program with goto rather than run). By PEEKing what the DATA pointer is before anything is READ, the program won’t have to contain some constants that would move around as soon as anything in the program is edited.
Btw have you tested if a GOTO back to the start is faster or slower than a FOR NEXT loop that never ends (i.e. either STEP 0 or actually faster using the same variable for the FOR loop and also as a temporary variable inside the loop, if there is any temp variable that always get set to some value that’s always less than whatever value the FOR loop is set to end at)?
An editor that can create tokenized code would have advantages. It could pack the lines longer than you could physically type them on a real machine.
At the simplest level, the optimizer could do things like combine lines, change integers to HEX, replace 0 with “.” (a cheat), and various other “do this instead of that” things.
But, a smarter one could move INIT stuff to the end, reposition code so GOTO/GOSUB are closer (by analyzing the potential GOTO paths).
This is where I like your METADATA idea… You could put in a special comment that would indicate this needs to be fast. You could also do that with variables, and it would sort them (a DIM in init code) with the ones you want faster at the start.
But actually “doing it” by itself might be impossible without a profiler.
Your mention of RESTORE and POKEs to change the position opens us up to an alternative to patching BASIC. There could be speed improvements by having integer numbers instead of floating point, when not needed. Also allowing GOTO a variable, or GOTO HEX value. Memory could be saved by storing “GOTO 12345” as “GOTOxy” where x and y were the two bytes representing 12345.
Lots of great ideas!
I will check GOTO versus a cheater FOR/NEXT. I expect GOTO will be faster, since it doesn’t have to look anything up – it just rewinds to the start of the program. I expect NEXT has to look at something, then figure out where to return to.
Great stuff!
Pingback: Adding gravity to a BASIC bouncing ball, follow-up. | Sub-Etha Software