The Highest-Level Feature of C

Discussion in 'C Programming' started by Lynn McGuire, Mar 19, 2013.

  1. Lynn McGuire

    Lynn McGuire Guest

    Lynn McGuire, Mar 19, 2013
    #1
    1. Advertising

  2. Lynn McGuire wrote:
    > 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.
    Johann Klammer, Mar 19, 2013
    #2
    1. Advertising

  3. Lynn McGuire

    Seebs Guest

    On 2013-03-19, Lynn McGuire <> wrote:
    > 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
    --
    Copyright 2013, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
    Seebs, Mar 20, 2013
    #3
  4. Lynn McGuire

    Walter Banks Guest

    Lynn McGuire wrote:

    > 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
    Walter Banks, Mar 20, 2013
    #4
  5. Walter Banks <> wrote:

    (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
    glen herrmannsfeldt, Mar 20, 2013
    #5
  6. Lynn McGuire

    Phil Carmody Guest

    Lynn McGuire <> writes:
    > 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
    --
    "In a world of magnets and miracles"
    -- Insane Clown Posse, Miracles, 2009. Much derided.
    "Magnets, how do they work"
    -- Pink Floyd, High Hopes, 1994. Lauded as lyrical geniuses.
    Phil Carmody, Mar 21, 2013
    #6
  7. "Lynn McGuire" <> wrote in message
    news:kiajhi$jui$...
    > 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
    James Harris \(es\), Mar 22, 2013
    #7
  8. Lynn McGuire

    BartC Guest

    "James Harris (es)" <> wrote in message
    news:kihdnb$f4t$...

    >> The Highest-Level Feature of C is?


    >> http://prog21.dadgum.com/166.html
    >>
    >> Shocked me.


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

    --
    Bartc
    BartC, Mar 22, 2013
    #8
  9. Lynn McGuire

    Öö Tiib Guest

    On Tuesday, 19 March 2013 23:00:00 UTC+2, Lynn McGuire wrote:
    > 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.
    Öö Tiib, Mar 22, 2013
    #9
  10. Lynn McGuire

    Walter Banks Guest

    glen herrmannsfeldt wrote:

    > 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..
    Walter Banks, Mar 23, 2013
    #10
  11. Walter Banks <> writes:
    > glen herrmannsfeldt wrote:
    >> 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.


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

    > Too bad it would be fun to see the surprise on customer
    > faces.


    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Working, but not speaking, for JetHead Development, Inc.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Mar 23, 2013
    #11
  12. Lynn McGuire

    Jorgen Grahn Guest

    On Fri, 2013-03-22, James Harris (es) wrote:
    ....
    > 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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Mar 23, 2013
    #12
  13. glen herrmannsfeldt <> writes:

    > 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?

    --
    /Wegge

    Leder efter redundant peering af dk.*,linux.debian.*
    Anders Wegge Keller, Mar 26, 2013
    #13
  14. Anders Wegge Keller <> wrote:
    > glen herrmannsfeldt <> writes:


    >> 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?


    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
    glen herrmannsfeldt, Mar 26, 2013
    #14
  15. glen herrmannsfeldt <> writes:

    > Anders Wegge Keller <> wrote:
    > > glen herrmannsfeldt <> writes:

    >
    > >> 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?

    >
    > 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,...}?

    --
    /Wegge

    Leder efter redundant peering af dk.*,linux.debian.*
    Anders Wegge Keller, Mar 26, 2013
    #15
  16. Lynn McGuire

    James Kuyper Guest

    On 03/26/2013 03:16 PM, Anders Wegge Keller wrote:
    > glen herrmannsfeldt <> writes:
    >
    >> Anders Wegge Keller <> wrote:
    >>> glen herrmannsfeldt <> writes:

    >>
    >>>> 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?

    >>
    >> 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]();
    James Kuyper, Mar 26, 2013
    #16
  17. James Kuyper <> writes:

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

    --
    /Wegge

    Leder efter redundant peering af dk.*,linux.debian.*
    Anders Wegge Keller, Mar 26, 2013
    #17
  18. Lynn McGuire

    BartC Guest

    "Anders Wegge Keller" <> wrote in message
    news:...
    > glen herrmannsfeldt <> writes:
    >
    >> Anders Wegge Keller <> wrote:
    >> > glen herrmannsfeldt <> writes:

    >>
    >> >> 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?

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

    --
    Bartc
    BartC, Mar 26, 2013
    #18
  19. BartC <> wrote:
    > "Anders Wegge Keller" <> wrote in message
    > news:...


    (snip, I wrote)

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


    (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
    glen herrmannsfeldt, Mar 26, 2013
    #19
  20. Lynn McGuire

    BartC Guest

    "glen herrmannsfeldt" <> wrote in message
    news:kitacv$615$...
    > BartC <> wrote:


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


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

    --
    Bartc
    BartC, Mar 26, 2013
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sparky Arbuckle

    Return Highest Record (SQL - Access)

    Sparky Arbuckle, Aug 17, 2005, in forum: ASP .Net
    Replies:
    4
    Views:
    3,109
    Paul Clement
    Aug 18, 2005
  2. Stone
    Replies:
    0
    Views:
    351
    Stone
    Nov 24, 2004
  3. NoKetch

    Rounding to next highest number?

    NoKetch, Dec 15, 2003, in forum: C Programming
    Replies:
    7
    Views:
    563
    Mark McIntyre
    Dec 15, 2003
  4. Jaspreet

    Second Highest number in an array

    Jaspreet, Sep 23, 2005, in forum: C Programming
    Replies:
    21
    Views:
    1,345
    Keith Thompson
    Feb 1, 2006
  5. pabbu
    Replies:
    8
    Views:
    700
    Marc Boyer
    Nov 7, 2005
Loading...

Share This Page