switch case to a jump table

[sam_cit]

Hi Everyone,

I wanted to know as to how a switch case like the following one is
converted into a jump table by the compiler, assuming that it does,

switch(i)
{
case 4 : {
...
printf("4");
break;
}
case 5:
case 6:
{
printf("56");
break;
}
case 1000: {
printf("1000");
break;
}
default : {
printf("default");
break;
}
};

[Malcolm McLean]

<sa*****@yahoo.co.inwrote in message
news:11**********************@p77g2000hsh.googlegr oups.com...

Hi Everyone,

I wanted to know as to how a switch case like the following one is
converted into a jump table by the compiler, assuming that it does,

switch(i)
{
case 4 : {
...
printf("4");
break;
}
case 5:
case 6:
{
printf("56");
break;
}
case 1000: {
printf("1000");
break;
}
default : {
printf("default");
break;
}
};

The compiler can grab 1001 * size of function pointer bytes of memory, and
construct a lookup table. It may or may consider the tradeoff to be worth
it.

Alternatively it can look for a function that converts the integer values
into unique keys with a limited range. In this case it would be something
like (x/100 + x % 10). The technical term is "perfect hashing". The second
approach is much more difficult to implement and I don't know if any
compilers actually use it, though I suspect they do.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Thad Smith]

sa*****@yahoo.co.in wrote:

I wanted to know as to how a switch case like the following one is
converted into a jump table by the compiler, assuming that it does,

switch(i)
{
case 4 : {
...
printf("4");
break;
}
case 5:
case 6:
{
printf("56");
break;
}
case 1000: {
printf("1000");
break;
}
default : {
printf("default");
break;
}
};

There are no requirements in C for how a compiler implements a switch
statement.

Many different techniques are used in practice. What I expect is that
when a compiler decides to use a lookup table, it first decides on the
bounds of the table. At run time, the code checks the switch argument
value against the bounds, and if within the table, looks up the address.
For your particular example, I would expect most compilers to not use
a table.
--
Thad

[Stephen Sprunk]

<sa*****@yahoo.co.inwrote in message
news:11**********************@p77g2000hsh.googlegr oups.com...

I wanted to know as to how a switch case like the following one is
converted into a jump table by the compiler, assuming that it does,

switch(i)
{
case 4 : {
...
printf("4");
break;
}
case 5:
case 6:
{
printf("56");
break;
}
case 1000: {
printf("1000");
break;
}
default : {
printf("default");
break;
}
};

I doubt a decent compiler would use a jump table for this; it's way too
sparse. Still, if it did, the asm would look something like this
pseudocode:
void *jumptable[1001] = { default, default, default, default, label4,
label56, label56, default, ... , default, label1000 };
/* insert your code to set i */
goto jumptable[i];
label4:
printf("4");
goto end;
label56:
printf("56");
goto end;
label1000:
printf("1000");
goto end;
default:
printf("default");
end:
S

--
Stephen Sprunk "Those people who think they know everything
CCIE #3723 are a great annoyance to those of us who do."
K5SSS --Isaac Asimov
--
Posted via a free Usenet account from http://www.teranews.com

[sam_cit]

On May 7, 6:22 pm, "Stephen Sprunk" <[e-mail]:

<[e-mail] in message

news:11**********************@p77g2000hsh.googlegr oups.com...

I wanted to know as to how a switch case like the following one is
converted into a jump table by the compiler, assuming that it does,

switch(i)
{
case 4 : {
...
printf("4");
break;
}
case 5:
case 6:
{
printf("56");
break;
}
case 1000: {
printf("1000");
break;
}
default : {
printf("default");
break;
}
};

I doubt a decent compiler would use a jump table for this; it's way too
sparse. Still, if it did, the asm would look something like this
pseudocode:

void *jumptable[1001] = { default, default, default, default, label4,
label56, label56, default, ... , default, label1000 };
/* insert your code to set i */
goto jumptable[i];
label4:
printf("4");
goto end;
label56:
printf("56");
goto end;
label1000:
printf("1000");
goto end;
default:
printf("default");
end:

S

--
Stephen Sprunk "Those people who think they know everything
CCIE #3723 are a great annoyance to those of us who do."
K5SSS --Isaac Asimov

--
Posted via a free Usenet account fromhttp://www.teranews.com- Hide quoted text -

- Show quoted text -

How would that work with negative values of i?

Moreover, it is correct to assum that,

case 5: printf("56");
break;
case 6: printf(56");
break;

is same for the jump table generation for the following switch case?

case 5:
case 6:
printf("56");
break;

Thanks in advance!!!

[Richard Tobin]

In article <11**********************@e51g2000hsg.googlegroups .com>,
<sa*****@yahoo.co.inwrote:

>void *jumptable[1001] = { default, default, default, default, label4,
label56, label56, default, ... , default, label1000 };
/* insert your code to set i */
goto jumptable[i];

....

>How would that work with negative values of i?

It wouldn't, not for values above 1000. Unless the compiler can
determine that the value is in range, it has to check it.

-- Richard

--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Chris Torek]

><sa*****@yahoo.co.inwrote in message

>news:11**********************@p77g2000hsh.googleg roups.com...

>I wanted to know as to how a switch case like the following one is
converted into a jump table by the compiler, assuming that it does ...

[code snipped, but the range for the selector was 4..1000]

In article <46***********************@free.teranews.com>
Stephen Sprunk <st*****@sprunk.orgwrote:

>I doubt a decent compiler would use a jump table for this; it's way too
sparse.

Yes, although as Richard Heathfield noted, one can apply a reduction
function first. (This complicates the code since each match must
then reject false hits.)

>Still, if it did, the asm would look something like this
pseudocode:

void *jumptable[1001] = { default, default, default, default, label4,
label56, label56, default, ... , default, label1000 };

Actually, more like:

static void *const __table[1000 - 4 + 1] =
{ &&__label4, &&__label56, &&__label56,
&&__label_default, ..., &&__label_default, &&__label1000 };

(using gcc's "&&label" syntax), and:

>/* insert your code to set i */
goto jumptable[i];

replace this "goto" with:

if (i >= 4 && i <= 1000) goto __table[i - 4];
goto __label_default;

or (closer to typical machine code):

if ((%t0 = i - 4) < 0) goto __label_default;
if (%t0 1000 - 4) goto __label_default;
goto __table[%t0];

(where %t0 is a "compiler's temporary values" machine register).

The specifics are quite machine-dependent, but in general, there
are two criteria for using a jump table: the "load factor" (or
"fill factor" or other similar name) has to be high enough, typically
at least 2/3 -- i.e., most of the table-slots must not be the
"default:" label, or if there is no default, the internally-generated
"end of switch" label (which is then used as the default) -- and
there must be some minimum number of target labels (typically at
least 3 to 5).

If the number of labels is very low, a simple compare/goto sequence
is usually best.

If the number of labels is high but the table is sparse, the compiler
should:

- break up the cases into contiguous sub-ranges
- use a hash system
- use a binary search
- use an interpolative search

and/or some combination of all of the above. For instance, if we
have cases 0, 1, 2, 3, 4, 6, 100, 9000, 9001, 9002, 9003, and 15000,
we might want machine code like:

if (i 100) {
if (i == 15000) goto __label_15000;
if (i < 9000 || i 9003) goto __label_default;
goto __table9000[i - 9000];
} else if (i == 100)
goto __label_100;
else if (i < 0 || i >= 6)
goto __label_default;
else
goto __table0[i - 0];

(I am not sure how often interpolative search would pay off.
Probably not often -- most cases where it would, would be
subsumed by a jump table.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Richard Heathfield]

Chris Torek said:

<snip>

In article <46***********************@free.teranews.com>
Stephen Sprunk <st*****@sprunk.orgwrote:

>>I doubt a decent compiler would use a jump table for this; it's way
too sparse.

Yes, although as Richard Heathfield noted, one can apply a reduction
function first.

Chris, I noted no such thing. (And of course you err too infrequently
for anyone to pass up the chance of correcting you, no matter how
trivial the slip.)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Keith Thompson]

sa*****@yahoo.co.in writes:

I wanted to know as to how a switch case like the following one is
converted into a jump table by the compiler, assuming that it does,

switch(i)
{
case 4 : {
...
printf("4");
break;
}
case 5:
case 6:
{
printf("56");
break;
}
case 1000: {
printf("1000");
break;
}
default : {
printf("default");
break;
}
};

Who cares?

The generated code, assuming a properly working compiler, will produce
the specified output for any value of i. It could use a jump table, a
sequence of conditional jumps, or a virtual flux capacitor. The
standard says exactly nothing about how this is done; it specifies
only the behavior of the final program.

If you're curious about what code is generated by a particular
compiler, you can compile the code with your own compiler and examine
the code it generates (typically "-S" tells the compiler to generate
an assembly listing; check your compiler's documentation). If you
want to know how compilers handle this in general, comp.compilers is
probably a better place to ask.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[¬a\\/b]

On Mon, 07 May 2007 19:17:48 +0000, Richard Heathfield wrote:

>Chris Torek said:
<snip>

>In article
Stephen Sprunk wrote:

>>>I doubt a decent compiler would use a jump table for this; it's way
too sparse.

Yes, although as Richard Heathfield noted, one can apply a reduction
function first.

Chris, I noted no such thing. (And of course you err too infrequently
for anyone to pass up the chance of correcting you, no matter how
trivial the slip.)

there are people that "err infrequently" but i, you, all ones, make
errors the same it is possible not to be said for some program