Gosub...return or goto, which is "bigger"

[andrewpro]

In the thread entitled "toggle question", the replies by YLP and beaniebots got me thinking...

Which would use less program space? Setting gosubs to 16, then not using them, or using gosubs. Like this:

start:
Goto othersub

othersub:
goto start

OR........

Start:
Gosub othersub

othersub:
return

They basically both have the same amount of appearant code, and both require pointers to know where to go back to, and labels, and such. And I dont necessarily mean jsut those lines up there, but what if you jsut used goto's throughout an entire, decent sized program as compared to gosubs? Is there any appreciable difference in code size, and if so, why? I call on the guru's to set my mind straight!

--Andy P

 

[evanh]

The second GOTO should take a couple extra code bytes for it's "start" label whereas the RETURN's return point is already known and sitting in reserved stack space which is not part of the code size.


Evan

 

[hippy]

The PICAXE is different to most micro's in that it doesn't push a return address, but pushes the number of the GOSUB and then on RETURN pops the number and uses it as an index into a table of addresses which indicate the next code after the GOSUB.

Both pieces of code have two opcodes each ( GOTO/GOTO and GOSUB/RETURN ) plus two addresses of where to goto ( GOTO/GOTO and GOSUB/Return Address ), but the second also needs the number of the GOSUB which will be pushed ( 0 to 15 ) so the second is 4 bits longer.

Edited by - hippy on 1/19/2006 8:12:58 PM

 

[evanh]

Wow, that's just broken but it does explain the GOSUB limit which I could never understand before. When and where did you find that detail?


Evan

 

[andrewpro]

Beddy Beddy interesting. So, MY next querry...is that 4 bits per gosub, or 4 bits for any amount of gosubs up to 16 (or 256)?

If it's per gosub, you could save anywhere from 8 to 128 bytes of code space by not using gosubs, but is there any other overhead that would negate this effect?

Theres no doubting that for convenience and ease of coding, gosubs are great, but when it comes to crunch time, would reducing or eliminating them give the extra space used by those 4 bits per return? (I'm guessing ti's per return).

--andy P

 

[Fowkc]

I don't see them being equivalent, as they're not really alternatives that do the same job. GOSUBs are useful when there's a piece of code that is called often from multiple locations, so you need to return to different places. Hippy's LCD code is like that. A GOTO has no "memory" of where it needs to go back to, and you could only have multiple return addresses by using a variable or some other code to determine where to GOTO next.

 

[hippy]

evanh : <i>Wow, that's just broken but it does explain the GOSUB limit which I could never understand before. When and where did you find that detail? </i>

Not broken, just different, and there's a very good historical reason for it. In the 'days of old' PICMicro's didn't have much spare SFR (RAM) and there was no stack the user could push data to. By using a 4-bit number to identify every GOSUB return point, a four-deep stack can be implemented in just two bytes. Storing the return addresses to the same depth would have required six bytes, and that would have to be reserved for all potential programs. Using a Return Address Table uses space in program memory of which there is a lot more of rather than eating into the much more valuable RAM.

Discovering all this involved a lot of research and experimentation.

andypro : <i>is that 4 bits per gosub, or 4 bits for any amount of gosubs up to 16 (or 256)? </i>

Every GOSUB in a program has a 4-bit number associated with it, and when '256 GOSUB' mode is selected, each will have an associated 8-bit number. Return Address Table entries are only added as needed, no program memory is reserved for GOSUB use. Every GOSUB in a program uses 4 or 5 bytes of memory depending on device variant and mode; don't use a GOSUB and that memory is free for some other command.

 

[wilf_nv]

Hi Hippy,

This PICAXE BASIC GOSUB scheme boggles the mind (mine anyway).

As I understand it from your description, GOTO and GOSUB (256 version for simplicity) are different as follows:

GOTO
----
GOTO LABEL is stored in the basic program as 1 byte command + 2 byte address (LABEL=$nnnn)

Executing GOTO LABEL sets the program address counter to $nnnn which is the adddress of the next basic statement that will be executed.

GOSUB
-----

Each GOSUB LABEL statement is stored in basic as 1 byte command with a 1 byte argument to jump to 1 of 256 subprocedures.

The LABEL in this case is not an absolute program address but an index into a table of up to 256 addresses of subprocedures. For each subprocedure that is used in the basic program there is a 2 byte address in the this table.

This does not limit the number of GOSUB statements in a basic program, only the number of subprocedures!

When a GOSUB statement is executed in a basic program, the address of the following basic statement is stored a RETURN stack. The stack is a group of registers (RAM) that can store 4 RETURN addresses.

Each GOSUB procedure should end with a RETURN statement. When the RETURN statement is executed, the last address stored in the RETURN stack is loaded into the program address counter which is the address of the next BASIC statement to be executed.

To summarize my understanding of this

Any number of GOTO statements can be used in a basic program. The argument of a GOTO statement is a 2 byte address.

Any number of GOSUB statements can be used in a basic program. The argument of a GOSUB statement is a 1 byte pointer to a table of up to 256 subprocedure addresses. Therefore
the number of subprocedures that that can be used in a basic program is limited to 256.

GOTO memory overhead
--------------------
3 bytes per GOTO statement
3 bytes per GOTO procedure (returns via GOTO)

Each GOTO LABEL statement requires 3 bytes and makes a jump to LABEL which is the address of the next basic statement to be executed.

The same GOTO LABEL can be used many times in a basic program to jump to a &quot;procedure&quot; which itself ends in a GOTO statement to &quot;return&quot; to a common re-entry point in the basic program. So if a GOTO statement jumps to a GOTO procedure that procedure requires an additional 3 bytes to return to the main program.

GOSUB memory overhead
------------------
2 bytes per GOSUB statement
3 bytes per subprocedure

Each GOSUB LABEL statement requires 2 bytes.
Up to 256 different LABELS can be used for subprocedures. Each subprocedure requires a 2 byte entry in the GOSUB index table.

Each subprocedure must end in a 1 byte RETURN statement by which it returns to execute the basic statement following the GOSUB statement.

Have I got that right?

wilf

 

[hippy]

Almost, and I'll admit it's hard. You are right with the GOTO, it's an opcode followed by the address of where to go. For the GOSUB it's a 'GOTO' and an address, plus a number to say which it was. The limit is on the number of GOSUB's.

IF we didn't have GOSUB's they would have to be implemented using GOTO's as follows ...

- GOSUB Sub
- GOSUB Sub
- END
-
- Sub:
- Do Something
- RETURN

would be ...

- stack(sp) = 1 ' Number of GOSUB
- sp = sp+1
- GOTO Sub
- ReturnPoint1:
-
- stack(sp) = 2 ' Number of GOSUB
- sp = sp+1
- GOTO Sub
- ReturnPoint2:
-
- END
-
- Sub:
- Do Something
- GOTO HandleReturn
-
- HandleReturn:
- sp = sp-1
- BRANCH stack(sp),(ReturnPoint1,ReturnPoint2)

All of this complexity is handled by the Firmware which executes a tokenized program which looks something like ...<code><pre><font size=2>OPCODE GOSUB
NUMBER 1
ADDRESS Sub
ReturnPoint1: </font></pre></code> <code><pre><font size=2>OPCODE GOSUB
NUMBER 2
ADDRESS Sub
ReturnPoint2: </font></pre></code> <code><pre><font size=2>OPCODE END </font></pre></code> <code><pre><font size=2>Sub:
:
OPCODE RETURN </font></pre></code> <code><pre><font size=2>ReturnAddressTable:
ADDRESS ReturnPoint1
ADDRESS ReturnPoint2 </font></pre></code>

Edited by - hippy on 1/21/2006 6:42:52 PM

 

[wilf_nv]

Thanks Hippy,

I understand it now but why? The GOSUB method I suggested seems much more elegant than the way it was implemented.

wilf