The Highest-Level Feature of C

[Lynn McGuire]

The Highest-Level Feature of C is?

Think about your answer before visiting:
http://prog21.dadgum.com/166.html

Shocked me.

Lynn

 

[Johann Klammer]

The Highest-Level Feature of C is?

Think about your answer before visiting:
http://prog21.dadgum.com/166.html

Shocked me.

Lynn

Yeah, I've always wondered why compilers would generate comparatively
messy assembler code for certain 'switch' statements...

I suspect that part was over-engineered, and looked simple to do when
they initially thought of it.

 

[Seebs]

The Highest-Level Feature of C is?

Think about your answer before visiting:
http://prog21.dadgum.com/166.html

Shocked me.

I'd seen that article already, but yeah, it is a fairly fascinating insight
into the nature of C. I mean, there's lots of other stuff that compilers are
*allowed* to do whatever they want with, but not many where that's so
explicitly stated.

-s

 

[Walter Banks]

The Highest-Level Feature of C is?

Think about your answer before visiting:
http://prog21.dadgum.com/166.html

Shocked me.

Switch statements in compilers are always interesting. When
we start developing a new compiler the only implemented
switch statement is if.. then .. else construct. Each processor
has its own switch strengths and weaknesses and we then
create alternative code for an indexed table, binary search,
sparse table, indexed tables not starting from 1 and sometimes
multiple tables. For each new processor metrics have to be
developed so the compiler determines which approach is
appropriate for each switch statement in the source.

The switch abstraction is nice but the implementation can
be quite complex.

Walter Banks
Byte Craft Limited

 

[glen herrmannsfeldt]

(snip)

Switch statements in compilers are always interesting. When
we start developing a new compiler the only implemented
switch statement is if.. then .. else construct.

Linear search if..then..else or binary tree if..then..else?

Each processor
has its own switch strengths and weaknesses and we then
create alternative code for an indexed table, binary search,
sparse table, indexed tables not starting from 1 and sometimes
multiple tables. For each new processor metrics have to be
developed so the compiler determines which approach is
appropriate for each switch statement in the source.

I once did a switch where all the cases where multiples of a
large power of two. If the compiler figured that out, it could
be done easily and fast, but I don't know if it did.

The switch abstraction is nice but the implementation can
be quite complex.

-- glen

 

[Phil Carmody]

The Highest-Level Feature of C is?

Think about your answer before visiting:
http://prog21.dadgum.com/166.html

Shocked me.

Even by the logic used in that article, the preprocessor
definitely wins. That's the thing that lets you write
your intent in a way that looks nothing like the final
generated reality.

Phil

 

[James Harris \(es\)]

The Highest-Level Feature of C is?

Think about your answer before visiting:
http://prog21.dadgum.com/166.html

Shocked me.

Don't be too shocked - the web page content is just an opinion. Which
feature would you have selected?

The author of that web page does have a good point. A switch statement can
be implemented in different ways. However, I'm not sure I would completely
agree. There are other viewpoints to consider. Here are a few of them:

For probably all C constructucts the implementation is not defined. For
example, given a series of 'if' statements if the tests were disjoint and
discrete a compiler could rewrite them as a jump table just as it might for
a normal switch statement. In a sense, then, neither is higher level than
the other.

As well as having a high-level element C's switch can be considered
particularly *low* level. Rather than selecting one of a number of
alternatives C's switch might be better understood as a multiway jump. This
is evidenced by the requirement for break statements and that switch cases
can be interleaved with other constructs. The interleaving is particularly
weird and unstructured - and low level.

An alternative candidate for the highest level feature of C (and the one I
thought of - as you told us to do - before clicking the link) is the
function call. There are many ways that parameters can be passed and results
returned. The compiler is free to choose how to interface functions based on
what it knows of caller and callee.

Possible other alternatives might be the initialisation of arrays and
structures or the manipulation of structures as units.

James

 

[BartC]

For probably all C constructucts the implementation is not defined. For
example, given a series of 'if' statements if the tests were disjoint and
discrete a compiler could rewrite them as a jump table just as it might
for a normal switch statement. In a sense, then, neither is higher level
than the other.

Just A*B could be implemented in a number of ways, mostly depending on type,
but can also be re-ordered, eliminated or incorporated into something else.

An alternative candidate for the highest level feature of C (and the one I
thought of - as you told us to do - before clicking the link) is the
function call. There are many ways that parameters can be passed and
results returned. The compiler is free to choose how to interface
functions based on what it knows of caller and callee.

I can't think of any individual high-level features that stand out. It's C's
optimising compilers that can make it higher level than it is, by generating
code seemingly unrelated to the source (if it isn't discarded altogether).
The code generation for switch would be a small part of that process.

 

[Öö Tiib]

The Highest-Level Feature of C is?

Think about your answer before visiting:
http://prog21.dadgum.com/166.html

Shocked me.

Why? After all the feature solves certain problems. The OOP languages
have chosen to solve some of those problems with virtual functions. The
virtual functions are notably complex. The problems they are solving must be
are considered complex as well.

 

[Walter Banks]

I once did a switch where all the cases were multiples of a
large power of two. If the compiler figured that out, it could
be done easily and fast, but I don't know if it did.

It probably didn't figure it out. It is the kind of thing that is
so rare that it would unlikely be part of the implementation.
Too bad it would be fun to see the surprise on customer
faces.

w..

 

[Keith Thompson]

It probably didn't figure it out. It is the kind of thing that is
so rare that it would unlikely be part of the implementation.

Unless it happens to appear in a benchmark, of course.

 

[Jorgen Grahn]

.

An alternative candidate for the highest level feature of C (and the one I
thought of - as you told us to do - before clicking the link) is the
function call.

Me too.

There are many ways that parameters can be passed and results
returned. The compiler is free to choose how to interface functions based on
what it knows of caller and callee.

And if inlining happens (which it does often, the way I write my code)
the function call doesn't even correspond to anything in the generated
code. And you almost never have to care!

/Jorgen

 

[Anders Wegge Keller]

I once did a switch where all the cases where multiples of a large
power of two. If the compiler figured that out, it could be done
easily and fast, but I don't know if it did.

Do you have a suggestion for how the compiler would be able to take
advantage from this, had it been able to detect the situation?

 

[glen herrmannsfeldt]

Do you have a suggestion for how the compiler would be able to take
advantage from this, had it been able to detect the situation?

Shift right and index a jump table.

I used to think that switch always used a jump table, as I knew
Fortran's computed-GOTO, which (in the compilers I knew) was always
done that way, and originally thought of switch as a more structured
form of computed-GOTO.

-- glen

 

[Anders Wegge Keller]

Shift right and index a jump table.

Yes? Do you suggest something like this:

jump = 0;
while (val) {
val = val >> 1;
if (val == 1) {
jumptable[jump]();
break;
}
jump++;
}

I used to think that switch always used a jump table, as I knew
Fortran's computed-GOTO, which (in the compilers I knew) was always
done that way, and originally thought of switch as a more structured
form of computed-GOTO.

Would that be slower or faster than bisection in the range of
{2,3,5,8,13,21,34,55,89,144,...}?

 

[James Kuyper]

Shift right and index a jump table.

Yes? Do you suggest something like this:

jump = 0;
while (val) {
val = val >> 1;
if (val == 1) {
jumptable[jump]();
break;
}
jump++;
}

I thought he was describing something much simpler:

jumptable[val>>LARGE_POWER_OF_2]();

 

[Anders Wegge Keller]

I thought he was describing something much simpler:

jumptable[val>>LARGE_POWER_OF_2]();

You are right. Shame on me for latching on to the pwoers of two,
without catching the "multiples".

 

[BartC]

Shift right and index a jump table.

Yes? Do you suggest something like this:

jump = 0;
while (val) {
val = val >> 1;
if (val == 1) {
jumptable[jump]();
break;
}
jump++;
}

The 'jump-table' would be part of the switch statement. If the source code
was:

switch (x) {
case 1024:
case 2048:
case 3072:

then the compiler might implement it as though it was:

switch (x>>10) {
case 1:
case 2:
case 3:

which can use a compact jump-table of 3 elements.

 

[glen herrmannsfeldt]

news:[email protected]...

(snip, I wrote)

(snip)

The 'jump-table' would be part of the switch statement.
If the source code was:

switch (x) {
case 1024:
case 2048:
case 3072:

then the compiler might implement it as though it was:

switch (x>>10) {
case 1:
case 2:
case 3:

which can use a compact jump-table of 3 elements.

Yes, but some might have been:

case 0x1000000:
case 0x2000000:
case 0x3000000:

Possibly expansions of preprocessor macros.

-- glen

 

[BartC]

Yes, but some might have been:

case 0x1000000:
case 0x2000000:
case 0x3000000:

Possibly expansions of preprocessor macros.

Isn't that the same thing? The compiler will know the constant value in each
case, whether it's from a macro or not.

If all case statements have at least N low bits that are zero, then the
shift-right-by-N optimisation can be done to make the jump table more
compact. (Although if it's already compact enough, for the values
(10,6,2,12) for example where N=1, then it might not be worth doing.)