BASIC Interpreter Speed Comparison: Prime Number Generation

[JamesD]

TRS-80 Model III
Limit 250 around 4 seconds but it's just too tough to get an accurate time
Limit 10000 139 seconds

The TRS-80 Model IIIis significantly faster than the VZ even though they both have origins in Level II BASIC and the VZ is clocked about faster.

The VZ *should* be down around 80 seconds for 10000 if I did the math right.

Edited December 2, 2017 by JamesD

[tecci06]

ACORN Electron.

Now, with the new code and without the screen turned off.

10CLS:CLEAR
20K%=0:I%=0:T%=0:P%=0
100PRINT"Prime Number Generator"
110INPUT"Upper Limit";N%
120ETIME=TIME
130T%=INT((N%-3)/2)
140DIMA%(T%+1)

160FORI%=0TOT%:A%(I%)=0:NEXT
200FORI%=0TOT%:IFA%(I%)THENPRINT"..";:NEXT:GOTO330
220P%=I%+I%+3:PRINT;P%;".";:K%=I%+P%:IFK%<=T%FORK%=K%TOT%STEPP%:A%(K%)=1:NEXT
260NEXT

330ETIME=(TIME-ETIME)/60
340PRINT:PRINT"Total: ";ETIME
360END

Limit 250: 2,35
Limit 10000: 86,83

 

It works now with the limit of 10000, because of the change of the variable A to A% etc.

Edited December 2, 2017 by tecci06

[+CyranoJ]

Well, 250 worked with the original code which was slow, but how do you tell the difference between 1.9 and 2.2 seconds with the latest code using hand timing?

 

Loop the 250 test 10 times.....

[_The Doctor__]

Cyrano, sometimes the solution is as plain as the nose on your face.

[JamesD]

Or use at least 2500?

[JamesD]

It's not like looping the test 250 time would correlate to the original test. It's completely different code.

[_The Doctor__]

say what!? I'm outta here. Have fun.

Edited December 2, 2017 by _The Doctor__

[JamesD]

Okay, I'm done

[tecci06]

Results on a Apple IIc

10 HOME : CLEAR
20 K = 0:I = 0:T = 0:P = 0

100 PRINT "Prime Number Generator"
110 INPUT "Upper Limit";N
130 T = INT ((N-3) / 2)
140 DIM A(T + 1)

150 FOR I = 0 TO T:A(I) = 0: NEXT
200 FOR I = 0 TO T: IF A(I) = 1 THEN PRINT "..";: NEXT: GOTO 340
210 P = I + I + 3: PRINT P;".";: K = I + P: IF K <  = T THEN FOR K = K TO T STEP P:A(K) = 1: NEXT
260 NEXT

340  PRINT : PRINT "Done"
350  END

With hand timing:

 

Limit 250: ~3 seconds

Limit 10000: 125 seconds

Edited December 3, 2017 by tecci06

[thorfdbg]

Atari++ defaults to PAL, not NTSC, so in the Atari basic code, you have to divide by 50, not 60 as given here. With these settings, and an upper limit of 10000, I get 176.72 seconds for Atari Basic on a standard XL Os, and 98.44 seconds (so almost twice as fast) on Basic++ and Os++. According to profiling, the main limitations are here in the Os screen scroller, a bit in the control character scan of the editor, and copying of variables to and from the basic run time stack. With the math pack patch, it is 83.82 seconds instead of 98.44 seconds, so the math pack is not quite the limiting factor. If compiled with the ABC compiler (all 3 byte integer math), it is down to 56 seconds. There, the time is mostly spend in the editor handler.

 

[JamesD]

ACORN Electron.

Now, with the new code and without the screen turned off.

10CLS:CLEAR
20K%=0:I%=0:T%=0:P%=0
100PRINT"Prime Number Generator"
110INPUT"Upper Limit";N%
120ETIME=TIME
130T%=INT((N%-3)/2)
140DIMA%(T%+1)

160FORI%=0TOT%:A%(I%)=0:NEXT
200FORI%=0TOT%:IFA%(I%)THENPRINT"..";:NEXT:GOTO330
220P%=I%+I%+3:PRINT;P%;".";:K%=I%+P%:IFK%<=T%FORK%=K%TOT%STEPP%:A%(K%)=1:NEXT
260NEXT

330ETIME=(TIME-ETIME)/60
340PRINT:PRINT"Total: ";ETIME
360END

Limit 250: 2,35

Limit 10000: 86,83

 

It works now with the limit of 10000, because of the change of the variable A to A% etc.

Does line 200 require the THEN statement on the Electron?

That may be good for a little improvement if you can drop it.

 

Edited December 3, 2017 by JamesD

[tecci06]

Does line 200 require the THEN statement on the Electron?

That may be good for a little improvement if you can drop it.

 

It is not required. But I did run without the THEN statement and did get:

Limit 250: 2,35 --> no improvement

Limit 10000: 86,63 instead of 86,83 well..... not much

Edited December 3, 2017 by tecci06

[JamesD]

It is not required. But I did run without the THEN statement and did get:

Limit 250: 2,35 --> no improvement

Limit 10000: 86,63 instead of 86,83 well..... not much

I didn't expect a huge difference, but I had hoped for a little more than that.

The low numbers won't show a difference on most machines because the improvement is smaller than the timer can measure.

 

[tecci06]

used your code from post #94 on my Commodore 64 (BASIC 2.0)

Limit 250: 3,133

Limit 10000: 136,5

[dmsc]

Hi!

 

Well, FastBasic is still faster than most other alternatives, with this code:

 

 

On NTSC, with screen ON, limit of 10000, I got 39.72 seconds:

 

 

With screen DMA OFF (poke 559,0 at start, poke 559,34 at end), I got 27.12 seconds:

 

 

All measurements are with XL OS, and time is mostly affected by screen write and scroll. With altirra XL-OS, I got 20.15 seconds.

Edited December 4, 2017 by dmsc

[JamesD]

Hi!

 

Well, FastBasic is still faster than most other alternatives, with this code:

....

Well, it is a compiler isn't it? It may use a bytecode interpreter, but it doesn't have to parse everything at runtime.

BASIC-09 turned in one of the best times on Ahl's benchmark even though it uses a bytecode interpreter, so I see no reason FastBasic couldn't do the same here.

I expect FastBasic to stay as one of the fastest even after people start posting results from other BASIC compilers.

The Atari MHz helps, but the language is geared more towards compilation than compilers that use the built in BASICs.

 

[JamesD]

Results on a Apple IIc

...

With hand timing:

 

Limit 250: ~3 seconds

Limit 10000: 125 seconds

 

used your code from post #94 on my Commodore 64 (BASIC 2.0)

Limit 250: 3,133

Limit 10000: 136,5

Even though they are clocked the same speed and originate from common code, I think the difference here comes down to how the keyboard was implemented.

 

[JamesD]

 

Even though they are clocked the same speed and originate from common code, I think the difference here comes down to how the keyboard was implemented.

 

I guess the C64 might have some clock cycles stolen by video as well.

[thorfdbg]

used your code from post #94 on my Commodore 64 (BASIC 2.0)

Limit 250: 3,133

Limit 10000: 136,5

That is surprisingly slow given that it had a better math model. Then again, it is all down to addition as far as math is concerned.

[KLund1]

Is someone going to put together another list with all the latest code updated times? It would fun to see.

[evilmoo]

Just for giggles, on Linux:

time for i in $(seq 1 2 10000); do factor $i; done |awk '$3 == "" {print $2}'

[JamesD]

I compiled the Plus/4 version with Austrospeed.
With the blanking code:
Limit 250 = 1.05 seconds
Limit 10000 = 43.3333333 seconds

Limit 20000 = 87.2333333 seconds

Skipping the parser makes a huge difference, but it's obviously not as efficient as FastBASIC.
It's probably making ROM calls and bankswitching between ROM and RAM.
It still handles larger arrays.

[dmsc]

Hi!

 

Just for giggles, on Linux:

time for i in $(seq 1 2 10000); do factor $i; done |awk '$3 == "" {print $2}'

 

Never tough of using the shell to list primes.... In my notebook, it gives "real: 0m7.351s, user: 0m5.546s", but you can use multiple cores with:

 

time for i in $(seq 1 2 10000); do factor $i & done |awk '$3 == "" {print $2}'

Here it's almost 5x faster, at "real: 0m1.570s, user: 0m3.926s", so it's 1.57 seconds for primes up to 10000.

 

For more fun still, you can use the recompiled-c64 basic at http://www.pagetable.com/?p=48with:

 

20 K=0:I=0:T=0:P=0
100 PRINT "Prime Number Generator"
110 INPUT "Upper Limit";N
130 T=(N-3)/2
140 DIMA(T+1)
160 FORI=0TOT:A(I)=0:NEXT
200 FORI=0TOT:IFA(I)THENPRINT"..";:NEXT:GOTO340
220 P=I+I+3:PRINTP;".";:K=I+P:IFK<=T THENFORK=KTOTSTEPP:A(K)=1:NEXT:NEXT:GOTO340
320 NEXT
340 PRINT
350 PRINT "Done: "
360 END

RUN
10000

Result is:

$ time ./cbmbasic  < primes

    **** COMMODORE 64 BASIC V2 ****

 64K RAM SYSTEM  38911 BASIC BYTES FREE

READY.
Prime Number Generator
Upper Limit?

 3.5.7...11.13...17.19...23.....29.31.....37...41.43...47.....53.....59.61.....67...71.73.....79...83.....89.......97...101.103...107.109...113.............127...131.....137.139.........149.151.....157.....163...167.....173.....179.181.........191.193...197.199...........211...........223...227.229...233.....239.241.........251.....257.....263.....269.271.....277...281.283.........293.............307...311.313...317.............331.....337.........347.349...353.....359.......367.....373.....379...383.....389.......397...401.......409.........419.421.........431.433.....439...443.....449.......457...461.463...467...........479.......487...491.......499...503.....509...........521.523.................541.....547.........557.....563.....569.571.....577.........587.....593.....599.601.....607.....613...617.619...........631.........641.643...647.....653.....659.661...........673...677.....683.......691.........701.......709.........719.......727.....733.....739...743.......751.....757...761.......769...773.............787.........797...........809.811.........821.823...827.829.........839.............853...857.859...863.............877...881.883...887...................907...911.......919.........929.......937...941.....947.....953.............967...971.....977.....983.......991.....997...........1009...1013.....1019.1021.........1031.1033.....1039.........1049.1051.........1061.1063.....1069.................1087...1091.1093...1097.....1103.....1109.......1117.....1123.....1129.....................1151.1153.........1163.......1171.........1181.....1187.....1193.......1201...........1213...1217.....1223.....1229.1231.....1237...........1249.........1259.................1277.1279...1283.....1289.1291.....1297...1301.1303...1307...........1319.1321.....1327.................................1361.....1367.....1373.......1381.................1399.........1409.............1423...1427.1429...1433.....1439.......1447...1451.1453.....1459...........1471.........1481.1483...1487.1489...1493.....1499...........1511...........1523.......1531...........1543.....1549...1553.....1559.......1567...1571.......1579...1583.............1597...1601.....1607.1609...1613.....1619.1621.....1627.........1637...................1657.....1663...1667.1669.......................1693...1697.1699.........1709...........1721.1723.........1733.......1741.....1747.....1753.....1759.................1777.....1783...1787.1789...........1801.........1811...........1823.......1831...............1847.............1861.....1867...1871.1873...1877.1879.........1889...........1901.....1907.....1913.................1931.1933...............1949.1951.....................1973.....1979.......1987.....1993...1997.1999...2003.......2011.....2017.........2027.2029.........2039.............2053.........2063.....2069...........2081.2083...2087.2089.........2099...........2111.2113...............2129.2131.....2137...2141.2143.........2153.......2161.................2179.......................2203...2207.....2213.......2221...............2237.2239...2243.......2251...............2267.2269...2273.......2281.....2287.....2293...2297...........2309.2311.....................2333.....2339.2341.....2347...2351.....2357.............2371.....2377...2381.2383.....2389...2393.....2399...........2411.....2417.....2423.............2437...2441.....2447...........2459.......2467.....2473...2477.........................2503.................2521.........2531.......2539...2543.....2549.2551.....2557.....................2579...........2591.2593...............2609.......2617...2621...........2633.............2647.........2657.2659...2663.......2671.....2677.....2683...2687.2689...2693.....2699.......2707...2711.2713.....2719.........2729.2731.........2741.......2749...2753.............2767.........2777...........2789.2791.....2797...2801.2803...............2819.............2833...2837.....2843.......2851.....2857...2861.................2879.......2887.........2897.....2903.....2909.......2917.........2927...........2939.............2953...2957.....2963.....2969.2971...........................2999.3001.........3011.......3019...3023.............3037...3041.......3049...........3061.....3067...........3079...3083.....3089...................3109.........3119.3121...............3137.........................3163...3167.3169...........3181.....3187...3191...........3203.....3209.......3217...3221.......3229.....................3251.3253...3257.3259...........3271...........................3299.3301.....3307.....3313.....3319...3323.....3329.3331...........3343...3347...........3359.3361.........3371.3373...............3389.3391...............3407.....3413...................3433...............3449.......3457...3461.3463...3467.3469.....................3491.......3499...........3511.....3517.........3527.3529...3533.....3539.3541.....3547.........3557.3559...........3571.........3581.3583.........3593.............3607.....3613...3617.....3623.......3631.....3637.....3643...............3659...........3671.3673...3677.............3691.....3697...3701.......3709.........3719.......3727.....3733.....3739.....................3761.....3767.3769.........3779.............3793...3797.....3803.................3821.3823.........3833.............3847...3851.3853.........3863.............3877...3881.......3889.................3907...3911.....3917.3919...3923.....3929.3931...........3943...3947...................3967.....................3989...........4001.4003...4007.....4013.....4019.4021.....4027.....................4049.4051.....4057...............4073.....4079...........4091.4093.....4099...........4111...............4127.4129...4133.....4139.............4153...4157.4159.................4177.......................4201.........4211.....4217.4219.........4229.4231.........4241.4243.........4253.....4259.4261.........4271.4273.........4283.....4289.......4297.............................4327.........4337.4339.........4349.......4357.....4363.........4373.................4391.....4397...........4409...........4421.4423.................4441.....4447...4451.....4457.....4463.................4481.4483.........4493.............4507.....4513...4517.4519...4523.......................4547.4549...........4561.....4567...............4583.......4591.....4597.....4603.................4621...............4637.4639...4643.....4649.4651.....4657.....4663.........4673.....4679...........4691...........4703.................4721.4723.....4729...4733.................4751.......4759.......................4783...4787.4789...4793.....4799.4801...........4813...4817.............4831.............................4861.........4871.....4877...........4889.............4903.....4909.........4919...........4931.4933...4937.....4943.......4951.....4957.........4967.4969...4973.............4987.....4993.....4999...5003.....5009.5011.........5021.5023...............5039...........5051.......5059.................5077...5081.....5087...........5099.5101.....5107.....5113.....5119...........................5147.....5153.............5167...5171.......5179.........5189.......5197...........5209.................5227...5231.5233...5237.......................5261...........5273.....5279.5281...............5297.....5303.....5309.............5323.........5333.............5347...5351.............................5381.....5387.....5393.....5399.......5407.....5413...5417.5419...........5431.....5437...5441.5443.....5449.....................5471.....5477.5479...5483.................5501.5503...5507...........5519.5521.....5527...5531.........................5557.....5563.....5569...5573.......5581.........5591...............................5623...............5639.5641.....5647...5651.5653...5657.5659.........5669.............5683.....5689...5693.......5701.........5711.....5717...................5737...5741.5743.....5749.............................5779...5783.......5791.........5801.....5807.....5813.......5821.....5827...........5839...5843.....5849.5851.....5857...5861.....5867.5869.........5879.5881...............5897.....5903...................5923...5927...........5939.............5953...........................5981.....5987...................6007...6011.................6029.......6037.....6043...6047.....6053.............6067.....6073.....6079.........6089.6091.........6101...........6113.......6121.........6131.6133.........6143.......6151...........6163.........6173.......................6197.6199...6203.......6211.....6217...6221.......6229.................6247.........6257.....6263.....6269.6271.....6277.........6287...........6299.6301.........6311.....6317.....6323.....6329.......6337.....6343.........6353.....6359.6361.....6367.....6373.....6379.........6389.......6397.......................6421.....6427.....................6449.6451.................6469...6473.......6481.........6491.............................6521.......6529.................6547...6551.6553.........6563.....6569.6571.....6577...6581.................6599.......6607...........6619.................6637...............6653.....6659.6661...........6673.....6679.........6689.6691.........6701.6703.....6709.........6719.............6733...6737.......................6761.6763...............6779.6781.........6791.6793.........6803...................6823...6827.6829...6833.......6841...............6857.....6863.....6869.6871...........6883...............6899.......6907...6911.....6917.............................6947.6949.........6959.6961.....6967...6971.....6977.....6983.......6991.....6997...7001...........7013.....7019.......7027...........7039...7043.............7057...........7069.........7079.......................7103.....7109...........7121.....7127.7129.....................7151.......7159.................7177.........7187.....7193.............7207...7211.7213.....7219.........7229.......7237.....7243...7247.....7253.............................7283.............7297.........7307.7309...........7321.........7331.7333...............7349.7351.................7369.......................7393.................7411.....7417...............7433.................7451.....7457.7459.................7477...7481.....7487.7489.........7499.......7507.........7517.....7523.....7529.......7537...7541.....7547.7549.........7559.7561...........7573...7577.....7583.....7589.7591...........7603...7607.............7621.................7639...7643.....7649...................7669...7673.......7681.....7687...7691.......7699...7703.............7717.....7723...7727.............7741...........7753...7757.7759.............................7789...7793.......................7817.....7823.....7829...........7841...........7853.............7867.....7873...7877.7879...7883.................7901.....7907...........7919.......7927.....7933...7937...........7949.7951...........7963.............................7993...............8009.8011.....8017.....................8039.............8053.....8059.........8069...........8081.....8087.8089...8093.......8101.........8111.....8117.....8123.......................8147.............8161.....8167...8171.......8179...........8191.................8209.........8219.8221.........8231.8233...8237.....8243...................8263.....8269...8273.............8287...8291.8293...8297.............8311.....8317...........8329.......................8353.........8363.....8369.......8377.........8387.8389.............................8419...8423.....8429.8431...........8443...8447.............8461.....8467.................................8501...........8513.......8521.....8527.........8537.8539...8543...................8563.........8573.......8581...............8597.8599.........8609.............8623...8627.8629...........8641.....8647...............8663.....8669.......8677...8681.......8689...8693.....8699.......8707.....8713.....8719...........8731.....8737...8741.....8747.....8753.......8761.................8779...8783...................8803...8807...........8819.8821.........8831.....8837.8839.........8849...........8861.8863...8867...................8887.....8893.............................8923.....8929...8933.......8941.........8951...........8963.....8969.8971...........................8999.9001.....9007...9011.9013...............9029...........9041.9043.....9049.........9059.......9067.......................9091...........9103.....9109.................9127.....9133...9137.............9151.....9157...9161...........9173.......9181.....9187...........9199...9203.....9209...........9221.....9227...........9239.9241...............9257...................9277...9281.9283.........9293.................9311.......9319...9323.............9337...9341.9343.....9349.....................9371.....9377.............9391.....9397.....9403.........9413.....9419.9421.........9431.9433...9437.9439.....................9461.9463...9467.....9473.....9479...........9491.....9497.............9511.........9521...........9533.....9539.......9547...9551...................................9587.............9601...........9613.....9619...9623.....9629.9631...........9643.....9649...........9661...............9677.9679.........9689.......9697.....................9719.9721...........9733.....9739...9743.....9749.................9767.9769...........9781.....9787...9791...........9803.......9811.....9817...........9829...9833.....9839...........9851.....9857.9859...........9871...........9883...9887.............9901.....9907...............9923.....9929.9931.........9941.......9949.................9967.....9973...........................
Done: 

READY.

real	0m0.066s
user	0m0.049s
sys	0m0.034s

[JamesD]

4 clock ticks on an NTSC system is about .0666... seconds on most 8 bits.

[JamesD]

That is surprisingly slow given that it had a better math model. Then again, it is all down to addition as far as math is concerned.

What do you mean by better math model?