Jump to content
Maury Markowitz

Anyone for a little benchmarking?

Recommended Posts

The only 8K BASIC interpreters I'm aware of either don't have floating point math or any extended BASIC commands.  The MS BASIC floating point libraries I've looked at take up around 2K.  That doesn't leave a lot of room for for speed optimizations.

@Maury MarkowitzI was looking at using tokens to identify what type of value followed to speed up the BASIC on the MC-10, and to do the conversions at tokenization time as you suggest.
To store floating point numbers, I planned on using pointer to a location in a table with the FP value, and the original string.  
Numbers don't convert exactly when using floating point, so the original string needs preserved somehow.
Plus, Microsoft BASIC has to copy the floating point number to a virtual floating point register, and the function that does that requires a pointer anyway.
I also considered converting line numbers to pointers, and the original ASCII line number can be generated from the line the pointer refers to.  
This makes the interpreter faster, and listing the file or editing a line easy, but saving the program in a compatible format is a little more difficult on a machine with only cassette tape with no on/off control.  🙄 

  • Like 1

Share this post


Link to post
Share on other sites
4 hours ago, flashjazzcat said:

No-one would argue with the assertion that more ROM space can allow for performance and optimisation improvements. But you appeared to be under the impression that the Atari interpreters - unlike 'the non-Atari Basic Interpreters used by the machines I listed above' - are operable within 8K. I point out that neither Atari BASIC, nor your 'interpreter of choice' Altirra BASIC, will work without the 2K OS FP ROM. Both BASICs are essentially 10K implementations, then, whether you like it or not.

 

Try it for yourself: take an XL/XE OS, fill $D800-$DFFF with $FF, and replace the 'SEC' ($38) instruction at the end of the OS checksum test with 'CLC' ($18) so that the bad checksum is overlooked. You'll see the OS boots just fine but Atari BASIC and Altirra BASIC crash before they even get a 'READY' prompt on the screen. If you can demonstrate either BASIC being operational with such a patched, FP-less OS, that's a different story, of course. :)

 

I can see why Atari placed the FP package in the OS since there was space available, and this a) makes the FP package accessible by other applications, and b) allows the BASIC cartridge to be 8K instead of 10K. And that is the only reason the BASIC cartridge is 8K and not 10K. Altirra BASIC is superb, and is my default drop-in replacement for Atari BASIC. It's even clear that it's a marvel of conciseness, given the features Avery managed to pack into it. But it still relies on 2K of FP code, and since it relies on it at all, it relies on it 'entirely'. Maybe if Avery wrote a 10K version of Altirra BASIC with the FP code built in, it would come it at a little under 10K... more than likely. Whatever.

 

If you can argue that the extra 2K is BASIC-specific, then I'll agree with your tally.  But if you're saying that BASIC is bigger than that because it relies on OS calls, then you'll have a very short list of cartridges of any sort that are, by that definition, really 8K.  "If you remove part of the BIOS, it crashes."  That's true for most computers, and even some consoles.  Only a select few programs on any system are truly self-contained.  You might as well argue that GM doesn't really build their own vehicles because they use parts made by Bosch, Renesas, Bose, etc.

  • Thanks 1

Share this post


Link to post
Share on other sites
1 hour ago, ChildOfCv said:

If you can argue that the extra 2K is BASIC-specific, then I'll agree with your tally.  But if you're saying that BASIC is bigger than that because it relies on OS calls, then you'll have a very short list of cartridges of any sort that are, by that definition, really 8K.  "If you remove part of the BIOS, it crashes."  That's true for most computers, and even some consoles.  Only a select few programs on any system are truly self-contained.  You might as well argue that GM doesn't really build their own vehicles because they use parts made by Bosch, Renesas, Bose, etc.

I knew it would be a matter of time before other parts of the OS were equated with the FP package. :) Most BASICs - indeed applications in general - are going to rely on the IO functions of the OS, but that's basically file and console IO in the case of BASIC. This does not change the fact that that an 8K FP BASIC on the A8 is not miraculously small compared to - say - a 10K implementation with similar features and self-contained FP code on another platform. I make the point about removing the FP package entirely in order to demonstrate that Altirra BASIC cannot function without it, regardless of whether one's BASIC program explicitly performs FP calculations.

 

It seems to me that the most positive aspect of the FP package residing in the OS ROM is that your FP applications can be smaller, since they need not implement their own FP code. A good example would be... I don't know... BASIC? It's the reason Atari BASIC fits onto an 8K ROM. I don't think the advantageous availability of the FP ROM to programs other than BASIC interpreters changes much, however, when one is making a qualitative comparison of the relative code size/efficiency trade-offs of BASICs on different platforms. 'FP BASIC can be smaller when it can call 2K of public FP code in the OS'. Well, yes it can.

 

Of course, I do think that Altirra BASIC exhibits impressive performance gains when compared to Atari BASIC. It seemed to me that the matter of the FP ROM had rather been overlooked, however.

  • Like 2

Share this post


Link to post
Share on other sites
2 hours ago, ChildOfCv said:

If you can argue that the extra 2K is BASIC-specific, then I'll agree with your tally.  But if you're saying that BASIC is bigger than that because it relies on OS calls, then you'll have a very short list of cartridges of any sort that are, by that definition, really 8K.  "If you remove part of the BIOS, it crashes."  That's true for most computers, and even some consoles.  Only a select few programs on any system are truly self-contained.  You might as well argue that GM doesn't really build their own vehicles because they use parts made by Bosch, Renesas, Bose, etc.

 

Absolutely correct.

 

Atari Basic (and ANY derivative that pursues direct or replacement-grade compatibility) MUST BE and IS an <= 8192 bytes ROM package. Period. Not one byte more, maybe less. Now, that its design follows the premise of using the FP package as far as you can get away while NOT exceeding those 8219 bytes, is in fact a design and implementation decision that pertains ATARI BASIC.

 

In that sense, the FP package is an OS RESOURCE, and NOT an Atari Basic one. And this on itself, introduces a HUGE benefit which is nothing else than performance elasticity (which seems completely overlooked here). You can optimize the 8K package (without ever touching OS resources) and still obtain higher performance. On the other hand, you can optimize OS resources and also obtain higher performance without EVER touching the 8K Basic Package itself. Now, You can optimize both and you will get fireworks!. This, however, CANNOT be achieved with Turbo Basic, MS Basic, etc.

 

As an opposite example, I actually wonder if Fast Basic-I (Integer only package) actually uses the OS FP package for ANYTHING... It seems to me it does not at all (will have to trace deeper) and it is, in fact, SMALLER than 8192 bytes, altogether (!)

 

Share this post


Link to post
Share on other sites
6 hours ago, Maury Markowitz said:

The reason I ask is BM2 time. Apple II running Applesoft is 8.5 seconds, while a stock XL is 7.3.

 

Altirra is 1.9?

 

This suggests that the Altirra version is using some sort of fast GOTO like Turbo or BASIC XL? Does anyone know?

Benchmark test #2 has been modified in the Atari BASIC in an important way:both of the loop statements are on the same line. This matters because Altirra BASIC has an optimization to start line number searches from the current line when possible, so this makes the line number search succeed immediately. Split the two lines and the time increases by about half. Altirra BASIC also uses a dedicated compare routine instead of subtraction, which helps with relational operators and FOR loops.

 

Turbo-Basic XL also has a hashed line cache, which speeds up line lookups after the first time. The problem with implementing such a cache is memory for it, as typically it reuses the 256 byte argument stack area, which is otherwise unused in TBXL due to the argument stack being moved elsewhere. I didn't implement the cache on Altirra BASIC due to needing to stick closely to Atari BASIC memory layout for compatibility. Altirra Extended BASIC does implement both the transposed SoA argument stack and the hashtable, since it has less compatibility and code size constraints.

 

2 hours ago, ChildOfCv said:

If you can argue that the extra 2K is BASIC-specific, then I'll agree with your tally.  But if you're saying that BASIC is bigger than that because it relies on OS calls, then you'll have a very short list of cartridges of any sort that are, by that definition, really 8K.  "If you remove part of the BIOS, it crashes."  That's true for most computers, and even some consoles.  Only a select few programs on any system are truly self-contained.  You might as well argue that GM doesn't really build their own vehicles because they use parts made by Bosch, Renesas, Bose, etc.

The math pack does contain a few bits that are undocumented and Atari BASIC specific. Some of the routines could be argued as Atari BASIC just leveraging internal math pack routines to save space in violation of best practices, but it's harder to justify constants like the ATN() polynomial being hidden in it, which the math pack itself has no use for. Altirra BASIC also uses these because, well, they have to be there, so might as well use them.

 

Share this post


Link to post
Share on other sites
4 hours ago, JamesD said:

The only 8K BASIC interpreters I'm aware of either don't have floating point math or any extended BASIC commands.

@Maury MarkowitzI was looking at using tokens to identify what type of value followed to speed up the BASIC on the MC-10, and to do the conversions at tokenization time as you suggest.
To store floating point numbers, I planned on using pointer to a location in a table with the FP value, and the original string.  
Numbers don't convert exactly when using floating point, so the original string needs preserved somehow.
Plus, Microsoft BASIC has to copy the floating point number to a virtual floating point register, and the function that does that requires a pointer anyway.
I also considered converting line numbers to pointers, and the original ASCII line number can be generated from the line the pointer refers to.  
This makes the interpreter faster, and listing the file or editing a line easy, but saving the program in a compatible format is a little more difficult on a machine with only cassette tape with no on/off control.  🙄 

Ok first off, how do I break up quotes so I can answer in bits at a time and retain the "posted by so-and-so"? If I reply I get a big block of quoted text, and if I try to edit in the middle it just goes nuts.  I know I can select-n-paste-as-quote, but the screen above this has a full page of replies so scrolling through it all is a pain!

 

So anyway:

 

Quote

The only 8K BASIC interpreters I'm aware of either don't have floating point math or any extended BASIC commands.


On the 6502, yes, but of course the original 8080 code was under 8k (barely) with 32-bit FP.

 

Quote

To store floating point numbers, I planned on using pointer to a location in a table with the FP value, and the original string.  

 

I have put considerable thought into this if you're interested in my solutions. However, they did assume Atari BASIC layout to some degree so some of the suggestions make no sense elsewhere.

 

It's funny - Atari BASIC uses a lookup table as you mention for MC, and that really is faster than MS's solution. However, that advantage is just WIPED OUT by the slowness of the loops. It's really sad.

 

Quote

Numbers don't convert exactly when using floating point

 

So there's the one upside to Atari's BCD code, it saves you having to do what you did. But tip-o-da-hat, that is a clever solution!

 

Quote

I also considered converting line numbers to pointers, and the original ASCII line number can be generated from the line the pointer refers to.

 

So... what's your thought here? Certainly you can replace Atari's 6-byte FP with a 16-bit int. Is that what you mean, store the actual value as a int instead of a string? Doesn't MS do that?

Share this post


Link to post
Share on other sites
1 hour ago, phaeron said:

Benchmark test #2 has been modified in the Atari BASIC in an important way:both of the loop statements are on the same line.

 

Ah yes, so it is not really the benchmark, and not really Atari BASIC.

 

@Faicuai, are you willing to run it again using real Atari BASIC instead of Altirra, and without merging the lines?

 

I just noticed that Wilkinson did the same on his version of the sieve, so it's invalid as well.

Share this post


Link to post
Share on other sites
Posted (edited)

what makes it invalid? it is permissible in a number of BASIC's. If a BASIC flavor can't do a certain thing, should that not thing then not be used in any other BASIC's that exist? There sure wouldn't be much left to work with if we did that...

Edited by _The Doctor__

Share this post


Link to post
Share on other sites
Posted (edited)
33 minutes ago, Maury Markowitz said:

Ah yes, so it is not really the benchmark, and not really Atari BASIC.

 

@Faicuai, are you willing to run it again using real Atari BASIC instead of Altirra, and without merging the lines?

 

I just noticed that Wilkinson did the same on his version of the sieve, so it's invalid as well.

 

Of course, not a problem (although I am traveling overseas, vacations, and will be back mid July). I will try to do it sometime via RPD on Win10, and check results.

 

In the mean time, the sources are posted since day #1, and anyone can jump into them with Altirra Basic 1.56 and Altirra FP package (no interest on Atari Basic, as it is simply a very well known and solidly engineered dead-weight).

 

If we insist on Atari Basic, I will also be interested, however, in equating ROM usage space to the HIGHEST driven by the machines on the test group. In other words, if the BBC uses 32K space for OS+Basic, I want the EXACT SAME space for the Atari, and use any other package that meets such criteria (I don't mind if any other versions or machines do the exact same, with the ABSOLUTELY BEST TOOL available, as long as we remained on the INTERPRETER domain). 

 

If you only have Altirra 3.20 Emulator, that is fine for running on your own, assuming that you use Avery's XL OS replacement. In this way, you should be able to check the difference on your end, at will.

 

However, I anticipate (at this point) little impact, though, if the increment in time is estimated from current 1.9 secs, assuming the ingredients I originally disclosed (Altirra 1.56 + Altirra FP).

 

Cheers!

Edited by Faicuai

Share this post


Link to post
Share on other sites
3 hours ago, flashjazzcat said:

I knew it would be a matter of time before other parts of the OS were equated with the FP package. :) Most BASICs - indeed applications in general - are going to rely on the IO functions of the OS, but that's basically file and console IO in the case of BASIC.

While true, the OS routines don't always have to be limited to running hardware.
 

1 hour ago, phaeron said:

The math pack does contain a few bits that are undocumented and Atari BASIC specific. Some of the routines could be argued as Atari BASIC just leveraging internal math pack routines to save space in violation of best practices, but it's harder to justify constants like the ATN() polynomial being hidden in it, which the math pack itself has no use for. Altirra BASIC also uses these because, well, they have to be there, so might as well use them.

  "Generic Spreadsheet for Atari" has just as much utility for the FP routines.  And ATN is not exactly a BASIC-specific function either--perhaps you need to figure out what angle something is based on the hypotenuse?  Or do you mean that it does things that are inseparable from BASIC?

 

3 hours ago, flashjazzcat said:

 

This does not change the fact that that an 8K FP BASIC on the A8 is not miraculously small compared to - say - a 10K implementation with similar features and self-contained FP code on another platform. I make the point about removing the FP package entirely in order to demonstrate that Altirra BASIC cannot function without it, regardless of whether one's BASIC program explicitly performs FP calculations.

Okay, I'll grant that one, now that I see where you're coming from.  Well, sorta.  Some systems have built-in FP support and therefore much less need for FP library solutions.  Of course, MS LibC on PCs still uses a function call for sin and cos even though there are fsin and fcos instructions, but then I've heard that they weren't that accurate, so it can make sense to prefer the library call over a potentially faster instruction.

 

Share this post


Link to post
Share on other sites
3 minutes ago, ChildOfCv said:

  "Generic Spreadsheet for Atari" has just as much utility for the FP routines.  And ATN is not exactly a BASIC-specific function either--perhaps you need to figure out what angle something is based on the hypotenuse?  Or do you mean that it does things that are inseparable from BASIC?

 

It's not the full ATN() routine, just the polynomial coefficients and the range reduction portion of BASIC's implementation of it, and both of which are undocumented.

 

  • Like 1

Share this post


Link to post
Share on other sites
25 minutes ago, phaeron said:

 

It's not the full ATN() routine, just the polynomial coefficients and the range reduction portion of BASIC's implementation of it, and both of which are undocumented.

 

Sounds vestigial, to me...

Share this post


Link to post
Share on other sites
1 hour ago, Maury Markowitz said:

Ok first off, how do I break up quotes so I can answer in bits at a time and retain the "posted by so-and-so"? If I reply I get a big block of quoted text, and if I try to edit in the middle it just goes nuts.  I know I can select-n-paste-as-quote, but the screen above this has a full page of replies so scrolling through it all is a pain!

I wish I knew!  At least we used to be able to edit the formatting.

 

Quote

On the 6502, yes, but of course the original 8080 code was under 8k (barely) with 32-bit FP.

There was an OR there.   Several Microsoft BASICs fit in 8K, but they don't support extended BASIC graphics or sound commands.
Integer BASIC on the Apple had a few extended BASIC type things.  I can't remember how large it is though.

 

Quote

So... what's your thought here? Certainly you can replace Atari's 6-byte FP with a 16-bit int. Is that what you mean, store the actual value as a int instead of a string? Doesn't MS do that?

I don't know what Atari BASIC does, but MS BASIC does not convert line numbers in GOTO or GOSUB statement to 16 bit integers during tokenization.
It does use 16 bit integers to represent the line number in the structure before each line of code.  
Every time it executes a GOTO or GOSUB, it has to parse the number from ASCII to a 16 bit int, then it searches through the linked list of lines looking for the 16 bit integer of the line you are jumping to.
I wanted to convert the ASCII to INTs when the line is entered (which by itself would be a big improvement), then convert those to pointers when you type RUN, so all the lookups take place before the code executes, and just directly jump to the line without any kind of search after that.  Not even a table lookup.
The drawback, is that you have to enter a non-runtime mode before you can actually add more lines, change lines, or save the program.
Would it be faster?  Yes!   But the mode switching, even though it could be automatic, would create a few delays as the interpreter performs the conversions.

  • Like 1

Share this post


Link to post
Share on other sites

automatic mode changing delay sounds just fine to me, We just want the performance during execution is all

Share this post


Link to post
Share on other sites

There is another drawback.  If you haven't finished typing all the code, and some line that hasn't been entered yet is referred to with a GOTO or GOSUB, you would necessarily get an error when you type RUN.  

Share this post


Link to post
Share on other sites

Cool, since it would likely dump out anyway once you hit the routine... you just need to make sure to have place holders for such things with a return or what have you... since you'd most likely be testing something to encounter such a happening anyway..

Share this post


Link to post
Share on other sites
Posted (edited)
9 hours ago, Maury Markowitz said:

Ok first off, how do I break up quotes so I can answer in bits at a time and retain the "posted by so-and-so"? If I reply I get a big block of quoted text, and if I try to edit in the middle it just goes nuts.  I know I can select-n-paste-as-quote, but the screen above this has a full page of replies so scrolling through it all is a pain!

Hit enter to break up a line if necessary.  Then place the cursor at the beginning of a blank line within the quote and hit enter.

Edited by ChildOfCv
Clarify how-to

Share this post


Link to post
Share on other sites
Posted (edited)
15 hours ago, _The Doctor__ said:

what makes it invalid? it is permissible in a number of BASIC's. If a BASIC flavor can't do a certain thing, should that not thing then not be used in any other BASIC's that exist? There sure wouldn't be much left to work with if we did that...

Any one of the machines listed in the R-F lists also benefit from this same trick. So if you change them in the same way then their numbers change too.

 

So you can't change one and not the other and have any basis for direct comparison. And direct comparison is the whole point of a benchmark.

 

Certainly one can use such modifications as a demonstration of how to improve performance, but not to compare it. For instance, if you run the code before and after modifications on a single platform then you are demonstrating how such changes effect performance. But if you run one set on one machine and another on a different one, which is what happened here, then you learn nothing at all.

Edited by Maury Markowitz

Share this post


Link to post
Share on other sites
Posted (edited)
15 hours ago, Faicuai said:

 

Of course, not a problem (although I am traveling overseas, vacations, and will be back mid July). I will try to do it sometime via RPD on Win10, and check results.



I am curious, does overseas entail a trip eastward or westward?

Edited by Maury Markowitz

Share this post


Link to post
Share on other sites

conversely, you could combine the lines on all the others just like the atari listing....

testing both ways... a true all around benchmark, you know, like almost all benchmarks that test different abilities and their effectiveness today... showing what machines work the most effectively using which method. Then you know which machine does what kind of proggy implementations the best.

  • Like 1

Share this post


Link to post
Share on other sites
Posted (edited)
14 hours ago, JamesD said:

I don't know what Atari BASIC does, but MS BASIC does not convert line numbers in GOTO or GOSUB statement to 16 bit integers during tokenization.

Wild! But I think I know why...

 

To be honest, I'm not sure what Atari BASIC (AB herein) does here. I know for normal numeric constants, like A=A+10, the constant is parsed and replaced by it's FP representation, with a $0E placed in front of it to indicate a constant. The FP is 40-bits, so the total length of any constant is 1-byte + 6-bytes.

 

I'm not sure if they do this for line numbers, I'll have to look. It would save the conversion at runtime, but since AB's maximum line number is 32767, it's 7 bytes of constant vs. maximum of 5 bytes of text, and typically maybe 3 bytes. Moreover, you have to convert the resulting FP number into the 16-bit line number anyway (which it uses, like MS), so there's still a little performance hit.

 

And wow, I just realized why they used a BCD math package! Its because if you tokenize a number into a "real" FP, as opposed to BCD, then when you convert it back to a string you might get line 99.999999... This doesn't really do anything, but it sure looks weird - too weird. That's the problem you were avoiding by storing the original string constant. AB doesn't have to do that, small integers will always convert back correctly.

 

Which brings me full circle on the whole int-FP question. If AB had 16-bit int constants, a relatively trivial upgrade, then you wouldn't need to use FP for (most) constants, and then you could replace the FP package with the MS one with few downsides. That makes for a very interesting test!

 

Quote

I wanted to convert the ASCII to INTs when the line is entered (which by itself would be a big improvement), then convert those to pointers when you type RUN, so all the lookups take place before the code executes, and just directly jump to the line without any kind of search after that.

In AB I would do that by using a unique token for the original 16-bit line number, say $0B, and then if you encounter an $0B during runtime...

 

Oh, wait, this works perfectly!

 

... if you encounter a $0B during runtime, you run the line-lookup routine, change the $0B to $0A, and change the 16-bit line number to a 16-bit line address.

 

I didn't think this would work because I think doing the scan-and-replace at program startup would be a high cost, especially in long programs. I note that BASIC XL does this if you use the FAST command. I concluded the table-lookup was the only solution that offered both a performance improvement and avoided startup issues.

 

But looking at it now, you don't have to do this replacement for every line, only the ones that actually get called. And you only know that at runtime, so just do that then. This does introduce some randomness in the performance of the GOTO, but its worst case is still MS's best case.

 

Of course one could combine the two approaches. When a $0B is encountered, you do the line-number-lookup and replace it in-place. But then you also put it in a lookup table. So then when the next unconverted GOTO pointed to the same line is seen, you can convert it using the table. However, I'm not convinced this is worthwhile given the complexity it would add to the runtime.

 

It seems a direct comparison of the two (three?) approaches would be needed. Unfortunately, existing benches would be useless for this, because they are very small and only have one or zero GOTOs. You'd want to run something much longer with lots of typical BASIC spaghetti to know what's really going on. Super Star Trek would be great, but I can't imagine a way to benchmark it.

Edited by Maury Markowitz

Share this post


Link to post
Share on other sites
Posted (edited)
21 minutes ago, _The Doctor__ said:

conversely, you could combine the lines on all the others just like the atari listing....

Sure, but they didn't do that when they published the results.

 

So if you want to compare the Atari to, say, the Apple II, you either have to have both machines and run the same code, or use the published result and use the original code.

 

As @phaeron noted, the difference is somewhere like a factor of 2x, so this is non-trivial. And yes, it would be about 2x on the Apple II as well.

Edited by Maury Markowitz

Share this post


Link to post
Share on other sites
4 hours ago, Maury Markowitz said:

Wild! But I think I know why...

 

To be honest, I'm not sure what Atari BASIC (AB herein) does here. I know for normal numeric constants, like A=A+10, the constant is parsed and replaced by it's FP representation, with a $0E placed in front of it to indicate a constant. The FP is 40-bits, so the total length of any constant is 1-byte + 6-bytes.

 

I'm not sure if they do this for line numbers, I'll have to look. It would save the conversion at runtime, but since AB's maximum line number is 32767, it's 7 bytes of constant vs. maximum of 5 bytes of text, and typically maybe 3 bytes. Moreover, you have to convert the resulting FP number into the 16-bit line number anyway (which it uses, like MS), so there's still a little performance hit.

Atari BASIC stores all line numbers in statements as FP decimal. One reason for this is that most statements that take line numbers also accept expressions. The line number for each line is stored as binary, however.

4 hours ago, Maury Markowitz said:

And wow, I just realized why they used a BCD math package! Its because if you tokenize a number into a "real" FP, as opposed to BCD, then when you convert it back to a string you might get line 99.999999... This doesn't really do anything, but it sure looks weird - too weird. That's the problem you were avoiding by storing the original string constant. AB doesn't have to do that, small integers will always convert back correctly.

No, this is not a problem for binary floating point either. In 32-bit binary floating point with a 23-bit mantissa, all integers under +/-2^24 are represented exactly.

4 hours ago, Maury Markowitz said:

But looking at it now, you don't have to do this replacement for every line, only the ones that actually get called. And you only know that at runtime, so just do that then. This does introduce some randomness in the performance of the GOTO, but its worst case is still MS's best case.

 

Of course one could combine the two approaches. When a $0B is encountered, you do the line-number-lookup and replace it in-place. But then you also put it in a lookup table. So then when the next unconverted GOTO pointed to the same line is seen, you can convert it using the table. However, I'm not convinced this is worthwhile given the complexity it would add to the runtime.

 

It seems a direct comparison of the two (three?) approaches would be needed. Unfortunately, existing benches would be useless for this, because they are very small and only have one or zero GOTOs. You'd want to run something much longer with lots of typical BASIC spaghetti to know what's really going on. Super Star Trek would be great, but I can't imagine a way to benchmark it.

Line number caching is actually quite a lot simpler than using binary addresses: it only requires some hashtable memory, a hash lookup/insertion in the line number lookup code, and a few hooks to invalidate/clear the hash table when execution starts or the program is modified. And unlike the binary address approach, it can accelerate computed GOTOs. There is still the cost of converting FP to binary, but that is such an important operation that most fast BASICs or math packs have it optimized using bit or digit conversion tables.

 

Caching the addresses in the program text requires a lot more interpreter code. The parser has to know which expressions are line numbers and detect single constants that can be safely converted to binary (GOTO -0.4 is valid), statements consuming line numbers need to use a special evaluator that can handle the binary lines, and in the event of a program modification or SAVE a full program scan is needed to convert addresses back to line numbers. Oh, and if Atari BASIC compatibility is needed, the binary numbers need to still take six bytes so there is room to convert to floating point, and LOAD needs to be able to do the same conversion as the parser. It's doable, but with a lot more complexity.

 

In practice, between common practice in Atari BASIC programs and line caching, I haven't seen line number lookup showing up very hot in the profiles in Altirra Extended BASIC. The expression evaluator dominates the profile for many programs since it is such a huge bottleneck for everything.

 

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...