Re: Needed features in upcoming standards

Discussion in 'C Programming' started by Willem, Jan 6, 2009.

  1. Willem

    Willem Guest

    Blake McBride wrote:
    ) The use of this feature is in virtual machines. VM's typically process
    ) op-codes. These op-codes can be treated as indexes into the branch
    ) array. This would be very, very fast. I know C can use arrays of
    ) function pointers that can be indexed into and executed but the problem
    ) is that you have the (often huge) function overhead associated with each
    ) instruction. The other probable response is a case statement. The
    ) problem is that a case statement must do a lot of time-consuming
    ) compares in order get to the correct case. In index and branch is much
    ) faster. (I know case statement are optimized to a point but I don't
    ) think they are guaranteed to be as fast as an index and branch).

    Case statements were *invented* to be turned into index-and-branch.
    Do you agree that computed gotos would be a moot point if compilers
    would *guarantee* that a case statement (perhaps with some restrictions,
    such as only with successive integers) would be turned into an
    index-and-branch ? Then why not ask for such a guarantee ?
    That would be ten times easier.

    ) 2. Function goto instead of call
    )
    ) When you call a function (typically) a call stack is created. When the
    ) function returns the return goes to the calling function. Some C
    ) compilers can do tail call elimination in certain circumstances but it
    ) is never guaranteed to support tail calls in all obvious conditions. C
    ) is often used as an intermediate language for other languages compilers
    ) (like Lisp, Scheme, etc.). Languages such as Scheme require tail call
    ) optimization. Coding in assembler is very un-portable. Using C as a
    ) portable assembler is great but not being able to eliminate tail calls
    ) is a big problem. Scheme compilers often use a set of tricks to make C
    ) eliminate tail calls but these tricks are very slow compared to what is
    ) really needed. If C had the ability to "goto" a function rather than
    ) "call" a function, other compiler writers can take advantage of this
    ) feature to give their languages tail call elimination without costly
    ) tricks or having to resort to assembler.

    Again. If a compiler were to *guarantee* that it does tail call
    elimination (perhaps with certain restrictions) then this point
    becomes moot.


    So, perhaps you should go looking for a compiler that makes such
    guarantees.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
     
    Willem, Jan 6, 2009
    #1
    1. Advertising

  2. In article <>,
    Blake McBride <> wrote:
    >Willem wrote:
    >>
    >> So, perhaps you should go looking for a compiler that makes such
    >> guarantees.

    >
    >Depending on a specific compiler destroys the whole reason for using C
    >as a portable assembler. It must be a standards change.


    That's not really true if, say, the specific compiler is gcc or
    something from MS. I have no real problem depending on gcc for my
    programs, since gcc is implemented just about everywhere.

    And, coincidentally enough, gcc does things along the lines of which you
    speak (I don't want to speak to specifics, but you get the drift).
     
    Kenny McCormack, Jan 6, 2009
    #2
    1. Advertising

  3. Willem

    Guest

    On Jan 6, 12:47 pm, Blake McBride <> wrote:
    > Willem wrote:
    >
    > > So, perhaps you should go looking for a compiler that makes such
    > > guarantees.

    >
    > Depending on a specific compiler destroys the whole reason for using C
    > as a portable assembler.  It must be a standards change.


    Except the problems you are seeking to solve would not be solved by a
    standards change.

    C++ does not place performance requirements on the code that compilers
    generate. Adding computed gotos and function gotos would *not*
    guarantee that you get jump tables and lightweight function jumps.
    That is simply outside the scope of the language. You would still end
    up relying on a specific compiler that optimized those constructs the
    way you wanted them to be optimized.

    The standard will never include wording that mandates, for example,
    that "function gotos" be implemented with tail call optimizations.
    Those details will always be implementation defined.

    Also, while such "optimized" (quoted because C++ would not guarantee
    any optimization) constructs are certainly useful in a VM application,
    their use in such a specialized type of application, IMHO, is not
    sufficient motivation for a language change.

    By the way, the place to discuss the standard is comp.std.c++; it is a
    moderated group and usually more appropriate (although it was down for
    a while recently, but seems to be happily up and running now).

    Jason
     
    , Jan 6, 2009
    #3
  4. Willem

    Guest

    On Jan 6, 12:26 pm, Willem <> wrote:
    > Case statements were *invented* to be turned into index-and-branch.


    Incidentally, since you mention it, I did observe on at least one
    occasion MSVC turning a switch statement into a jump table. I have a
    hard time reproducing that behavior at will, though. IIRC it was in a
    fairly old version of the compiler, VC 4.0 maybe.

    Jason
     
    , Jan 6, 2009
    #4
  5. Willem

    red floyd Guest

    On Jan 6, 10:16 am, ""
    <> wrote:
    > On Jan 6, 12:26 pm, Willem <> wrote:
    >
    > > Case statements were *invented* to be turned into index-and-branch.

    >
    > Incidentally, since you mention it, I did observe on at least one
    > occasion MSVC turning a switch statement into a jump table. I have a
    > hard time reproducing that behavior at will, though. IIRC it was in a
    > fairly old version of the compiler, VC 4.0 maybe.



    Heck, on an old Z8000 ZEUS compiler, switch statements were converted
    into jump tables. This was back in the mid-80s.
     
    red floyd, Jan 6, 2009
    #5
  6. wrote:
    > On Jan 6, 12:26 pm, Willem <> wrote:
    >> Case statements were *invented* to be turned into index-and-branch.

    >
    > Incidentally, since you mention it, I did observe on at least one
    > occasion MSVC turning a switch statement into a jump table. I have a
    > hard time reproducing that behavior at will, though. IIRC it was in a
    > fairly old version of the compiler, VC 4.0 maybe.


    The easiest way to persuade your compiler to do this optimization is to
    have a long list of cases with sequential values. Large holes in the
    sequence cause the jump table to get excessively large, and if the list
    is too short, the compiler may decide that it's faster to use some other
    method (like a binary search).

    This optimization is especially useful when every case consists of a
    single function call (all of the same signature, including the same
    parameters if any) and then a break. The compiler can turn the entire
    thing into one indirect call via the jump table. For less uniform
    cases, all it can do is turn it into an indirect goto. You can directly
    write the former yourself if you want to be sure that's what you get,
    but you can't do the latter in standard C.

    S
     
    Stephen Sprunk, Jan 6, 2009
    #6
  7. In article <1231272028.168873@news1nwk>,
    Eric Sosman <> wrote:

    > You'll typically get at least one comparison to see whether
    >the index is in the range of covered cases.


    This was one of the disappointments of C89: many people had assumed
    that enum types would be sufficiently constrained that a switch-on-enum
    would not need such a check.

    > IMHO the opportunity for optimization is pretty slight unless
    >*very* little work is being done in each `case'


    But there is an important use case in which this is true: implementing
    virtual machines.

    -- Richard
    --
    Please remember to mention me / in tapes you leave behind.
     
    Richard Tobin, Jan 6, 2009
    #7
  8. In article <>,
    christian.bau <> wrote:

    >> This was one of the disappointments of C89: many people had assumed
    >> that enum types would be sufficiently constrained that a switch-on-enum
    >> would not need such a check.


    >You could just add
    >
    > default: i = i++;
    >
    >as the last case. That would allow the compiler to remove the check


    Unfortunately it would also allow the compiler to do various other
    things :)

    In practice, we resorted to editing the assembler output of the
    compiler to remove the check. It produced, IIRC, a speedup of about
    10%, which is certainly worthwhile when using C to implement another
    programming language.

    -- Richard

    --
    Please remember to mention me / in tapes you leave behind.
     
    Richard Tobin, Jan 6, 2009
    #8
  9. Willem

    JC Guest

    On Jan 6, 5:34 pm, "christian.bau" <>
    wrote:
    > On Jan 6, 9:34 pm, (Richard Tobin) wrote:
    >
    > > This was one of the disappointments of C89: many people had assumed
    > > that enum types would be sufficiently constrained that a switch-on-enum
    > > would not need such a check.

    >
    > You could just add
    >
    >     default: i = i++;
    >
    > as the last case. That would allow the compiler to remove the check
    > (because if the check fails, behaviour of this code would be
    > undefined).


    I do know that the MS compiler provides an __assume() extension that
    lets you tell the compiler something that is absolutely known to be
    true, in hopes that you can give it a little more info for
    optimizations.

    You can use it to eliminate the default block of a switch statement
    (this is, in fact, their example usage of __assume):

    switch (value) {
    case ...: ...;
    case ...: ...;
    default: __assume(0);
    }

    I don't know if other compilers have similar extensions. I think I've
    used __assume() exactly once, though, and not in a serious project.

    Jason
     
    JC, Jan 6, 2009
    #9
  10. Willem

    Grizlyk Guest

    On Jan 6, 9:14 pm, "" wrote:
    > C++ does not place performance requirements on the code that compilers
    > generate. ...
    > That is simply outside the scope of the language.


    This is not performance question. We are speaking here about usage of
    something, that can not be reached by languge in other way. "VLA" in
    stack, "moveable data type" are other examples of the "something". As
    for me, i no need the futures with goto, but if any want why not?
    Other question is "how to set the properties under compier control",
    to avoid raw usage of pointers, to make auto-fill of jump array.
     
    Grizlyk, Jan 7, 2009
    #10
  11. Willem

    Guest

    On Jan 7, 12:06 am, Grizlyk <> wrote:
    > On Jan 6, 9:14 pm, "" wrote:
    >
    > > C++ does not place performance requirements on the code that compilers
    > > generate. ...
    > > That is simply outside the scope of the language.

    >
    > This is not performance question.


    It *is* a performance question -- the OP's motivation for these
    changes are entirely performance related. Performance is outside the
    scope of the language, however, and even if the proposed changes were
    adopted they would not be guaranteed to solve the problem they were
    intended to solve (which was, performance issues).

    > We are speaking here about usage of
    > something, that can not be reached by languge in other way.


    There were two proposed additions: computed gotos and function gotos.
    Both of these are already possible with C and C++. Computed gotos can
    be accomplished by using function pointers. Function gotos can be
    accomplished by simply calling functions. Both of these achieve the
    same end effect as the proposed changes. The difference is that these
    approaches do not meet the OP's performance requirements.

    > "VLA" in
    > stack, "moveable data type" are other examples of the "something".


    Neither VLAs nor "movable data types" were mentioned in the proposed
    additions.

    > As
    > for me, i no need the futures with goto, but if any want why not?


    Avoiding feature bloat is a compelling reason. If a new feature is
    added to the language it should be sufficiently motivated and provide
    features and guarantees that are not otherwise available. I agree with
    you that the proposed changes would not cause any direct harm, but I
    feel they would not provide a significant benefit either (mainly
    because the standard can not provide the performance guarantees that
    the OP seeks).

    > Other question is "how to set the properties under compier control",
    > to avoid raw usage of pointers, to make auto-fill of jump array.


    Apologies if I'm misunderstanding your question (please rephrase it if
    I am). The computed gotos, as suggested, do not require usage of raw
    pointers. Instead, you would initialize the jump array with standard
    goto labels (something similar is already a GCC extension, as
    mentioned by others), e.g.:

    void f (void) {

    jump_dest jmps[] = { label1, label2, label3 };

    goto jmps[rand() % 3];

    label1:
    // some code
    return;

    label2:
    // some code
    return

    label3:
    // some code
    return

    }


    Jason
     
    , Jan 7, 2009
    #11
  12. Willem

    JC Guest

    On Jan 7, 1:09 am, (blargg) wrote:
    > Hahah, maintenance programmers would love that!
    >
    >     switch ( x )
    >     {
    >     ...
    >     default:
    >         int i = i++; // 10% performance increase. DO NOT REMOVE!
    >     }
    >
    > That's about as close as you can get to a magic line.


    I think I finally found a signature, hehe.

    --
    default:
    int i = i++; // 10% performance increase. DO NOT REMOVE!
     
    JC, Jan 7, 2009
    #12
  13. Willem

    red floyd Guest

    Jeff Schwab wrote:
    > red floyd wrote:
    >> On Jan 6, 10:16 am, ""
    >> <> wrote:
    >>> On Jan 6, 12:26 pm, Willem <> wrote:
    >>>
    >>>> Case statements were *invented* to be turned into index-and-branch.
    >>> Incidentally, since you mention it, I did observe on at least one
    >>> occasion MSVC turning a switch statement into a jump table. I have a
    >>> hard time reproducing that behavior at will, though. IIRC it was in a
    >>> fairly old version of the compiler, VC 4.0 maybe.

    >>
    >>
    >> Heck, on an old Z8000 ZEUS compiler, switch statements were converted
    >> into jump tables. This was back in the mid-80s.

    >
    > I wonder whether any modern compilers turn if/else trees into jump
    > tables (when logically equivalent).


    Not only that, but the Z8000 compiler did jump tables for non-contiguous
    switch values, by iterating through two tables simultaneously -- a value
    table and a jump table. Of course, it helped that the Z8000 had
    hardware support for that (CPIR instruction)
     
    red floyd, Jan 7, 2009
    #13
  14. Willem

    James Kanze Guest

    On Jan 6, 6:26 pm, Willem <> wrote:
    > Blake McBride wrote:


    > > The use of this feature is in virtual machines. VM's
    > > typically process op-codes. These op-codes can be treated
    > > as indexes into the branch array. This would be very, very
    > > fast. I know C can use arrays of function pointers that can
    > > be indexed into and executed but the problem is that you
    > > have the (often huge) function overhead associated with each
    > > instruction. The other probable response is a case
    > > statement. The problem is that a case statement must do a
    > > lot of time-consuming compares in order get to the correct
    > > case. In index and branch is much faster. (I know case
    > > statement are optimized to a point but I don't think they
    > > are guaranteed to be as fast as an index and branch).


    > Case statements were *invented* to be turned into
    > index-and-branch. Do you agree that computed gotos would be a
    > moot point if compilers would *guarantee* that a case
    > statement (perhaps with some restrictions, such as only with
    > successive integers) would be turned into an index-and-branch?
    > Then why not ask for such a guarantee? That would be ten
    > times easier.


    Neither have the slightest chance. Computed goto's, because
    they are universally recognized as a misfeature, only useful for
    obfuscation. And requirements on *how* a compiler should
    implement a feature are not within the realm of the standard;
    one basic principle is that anything the compiler does is fine,
    as long as the observable behavior of the program is maintained.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 7, 2009
    #14
  15. Willem

    James Kanze Guest

    On Jan 6, 7:16 pm, ""
    <> wrote:
    > On Jan 6, 12:26 pm, Willem <> wrote:


    > > Case statements were *invented* to be turned into
    > > index-and-branch.


    > Incidentally, since you mention it, I did observe on at least
    > one occasion MSVC turning a switch statement into a jump
    > table. I have a hard time reproducing that behavior at will,
    > though. IIRC it was in a fairly old version of the compiler,
    > VC 4.0 maybe.


    I would expect most compilers use a jump table to implement
    switch when the cases form a dense set, and this is the fastest
    solution for the underlying hardware. (G++, Sun CC and VC++ all
    do, at least in the versions I have handy.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 7, 2009
    #15
  16. Willem

    James Kanze Guest

    On Jan 7, 7:56 am, red floyd <> wrote:
    > Jeff Schwab wrote:
    > > red floyd wrote:
    > >> On Jan 6, 10:16 am, ""
    > >> <> wrote:
    > >>> On Jan 6, 12:26 pm, Willem <> wrote:


    > >>>> Case statements were *invented* to be turned into index-and-branch.
    > >>> Incidentally, since you mention it, I did observe on at
    > >>> least one occasion MSVC turning a switch statement into a
    > >>> jump table. I have a hard time reproducing that behavior
    > >>> at will, though. IIRC it was in a fairly old version of
    > >>> the compiler, VC 4.0 maybe.


    > >> Heck, on an old Z8000 ZEUS compiler, switch statements were
    > >> converted into jump tables. This was back in the mid-80s.


    > > I wonder whether any modern compilers turn if/else trees
    > > into jump tables (when logically equivalent).


    > Not only that, but the Z8000 compiler did jump tables for
    > non-contiguous switch values, by iterating through two tables
    > simultaneously -- a value table and a jump table. Of course,
    > it helped that the Z8000 had hardware support for that (CPIR
    > instruction)


    Back when I was working on compilers (and the Z8000 was still
    around), the usual rule for handling switch statements was:

    if ( "dense" )
    generate bounds check and jump table
    else if ( "few entries" )
    generate linear lookup table, using index into jump
    table
    else
    generate inline binary search.

    In this context, "dense" would mean that the difference between
    the largest and the smallest entries was smaller than 2 or 3
    times the total number of entires (the exact cut-off point
    varied), and "few entries" depended on the hardware---for
    machines with hardware supported linear search (like the 8086 I
    was working on at the time), this value could be quite high.
    Some (not a lot) of the compilers would also look for dense
    subsets of entries, and use a lookup table for them.

    For modern machines, where an indirect jump could cause problems
    with branch prediction, I expect that the binary search is used
    far more often, perhaps even with dense switchs, provided there
    aren't too many entries.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 7, 2009
    #16
  17. Willem

    James Kanze Guest

    On Jan 6, 10:34 pm, (Richard Tobin) wrote:
    > In article <1231272028.168873@news1nwk>,
    > Eric Sosman <> wrote:


    > >You'll typically get at least one comparison to see whether
    > >the index is in the range of covered cases.


    > This was one of the disappointments of C89: many people had
    > assumed that enum types would be sufficiently constrained that
    > a switch-on-enum would not need such a check.


    > >IMHO the opportunity for optimization is pretty slight unless
    > >*very* little work is being done in each `case'


    > But there is an important use case in which this is true:
    > implementing virtual machines.


    I don't think so. If performance isn't an issue, the virtual
    machine will just use a table of pointers to functions. If it
    is an issue, the virtual machine will compile larger blocks to
    machine code, using all of the standard optimization techniques
    for this, including (usually) profiling information gathered
    when the block was executed earlier.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 7, 2009
    #17
  18. Willem

    James Kanze Guest

    On Jan 7, 12:02 am, (Richard Tobin) wrote:
    > In article
    > <>,


    > christian.bau <> wrote:
    > >> This was one of the disappointments of C89: many people had
    > >> assumed that enum types would be sufficiently constrained
    > >> that a switch-on-enum would not need such a check.

    > >You could just add


    > > default: i = i++;


    > >as the last case. That would allow the compiler to remove the check


    > Unfortunately it would also allow the compiler to do various other
    > things :)


    > In practice, we resorted to editing the assembler output of
    > the compiler to remove the check. It produced, IIRC, a
    > speedup of about 10%, which is certainly worthwhile when using
    > C to implement another programming language.


    A "computed goto" or a goto through a variable would be useful
    when using C as an intermediate language, output from a compiler
    front end. Given its wide availability today, however, I expect
    most compiler front-ends would prefer GCC's RTL. (But I've not
    been active in compilers for a while, so I'm not sure.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 7, 2009
    #18
  19. Willem

    James Kanze Guest

    On Jan 7, 7:09 am, (blargg) wrote:
    > christian.bau wrote:
    > > On Jan 6, 9:34=A0pm, (Richard Tobin) wrote:
    > > > This was one of the disappointments of C89: many people
    > > > had assumed that enum types would be sufficiently
    > > > constrained that a switch-on-enum would not need such a
    > > > check.


    > > You could just add


    > > default: i = i++;


    > > as the last case. That would allow the compiler to remove
    > > the check (because if the check fails, behaviour of this
    > > code would be undefined).


    > Hahah, maintenance programmers would love that!


    > switch ( x )
    > {
    > ...
    > default:
    > int i = i++; // 10% performance increase. DO NOT REMOVE!
    > }


    > That's about as close as you can get to a magic line.


    Yes. It would require some documentation:). I'd also worry
    about any compiler which recognized it as undefined behavior
    (and so could provide the performance benefit) also outputting
    a warning about it.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 7, 2009
    #19
  20. In article <>,
    James Kanze <> wrote:

    >> But there is an important use case in which this is true:
    >> implementing virtual machines.


    >I don't think so. If performance isn't an issue, the virtual
    >machine will just use a table of pointers to functions. If it
    >is an issue, the virtual machine will compile larger blocks to
    >machine code


    Switching from interpreting virtual machine code in portable C to
    generating native code is a big step. Obviously the machine code
    itself has to vary from system to system, but so does support code for
    loading it, flushing caches, and so on. The maintenance burden is
    much higher. This is all very well if you're a large commercial
    company, but for many of us getting a 10-20% speedup in a portable
    version is quite worthwhile.

    -- Richard
    --
    Please remember to mention me / in tapes you leave behind.
     
    Richard Tobin, Jan 7, 2009
    #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. Omnicore Software
    Replies:
    1
    Views:
    456
    Tim Tyler
    Sep 29, 2003
  2. Jonathan Mcdougall
    Replies:
    2
    Views:
    522
    Kaz Kylheku
    Nov 3, 2005
  3. David Lee

    Features and standards

    David Lee, Mar 11, 2008, in forum: C Programming
    Replies:
    19
    Views:
    723
    Keith Thompson
    Mar 16, 2008
  4. Willem
    Replies:
    25
    Views:
    723
    Keith Thompson
    Jan 9, 2009
  5. user923005
    Replies:
    4
    Views:
    305
Loading...

Share This Page