switch case to a jump table

S

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;
}
};
 
M

Malcolm McLean

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.
 
T

Thad Smith

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.
 
S

Stephen Sprunk

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;
label4:
printf("4");
goto end;
label56:
printf("56");
goto end;
label1000:
printf("1000");
goto end;
default:
printf("default");
end:


S
 
S

sam_cit

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;
label4:
printf("4");
goto end;
label56:
printf("56");
goto end;
label1000:
printf("1000");
goto end;
default:
printf("default");
end:

S


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!!!
 
R

Richard Tobin

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

How would that work with negative values of i?[/QUOTE]

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
 
C

Chris Torek

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

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;


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.)
 
R

Richard Heathfield

Chris Torek said:

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.)
 
K

Keith Thompson

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.
 
¬

¬a\\/b

Chris Torek said:


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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top