Last year, I posted an article dealing with Optimizing Color BASIC. In it, I covered a variety of techniques that could be done to speed up a BASIC program. While this was specifically written about the Microsoft Color BASIC on the Radio Shack Color Computers, I expect it may also apply to similar BASICs on other systems.
James J. left an interesting comment:
Oh yeah. If anyone cares to experiment with modifying the BASIC interpreter, it might be fun to make the symbol table “adaptive”. When you find a variable in the symbol table, if it’s not the first one, swap it with its predecessor. The idea is that the more frequently looked up symbols migrate towards the front and thus are more quickly found. The question is whether the migration improves things enough to make up for the swapping. – James J.
This got me curious as to how much of a difference this would make, so I did a little experiment.
In this Microsoft BASIC, variables get created when you first use them. Early on, I learned a tip that you could define all your variables at the start of your program and get that out of the way before your actual code begins. You can do this with the DIM statement:
Originally, I thought DIM was only used to define an array, such as DIM A$(10).
I decided to use this to test how much of a difference variable placement makes. Variables defined first would be found quicker when you access them. Variables defined much later would take more time to find since the interpreter has to walk through all of them looking for a match.
Using the Xroar CoCo/Dragon emulator, I wrote a simple test program that timed two FOR/NEXT loops using two different variables. It looks like this:
As you can see, with just two variables, A and Z, there wasn’t much difference between the time it takes to use them in a small FOR/NEXT loop. I expect if the loop time was much later, you’d see more and more difference.
But what if there were more variables? I changed line 10 to define 26 different variables (A through Z) then ran the same test:
Now we see quite a bit of difference between using A and using Z. If I knew Z was something I would be using the most, I might define it at the start of the DIM. I did another test, where I defined Z first, and A last:
As expected, now the Z variable is faster than A.
Every time BASIC has to access a variable, it makes a linear (I assume*) search through all the variables looking for a match.
Side Note: * There is an excellent Super/Disk/Extended/Color Basic Unraveled book set which contains fully commented disassemblies of the ROMs. I could easily stop assuming and actually know if I was willing to take a few minutes to consult these books.
However, when I first posted these results to the Facebook CoCo group, James responded there:
Didn’t realize it made that much difference–doesn’t the interpreter’s FOR loop stack remember the symbol table entry for the control variable? – James J.
Indeed, this does seem to be a bad test. FOR/NEXT does not need the variable after the NEXT. If you omit the variable (just using NEXT by itself), it does not need to do this lookup and both get faster:
I guess I need a better test.
How about using the variable directly, such as simple addition?
Z, being defined at the end, is slower. And if we reverse that (see line 10, defining Z first), Z becomes faster:
You can speed up programs by defining often-used variables earlier.
James’ suggestion about modifying the interpreter to do this automatically is a very interesting idea. If it continually did it, the program would adapt based on current usage. If it entered a subroutine that did a bunch of work, those variables would become faster, then when it exited and went back to other code, those variables would become faster.
I do not know if the BASIC language lasted long enough to ever evolve to this level, but it sure would be fun to apply these techniques to the old 8-bit machines and see how much better (er, faster) BASIC could become.
Thanks for the comment, James!