Is GOTO ever not evil?

[Adam James]

I've long suspected I might be the Antichrist, but last night came the strongest evidence yet.

I'm learning BBC BASIC while writing a game, and yesterday was all about speed-optimising the main loop. Thanks in no small part to some great insight from others in another thread, I thought I'd reached the point of diminishing returns.

But last night I finally addressed two lines of code that had been nagging me from the start:

Code: Select all

  217IFU%>20ANDX%>=L%ANDX%<=M%A%=FNC(I%)
  220IFU%>20ORABS(X%)>292U%=RND(2):S%?I%=U%:X%=RND(440)-220:C%?I%=RND(7)

I wondered how costly the repetition of 'IFU%>20' was. So in order to bypass as much code as possible if U% was 20 or less, I ended up with this:

Code: Select all

  214IFU%<21THENGOTO220
  217IFX%>=L%ANDX%<=M%A%=FNC(I%)
  218U%=RND(2):S%?I%=U%:X%=RND(440)-220:C%?I%=RND(7)
  220IFABS(X%)>292U%=RND(2):S%?I%=U%:X%=RND(440)-220:C%?I%=RND(7)

So that's a GOTO statement, and a repetition of 'U%=RND(2):S%?I%=U%:X%=RND(440)-220:C%?I%=RND(7)', both of which don't feel great.

But it gave me a time reduction of 3.5%, which I don't want to give up just for the sake of good practice. At this late stage in optimisation, that's a huge gain.

I've also just now realised that I can optimise it a bit further by adding 219GOTO240, since at that point, line 220 is redundant. I just made that change now, and while I was hoping for better gains, it is a tiny improvement.

So TWO GOTOs, and ONE repetition of code.

Is this justified, or is there a better way?

[Adam James]

I should add that I had earlier tried G%=U%>20, i.e. putting the result into another variable, and testing that variable instead in both of the IF statements. That was slower than the original.

[flaxcottage]

In BBC BASIC found on the 8 bit machines the use of GOTO is often mandatory and is frequently used to speed up processing. BASIC 2, for example, does not have multi-line IF ... THEN ... ELSE ..., WHILE ... ENDWHILE or CASE statements. To get round these 'deficiencies' one can use GOTO.

GOTO is regarded by some as a low-level programming construct but low-level languages are often faster than higher level languages. Personally I never worried about using GOTO except for jumping out of loops, procedures, etc. which will leave the stack corrupted.

However, I do prefer the use of functions and procedures to the use of GOSUB.

[roland]

Of course it is justified, it's a legal basic command

The IF statement in BBC (and also Atom) BASIC has the limitation that you cannot use a block of code just like other languages like C:

if (condition) {
.... block of statements
}

So if you want to optimize for speed then GOTO would be a good choice.

[Adam James]

In BBC BASIC found on the 8 bit machines the use of GOTO is often mandatory and is frequently used to speed up processing. BASIC 2, for example, does not have multi-line IF ... THEN ... ELSE ..., WHILE ... ENDWHILE or CASE statements. To get round these 'deficiencies' one can use GOTO.

That's good to hear and exactly how I felt. If I was using e.g. Javascript I could have used nested IFs and code blocks. So it did feel like I was working around a 'deficiency' in BASIC, but didn't want to say it as I feared there may be a better way.

[Adam James]

Of course it is justified, it's a legal basic command

The IF statement in BBC (and also Atom) BASIC has the limitation that you cannot use a block of code just like other languages like C:

if (condition) {
.... block of statements
}

So if you want to optimize for speed then GOTO would be a good choice.

I'm liking this feedback so far, thank you:)

I'm not liking how much of a mess the code now is, and the fact I already fell foul of changing one of the lines of code that is repeated but forgetting to change the other! But if that's how one rolls in BBC BASIC then it's good to be in company.

[BigEd]

I think it must be true that the larger your program is, the slower GOTO will be - so you had a better chance of a speedup because your program is small.

(I don't know if GOTO targets are searched for from the present line or from the start of the program.)

I think removing the THEN might be a little faster too.

[Adam James]

I think it must be true that the larger your program is, the slower GOTO will be - so you had a better chance of a speedup because your program is small.

(I don't know if GOTO targets are searched for from the present line or from the start of the program.)

I think removing the THEN might be a little faster too.

Interesting RE speed of GOTO vs program size and how the interpreter finds the line, I hadn't considered that!

Also good spot on the THEN statements. I'd tried to get out of the habit of using those. In my optimisation tests yesterday I noticed that removing them gave me a 0.0006% reduction in time, but more importantly, another program I'm writing is close to the memory limit, and is full of THEN statements because I didn't realise that they could be omitted until recently.

[1024MAK]

There is nothing wrong with GOTO. As with a lot of things that involve humans, there will always be people who bodge together code and hence use GOTO when there are better methods. Without multiline IF - ENDIF structures, often there is little alternative to using GOTO if a large chunk of code need to be skipped unless you can use a procedure.

Try to structure the code in a manner that minimises execution of jumps of all kinds, all jumps cost time.
At the same time, try to keep the main speed sensitive code at the start. Then put little used subroutines (as procedures) at the end.

Mark

[Adam James]

I think it must be true that the larger your program is, the slower GOTO will be - so you had a better chance of a speedup because your program is small.

(I don't know if GOTO targets are searched for from the present line or from the start of the program.)

At the same time, try to keep the main speed sensitive code at the start. Then put little used subroutines (as procedures) at the end.

I almost treated these comments as something to remember for the future.

But no, I've gone so far with optimising this game that I felt I should make the effort to reorganise it (what a pain with line numbers!) to see what benefits this might have.

My main loop is now right at the start of the program. It's shaved off nearly 1.5% of the time taken for an average cycle. Thank you!

From when I started the optimisation process, to now, the average time taken for a cycle has reduced to almost exactly two-thirds.

Which worryingly is about 66.666% so I go back to my original question

[julie_m]

There has been a lot of nonsense talked about GOTO by people who ought to know better.

GOTO is just a way of implementing an unconditional jump. Nothing more, nothing less. And every non-trivial program will have unconditional jumps in it. Especially in machine code. Of course GOTO can be abused, creating hard-to-follow code; but it's just as possible to write code without a single GOTO anywhere in it, that is still harder to follow than an equivalent program with one or more GOTO.

The fact that every high-level language compiler and interpreter necessarily contains unconditional jump instructions, and every high-level language compiler produces machine code that itself contains unconditional jump instructions, might just be the biggest irony since someone gave themself an endorphin rush while preaching a sermon on the evils of heroin .....

[1024MAK]

in terms of machines running at low level, the reset vector can be considered to be the first instruction that the 6502 executes and its effectively just an unconditional jump, in other words, a GOTO...

So no, GOTO is definitely not evil.

Mark

[BigEd]

There are writings, though, from the 70s, when people really were arguing against structured programming. These days we can surely agree that spaghetti code isn't ideal for most purposes, that a certain amount of subroutines and loops can help readability and maintainability without too much loss of density and performance, at the same time as agreeing that sometimes a jump is what's needed. (If we had block-structured IF THEN ELSE, if we had a WHILE CONDITION DO, and maybe a SWITCH CASE, we'd be even better off - but we do already have FOR, REPEAT, PROC and FN. We even have LOCAL!)

[Richard Russell]

I think it must be true that the larger your program is, the slower GOTO will be

Exactly - this is a key point, GOTO in BBC BASIC is potentially very slow. Because it's deprecated (there are always alternatives, whatever some people may say) it's not optimised: it works by searching the program line-by-line, linearly, from the beginning every time. There are no shortcuts like cacheing, or a binary chop, or searching forwards from the current point if the destination line is greater than the current line.

So if you attempt to measure the speed of GOTO using a typical short benchmark program it can seem quite fast, but once your program has grown to hundreds or thousands of lines a GOTO (or GOSUB) to a line towards the end of the program is going to be slow, and is best avoided.

[Richard Russell]

If we had block-structured IF THEN ELSE, if we had a WHILE CONDITION DO, and maybe a SWITCH CASE, we'd be even better off

True, but these things can be synthesised quite easily without having to call upon GOTO. For a block-structured IF..THEN..ELSE replace:

Code: Select all

      IF <condition> THEN
        <true block>
      ELSE
        <false block>
      ENDIF

with:

Code: Select all

      IF <condition> PROCtrueblock ELSE PROCfalseblock

For a WHILE..ENDWHILE replace:

Code: Select all

      WHILE <condition>
        <while block>
      ENDWHILE

with:

Code: Select all

      IF <condition> REPEAT PROCwhileblock : UNTIL NOT <condition>

For a CASE statement you can use a cascaded IF THEN (until you reach the line-length limit at least):

Code: Select all

      IF <condition1> PROCwhen1 ELSE IF <condition2> PROCwhen2 ELSE PROCotherwise

[Adam James]

Exactly - this is a key point, GOTO in BBC BASIC is potentially very slow. Because it's deprecated (there are always alternatives, whatever some people may say) it's not optimised: it works by searching the program line-by-line, linearly, from the beginning every time. There are no shortcuts like cacheing, or a binary chop, or searching forwards from the current point if the destination line is greater than the current line.

This now explains why my second GOTO, to skip a redundant line that started 'IFABS(X%)>292', had such a disappointing speed improvement - almost negligible.

I had hoped that 'ABS(X%)>292' was quite a task and eliminating it would get a significant improvement, but I was effectively replacing it with a search through all lines to get to line 240.

If my program had been larger with the main loop appearing even later, the attempt to skip a redundant calculation could actually have made it slower.

[Richard Russell]

it's just as possible to write code without a single GOTO anywhere in it, that is still harder to follow than an equivalent program with one or more GOTO.

Of course one could contrive to write a hard-to-follow program without GOTOs, but I would argue that it is much easier to write one with GOTOs! Personally I never use GOTOs in BBC BASIC (with the sole exception of programs that test that GOTO still works!), and that includes the 8-bit interpreters that were 'missing' some structures. I have yet to be persuaded, after nearly 40 years, that there is ever any good reason to use GOTO.

[Adam James]

I have yet to be persuaded, after nearly 40 years, that there is ever any good reason to use GOTO.

Not even for the speed optimisation in this case?

I'll go back to my original question: is it justified, or is there a better way? And add: even if it is justified and there is no better way, is it so awful that is should be avoided.

[roland]

Code: Select all

      IF <condition> PROCtrueblock ELSE PROCfalseblock

How does basic know where PROCtrueblock and PROCfalseblock start? Are those addresses or line numbers stored anywhere?

I wonder why Wilson did not implement the labels for GOTO and GOSUB, just like in Atom basic. The label adresses are registered in the workspace so whether the program is 10 lines or 32767 lines long, GOTO a is always fast once the address is known.

[BigEd]

Of course there's no absolute answer: it's a matter of taste. One person may never use GOTO, another may write spaghetti.

I think it's best used sparingly: when it seems an advantage to use it, and knowing how it might have been avoided. (Thanks, Richard, for the illustrations!)

[BigEd]

Code: Select all

      IF <condition> PROCtrueblock ELSE PROCfalseblock

How does basic know where PROCtrueblock and PROCfalseblock start? Are those addresses or line numbers stored anywhere?

Yes, once they've been found once, their locations are known. First use is slower than subsequent uses.

I wonder why Wilson did not implement the labels for GOTO and GOSUB, just like in Atom basic. The label adresses are registered in the workspace so whether the program is 10 lines or 32767 lines long, GOTO a is always fast once the address is known.

Interesting: in effect this optimisation was moved to the named routines (proc and fn)

[Adam James]

I think it's best used sparingly: when it seems an advantage to use it, and knowing how it might have been avoided.

That's exactly where I am at currently, based on this recent experience, but am open to persuasion.

[1024MAK]

If you move away from BBC BASIC, then with other (mostly older) versions, it rather harder to write programs that don’t use GOTO.
However if you use later versions such as OPL (Psion organiser programming language), SuperBASIC (Sinclair QL) or GFA BASIC (Atari ST etc.) then there is very little need for using GOTO. Indeed in one of these you can then loose the line numbers. Then GOTO becomes GOTO <label>.

Personally, and it will always come down to the choice of the individual, if I am writing code where speed is not the primary requirement, then I much prefer to construct my programs using blocks of code in procedures or subroutines. I put a very short main routine (often with a loop) at the beginning, then the rest of the code follows as procedures or subroutines. Sometimes the main loop only contains a loop and calls to procedures or subroutines.

If I’m writing a short and simple program, then I may not use any procedures or subroutines. Sometimes such programs will use a GOTO. But mainly I don’t use GOTO very often apart from one exception.

The exception is if I want to run a routine to test or experiment something, in which case the last line may be a GOTO 1 or GOTO 10 (in other words, loop back to the first line of the program or sometimes the second or third line).

Mark

[jgharston]

In BBC BASIC found on the 8 bit machines the use of GOTO is often mandatory and is frequently used to speed up processing. BASIC 2, for example, does not have multi-line IF ... THEN ... ELSE ..., WHILE ... ENDWHILE or CASE statements. To get round these 'deficiencies' one can use GOTO.

Not really, stick the code in a subroutine.
Instead of
IF NOT thing THEN GOTO blah
thing
thing
thing
thing
...

do:
IF thing THEN PROCfoo
...

DEFPROCfoo
thing
thing
thing
thing
ENDPROC

WHILE is a rewritten REPEAT/UNTIL

CASE is a multiple IF/ENDPROC
DEFPROCwibble
IF thing:PROCfoo:ENDPROC
IF blah:PROCping:ENDPROC
IF zoot:PROCbleigh:ENDPROC
cow
ENDPROC

[jgharston]

I see Richard's already posted exactly what I said.

[Richard Russell]

How does basic know where PROCtrueblock and PROCfalseblock start?

It uses the same mechanism that is used for variables (the procedure names and their associated memory addresses are stored in a linked-list in the heap). It's pretty fast, although (as has been discussed here before) the simple optimisation of moving the most-recently accessed node to the head of the list was somehow missed by Sophie. My 'modern' BASICs do that.

I wonder why Wilson did not implement the labels for GOTO and GOSUB, just like in Atom basic.

I don't remember it having been discussed back then. My assumption is that with the emphasis being placed on the structured features of the language (REPEAT..UNTIL loops, named functions and procedures etc.) GOTO and GOSUB were - rightly in my judgement - considered a low priority. Again, my modern BASICs have labels.

[leenew]

DEFPROCwibble
IF thing:PROCfoo:ENDPROC
IF blah:PROCping:ENDPROC
IF zoot:PROCbleigh:ENDPROC
cow
ENDPROC

This looks almost exactly like the code for my new adventure game...

Lee.

[Lardo Boffin]

I have yet to be persuaded, after nearly 40 years, that there is ever any good reason to use GOTO.

I had to write a data fix script in TSQL recently that fixed a hierarchical table of data that effectively had 4 levels of structure. Each level shared the same basic fix code.
The key with this script was that it could be run on a SQL server without affecting the schema in any way.
This meant I could not create sub routines / functions etc. for the shared fix code.

So I have two choices:

1) Write the fix code 4 times
2) Write it once and use GOTO to jump to it

The fix code was fairly large (several hundred lines) and complex. Having to apply any changes for improvements or bug-fixes 4 times is never good.

So I used a GOTO to jump to the shared fix code when required at each of the four levels. Needless to say I got it in the neck at work but nobody volunteered to improve it or maintain it.

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

[Richard Russell]

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.

[lurkio]

I wonder why Wilson did not implement the labels for GOTO and GOSUB, just like in Atom basic.

I don't remember it having been discussed back then.

Interesting...

BBC BASIC is a compromise between my advanced interpreter of the day and the BBC's desire to keep the language "standard". Most of the time the advanced features managed to get included unchanged, so overall I was happy (the only significant loss I can remember is over labels vs line numbers - the BBC committee insisted on line numbers).

http://www.retroisle.com/others/acornbb ... erview.php