Basic V Performance

I have a real time server written in Basic V running on a Rasperry Pi and would like to check for performance issues as it uses a fair percentage of the available CPU time (around 50% according to !CPU Load).

Does BBC Basic V remember where procedures are – or does it have to search for them on every call? ie is there any advantage to putting common ones near the start of the file? (I don’t use GOSUBs)

What advantage would I get with CASE OF rather than 20, or so, IF statements?

Any particular structures to avoid, if used lots of times?

BASIC employs two techniques to speed up procedures.

The first time a procedure is called its DEFinition is searched for through the program and its location and details of its parameters are cached in a linked list. The next time it is called, its name is looked for in the list and it is executed directly from there. There is an advantage to calling commonly called procedures early to put them at the head of the list, but that is tricky to contrive.

When a procedure is called, the address of its cached details is stored in a location in the workspace allocated to the “Synergistic Cache Technology”. This has a unique location for program pointers based on the bottom 7 bits – 128 spaces. This data remains in place until it is replaced by routine or variable data at another program pointer with the same 7 bits. If the data is still valid [Edit: when the program returns to that point], the procedure is called immediately without having to be looked up in the list.

There may be an advantage in keeping loops tight to make a valid cache hit more probable, but beyond that I think it is a matter of statistics that makes this give programs a speed advantage.

CASE is slow, as is multiline IF, if the WHEN (or ELSE) clauses are extensive. BASIC has to jump from line to line to find the ENDCASE or ENDIF, which might be expensive. It does this efficiently, if there are no spaces at the start of lines or REMs or blank lines, but it still takes time. The first stategy is to put the WHEN clauses into procedures called on the same line as the WHEN. The second is to make sure the system variable <Basic$Crunch> is set, so that BASIC strips unwanted spaces and REMs for you.

If you really want speed, StrongBS does some optimisations that are really not useable as programming techniques. One is to replace CASE with multiple single line IFs, but I think that is going too far. ;-)

That is interesting. I wonder why Sophie, presumably, decided that the interpreter should do its scanning this way rather than with a single initial sweep?

When I ported Bob , David Betz’s little experimental OOP language, to RISC OS, variable lookup was implemented very naively. Later versions used hashing, which turned out to be much quicker on average. BASIC (used to?) use separate buckets according to the initial character of a variable. Has anybody experimented with other string comparison methods for BASIC’s interpreter? The hardware environment now is a far cry from that of the early days of Acorn.

My guess is that was to avoid using memory if a routine is never called. I expect the speed penalty is quite small. I think BB4W only does a scan of all the definitions when the first routine is called, which is why you cannot use a routine pointer until that happens – or has that changed? Basalt does scan all routines initially so that pointers can be used. [Edit: ¹]

The BASIC variable and routine name lookup has not changed and seperate buckets for initial letters are used. That is why a competent cruncher allocates short variable names with the first character changing first. Do not forget that SCT – many variables make a hit in the cache and do not have to be looked up at all.

I cannot see anyone making a big step to change this, though my recent suggestion to use “move to the front of list” might have some value.

¹ If you were using Basalt then ordering the routine definitions by frequency of use makes sense. ;-)

Another possible explanation for why BASIC only caches function pointers on first uses is that there’s some horrible thing which the interpreter needs to maintain compatibility with – e.g. self-modifying programs. Consider a copy protection method where a BASIC program decrypts a portion of itself on load.

Or maybe it’s just the fear of such a thing existing that lead to the safe route being taken.

Self-modifying programs – yes, I can see why that could be a reason for late resolution of names.

My guess is that was to avoid using memory if a routine is never called.

Exact. In 8bit world, problem was memory. So BBC Basic is made to use little RAM. And SCT to speed up things on later computers. Today we can resolve all references at loading (as Basalt).

Or maybe it’s just the fear of such a thing existing that lead to the safe route being taken.

Yep…

Excellent. Thank you all for the comments. I will look them all in more detail.

The second is to make sure the system variable <Basic$Crunch> is set

For those of us lunatics, what should it be set to… or is it’s mere presence the trigger?

:@)

is it’s mere presence the trigger?

Yes!

is it’s mere presence the trigger?

Yes!

So the common sense thing would be to add one little line to the !boot in the !HardDisc download so that everyone has the improvement?

How early on? and does the boot occur faster with the improvements in the boot components that are in BASIC?

Yes. I have advocated that for quite a while.

I doubt whether there would be any speed advantage in the boot process, so it could go in anywhere convenient. I have had an Obey file in Tasks, but Basalt does it anyway.

Would it be better for BASIC V to just do it, as BASIC VI does?

Would it be better for BASIC V to just do it, as BASIC VI does?

What makes you think BASIC VI auto-crunches?
As far as I can see, CHECKCRUNCH is defined here in ModHead and is hardwired to ‘1’, not dependent upon which version of BASIC is being built. Wouldn’t this imply that both versions of BASIC look for BASIC$Crunch?
I’ve looked at the binary of the Pi build of BASIC64 (VI) and the variable string is present, at the top, just prior to the BASIC identification message. That shouldn’t be there if BASIC64 does this as a matter of course…

Basic manual:

“Note that, in BASIC VI, programs with -quit set will be CRUNCH %1111, as will LIBRARY subprograms. BASIC V will also do this if the OS variable BASIC$Crunch exists. OVERLAY statements will not be CRUNCHed.”

That shouldn’t be there if BASIC64 does this as a matter of course…

How about this: I just did a quick check to see if it really does – AFAICT it does not.

When did that happen?

I assume that we are not talking about auto crunching the file. I like to be able to read my files.

Now back to the original question – and answers ….
…. I have reworked just one large multi-line IF THEN …. ENDIF (which often comes out false) and the performance difference is quite remarkable. I will continue to work on all of the suggestions (including the CASE statements!).

I assume that we are not talking about auto crunching the file.

Not at all. Just the program in memory.

the performance difference is quite remarkable.

It’s great when a plan comes together. ;-)

Can you repeat those tests on an emulator? Did BASIC64 ever auto crunch?

I have gone back to v1.05 (Arthur/RO2 I think) and that does, but v1.20 (RO3.1 I think) does not. I do not have anything in between. ;-)

So, the manual, written for the early version, is correct. It never occured to me to check that it could be incorrect for later versions. ;-(

Note that, in BASIC VI, programs with -quit set will be CRUNCH %1111

but …

How about this: I just did a quick check to see if it really does – AFAICT it does not.

BASIC VI does not auto CRUNCH here on the Pi, it doesn’t on OS4.39 either.

When did that happen?

A long time ago perhaps, the BASIC Guide is Issue 1, October 1992.

I did find a BASIC64 module from A3000 times, version 1.05 (12 Mar 1992), and that does not contain the variable BASIC$Crunch suggesting it might have worked as the BASIC Guide says.

the BASIC Guide is Issue 1, October 1992.

An earlier BASIC Guide, Issue 1, 1988, made out of paper, doesn’t mention CRUNCHing at all, not even as a keyword.

CVS has a few clues as to what’s happened to the crunching in BASIC VI. This file references the addition of BASIC$Crunch and the unconditional crunching in BASIC VI, but none of the other log files references when unconditional crunching was removed.

However looking through some of the deleted files, there’s this old BASIC VI build/header file which has the check for BASIC$Crunch enabled. A cursory comparison against the BASIC V version suggests that the only difference between the two is the setting of the FP option.

So as a guess, I’d say that the following happened:

• Originally there was only one ‘ModuleAB’ file, and switching between building BASIC / BASIC64 required changing the settings in the file manually. After all, BASIC64 in ROM looks to be a relatively recent thing (RISC OS 4/5, at least judging by Peter Howkins’ module DB – I can’t actually remember the first machine I saw with BASIC64 in ROM), so making sure builds of BASIC64 could be automated wouldn’t have been a high priority when the changes were first made.
• When the sources were moved to new source tree during RISC OS 3.5 development (or possibly later in the same year when the makefile was changed to allow BASIC64 to be built for the disc image), Aideen spotted that there was only one build file and figured it was about time that a build file for BASIC64 was added (although why the code wasn’t refactored so that the entire module header wasn’t duplicated in both files is anyone’s guess). He correctly changed the FP setting, but didn’t realise that CHECKCRUNCH also needed changing, and so the unconditional crunching has been accidentally disabled ever since then.

I think a little clarification of terminology might help. There are two BASIC books:

“BBC BASIC Guide, Issue 1, 1988” is for version 1.04 and, as you say, does not have CRUNCH, nor BASIC VI.

“BBC BASIC Reference Manual Issue 1, October 1992” is for version 1.05 and does have CRUNCH and BASIC VI.

Here are a couple of extracts from documents SW sent me back in the 90s:

(12) CRUNCH command

[…]

(a) Programs with -quit set will be CRUNCH %1111 and LIBRARY and INSTALL 

sub_programs will be CRUNCH %1111. CRUNCH %10 may make a program uneditable. 

OVERLAYs will not be CRUNCHed. 1

(b) BASIC V 1.04 cannot read assembler statements that have been crunched: 

such things as EORR4,R4,R5 give it terminal heart burn. 2

© The interpreter has been optimised for fully crunched programs.

[…]

05-Jun-91   Auto CRUNCH removed from BASIC V (not VI)

10-Jun-91   BASIC V AutoCRUNCHes if BASIC$Crunch is defined

¹ This implies that auto-crunch was originally available in both V and VI, but:
² Auto-crunch may have been removed from V v1.05 because of compatibility with v1.04, although I cannot quite work out why.

Not easily. I only have Virtual RPC and I need to reconfigure routers etc. Maybe in a day or two.

I think a little clarification of terminology might help. There are two BASIC books:

Thanks, that does help. Neither book overtly states what version it is for, the best there is is the history appendix in the later book where CRUNCH is introduced for 1.05.

P.S. Look a bit harder and the earlier book refers BASIC V version 1.03 (C) Acorn 1988 on page 205.