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
[Richard Woolcock (KaVir):]
>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 ...
>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 :)
Any compiler that still does that should be taken out and shot. Even
toy compilers do better. I very much doubt any commercial compiler will
do it. There are generally a small number of schemes that a compiler
will use to handle switch statements, depending on the density and
number of the index values. Some methods:
- emit an inline table containing offsets to the code to be executed.
Table is directly indexed by a multiple of the switch value,
usually with a range-test to handle the default. A variant is
to have branch instructions in the table, and to branch to
the appropriate one which then branches to the final code.
- emit an inline table containing index values and code offsets.
Either call a run-time routine, or emit an in-line binary
search to search the table. Similar alternate.
- emit a sequence of instructions that implement an inline binary
search of the index space directly, using inline constants.
- emit a sequence of instructions to do a simple linear search, much
as KaVir suggests. If the compiler does this for more than about
4 or 5 tests, however, it should be shot. This would be done when
the index values are such that, on average, this simple linear
search is the fastest method.
I'm sure I'm missing some - I found lots when I was writing disassemblers
about 10 years ago. I used the first and second in my Draco compiler,
and my AmigaMUD bytecode has those as well.
--
Don't design inefficiency in - it'll happen in the implementation. - me
Chris Gray cg@ami-cg.GraySage.Edmonton.AB.CA
http://www.GraySage.Edmonton.AB.CA/cg/ - 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
- 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