February 1999
- client images Chris Gray
- Question on c++ switch optimization, and parsers in general. Ben Greear
- Question on c++ switch optimization, and parsers in general. Adam Wiggins
- Question on c++ switch optimization, and parsers in general. Ola Fosheim Grøstad
- Question on c++ switch optimization, and parsers in general. Chris Gray
- Question on c++ switch optimization, and parsers in general. Chris Gray
- Question on c++ switch optimization, and parsers in general. T. Alexander Popiel
- Question on c++ switch optimization, and parsers in general. Ola Fosheim Grøstad
- Question on c++ switch optimization, and parsers in general. Richard Woolcock
- Question on c++ switch optimization, and parsers in general. Marc Hernandez
On Tue, 9 Feb 1999, Richard Woolcock wrote:
> Ben Greear wrote:
> >
> > Well, after the 400th person said my parse engine was an insult to
> > hackers everywhere (I was the first of those 400!!), I am re-writing it.
> >
> > Basically, I'll have a bunch of classes hashed into an array
> > that will contain the keywords mapped to an enum.
> >
> > Now, I get the enum, and then I need to call the various commands
> > that the enum maps to.
> >
> > Currently, I'm using a huge (~400 cases) switch statement.
> >
> > So, the question is: Is that efficient? Does the compiler
> > generate code that does better than a linear search down the
> > case statements? If not, I can manually hack a sort of n-ary
> > tree performance into it, but I'd wrather not if I can help it.
I decided to do some tests on this as I have been curious about it
and now seemed to be a good time.
I had 2 different compilers (MSVC 5.0 and gcc on a Sparc) produce
assembly output (very good things to do with these sorts of things).
With gcc I compiled a .cpp and a .c file. It uses the extension
as the file type.
> I don't know about C++, but I can speak for C.
In the switch regard both compilers acted the same.
> I believe that switch statements are compiled down to the equivilent
> of if statements, ie:
>
> switch ( x )
> {
> case 1: ...
> case 2: ...
> case 3: ...
> default: ...
> }
>
> Is no more efficient than:
>
> if ( x == 1 ) ...
> else if ( x == 2 ) ...
> else if ( x == 3 ) ...
> else ...
> So basically, no, it's no better than a linear search. Not that it
> really matters, unless you have thousands of commands. I prefer the
> diku-style array of commands, but you'd have to go through that in
> a linear fashion too (you could do a binary search through it, but
> that might result in annoying things like typing 's' resulting in
> 'sit' rather than 'south'). Still, it's nicer to look at.
>
> Some more modern compilers may treat switch statements better than
> the ones I'm used to - if so, I'd appreciate it if someone told me :)
My test code looked roughly like:
int i;
int d;
i=rand()&255;
switch(i)
{
case 0:
d=rand();
break;
case 1:
d=rand();
break;
. . .
They do things differently. It was very interesting actually.
With only two cases did the case statements generate code that looked like
if/thens. With 3 it generated this:
sub eax, 0
je SHORT $L491
dec eax
je SHORT $L491
dec eax
jne SHORT $L488
Which I thought was cute. With more it generates a jump table.
This code looks roughly like:
cmp eax, 35 ; 00000023H
ja SHORT $L488
jmp DWORD PTR $L535[eax*4]
Where $L535 is the jump table location. I had the same code for each
case statement. In the debug build the code was repeated, but in the
release build it recognized these basic blocks as identicle and used the
same code.
I also did wildly varying values and sequential values as well as
skips every now and then. Skips were easy, the compiler just put the end
of the switch statement as the place to jump to.
So it appears that a switch with sequential values is roughly
equivelent to a indirect jump. Not too bad actually.
As a side note. The compiler did not pickup on the fact that i
could never be greater than 255.
Marc Hernandez
- Question on c++ switch optimization, and parsers in general. Marc Hernandez
- Question on c++ switch optimization, and parsers i Chris Gray
- Question on c++ switch optimization, and parsers i Jon A. Lambert
- Question on c++ switch optimization, and parsers i Chris Gray
- optimizing code diablo@best.com
- optimizing code Hans-Henrik Staerfeldt
- optimizing code Chris Gray
- code profiling Chris Gray
- World-file parsing and RTTI? The Arrow
- World-file parsing and RTTI? Mark Gritter
- pet peeves diablo@best.com
- pet peeves diablo@best.com
- pet peeves Caliban Tiresias Darklock
- pet peeves Marc Bowden
- pet peeves Richard Woolcock
- pet peeves Koster, Raph
- pet peeves diablo@best.com
- pet peeves Caliban Tiresias Darklock
- pet peeves Kristen Koster
- pet peeves Caliban Tiresias Darklock
- pet peeves Adam Wiggins
- pet peeves Wes Connell
- pet peeves J C Lawrence
- pet peeves Matthew Mihaly
- pet peeves Ling
- pet peeves Ola Fosheim Grøstad
- pet peeves Matthew Mihaly
- pet peeves Ola Fosheim Grøstad
- pet peeves Matthew Mihaly
- pet peeves David Bennett
- pet peeves Robert Woods
- pet peeves Wes Connell
- pet peeves Travis S. Casey
- pet peeves Matthew Mihaly
- pet peeves Neerenberg, AaronX
- pet peeves greg
- pet peeves Richard Woolcock
- pet peeves J C Lawrence
- pet peeves Martin Keegan
- pet peeves Ola Fosheim Grøstad
- pet peeves J C Lawrence
- pet peeves diablo@best.com
- pet peeves Brandon A Downey
- pet peeves diablo@best.com
- pet peeves Darren Henderson
- pet peeves diablo@best.com
- pet peeves Darren Henderson
- pet peeves Steve Houchard
- pet peeves diablo@best.com
- pet peeves Darren Henderson
- pet peeves diablo@best.com
- pet peeves Steve Houchard
- pet peeves diablo@best.com
- pet peeves Richard Woolcock
- pet peeves diablo@best.com
- pet peeves Richard Woolcock
- pet peeves Apocalypse
- pet peeves Caliban Tiresias Darklock
- pet peeves diablo@best.com
- pet peeves Adam Wiggins
- pet peeves diablo@best.com
- pet peeves Adam Wiggins
- pet peeves diablo@best.com
- pet peeves Mik Clarke
- pet peeves Caliban Tiresias Darklock
- pet peeves Travis S. Casey
- pet peeves Caliban Tiresias Darklock
- pet peeves Benjamin D. Wiechel
- pet peeves Marc Bowden
- pet peeves Matthew Mihaly
- pet peeves Mik Clarke
- pet peeves Benjamin D. Wiechel
- pet peeves Matthew Mihaly
- pet peeves Caliban Tiresias Darklock
- pet peeves Marc Bowden
- pet peeves Matthew Mihaly
- pet peeves David Bennett
- pet peeves David Bennett
- pet peeves Petri Virkkula
- pet peeves J C Lawrence
- Horror Themed Muds [was CthulhuMud Driver 6] Christopher Allen
- Horror Themed Muds [was CthulhuMud Driver 6] Caliban Tiresias Darklock
- Horror Themed Muds [was CthulhuMud Driver 6] Mik Clarke
- CthulhuMud Driver 6 Mik Clarke
- CthulhuMud Driver 6 J C Lawrence
- Mathengine Ling
- Mathengine Apocalypse
- Website update Koster, Raph
- Influential muds Koster, Raph
- Influential muds Dan Shiovitz
- Influential muds Adam Wiggins
- Influential muds Sunny Gulati
- Influential muds diablo@best.com
- Influential muds Juha Lindfors
- Influential muds Brandon J. Rickman
- Influential muds Caliban Tiresias Darklock
- Influential muds Andy Cink
- Influential muds J C Lawrence
- Influential muds Dr. Cat
- Influential muds Jay Carlson
- Influential muds Mik Clarke
- Influential muds Richard Woolcock
- Influential muds Koster, Raph
- Influential muds Mik Clarke
- Influential muds Ola Fosheim Grøstad
- Influential muds Dan Root
- Influential muds Benjamin D. Wiechel
- State of the art? Andy Cink
- State of the art? diablo@best.com
- State of the art? Caliban Tiresias Darklock
- State of the art? ##Make Nylander
- State of the art? diablo@best.com
- State of the art? Martin Keegan
- State of the art? David Bennett
- State of the art? Martin Keegan
- State of the art? Andy Cink
- State of the art? J C Lawrence
- State of the art? David Bennett
- State of the art? Matthew Mihaly
- State of the art? Caliban Tiresias Darklock
- State of the art? Matthew Mihaly
- State of the art? Ola Fosheim Grøstad
- State of the art? Ola Fosheim Grøstad
- State of the art? J C Lawrence
- State of the art? Matthew Mihaly
- State of the art? Mik Clarke
- State of the art? J C Lawrence
- The Terrorist Class Ola Fosheim Grøstad
- The Terrorist Class Mik Clarke
- Welcome To "MUD-Dev"! mud-dev-admin@kanga.nu
- IMPORTANT ADMIN: New list setup requires your attention J C Lawrence
- ADMIN: URL change J C Lawrence
- PermaDeath (was pet peeves) Marc Hernandez
- ScryMUD 1.8.7 released. Ben Greear
- PermaDeath Sayeed
- PermaDeath Ola Fosheim Grøstad
- PermaDeath Sayeed
- roleplaying and immersion (was: PermaDeath) Ola Fosheim Grøstad
- Roleplaying and Immersion (was: PermaDeath) Sayeed
- Roleplaying and Immersion (was: PermaDeath) Adam Wiggins
- Roleplaying and Immersion (was: PermaDeath) J C Lawrence
- Roleplaying and Immersion (was: PermaDeath) Ola Fosheim Grøstad
- WEB: VR-stuff Ola Fosheim Grøstad
- WEB: VR-stuff J C Lawrence
- WEB: VR-stuff Mik Clarke
- WEB: VR-stuff Marian Griffith
- WEB: VR-stuff J C Lawrence
- ADMIN: The list archives are now online and fully searchable J C Lawrence
- Theories was pet peeves Wes Connell