[Oberon] Numeric CASE vs IF THEN ELSE Performance

[Chris Burrows]

> -----Original Message-----
> From: Oberon [mailto:oberon-bounces at lists.inf.ethz.ch] On Behalf Of
> John R. Strohm
> Sent: Monday, 11 June 2018 2:48 AM
> To: ETH Oberon and related systems
> Subject: Re: [Oberon] Numeric CASE vs IF THEN ELSE Performance
> 
> Andreas Pirklbauer said:

> >Thx. That s a helpful hint. Unfortunately my compiler (so far) only
> >implements the "jump-table technique", so it does not fare well (in
> >terms of code-space requirements) in cases where the sparseness of
> >values in the case-label range is high.
> >
> 
> As I understand it, the assumption in Oberon is that the programmer
> is part of the optimization process, in that he/she is expected to
> understand that sparseness in the CASE selection range will lead to
> large jump tables, which means that a sparse selection should be
> implemented with an IF-THEN-ELSE chain or even tree.
> 

Yes - that is true. Section 16. Optimizations and the Frontend/Backend Structure in Wirth's Compiler Construction has a good discussion of the pros and cons of optimization. Quote:

"Furthermore, we must distinguish between optimizations whose effects could also be obtained by a more appropriate formulation of the source program, and those where this is impossible. The first kind of optimization mainly serves the untalented or sloppy programmer, but merely burdens all the other users through the increased size and decreased speed of the compiler."

A competent programmer should have a much better idea of the behaviour that he wants than a 'smart' compiler. This is particularly true when programming embedded systems. It is often more important to have predictable timing rather than fastest possible timing. A compiler that completely reorganises your code behind the scenes just because you have added or changed one or two statements is more often a curse than a saviour. 

Having said that Astrobe implementation of CASE does use a couple of pre-existing memory-saving optimisation techniques to help the programmer to avoid creating huge jump tables:

1. The minimum value allowed for a CASE label is 0 and the maximum value is 255, hence the absolute maximum size of the jump table is 1 KBytes. This value was chosen for its suitability for use with CHAR selectors. This might appear at first sight to be overly restrictive but in practice it has not been a problem.

I can only recall ever receiving one support question related to this and that was seven years ago. The example was:

CASE degs OF
   0:
  90:
 180:
 270:
END

I suggested that this could be recoded as: 

CASE degs DIV 90 OF
   0:
   1:
   2:
   3:
END
 
With the proviso that using DIV with a divisor that is not a power of two is inefficient and that this particular example would be smaller and execute faster using a chain of IF-ELSIF-ELSIFs...

2. If the minimum CASE label used in a particular CASE statement is greater than zero we offset all labels by that amount to avoid the unused entries at the beginning of the jump table. e.g. internally,

CASE ch OF
"a": ...
"b": ...
"c": ...

is treated as though the programmer had written:

CASE ORD(ch) - ORD("a") OF
0: ...
1: ...
2: ...  

This requires one additional instruction (4 bytes) for the CASE statement but, for this example, saves 388 bytes of unnecessary jump table locations.

Regards,
Chris Burrows
CFB Software
http://www.astrobe.com/RISC5