Author: Heiner Marxen
Date: 05:40:42 09/02/02
Go up one level in this thread
On September 01, 2002 at 23:33:26, Robert Hyatt wrote:
>On September 01, 2002 at 20:46:55, Pham Hong Nguyen wrote:
>
>>The following article and discussion may be useful for you!
>>
>>http://www.codeguru.com/cpp_mfc/switch.html
>
>
>That is basically wrong.
>
>Compile a simple piece of code with gcc, using -O and you will see
>why.
>
>gcc creates a jump table of addresses for each case. It computes the
>entry to load and jumps to that. No compares and branches. Someone
>doesn't know how compilers do things. If you have really oddball case
>value, it might have to resort to that. But for the kinds of values
>we use in chess, no way...
Basically you are right Bob. Some additional info:
How to implement a switch statement always is a compiler decision, based
on code length, execution time (average and worst case), and code generation
simplicity (some compilers do not bother).
I know of three basic techniques to implement a switch statement
(since I wrote a C compiler code generation for "switch", some 12 years ago):
(1) Cascade of compare & jump on equal, as described in the linked article.
(2) jump-address table, indexed after a range check, as Bob describes.
(3) a kind of binary decision tree, to reduce the worst case run time of (1),
as well as the average execution time.
A high quality implementation of "switch" will have to mix techniques,
and should track the range of possible values for each partial construct.
Details omitted ;-)
Sometimes a bad decision by the compiler can really hurt (that has happened
to me at least twice). From time to time I look at the assembler generated
for some of my favorite switch statements. But then, when I dislike the
generated code, there is not much I can do, except to wait for the next
compiler update...
Cheers,
Heiner
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.