Re: [Boost-users] Sequence of Types, What For?
From: "Andrew Holden" <aholden@charteroaksystems.com>
3: Look up the value in the first array, and then look up the code block number in the second array.
4: Go to the pointer you just got.
The actual blocks of code are laid out in order right after the goto in step 4, in the same order as the source code. Breaks become goto end of switch. If you leave out a break, the processor really does JUST fall through to the next case.
All in all, if you have a monster switch statement, the compiler-generated code probably is just about as fast as you can get. It takes less than a dozen machine instructions to implement it, and it has constant complexity.
Actually this is not particularly good. For one thing, it's O(n), not constant time, because doing an array lookup is O(n). For many switch use-cases this is no big deal, but it certainly isn't unheard of to have a switch with dozens (or more) of cases, each of which does almost nothing (like return a value). In this case, the lookup can actually dominate your runtime. There's a theorem in hash theory (proved by Komlos, one of my old profs) that says that you can always generate a perfect hash function if you know the values you need to hash. That is, you can generate a hash function that requires exactly one lookup in every case. But I don't know any compiler that actually does this. Since all cases are known at compile time, doing this should be a beneficial runtime optimization for large switches (if the generated hash function is sufficiently cheap). Maybe this could be done using the MPL? I don't know TMP well enough to know where to begin on something like this. See http://en.wikipedia.org/wiki/Perfect_hash_function for more detail. - James Jones Administrative Data Mgmt. Webmaster 375 Raritan Center Pkwy, Suite A Data Architect Edison, NJ 08837
At 5:15 PM -0500 11/7/06, <james.jones@firstinvestors.com> wrote:
There's a theorem in hash theory (proved by Komlos, one of my old profs) that says that you can always generate a perfect hash function if you know the values you need to hash. That is, you can generate a hash function that requires exactly one lookup in every case. But I don't know any compiler that actually does this. Since all cases are known at compile time, doing this should be a beneficial runtime optimization for large switches (if the generated hash function is sufficiently cheap). Maybe this could be done using the MPL? I don't know TMP well enough to know where to begin on something like this.
I remember doing this in college, in the "compiler construction" class - we had a perfect hash table for the keywords in the language that we were compiling. -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> It is by caffeine alone I set my mind in motion. It is by the beans of Java that thoughts acquire speed, the hands acquire shaking, the shaking becomes a warning. It is by caffeine alone I set my mind in motion.
At 2:18 PM -0800 11/7/06, Marshall Clow wrote:
At 5:15 PM -0500 11/7/06, <james.jones@firstinvestors.com> wrote:
There's a theorem in hash theory (proved by Komlos, one of my old profs) that says that you can always generate a perfect hash function if you know the values you need to hash. That is, you can generate a hash function that requires exactly one lookup in every case. But I don't know any compiler that actually does this. Since all cases are known at compile time, doing this should be a beneficial runtime optimization for large switches (if the generated hash function is sufficiently cheap). Maybe this could be done using the MPL? I don't know TMP well enough to know where to begin on something like this.
I remember doing this in college, in the "compiler construction" class - we had a perfect hash table for the keywords in the language that we were compiling.
Looking over my posting, I misspoke - it was another group in my class, not mine, who had the perfect hash function in their compiler. Historical Revisionism strikes again :-( -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> Here's to parties we tossed, to the games that we lost; We will say that we won them, some day. -- Bright College Days; Tom Lehrer.
doing an array lookup is O(n). Huh? Array indexing is constant time. The compiler doesn't scan the array, it uses the switch value directly as the index (after some mathematical
james.jones@firstinvestors.com wrote: transformation, perhaps.) Sebastian Redl
Sebastian Redl wrote:
doing an array lookup is O(n). Huh? Array indexing is constant time. The compiler doesn't scan the array, it uses the switch value directly as the index (after some mathematical
james.jones@firstinvestors.com wrote: transformation, perhaps.)
I think I see where the confusion came from: poor wording on my part. In step three, where I talk about "looking stuff up" in the arrays, I meant to say the array is indexed by the stuff, not that the runtime must search for it. The lookup, in this case, is a simple indexing operation, and is often implemented in one or two machine instructions.
participants (5)
-
Andrew Holden -
David Abrahams -
james.jonesīŧ firstinvestors.com -
Marshall Clow -
Sebastian Redl