Numeric CASE vs IF THEN ELSE performance
Posted: Sat Jun 09, 2018 11:34 pm
This is a relaunch of a discussion started on the ETH Oberon mailing list...
Following feedback from Prof Wirth I have managed to improve the performance of the numeric CASE statement in RISC5 Oberon by implementing a variant of the Branch Conditional instruction in the RISC5 processor.
The standard branch via register instruction is
The new variant of this instruction is
i.e. the target of the branch is computed by adding the contents of register n to the current program counter.
Consequently, the average overhead of any selection in a CASE statement, including range checking, is now a constant 6 instructions. The average overhead of any selection in an IF THEN ELSE statement is (N + 1) * 2 instructions. Hence, in situations where there is an equal probability of each selection occurring CASE is faster than IF whenever there are more than 2 selections.
I have attached an example, Soundex.Mod, to illustrate the differences. The example includes an Astrobe compiler listing file which shows the actual code generated for each statement in a disassembler-style listing, and a screenshot of the output showing the actual results running on an Arty development board.
If you look at the disassembler listing you will see that another CASE benefit (particularly useful for embedded systems) is that it uses significantly less code space than IF THEN ELSE as long as the selections are not too sparse. The total code generated for each version of the Soundex procedures is:
Contact Astrobe support If you are interested in acquiring a copy of the Oberon source code of the modified Project Oberon compiler which adds these features.
Following feedback from Prof Wirth I have managed to improve the performance of the numeric CASE statement in RISC5 Oberon by implementing a variant of the Branch Conditional instruction in the RISC5 processor.
The standard branch via register instruction is
Code: Select all
BR,cond [Rn]Code: Select all
BR,cond PC,[Rn]i.e. the target of the branch is computed by adding the contents of register n to the current program counter.
Consequently, the average overhead of any selection in a CASE statement, including range checking, is now a constant 6 instructions. The average overhead of any selection in an IF THEN ELSE statement is (N + 1) * 2 instructions. Hence, in situations where there is an equal probability of each selection occurring CASE is faster than IF whenever there are more than 2 selections.
I have attached an example, Soundex.Mod, to illustrate the differences. The example includes an Astrobe compiler listing file which shows the actual code generated for each statement in a disassembler-style listing, and a screenshot of the output showing the actual results running on an Arty development board.
If you look at the disassembler listing you will see that another CASE benefit (particularly useful for embedded systems) is that it uses significantly less code space than IF THEN ELSE as long as the selections are not too sparse. The total code generated for each version of the Soundex procedures is:
Code: Select all
IF-THEN-ELSE: 420 Bytes
CASE: 240 Bytes