Is GOTO ever not evil?

[tricky]

In my converters for the beeb I often find myself using GOTO and I have a few in my work code! All c/c++.

[Adam James]

As has been noted, the use of GOTO (or an equivalent) is unavoidable in many programming languages, or even if it is avoidable it may have advantages which I haven't found to apply in BBC BASIC.

I don't know if you missed my earlier question, but I'm wondering if the example I gave at the start is not an example of GOTO serving a purpose in BBC BASIC? Is there a better way to speed-optimise the example in BBC BASIC?

[Richard Russell]

"the only significant loss I can remember is over labels vs line numbers - the BBC committee insisted on line numbers"

There was an overriding consideration that 'standard' BASIC programs of the day (usually in a Microsoft-derived dialect) should run unmodified in BBC BASIC, so that made support for line numbers mandatory and governed several other language features such as array bounds (as discussed here before we seem to have dropped the ball with LOG).

But Sophie could have implemented line numbers in a more efficient way had she wanted to (for example by treating them internally as labels, as Liberty BASIC does) without falling foul of the requirements of the BBC Specification.

[Richard Russell]

I'm wondering if the example I gave at the start is not an example of GOTO serving a purpose in BBC BASIC? Is there a better way to speed-optimise the example in BBC BASIC?

If speed was that important to me (which has been very rare) I would almost certainly have used something other than interpreted BASIC, at least for the time-critical parts of the program.

[Adam James]

If speed was that important to me (which has been very rare) I would almost certainly have used something other than interpreted BASIC, as least for the time-critical parts of the program.

I think that's changing the boundaries in order to fit a world-view. In the same way you told Lardo Boffin you don't see the relevance of GOTO in other languages because you were talking about BBC BASIC, I'd say the same to you.

So, sticking to BBC BASIC, is there a better way to speed-optimise this? I'm not asking you to write the code, but if you have any ideas I'll give them a try.

Programming purely in BBC BASIC is a perfectly reasonable boundary. If I were to be purely focused on speed, I would be booking time on a quantum computer. But I'm focused on speed within BBC BASIC as that's within my intellectual reach and I'm finding it fun.

[Richard Russell]

In my converters for the beeb I often find myself using GOTO and I have a few in my work code! All c/c++.

I have very occasionally used goto in C. There aren't the 'cheats' available in C that there are in BBC BASIC, making it harder to avoid. For example when handling errors I might use ON ERROR in BBC BASIC but goto in C.

[Lardo Boffin]

I could have not used GOTO in this case but I think that would be the wrong way forward given the constraints I faced.

My comment about not using GOTO was, of course, specific to BBC BASIC. You seem to be referring to a different language so I don't see the relevance. As has been noted, the use of GOTO (or an equivalent) is unavoidable in many programming languages, or even if it is avoidable it may have advantages which I haven't found to apply in BBC BASIC.

My apologies. Had a realised your point applied strictly to BBC Basic (should have worked that one out) I would not have referenced your post in my post.

[Richard Russell]

So, sticking to BBC BASIC, is there a better way to speed-optimise this?

On the general question of how to optimise your original code, something worth considering is changing:

Code: Select all

  217 IFU%>20ANDX%>=L%ANDX%<=M%A%=FNC(I%) 

to this, by replacing the ANDs with IFs:

Code: Select all

  217 IFU%>20IFX%>=L%IFX%<=M%A%=FNC(I%) 

To optimise it further ensure that the first condition you test is the one most likely to fail, so the rest of the line can be abandoned as soon as possible.

[Adam James]

replacing the ANDs with IFs:
To optimise it further ensure that the first condition you test is the one most likely to fail, so the rest of the line can be abandoned as soon as possible.

Excellent!

My timings from my test set-up (ratios is all that matters):

Original: 1170
Goto: 1129
Two Gotos: 1126
Replace ANDs with IFs: 1132

So the GOTO approach is a hair faster, but results in horrible code and a duplicated line of code which has already caught me out when I forgot to update both of them.

Is it worth sticking with the GOTOs to reduce time taken to 99.47% of the IF approach?

Even in my current state of mind where I'm getting quite obsessive with shaving time, I think not. I bet I'll find more ANDs I can change to IFs to make up for it as well.

Great stuff, thank you:)

[julie_m]

I think labels could have been added to BBC BASIC, coexisting with line numbers, following the "dot" syntax from the built-in assembler more or less exactly. It would have required an additional variable type (representing an address in memory of the beginning of a line, whence to continue execution) and some overloading magic. (GOTO|GOSUB|RESTORE) would have to be able to take either an integer (specifying a line number) or a BASIC label for an argument. A label should have a manifestation if any other attempt be made to read its value, and the Principle of Least Astonishment suggests it should return the value of the line number defining the label; so

Code: Select all

100.wibble
110PRINT"wibble=";wibble
120K$=GET$
130IFK$="1"GOTOwibble
140END

should produce

Code: Select all

wibble=100
>_

simply because GOTOwibble is functionally equivalent to GOTO100 (although the actual address stored probably would belong to the next instruction after the label definition). PRINT wants to convert whatever wibble is to a string or a floating-point number; it can get a numeric value by backtracking from the supplied address to find its line number. (On a machine with a 16-bit address bus, the pre-existing 16-bit line number limit would make it possible to fit both manifestations into 4 bytes.) This behaviour is also consistent with the behaviour of the assembler, where label definitions are treated as BASIC variable assignments where the variable named in the label takes as its value the current address in memory, which will be the location of the next instruction processed by the assembler and can be used as a target for subsequent instructions.

As far as LOG goes, I think Acorn made exactly the right decision in line with the aforementioned Principle of Least Astonishment. In common British parlance, "log" by itself usually implies the base-10 log. It might well have been different in the USA, where scientific calculators with only the base-e natural log (which is the easiest to evaluate, by summing an ever-decreasing series of terms until you reach the limit of your available precision) were adopted more quickly; but in the UK, log tables remained in use into the 1990s, because teachers insisted calculators cannot be trusted -- if your calculator packs up in the middle of an exam, what are you going to do? You have to know how to do it yourself, in case your fancy machine ever lets you down. Whenever "log" was written without a base, it could be assumed to mean the base-10 log, and the base-e log was usually written as ln. Naming the functions LOG and LOG10 would have been awkward to tokenise and probably would have required brackets around the argument (is LOG1024 LOG 1024 or LOG10 24?)

[Adam James]

On the general question of how to optimise your original code, something worth considering is changing...

Gaaaaargh! I've just realised I've got in a pickle. I was running that test on BeebEm on my PC and it's the old version of the code, before I shifted the main loop to the start to speed up the GOTOs.

Testing it with the latest code, the 2xGOTO approach takes 1018 and the AND-IF approach takes 1038.

So the GOTOs take 98.07% of the time of the IF approach.

That's enough to sway me to stick with the horrible code. But at least I now know the AND-IF trick and have seen what an improvement it can make! Thanks:)

[fordp]

I would say line numbers are the real issue goto label is way better.

[Richard Russell]

I think labels could have been added to BBC BASIC, coexisting with line numbers, following the "dot" syntax from the built-in assembler more or less exactly.

I did consider adopting the 'dot' syntax, but instead I borrowed (approximately) the syntax used by Liberty BASIC which is to put the label in parentheses:

Code: Select all

      GOTO mylabel
      ...
(mylabel)

One reason was that it made syntax-colouring the labels more straightforward. This is implemented in BBC BASIC for Windows, BBC BASIC for SDL 2.0 and the new Console Mode editions.

It would have required an additional variable type

I was lazy, and labels share the same namespace as variables. Since a 'suffixless' numeric variable always has enough precision to contain an address (even in a 64-bit implementation) this means that undecorated labels can be used, but if you'd rather adopt a specific naming convention you can.

(GOTO|GOSUB|RESTORE) would have to be able to take either an integer (specifying a line number) or a BASIC label for an argument.

The "magic" in my case is trivial: a destination value less than 65536 is a line number, otherwise it's a label (memory addresses can never be less than that in my 32-bit and 64-bit BASICs).

the Principle of Least Astonishment suggests it should return the value of the line number defining the label

If you are using labels, it is highly unlikely that any lines will be numbered!

As far as LOG goes, I think Acorn made exactly the right decision in line with the aforementioned Principle of Least Astonishment.

The BBC's view (which I share) was that compatibility with Microsoft BASICs was more important, so LOG was a regrettable mistake. We knew we were vulnerable to being criticised for tying viewers to one specific machine, the BBC Micro, which would have been inexcusable (and 'politically' unacceptable).

[julie_m]

The BBC's view (which I share) was that compatibility with Microsoft BASICs was more important, so LOG was a regrettable mistake. We knew we were vulnerable to being criticised for tying viewers to one specific machine, the BBC Micro, which would have been inexcusable (and 'politically' unacceptable).

I think not maintaining the British definition of "log" probably would have been even more politically unacceptable! For how often the LOG function was ever used, and considering the proportion of such occasions when LOG(X) was not immediately divided by LOG(10) to get the base-10 log of X anyway, which of course would have worked perfectly since in BBC BASIC, LOG(10) = 1.

And why do compatible when you can do better?

[Richard Russell]

And why do compatible when you can do better?

I explained that. For the BBC to commission its own Micro to accompany the Computer Literacy Project was a real hot-potato, even then (it would never be allowed now). To get the agreement of the relevant Government and other bodies we had to demonstrate that we were not locking out owners of other brands of micro, nor giving Acorn an unfair advantage over other manufacturers.

So one major consideration was that the language (which became BBC BASIC), whilst it could of course have additional features, must not unnecessarily break compatibility with the BASICs commonly found on other home computers of the day. They almost invariably used a variant or derivative of Microsoft BASIC, in which the LOG function returns the natural (Napierian) logarithm.

So that's what LOG should have done in BBC BASIC. I have no recollection of this being discussed at the time; that's not to say it wasn't but short of ploughing through all my archived records I have no evidence for it. Either way we are where we are.

[Richard Russell]

following the "dot" syntax from the built-in assembler more or less exactly.

Slightly more on-topic, I've remembered one reason why I decided not to use that approach. You want to be able to quickly scan the program to find all the labels and store their addresses, in much the same way that the program is scanned for PROCs and FNs, and you don't want that scan to find assembler labels!

Therefore lines containing labels should start with a unique character that can be quickly searched for, just as PROC and FN definitions start with the token for DEF. With the approach I adopted that character was the left-parenthesis '(', which won't occur as the first character of a line in any other circumstance.

[Coeus]

On this suggestion from Richard:

Code: Select all

 217 IFU%>20IFX%>=L%IFX%<=M%A%=FNC(I%) 

I think it is worth understanding why it is faster. In C the AND and OR operators have two variants: the logical kind (&& and ||) and the bitwise version (& and |). The logical kind does "short circuit" evaluation, so for example if you write:

Code: Select all

if (u >= 20 && x > l) { ...

Then if x is smaller than 20 then x > l is never evaluated because the overall result of that expression is now known (false) BBC Basic (at least as implemented on the BBC Micro) does not have these logical operators, only the bitwise ones. So when you write:

Code: Select all

IFU%>20ANDX%>=L%

What happens if the interpreter evaluates U%>20, which produces an integer which either has all its bits sets, for true, or all its bits clear for zero. It then does the same for X%>=L%. Finally it does the bitwise AND between those two values and uses the integer result of that to decide whether to execute the statement controlled by the IF.

Re-working that to the way Richard has it makes it behave like the C example. This isn't just important for speed but for when functions have side-effects.

[Richard Russell]

The logical kind does "short circuit" evaluation

See: https://www.bbcbasic.co.uk/wiki/doku.ph ... evaluation