Optimizing BASIC: Fancy Mandelbrot Set Zoomed Plot Calculations

[Scott Robison]

I decided to create a different thread to document my approach to optimizing @SlithyMatt's BASIC code. Not because his code is bad. It is intended to teach. This is just a fun exercise to get a baseline calculation of the current code speed and what various optimizations do to enhance the performance. It will never run fast in BASIC!

I've taken his code and removed the graphical parts of it. I think those parts are near optimal for BASIC. As he rightly observes, the math is what makes this program slow. So here is the baseline code I'm working with:

10 TI=0

100 FOR PY=0 TO 9

110 FOR PX=0 TO 9

120 XZ = PX*0.000036/320-0.747345

130 YZ = PY*0.000027/240+0.08784

140 X = 0

150 Y = 0

160 FOR I=0 TO 355

170 IF X*X+Y*Y > 4 THEN GOTO 215

180 XT = X*X - Y*Y + XZ

190 Y = 2*X*Y + YZ

200 X = XT

210 NEXT I

215 I = I - 100

216 IF I=256 THEN I=0

217 B = 0

218 OS = $4000

219 Y = PY

220 IF Y < 153 THEN GOTO 230

221 IF Y = 153 AND PX < 192 THEN GOTO 230

222 B = 1

223 OS = -192

224 Y = PY-153

230 REM

240 NEXT PX

260 NEXT PY

270 PRINT TI/60

Note that instead of a 320x240 plot, I'm restricting my calculations to the top left corner in a 10x10 area of the non-plot. While that might not be the slowest part of the program, it is "representative". In testing, it takes 115.5333 seconds to run. That is based on setting TI to 0 and then displaying TI/60 at the end. This generates the same number whether in warp mode or not, as the emulated computer still emulates the same system. 500% of real time speed means that I can run that 115.5333 second program in about 20 seconds of wall clock time, but jiffies pass at the same relative rate whether or not warp mode is enabled.

So, baseline is 115.5333 seconds for a 10x10 area. If we extrapolate, there are 32x24 blocks that are 10x10, so 24.64 hours to calculate the information for an entire screen of 320x240. This is really close to what @SlithyMattreported, so it seems like a reasonable test case. Next post shortly...

[Edmond D]

This sounds like a great approach to optimizing the code. As you mentioned, the original code is for teaching - illustrative and clear to us humans. Starting from a clear working example and then optimizing step by step is my preferred way to do this type of task. Trying to optimize while writing the first draft seems to be a way to have faulty, hard to understand, broken code that might never run right to begin with ?

 

[Scott Robison]

The first change is just to a single line of code. Line 10 is replaced with:

10 TI=0:Y=0:X=0:I=0:PY=0:PX=0:YZ=0:XZ=0:XT=0

Every time a variable is accessed, BASIC has to look through the variable table for it. If it is the first variable, great! It is found quickly! If it is the 100th variable, it takes 100 times as long. Thus you want to create your variables in the order they will be most frequently accessed. In this case, X & Y are used the most, so they are created first (TI isn't a real variable). XZ, YZ, and ZT are used the least so we create them last.

New time: 107.7666 seconds. Extended time estimate: 22.99 hours. Time saved: 1.65 hours. 6.7% faster.

[Scott Robison]

Next I did one thing that helped a little bit but not as much as I'd hoped, and another I should have done for the baseline. Here is the code:

10 TI=0:Y=0:X=0:I=0:V=0:U=0:R=0:Q=0:T=0

100 FOR V=0 TO 9

110 FOR U=0 TO 9

120 Q = U*0.000036/320-0.747345

130 R = V*0.000027/240+0.08784

140 X = 0

150 Y = 0

160 FOR I=0 TO 355

170 IF X*X+Y*Y > 4 THEN GOTO 215

180 T = X*X - Y*Y + Q

190 Y = 2*X*Y + R

200 X = T

210 NEXT I

215 I = I - 100

216 IF I=256 THEN I=0

230 REM

240 NEXT U

260 NEXT V

270 PRINT TI/60

I've replaced all two character variable names with single character names. They are faster to interpret, but not as much as I thought. I also removed lines 217 - 229 as they are not really part of the math, they are part of the plot. Removing them actually slowed things down slightly.

New time: 107.1666 seconds. Extended time estimate: 22.86 hours. Total time saved: 1.78 hours. 7.2% faster.

[Scott Robison]

Note that line 130 only really needs to be computed when the value of V changes. Move line 130 to line 105 so it is only computed once per iteration of V.

Also note that we square X & Y twice in line 170 and 180. We can make that faster if we only do it once per loop and reuse it as needed.

Finally, line 180 computes a temporary value as T, then computes Y, then puts the temp value in X. Since we precomputed X^2 & Y^2, we can remove the need for a temporary by swapping 180 and 190.

New code:

10 TI=0:Y=0:X=0:I=0:V=0:U=0:N=0:M=0:R=0:Q=0

100 FOR V=0 TO 9

105 R = V*0.000027/240+0.08784

110 FOR U=0 TO 9

120 Q = U*0.000036/320-0.747345

140 X = 0

150 Y = 0

160 FOR I=0 TO 355

165 M=X*X:N=Y*Y

170 IF M+N > 4 THEN GOTO 215

180 Y = 2*X*Y + R

190 X = M - N + Q

210 NEXT I

215 I = I - 100

216 IF I=256 THEN I=0

230 REM

240 NEXT U

260 NEXT V

270 PRINT TI/60

New time: 98.0333 seconds. Extended time estimate: 20.91 hours. Total time saved: 3.73 hours. 15.1% faster.

[Scott Robison]

Getting close to the end of the mechanical changes that can make it faster. First the latest code:

0 TI=0:Y=0:X=0:I=0:V=0:U=0:N=0:M=0:R=0:Q=0

1 K=0.000027/240:J=0.000036/320:R=0.08784

2 FORV=0TO9:Q=-0.747345:FORU=0TO9:X=0:Y=0:M=0:N=0

3 FORI=0TO355:IFM+N>4GOTO5

4 Y=2*X*Y+R:X=M-N+Q:M=X*X:N=Y*Y:NEXTI

5 I=I-100:IFI=256THENI=0

6 REM

7 Q=Q+J:NEXTU:R=R+K:NEXTV

8 PRINTTI/60

I've crunched it at this point removing all the extra space. I removed THEN from THEN GOTO as the extra keyword isn't needed. I also changed how X^2 & Y^2 are calculated. We know every time into the I loop that X & Y are 0, so X^2 & Y^2 are 0. Rather than multiplying 0*0 to get 0, we just initialize the values before the loop, and we only do the multiplication at the end of the I loop instead of at the beginning. Thus we save a couple multiplications for every pixel to be plotted.

Also you'll note the line numbers are different. Shorter line numbers actually don't save any time except for when following a GOTO. It is faster to convert "5" to an integer than it is to convert "215" to an integer.

Also, look at previous line 105 and 120. Every time through the loop we do a multiplication, a division, and an addition. But we know every time that the first value will be 0, so 0*anything/anything is still 0. Instead we just set the value of the variable to its known non-0 part before entering the loop, then at the end of each loop we add a linear offset. In other words, we are taking advantage of "y=mx+b". We compute m then just add it at the end of each loop iteration.

I think that's all the changes I made this time. It took a bit longer to come up with enough that it felt worth updating.

New time: 94.4166 seconds. Extended time estimate: 20.14 hours. Total time saved: 4.5 hours. 18.3% faster.

[Scott Robison]

One last post, at least for now. Replaced all the 0 constants with a decimal point as I remembered they are slightly faster to process by BASIC.

0 TI=.:Y=.:X=.:I=.:V=.:U=.:N=.:M=.:R=.:Q=.

1 K=.000027/240:J=.000036/320:R=0.08784

2 FORV=.TO9:Q=-0.747345:FORU=.TO9:X=.:Y=.:M=.:N=.

3 FORI=.TO355:IFM+N>4GOTO5

4 Y=2*X*Y+R:X=M-N+Q:M=X*X:N=Y*Y:NEXTI

5 I=I-100:IFI=256THENI=.

6 REM

7 Q=Q+J:NEXTU:R=R+K:NEXTV

8 PRINTTI/60

New time: 94.3833 seconds. Extended time estimate: 20.135 hours. Total time saved: 4.505 hours. 18.3% faster. Effectively unchanged.

[Scott Robison]

Note: There might be some savings to be had by converting some floating point values to variables, but at that point you have to ask yourself: Is it faster to lookup a variable by name or to convert a string to a float?