[OT] Switch question

[Sean Kenwrick]

I have a large switch statement (~50 cases ) inside a critical inner loop of
a byte code interpreter I am working on, and I am wondering if I should take
any steps to optimise this loop.

Are switch statements usually compiled as if...else if..else if...else type
statements? Are there other ways that the compiler could implement switch
statements that are more efficient?

With regards to my code, would it be better to put the most common cases
near the top of the switch statement or should I consider making a lookup
table of function pointers instead (but the function call overhead might
kill it) - this is the first time that I wish I could put labels into arrays
and do 'goto label[x]' )

I've tried posting to comp.compilers but nothing has appeared in this group
for iver a week and it seems to be dead ....

Any advice, hints etc would be appreciated...

Sean

 

[Sean Kenwrick]

I have a large switch statement (~50 cases ) inside a critical inner loop of
a byte code interpreter I am working on, and I am wondering if I should take
any steps to optimise this loop.

Are switch statements usually compiled as if...else if..else if...else type
statements? Are there other ways that the compiler could implement switch
statements that are more efficient?

With regards to my code, would it be better to put the most common cases
near the top of the switch statement or should I consider making a lookup
table of function pointers instead (but the function call overhead might
kill it) - this is the first time that I wish I could put labels into arrays
and do 'goto label[x]' )

I've tried posting to comp.compilers but nothing has appeared in this group
for iver a week and it seems to be dead ....

Any advice, hints etc would be appreciated...

Sean

I decided to roll up my sleeves and look at the disassemby for this part of
the code and I thought I would share the result with the group. It
seems that the compiler (Borland C++Builder) is pretty intelligent and
noticed that all my case statements were literal constants of a fairly low
value, so it simply made a lookup table and did the equivalent of 'goto
label[x]' for each case - so this is already the optimal solution! I
would guess that if I had variables in my case statements or if the case
statements had high values (e.g. case 99999999 then it would have to
revert to if..else if...else (or perhaps a hybrid of the two solution...)

Sean

 

[Darrell Grainger]

I have a large switch statement (~50 cases ) inside a critical inner loop of
a byte code interpreter I am working on, and I am wondering if I should take
any steps to optimise this loop.

Are switch statements usually compiled as if...else if..else if...else type
statements? Are there other ways that the compiler could implement switch
statements that are more efficient?

How something is implemented in machine code is not defined by the C
standard. Each compiler can do it differently. A good C compiler will take
into consideration the architecture of the processor.

Take for instance, I have worked on a processor that does parallel
operations. It was designed so I could call a function (do a push return
address and then branch) and while the function call is being decoded by
the processor I could initialize the input parameters for the function. By
the time the function call was decoding and running the input parameters
would be initialized. If a switch statement used branching (a parallel
operation) and certain instructions with every case statement the compiler
will optimize accordingly. This same optimization would be sure death on
many other processors.

Are there other ways to implement switch statements. Absolutely. Are they
more efficient? Depends on the architecture of the processor again. Could
even depend on the operating system.

With regards to my code, would it be better to put the most common cases
near the top of the switch statement or should I consider making a lookup
table of function pointers instead (but the function call overhead might
kill it) - this is the first time that I wish I could put labels into arrays
and do 'goto label[x]' )

Again, depends on the processor. If all cases are going to result in a
branch and a branch requires the flushing of the pipe, it will not make a
difference. On the other hand, some processors have a branch and a short
branch. The short branch incurs less processor time. If you could optimize
it to use short branches when possible and put the most common cases
within the short branch range you might see some improvement.

Bottom line, if you are trying to squeak out maximum efficiency you are
probably going to have to trust the compiler or get a better understanding
of the processor's architecture.

 

[Mike Wahler]

I have a large switch statement (~50 cases ) inside a critical inner

loop

of
a byte code interpreter I am working on, and I am wondering if I should take
any steps to optimise this loop.

Are switch statements usually compiled as if...else if..else if...else type
statements? Are there other ways that the compiler could implement switch
statements that are more efficient?

With regards to my code, would it be better to put the most common cases
near the top of the switch statement or should I consider making a lookup
table of function pointers instead (but the function call overhead might
kill it) - this is the first time that I wish I could put labels into arrays
and do 'goto label[x]' )

I've tried posting to comp.compilers but nothing has appeared in this group
for iver a week and it seems to be dead ....

Any advice, hints etc would be appreciated...

Sean

I decided to roll up my sleeves and look at the disassemby for this part of
the code and I thought I would share the result with the group. It
seems that the compiler (Borland C++Builder) is pretty intelligent and
noticed that all my case statements were literal constants of a fairly low
value, so it simply made a lookup table and did the equivalent of 'goto
label[x]' for each case - so this is already the optimal solution!

Yes, modern compilers are getting pretty smart.

I
would guess that if I had variables in my case statements

Not allowed by the language. The 'case' expressions must be constant
expressions.

or if the case
statements had high values (e.g. case 99999999 then it would have to
revert to if..else if...else (or perhaps a hybrid of the two solution...)

Well, try it and see.

-Mike

 

[August Derleth]

I have a large switch statement (~50 cases ) inside a critical inner loop of
a byte code interpreter I am working on, and I am wondering if I should take
any steps to optimise this loop.

Are switch statements usually compiled as if...else if..else if...else type
statements?

No. Not by any compiler for a machine that handles either `branch to
address held at this memory location' or `branch to address held in this
register', both of which are methods of implementing a jump table.

Let me explain:

On the Intel x86-series chips, the jump opcodes (both conditional and
unconditional) can accept registers as destinations, in which case the
contents of the register is used as the destination. So the gcc compiler
(the one I use myself, but I'm sure most other x86 compilers do the
same) loads the eax register with the location of the beginning of the
jump table, then adds in the value passed to the switch statement to
derive a destination. It jumps to that location now in the eax register,
and so the switch statement is executed.

This is much more efficient than a series of if-else statements, but it
depends on what the machine will let you do with the jump opcodes. (And,
to a smaller extent, on how intelligent the compiler is. But I have a
hard time imagining a C compiler so stupid as to /not/ do a jump table
on a machine which allows it to.)

this is the first time that I wish I could put labels into arrays
and do 'goto label[x]' )

Heh... this is what the compiler is doing anyway. This is /exactly/ what
it's doing.

I've tried posting to comp.compilers but nothing has appeared in this group
for iver a week and it seems to be dead ....

Any advice, hints etc would be appreciated...

My advice would be to time the code and only refactor what needs
refactoring. A profiling tool will tell you where the machine actually
spends its time. Maybe you will decide the compiler is already doing a
good enough job (try passing in some options to turn up the optimization
level), maybe you can get away with a slightly different algorithm. Only
rewrite in assembly if there's no other option. (Not because assembly is
evil and nasty ... it sometimes /is/, but not always ... but because the
next person to look at the code (you, maybe?) will probably understand C
a lot better than a given assembly language.)

 

[Keith Thompson]

I've tried posting to comp.compilers but nothing has appeared in this group
for iver a week and it seems to be dead ....

<ot>comp.compilers is moderated; articles appear when the moderator
gets around to processing them.</ot>

 

[Sean Kenwrick]

I have a large switch statement (~50 cases ) inside a critical inner

loop

of
a byte code interpreter I am working on, and I am wondering if I

should
take

any steps to optimise this loop.

Are switch statements usually compiled as if...else if..else if...else type
statements? Are there other ways that the compiler could implement switch
statements that are more efficient?

With regards to my code, would it be better to put the most common cases
near the top of the switch statement or should I consider making a lookup
table of function pointers instead (but the function call overhead might
kill it) - this is the first time that I wish I could put labels into arrays
and do 'goto label[x]' )

I've tried posting to comp.compilers but nothing has appeared in this group
for iver a week and it seems to be dead ....

Any advice, hints etc would be appreciated...

Sean

I decided to roll up my sleeves and look at the disassemby for this part of
the code and I thought I would share the result with the group. It
seems that the compiler (Borland C++Builder) is pretty intelligent and
noticed that all my case statements were literal constants of a fairly low
value, so it simply made a lookup table and did the equivalent of 'goto
label[x]' for each case - so this is already the optimal solution!

Yes, modern compilers are getting pretty smart.

I
would guess that if I had variables in my case statements

Not allowed by the language. The 'case' expressions must be constant
expressions.

or if the case
statements had high values (e.g. case 99999999 then it would have to
revert to if..else if...else (or perhaps a hybrid of the two

solution...)


Well, try it and see.

-Mike

I did try this and it certainly changed the code. It looks like it is
doing a binary search of the case statements to find the matching one! I
can't be totally sure though since it was taking me too long to figure it
out the logic and I am not familiar with x86 assembly (the last time I used
assembly was on the ZX spectrum).....

Sean

 

[Eric Sosman]

I have a large switch statement (~50 cases ) inside a critical inner loop of
a byte code interpreter I am working on, and I am wondering if I should take
any steps to optimise this loop.

Others have explained some of the techniques used to
implement `switch' statements, but no response I've yet seen
has addressed your direct question: "Should I take any steps
to optimize this loop?" The answer is simple: "No."

How can I be so sure (or even so cocksure)? Because if
you're wondering whether the loop is worth optimizing, that
means you have not yet measured the performance and found that
the loop's execution time is a problem. To paraphrase Sherlock
Holmes, it is a capital mistake to optimize in the absence of
data. Or, as Donald Knuth put it, "Premature optimization is
the root of all evil."

You should only optimize when you have reason to believe
that optimization will produce enough benefit to repay the
effort and risk. IMHO, reliable reasons are of two kinds:
theoretical and experimental. The former reasons come from
studies of things like algorithmic complexity, and may drive
you, say, to use a hash table instead of a linear list --
this is "optimization" of a kind, but perhaps not the kind
you have in mind. The second reasons come from measurement:
after you have chosen and implemented your algorithm, you
measure the performance and find it wanting. Only then should
"optimization" in the usual sense enter the picture.

Jackson's Laws of Program Optimization:

First Law: Don't do it.

Second Law (for experts only): Don't do it yet.

Ponder before proceeding.

 

[Chris Torek]

Others have explained some of the techniques used to
implement `switch' statements, but no response I've yet seen
has addressed your direct question: "Should I take any steps
to optimize this loop?" The answer is simple: "No."

[ snippage -- see original ]

You should only optimize when you have reason to believe
that optimization will produce enough benefit to repay the
effort and risk. ... The second reasons come from measurement:
after you have chosen and implemented your algorithm, you
measure the performance and find it wanting. Only then should
"optimization" in the usual sense enter the picture.

And note that the results today may differ from those of yesterday
-- or in this case, two decades ago. In the mid-1980s I was writing
programs to deal with TeX "DVI" output files. TeX, Knuth's
typesetting program, was already slow enough, and after much
profiling of my own code I found that the way to optimize the main
loop's recurring switch was to change:

switch (code) {
case X1: case X2: case X3: case X4:
deal with an X operation
break;
case Y1: case Y2: case Y3: case Y4:
deal with a Y operation
break;
etc, for 256 total cases
}

into:

switch (class_table

) {
    case CLASS_X:
        deal with an X operation
        break;
    case CLASS_Y:
        deal with a Y operation
        break;
    etc, for a total of about two dozen cases
    }

On today's CPUs, this would probably actually slow down the code,
compared with the 256-cases method.  At the same time, on today's
CPUs, an entire hundreds-of-pages thesis might be page-sorted and
then converted from DVI to PostScript or PDF in a few seconds,
rather than dozens of minutes -- it really is no longer so crucial
to speed the program up by 10% or so (then, minutes; today, just
seconds or perhaps even fractions of seconds).

 

[Alan Balmer]

I have a large switch statement (~50 cases ) inside a critical inner loop of
a byte code interpreter I am working on, and I am wondering if I should take
any steps to optimise this loop.

How would we know ? <G>. Is it running too slow? Have you profiled the
program and determined that the switch statement in this loop is using
a significant amount of time? If you haven't done this, you're not
ready to start optimizing.

Are switch statements usually compiled as if...else if..else if...else type
statements?

Very unlikely.

Are there other ways that the compiler could implement switch
statements that are more efficient?

Yes - several ways. The compiler may choose different ways depending
on its analysis of your code.

With regards to my code, would it be better to put the most common cases
near the top of the switch statement

Probably a waste of time, and may make the code less readable.

or should I consider making a lookup
table of function pointers instead (but the function call overhead might
kill it) - this is the first time that I wish I could put labels into arrays
and do 'goto label[x]' )

No. This would be restricting the compiler's choices. As for "goto
label[x]', the compiler may choose to do it that way.

I've tried posting to comp.compilers but nothing has appeared in this group
for iver a week and it seems to be dead ....

Any advice, hints etc would be appreciated...

Sean

Profile first. Profile after each change. Look for better algorithms
before worrying about code details. Study the compiler's output - you
may be surprised.

 

[Villy Kruse]

How would we know ? <G>. Is it running too slow? Have you profiled the
program and determined that the switch statement in this loop is using
a significant amount of time? If you haven't done this, you're not
ready to start optimizing.
Very unlikely.

The most common ways I've seen is either a table lookup if the range
of possible case values is within reasonable limits and a binary search
algorithm otherwise. The binary search works by first testing for the
middle case value. If it is less all higher values are immediately
eliminated and the process is repeated with the lower half of the
interval. If it is higher the higher half is searched instead and if
it happens to be equal the case label is found.


Villy

 

[Rob Thorpe]

I have a large switch statement (~50 cases ) inside a critical inner

loop
of

a byte code interpreter I am working on, and I am wondering if I

should
take

any steps to optimise this loop.

Are switch statements usually compiled as if...else if..else if...else type
statements? Are there other ways that the compiler could implement switch
statements that are more efficient?

With regards to my code, would it be better to put the most common cases
near the top of the switch statement or should I consider making a lookup
table of function pointers instead (but the function call overhead might
kill it) - this is the first time that I wish I could put labels into arrays
and do 'goto label[x]' )

I've tried posting to comp.compilers but nothing has appeared in this group
for iver a week and it seems to be dead ....

Any advice, hints etc would be appreciated...

Sean

I decided to roll up my sleeves and look at the disassemby for this part of
the code and I thought I would share the result with the group. It
seems that the compiler (Borland C++Builder) is pretty intelligent and
noticed that all my case statements were literal constants of a fairly low
value, so it simply made a lookup table and did the equivalent of 'goto
label[x]' for each case - so this is already the optimal solution!

Yes, modern compilers are getting pretty smart.

I
would guess that if I had variables in my case statements

Not allowed by the language. The 'case' expressions must be constant
expressions.

or if the case
statements had high values (e.g. case 99999999 then it would have to
revert to if..else if...else (or perhaps a hybrid of the two

solution...)


Well, try it and see.

-Mike

I did try this and it certainly changed the code. It looks like it is
doing a binary search of the case statements to find the matching one! I
can't be totally sure though since it was taking me too long to figure it
out the logic and I am not familiar with x86 assembly (the last time I used
assembly was on the ZX spectrum).....

Anton Etrl has written extensively on exactly the subject you are
investigating:

http://www.complang.tuwien.ac.at/anton/home.html
http://www.complang.tuwien.ac.at/projects/forth.html

Going beyond the problem of using case in interpreter loops, you might
consider reading the documentation about the extra features some
compilers provide to do this.

Since the inner loop of an interpreter should not be very complex it
could be worth the effort needed to use them, while still providing a
portable version.

Though this isn't really about C, so I'll stop here.