BASIC and ELSE and GOTO and Work – part 1

My recent return to exploring my old Commodore VIC-20 code has reminded me about the main reason I jumped ship to a Radio Shack TRS-80 Color Computer: Extended Color BASIC. The older CBM BASIC V2 used by the VIC was missing keywords like ELSE, and had no functions for graphics or sounds. While I am having a blast re-learning how to program VIC-20 games, I sure do miss things like ELSE.

But should I?

IF/THEN/ELSE versus IF/THEN versus ON/GOTO

Pop quiz time! Suppose you were trying to determine if you needed to move a game character up, down, left or right. Which is the faster way to handle four choices?

30 IF Z=1 THEN 100 ELSE IF Z=2 THEN 200 ELSE IF Z=3 THEN 400 ELSE IF Z=4 THEN 500

…or…

30 IF Z=1 THEN 100
31 IF Z=2 THEN 200
32 IF Z=3 THEN 400
33 IF Z=4 THEN 500

Of course, if the values were only 1, 2, 3 and 4, you wouldn’t do either. Instead, you might just do:

ON Z GOTO 100,200,300,400

…but for the sake of this question, assume the values are not in any kind of order that allows you to do that.

IF/THEN/Work/ELSE versus IF/THEN/WORK

Suppose you were a junior high kid learning to program and you wanted to update some player X/Y positions based on keyboard input. Which one of these would be faster?

30 IF Z=1 THEN X=X+1 ELSE IF Z=2 THEN X=X-1 IF Z=3 THEN Y=Y+1 IF Z=4 THEN Y=Y-1

…versus…

30 IF Z=1 THEN X=X+1
31 IF Z=2 THEN X=X-1
32 IF Z=3 THEN Y=Y+1
33 IF Z=4 THEN Y=Y-1

All is not fair

I should point out that the speed it takes to run these snippets depends on the value of Z. For the sake of this article, let’s assume no key is pressed, so Z is set to something that is not 1, 2, 3 or 4.

Obviously, when there are four IFs in a row (either in a single line with ELSE, or on separate lines), the order of the checks determines how fast you get to each one. If Z is 1, and that is the first IF check, that happens faster than if Z is 4 and the code has to check against 1, 2 and 3 before finally checking against 4.

The same thing applies in languages that use switch/case type logic, so the things that need to be the fastest or happen most often should be at the top of the list and checked before things that happen less often.

Because of this, to be fair, we should also check best case (Z=1) and worst case (Z=4) and see what that does.

Benchmarking going to a line

In my benchmark program, this one counted to 954:

0 REM elsetst1.bas '954
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN 100 ELSE IF Z=2 THEN 200 ELSE IF Z=3 THEN 400 ELSE IF Z=4 THEN 500
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

And this one was a tiny bit faster. It counted to 942:

0 REM elsetst1.bas '942
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN 100
31 IF Z=2 THEN 200
32 IF Z=3 THEN 300
33 IF Z=4 THEN 400
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

Thus, using ELSE was a bit worse if none of the conditions were true.

IF we could have used ON/GOTO, that would be blazing at 253!

0 REM elsetst3.bas '253
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 ON Z GOTO 100,200,300,400
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

But I said we couldn’t, because I changed the rules to “do work” rather than “go to a line.”

Benchmarking doing work

Doing work with ELSE clocked in at 601:

0 REM elsetst4.bas '601
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN X=X+1 ELSE IF Z=2 THEN X=X-1 IF Z=3 THEN Y=Y+1 IF Z=4 THEN Y=Y-1
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

Since ELSE was slower to go to a line, I thought maybe it would be here, too, but instead, splitting the statements was slower. This one reports 963:

0 REM elsetst5.bas '963
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN X=X+1
31 IF Z=2 THEN X=X-1
32 IF Z=3 THEN Y=Y+1
33 IF Z=4 THEN Y=Y-1
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

It seems like ELSE has its place, but not for just going to a line.

Best versus Worst: FIGHT!

Let’s try some best and worst cases now. For this test, I’ll resolve the jumps to lines 100, 200, 300 and 400 by adding this:

100 GOTO 70
200 GOTO 70
300 GOTO 70
400 GOTO 70

That will greatly slow things down since we have to search forward to the new line, then it has to start back at the top of the program and search forward to find line 70. BUT, it will be consistent from test to test. I’ll add a “6 Z=1” or “6 Z=4” line.

  • elsetst1.bas (else): Z=1 produces 507. Z=4 produces 1058.
  • elsetst2.bas (separate): Z=1 produces 390. Z=4 produces 1053.
  • elsetst3.bas (on/goto): Z=1 produces 317. Z=4 produces 357.

Wow. ON/GOTO is really good at going places, best or worst case.

And what about the “doing work” stuff?

  • elsetst4.bas (else): Z=1 produces 632. Z=4 produces 633.
  • elsetst5.bas (separate): Z=1 produces 1171. Z=4 produces 1172.

In conclusion…

If you are using IF to go to some code, ON/GOTO is the fastest, following by separate lines. Even in the worst case, separate lines are still a tiny bit faster, which surprised me. I suspect it’s the time it takes to parse the ELSE versus a new line number. Retesting with all the spaces removed might change the results and make them closer.

But it does look like we need to stop doing “IF X=Y THEN ZZZ ELSE IF X=Y THEN ZZZ ELSE” unless we really need the extra bytes ELSE saves over a new line number.

And if you are trying to do work, ELSE seems substantially faster than separate line numbers. But, in both cases, best and worst case are very close. I believe this is a benchmark issue, since the time to scan a few lines is tiny compared to the time it takes to do something like “X=X+1”, and both best and worst case do the same amount of work. A better test would need to be performed.

Bonus

There is a way to speed up the separate line statements when doing work, especially for better case. Consider this:

0 REM elsetst6.bas '1034
5 DIM TE,TM,B,A,TT
10 FORA=0TO3:TIMER=0:TM=TIMER
20 FORB=0TO1000
30 IF Z=1 THEN X=X+1:GOTO 70
31 IF Z=2 THEN X=X-1:GOTO 70
32 IF Z=3 THEN Y=Y+1:GOTO 70
33 IF Z=4 THEN Y=Y-1
70 NEXT
80 TE=TIMER-TM:PRINTA,TE
90 TT=TT+TE:NEXT:PRINTTT/A:END

By adding the GOTO, if line 30 is satisfied (Z=1), the parser can start searching for line 70 without having to do the check against Z three more times. But, when a case is not satisfied, it now has to parse through the GOTO token and a line number to find the end of the line, meaning that for worst case (Z=4) it should be a bit slower.

Let’s see if this works.

  • elsetst6.bas (separate/goto): Z=1 produces 544. Z=4 produces 1241.

Compare that to the previous version without the end line GOTOs:

  • elsetst5.bas (separate): Z=1 produces 1171. Z=4 produces 1172.

It looks like there’s a significant improvement for best case, and a slight decrease in performance for worst case (the overhead of skipping more characters to find the end of the line for the false conditions).

The more you know…

I guess I am learning quite a bit by revisiting the VIC-20 and having to do things without ELSE.

What do you think? Did I miss anything?

Until next time…

3 thoughts on “BASIC and ELSE and GOTO and Work – part 1

  1. MiaM

    Another test you might try is to replace all GOTOs with an infinite for-next loop. Having the test at the end of the loop and end each IF THEN statement with NEXT (effectively jumping back to the start of the main loop) would both speed up the jump back itself but also remove the need for the other tests once the correct match has been found. In an action game you might want to arrange the if lines so that the execution time is as similar as possible for all different cases. Sure, there aren’t any difference in execution time between the add/subtract one to/from X or Y, but still.

    Reply
  2. Adam Coolich

    In a way, you’re using ON GOTO like the CASE statement in Pascal.

    For test#6, you wrote:
    30 IF Z=1 THEN X=X+1:GOTO 70
    31 IF Z=2 THEN X=X-1:GOTO 70
    32 IF Z=3 THEN Y=Y+1:GOTO 70
    33 IF Z=4 THEN Y=Y-1

    What if you tried ON GOSUB for the decision line to branch to work lines?

    30 ON Z GOSUB 100,101,102,103
    100 X=X+1:RETURN
    101 X=X-1:RETURN
    102 Y=Y+1:RETURN
    103 Y=Y-1:RETURN

    Time went down to 254!

    Full code:
    0 REM elsetst7.bas
    5 DIM TE,TM,B,A,TT
    10 FORA=0TO3:TIMER=0:TM=TIMER
    20 FORB=0TO1000
    30 ON Z GOSUB 100,101,102,103
    70 NEXT
    80 TE=TIMER-TM:PRINTA,TE
    90 TT=TT+TE:NEXT:PRINTTT/A:END
    100 X=X+1:RETURN
    101 X=X-1:RETURN
    102 Y=Y+1:RETURN
    103 Y=Y-1:RETURN

    Reply
    1. Allen Huffman Post author

      This must be saving time having to search back for a GOTO when done. Great idea. I’ll keep track of these comments and write up a follow up. Thanks!

      Reply

Leave a Reply to MiaMCancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.