What are the impacts of line numbering in BASIC/XB on execution speed?

[apersson850]

56 minutes ago, Badaboom said:

To code well in basic is to master zen.

 

It isn't the time that matters but the journey. ?

Precisely!

BASIC is there for simplicity in use, not for utmost execution speed. Keeping software logical and structured saves time in development and maintenance of the software.

To speed up BASIC it's better to be clever when selecting algorithms, rather than trying to store the lines in a specific order, use alienated variable names (like A, B and C instead of COUNTER, INDEX and SUM), or mess up subroutines with multiple cryptical entries and exits.

 

Refactor your code instead, if you have messed it up. Logic and structure frequently also renders faster execution, as you tend to do less unnecessary things, if your code is in good order.

 

SUB is a very good addition to Extended BASIC. One of its more valuable assets. The local variables are especially valuable if you do, as was suggested above, a library of functions, which you can merge with your program. Regardless of which line numbers the SUB ends up occupying, and regardless of which variable names you have used in the SUB and your main program, it still works the same. That's not at all the same if you use the GOSUB statement, in which case the namespace for your variables are the same as for the main program. You also must keep track of where it is, when you write your code, as it's called by line number reference.

 

Before I made it possible to use Pascal on my TI, I mainly used Extended BASIC. I used the SUB facilities extensively. If it cost some seconds in execution, it paid that back in quicker development.

[+OLD CS1]

I dig it.  The test protocol was done against the least important part of the program but the most observable.  The attract mode and marquee make use of the same subroutines as the game loop, so the observation can be correlated with game play.  Specifically, the responsiveness of the input routines.  I have developed an input routine which accepts input from both keyboard and joystick over the years to be as fast as I can get it.  That means not just its exit but also its entry.  Combined with bumming the code, placing the routine strategically in the program becomes important.

 

Thus, while we can observe the disparity in timing between two different instances just running the attract, it may not be observable in game play visually, notwithstanding slow TI BASIC "display-at" routines, but is still perceptible when interacting.

 

Of course, I still put the user input routine way up in the subroutine list (like the fifth subroutine, beyond routines which are used for game setup then lay dormant during game play... ugh.)

[apersson850]

If there was a need for speed, I usually augmented Extended BASIC with assembly. Or for things that couldn't be done in Extended BASIC.

[+OLD CS1]

3 hours ago, apersson850 said:

If there was a need for speed, I usually augmented Extended BASIC with assembly. Or for things that couldn't be done in Extended BASIC.

That is a luxury

[apersson850]

With Extended BASIC you got a comprehensive BASIC implementation together with the ability to use assembly support in the 8 K RAM section. That allowed pretty complex applications.

 

I wrote an assembly system to store and retrieve strings in the 8 K RAM. You could also store them in, or read them from, a file.

That was used in a simple wordprocessor, otherwise written in BASIC.

[+OLD CS1]

Right, but restricting one's self to just a console, a cassette deck, and XB, or any configuration without an E/A or MiniMemory, one is generally not writing assembly without a special tool or trick.  In any case, such a discussion it outside the scope of this topic, which is to deal with line numbering and subroutines within the confines of BASIC/XB.

[apersson850]

Yes, if you don't have expansion memory, then that's not a viable option. The minimum configuration were I was involved in a meaningful Extended BASIC program with assembly support was for a console with tape recorder, Extended BASIC module and 32 K memory expansion only. We used CALL LOAD statements to get a minimum loader in there, then that loaded the assembly program.

[+OLD CS1]

On 8/2/2020 at 8:56 PM, Badaboom said:

To code well in basic is to master zen.

[RXB]

I can post the Assembly and GPL for XB to find and execute XB Line numbers so if you want help fix this it would be welcome?

 

RXB ROMs.zip

[+OLD CS1]

33 minutes ago, RXB said:

I can post the Assembly and GPL for XB to find and execute XB Line numbers so if you want help fix this it would be welcome?

 

RXB ROMs.zip 1.15 MB · 1 download

This is a thought, but I honestly do not see a problem with how it currently functions.  The results of the experiments show that sub-routines with low line numbers out-perform sub-routines with high line numbers (relative to the GOSUB.)  Just knowing that will make the difference.  I think, and those who know more can smack me down, that the only way to improve would be to change how BASIC/XB searches for lines.  It seems right now the table is searched from one end to the other.  Maybe a binary search would increase performance, but by how much?

[RXB]

Page 83 and 84 lay out XB line number table and actually it is searched from highest address to lowest address so auto increment is not able to be used.

 

 

Explorer_-_by_Millers_Graphics_-_Manual_(ENG).pdf

[+retroclouds]

For details on the line number table you for example also might want to check the Extended Basic design document (page 20 onwards).

 

 

 

[Retrospect]

I've always wanted to know , when making my games, where exactly to put the graphical definitions .... and what speed impact would it have if I ;

1 .... put them at the top of the program list  (if I'm only using one set of definitions)
2 ... put them at the bottom of the program list as a subroutine (usually do this when there's two sets of definitions)

I mean, I compile 95 percent of the time but I still don't know if there would be any "lag" in player movements due to how I've structured my code.

[+OLD CS1]

7 minutes ago, Retrospect said:

I mean, I compile 95 percent of the time but I still don't know if there would be any "lag" in player movements due to how I've structured my code.

Having no empirical data, I am pretty certain the compiler obviates that kind of optimization.

[Retrospect]

2 minutes ago, OLD CS1 said:

Having no empirical data, I am pretty certain the compiler obviates that kind of optimization.

Right.  There'd probably be an impact if it was straight XB or Basic then?

[+OLD CS1]

1 minute ago, Retrospect said:

Right.  There'd probably be an impact if it was straight XB or Basic then?

Yuppers.  Provably, as done above.

[senior_falcon]

15 hours ago, OLD CS1 said:

This is a thought, but I honestly do not see a problem with how it currently functions.  The results of the experiments show that sub-routines with low line numbers out-perform sub-routines with high line numbers (relative to the GOSUB.)  Just knowing that will make the difference.  I think, and those who know more can smack me down, that the only way to improve would be to change how BASIC/XB searches for lines.  It seems right now the table is searched from one end to the other.  Maybe a binary search would increase performance, but by how much?

If the program was resequenced (RES 1,1) then XB could determine that GOTO 100 would mean going to the 100th line. Since each entry in the line number table requires 4 bytes you can quickly determine that the entry in the line number table for line 100 is 400 bytes in from the start of the table. This would lead to some speed increase in a long program, but you'd give up a lot of versatility, and I suspect it would not be a major speed increase.

 

7 hours ago, OLD CS1 said:

Having no empirical data, I am pretty certain the compiler obviates that kind of optimization.

That is correct. Position in the line number table makes no difference in compiled code.

[RXB]

If you did not know this a XB program and for that matter TI Basic do not keep the program lines in SEQUENCE.

Want some proof type in a XB or TI Basic program and how it resides in memory is as you typed it in not by line number.

See as LINE NUMBER and ADDRESS of line are in memory each line points to the next line typed in even if out of sequence.

And the program starts from highest memory address to lowest in memory all in the order you typed it.

 

So with this in mind you can control the speed of execution by the way you type in the XB or TI Basic program

and not use RESEQUENCE as that would defeat your original goal to speed up execution of program.

 

Of course all this is pointless if you use a compiler.

[senior_falcon]

1 hour ago, RXB said:

If you did not know this a XB program and for that matter TI Basic do not keep the program lines in SEQUENCE.

Want some proof type in a XB or TI Basic program and how it resides in memory is as you typed it in not by line number.

See as LINE NUMBER and ADDRESS of line are in memory each line points to the next line typed in even if out of sequence.

And the program starts from highest memory address to lowest in memory all in the order you typed it.

 

So with this in mind you can control the speed of execution by the way you type in the XB or TI Basic program

and not use RESEQUENCE as that would defeat your original goal to speed up execution of program.

 

Of course all this is pointless if you use a compiler.

One thing that is always true is that the line number table is in sequential order. Each entry in the line number table contains 4 bytes: 2 bytes are the line number, and 2 point to the address of the code. The address of the code makes no difference in program execution speed. It can be in low memory, high memory, or cartridge memory. (naturally XB prefers to put the code in high memory, but you can put it elsewhere and change the pointers.) No matter where the code is, it takes XB the same amount of time to get to it. So the order you enter the code makes no difference, nor does it make any difference if you resequence.

[RXB]

1 hour ago, senior_falcon said:

One thing that is always true is that the line number table is in sequential order. Each entry in the line number table contains 4 bytes: 2 bytes are the line number, and 2 point to the address of the code. The address of the code makes no difference in program execution speed. It can be in low memory, high memory, or cartridge memory. (naturally XB prefers to put the code in high memory, but you can put it elsewhere and change the pointers.) No matter where the code is, it takes XB the same amount of time to get to it. So the order you enter the code makes no difference, nor does it make any difference if you resequence.

Does this mean PRESCANT or other methods do not speed up an XB program thus are a waste of time to use?

 

When you have a GOTO or a GOSUB or IF THEN  or IF THEN ELSE or ON GOTO or ON GOSUB or ON ERROR or ON BREAK or ON WARNING or SUB

how do you think it finds that line in the program? 

After all not all lines are exactly the same exact length are they so there is no index to tell it, it does a search for that line number and address.

If the line number is closer it takes less time to find that line number thus the address to execute it.

 

You can find this is in the GPL and ROM source code I provided to prove this.

[senior_falcon]

16 minutes ago, RXB said:

Does this mean PRESCANT or other methods do not speed up an XB program thus are a waste of time to use?

This is a totally different subject and has nothing to do with this discussion.

 

When you have a GOTO or a GOSUB or IF THEN  or IF THEN ELSE or ON GOTO or ON GOSUB or ON ERROR or ON BREAK or ON WARNING or SUB how do you think it finds that line in the program? 

It goes through the line number table to find where the code for that line is.

After all not all lines are exactly the same exact length are they so there is no index to tell it, (there IS an index, it is called the line number table) it does a search for that line number and address.

If the line number is closer it takes less time to find that line number thus the address to execute it. It is true that the line number will be found quicker if it is near the beginning of the table. However, this is NOT what you said above, which was:

"So with this in mind you can control the speed of execution by the way you type in the XB or TI Basic program

and not use RESEQUENCE as that would defeat your original goal to speed up execution of program."

To reiterate: It does not make any difference which order you type in the lines. If the program is the same then the line number table will be exactly in the same place and in the same order, and the program will execute at the same speed. (The pointers in the line number table will be different because the actual XB code is in different locations, but that does not effect the speed) Bottom line is that it makes absolutely no difference what order you enter the lines. For the life of me I cannot understand why you think resequence would make any difference.

 

 

[+OLD CS1]

BASIC does a lot of work in the background.  Knowing what I now know, I understand why entering long programs BITD would eventually get so sluggish.  In addition to being sorted, the entire line number table is moved down in memory as new lines are entered.  The tokenized program store is not sorted, but it is moved around as lines are deleted and added.  Crazy amount of shuffling around happens when entering and editing a program.

[senior_falcon]

There sure is. You can see this easily when pasting a long program into Classic99. It starts out pretty fast, but as the program grows the lines take longer and longer to enter.

 

[RXB]

2 hours ago, senior_falcon said:

 

Maybe due to XB has to search for that line it does not know EXACTLY WHERE IT IS as it has to find the pointer that is the line number in this case.

There a few line number searches in XB this is one of them in the ROM1:

1257            * NUD routine for "GOTO"  
  1258 675C 04C3  GOTO   CLR  R3                Dummy index for "ON" code   
  1259            * Common (ON) GOTO/GOSUB THEN/ELSE code to fine line  
  1260            *   
  1261            * Get line number from program  
  1262 675E 0288  GOTO20 CI   R8,LNZ*256        Must have line number token   
       6760 C900  
  1263 6762 16EA         JNE  ERR1B             Don't, so error   
  1264 6764 06A0  GETL10 BL   @PGMCHR           Get MSB of the line number  
       6766 6C74  
  1265 6768 D008         MOVB R8,R0             Save it   
  1266 676A 06A0         BL   @PGMCHR           Read the character  
       676C 6C74  
  1267 676E 0603         DEC  R3                Decrement the "ON" index  
  1268 6770 1534         JGT  GOTO40            Loop if not there yet   
  1269            *   
  1270            * Find the program line   
  1271            *   
  1272 6772 C060         MOV  @STLN,R1          Get into line # table   
       6774 8330  
  1273 6776 D0A0         MOVB @RAMFLG,R2        Check ERAM flag to see where? 
       6778 8389  

 99/4 ASSEMBLER
PARSES                                                       PAGE 0028
  1274 677A 1310         JEQ  GOTO31            From VDP, go handle it  
  1275 677C C081         MOV  R1,R2             Copy address  
  1276 677E 8801  GOT32  C    R1,@ENLN          Finished w/line # table?  
       6780 8332  
  1277 6782 1422         JHE  GOTO34            Yes, so line doesn't exist  
  1278 6784 D0F2         MOVB *R2+,R3           2nd byte match?   
  1279 6786 0243         ANDI R3,>7FFF          Reset possible breakpoint   
       6788 7FFF  
  1280 678A 9003         CB   R3,R0             Compare 1st byte of #, Match? 
  1281 678C 1605         JNE  GOT35             Not a match, so move on   
  1282 678E 9232         CB   *R2+,R8           2nd byte match?   
  1283 6790 131E         JEQ  GOTO36            Yes, line is found!   
  1284 6792 05C2  GOT33  INCT R2                Skip line pointer   
  1285 6794 C042         MOV  R2,R1             Advance to next line in table 
  1286 6796 10F3         JMP  GOT32             Go back for more  
  1287 6798 D0F2  GOT35  MOVB *R2+,R3           Skip 2nd byte of line #   
  1288 679A 10FB         JMP  GOT33             And jump back in  
  1289 679C D7E0  GOTO31 MOVB @R1LB,*R15        Get the data from the VDP   
       679E 83E3  
  1290 67A0 0202         LI   R2,XVDPRD         Load up to read data  
       67A2 8800  
  1291 67A4 D7C1         MOVB R1,*R15           Write out MSB of address  
  1292 67A6 8801  GOTO32 C    R1,@ENLN          Finished w/line # table   
       67A8 8332  
  1293 67AA 140E         JHE  GOTO34            Yes, so line doesn't exist  
  1294 67AC D0D2         MOVB *R2,R3            Save in temporary place for   
  1295            *                              breakpoint checking  
  1296 67AE 0243         ANDI R3,>7FFF          Reset possible breakpoint   
       67B0 7FFF  
  1297 67B2 9003         CB   R3,R0             Compare 1st byte of #, Match? 
  1298 67B4 1607         JNE  GOTO35            Not a match, so move on   
  1299 67B6 9212         CB   *R2,R8            2nd byte match?   
  1300 67B8 130A         JEQ  GOTO36            Yes, line is found!   
  1301 67BA D0D2  GOTO33 MOVB *R2,R3            Skip 1st byte of line pointer 
  1302 67BC 0221         AI   R1,4              Advance to next line in table 
       67BE 0004  
  1303 67C0 D0D2         MOVB *R2,R3            Skip 1nd byte of line pointer 
  1304 67C2 10F1         JMP  GOTO32            Go back for more  
  1305 67C4 D0D2  GOTO35 MOVB *R2,R3            Skip 2nd byte of line #   
  1306 67C6 10F9         JMP  GOTO33            And jump back in  
  1307 67C8 0200  GOTO34 LI   R0,ERRLNF         LINE NOT FOUND error vector   
       67CA 0303  
  1308 67CC 10A0         JMP  GOTO95            Jump for error exit   
  1309 67CE 05C1  GOTO36 INCT R1                Adjust to line pointer  
  1310 67D0 C801         MOV  R1,@EXTRAM        Save for execution of the line
       67D2 832E  
  1311 67D4 0649         DECT R9                Pop saved link to goto  
  1312 67D6 0460         B    @EXEC10           Reenter EXEC code directly  
       67D8 650E  
  1313 67DA 06A0  GOTO40 BL   @PGMCHR           Get next token  
       67DC 6C74  
  1314 67DE 06A0         BL   @EOSTMT           Premature end of statement?   
       67E0 6862  
  1315 67E2 1393         JEQ  GOTO90            Yes =>BAD VALUE for index   
  1316 67E4 0288         CI   R8,COMMAZ*256     Comma next ?  
       67E6 B300  
  1317 67E8 1603         JNE  ERR1C             No, error   
  1318 67EA 06A0  GOTO50 BL   @PGMCHR           Yes, get next character   
       67EC 6C74  

 99/4 ASSEMBLER
PARSES                                                       PAGE 0029
  1319 67EE 10B7         JMP  GOTO20            And check this index value  
  1320 67F0 10A3  ERR1C  JMP  ERR1B             Linking becuase long-distance 
  1321 67F2 0200  ERR51  LI   R0,>0903          RETURN WITHOUT GOSUB  
       67F4 0903  
  1322 67F6 108B         JMP  GOTO95            Exit to GPL   

[RXB]

This is just the GOTO and ON ERROR search, the GOSUB is below this one and there are others, they do use some of the same routines.

But there are way more then one LINE NUMBER SEARCH ROUTINE.

You are correct this is a mess as they go from highest address to lowest address for programs, I have no clue why as it looks insane.

Anyone with a brain cell would start from lowest address and go higher address as that would allow for *Register+ auto increments.

Instead they have to go backwards DOWN in memory all the time making sure it slows the XB reading down on purpose.

You could not be more ass backwards to slow XB or TI Basic down.