Newsgroups: comp.sys.apple2.programmer
Path: news.uiowa.edu!chi-news.cic.net!newsfeed.internetmci.com!in1.uu.net!eskimo!mattack
From: mattack@eskimo.com (Matt Ackeret)
Subject: Orca/C compilation of switch statements...
X-Nntp-Posting-Host: eskimo.com
Message-ID: <DHqnr5.51x@eskimo.com>
Sender: news@eskimo.com (News User Id)
Organization: Eskimo North (206) For-Ever
Date: Wed, 8 Nov 1995 19:06:40 GMT
Lines: 75


	I asked Mike Westerfield about how Orca/C compiled switch statements
and whether it was advantageous to manually sort the most-frequently-called
cases at the top.  (I'm doing a bit more work on my port of ZIP, the 
Infocom-style interpreter... someone else did some work to take out the
VM-ish paging which is mostly just a time-sink for the GS and I'm putting any
other first-pass speed improvements I can find in.)

	Here's my original question:
Does manual ordering of the 'case's in a switch statement help in terms of
code execution time in Orca/C?

Or does it use a jump table or some other method for constant-speed
execution no matter where in the switch statement you are located?

(If any of the above depends on optimization levels, that info would be
useful too).
-------

	Here's his reply:

First, feel free to post the answer I give to any question anywhere you like.

Actually, whether or not the ordering is important in a switch statement
depends on the specific switch statement.  ORCA/C uses two different methods
for generating switch statements, depending on whether the case labels are
dense or sparse.

For dense case labels with an integer switch value and all integer case
labels, ORCA/C creates a table of return addresses (jump tables don't work as
well on the 65816), and pushes a return address based on the switch value.
 In this case, the order you use in your source code won't matter at all.

For widely spread case labels, or when either the switch value or at least
one of the case labels is a long, the case labels are tested sequentially.
 This check is faster than a series of if-else statements, since the compiler
uses it's knowledge of the C language and the fact that it's compiling a
switch statement to avoid spurious loading of the switch statement's value.
 The order does make a difference, though.  If frequently used case labels
appear first, there will be a slight improvement in performance.

At one point I worked out the break-even point for the two methods, but I no
longer remember what it was.  It was not large; as best I recall it was 3-5
sequential tests take longer than the table lookup.  In general, then, the
table lookup is better from a speed standpoint.  The problem is that the
lookup tables are very, very large for common code like

   switch (i) {
      case 1: ...
      case 500: ...
      }

If you don't think code like this is common, take a look at a menu handling
subroutine sometime.  :)

ORCA/C uses this expression to decide if the case labels are sparse or dense:

   if (maxVal - minVal) div labelCount > sparse then
      <<<test the labels sequentially>>>
   else
      <<<use a table lookup>>>;

where

   maxVal -> largest case label value
   minVal -> smallest case label value
   labelCount -> number of case labels
   sparse -> the sparse trigger constant.  This can (and has) change with new
versions of the compiler.  In ORCA/C 2.0.3 the value is 5.

If I can be of further help, please let me know.

-- 
unknown@apple.com		Apple II Forever
These opinions are mine, not Apple's.