loops - Case where goto's cannot be removed (optimization)

Discussion in 'C Programming' started by anon.asdf@gmail.com, Aug 14, 2007.

  1. Guest

    Hi!

    The following code is a snippet where the goto's cannot be removed
    "without increasing code-size, or decreasing performance".

    /*********A**************/
    int var_other_thread;
    // value changed by another thread

    int var_this_thread;

    int array[100];

    #define EQUAL \
    var_this_thread == var_other_thread

    #define NOT_EQUAL \
    var_this_thread != var_other_thread

    void myfuncA(void)
    {
    if (EQUAL) goto label2;

    label1:
    var_this_thread = var_other_thread;

    label2:
    array[var_this_thread] = 1;
    if (NOT_EQUAL) goto label1;
    }
    /***********************/

    Actually one goto can be removed without worsening code-size or
    performance:

    /*********B**************/
    #define EQUAL \
    var_this_thread == var_other_thread

    void myfuncB(void)
    {
    if (EQUAL)
    goto here;
    while(1) {
    var_this_thread = var_other_thread;
    here:
    array[var_this_thread] = 1;
    if (EQUAL)
    break;
    }
    }
    /***********************/

    In terms of machine code, myfuncB(void) will be the same as
    myfuncA(void), right???


    hmm... the above example is not so good.
    I just realized that an optimization would be to leave the first
    conditional and always force the assignment, right? Example below:
    ->
    /*********C**************/
    #define NOT_EQUAL \
    var_this_thread != var_other_thread

    void myfuncC(void)
    {
    do {
    var_this_thread = var_other_thread;
    array[var_this_thread] = 1;
    } while (NOT_EQUAL);
    }
    /***********************/

    -anon.asdf
    , Aug 14, 2007
    #1
    1. Advertising

  2. Eric Sosman Guest

    wrote On 08/14/07 15:33,:
    > Hi!
    >
    > The following code is a snippet where the goto's cannot be removed
    > "without increasing code-size, or decreasing performance".
    >
    > /*********A**************/
    > int var_other_thread;
    > // value changed by another thread
    >
    > int var_this_thread;
    >
    > int array[100];
    >
    > #define EQUAL \
    > var_this_thread == var_other_thread
    >
    > #define NOT_EQUAL \
    > var_this_thread != var_other_thread
    >
    > void myfuncA(void)
    > {
    > if (EQUAL) goto label2;
    >
    > label1:
    > var_this_thread = var_other_thread;
    >
    > label2:
    > array[var_this_thread] = 1;
    > if (NOT_EQUAL) goto label1;
    > }
    > /***********************/


    void myfuncA(void)
    {
    do {
    array[var_this_thread = var_other_thread] = 1;
    } while (NOT_EQUAL);
    }

    Argument: The test for EQUAL is wasted, because if
    the two variables are equal it does no harm to copy one
    to the other. Yes, it takes time -- but eliminating the
    test and the conditional jump saves time, so it is by no
    means obvious that there's a net loss.

    <off-topic>

    Of course, neither the original nor my rewrite is
    any use at all in an actual multi-threaded program. And
    before anybody mentions it, no: `volatile' doesn't help.

    </off-topic>

    > Actually one goto can be removed without worsening code-size or
    > performance:
    >
    > /*********B**************/
    > #define EQUAL \
    > var_this_thread == var_other_thread
    >
    > void myfuncB(void)
    > {
    > if (EQUAL)
    > goto here;
    > while(1) {
    > var_this_thread = var_other_thread;
    > here:
    > array[var_this_thread] = 1;
    > if (EQUAL)
    > break;
    > }
    > }
    > /***********************/


    This doesn't remove a goto; it just changes the
    way it's spelled.

    > In terms of machine code, myfuncB(void) will be the same as
    > myfuncA(void), right???


    You'll need to ask your compiler; the C language
    itself cannot answer the question.

    > hmm... the above example is not so good.


    "Herein he was right."

    > I just realized that an optimization would be to leave the first
    > conditional and always force the assignment, right? Example below:
    > ->
    > /*********C**************/
    > #define NOT_EQUAL \
    > var_this_thread != var_other_thread
    >
    > void myfuncC(void)
    > {
    > do {
    > var_this_thread = var_other_thread;
    > array[var_this_thread] = 1;
    > } while (NOT_EQUAL);
    > }
    > /***********************/


    How about that? You arrived at the same answer I
    did, and disproved your own assertion that the gotos
    could not be removed. Inquiring minds want to know:
    Having refuted your own thesis, why did you press Send?

    --
    Eric Sosman, Aug 14, 2007
    #2
    1. Advertising

  3. Guest

    On Aug 14, 10:00 pm, Eric Sosman <> wrote:
    >
    > How about that? You arrived at the same answer I
    > did, and disproved your own assertion that the gotos
    > could not be removed. Inquiring minds want to know:
    > Having refuted your own thesis, why did you press Send?


    Hi Eric!

    Thank's for your kind reply. I hit send, since I wanted to know if the
    code structure (in terms of "if" and "goto") could be reformed, to an
    equivalent that does not use goto.
    (It is not possible.)

    I wanted an analysis of code structure (in terms of "if" and "goto")
    and not the contents...
    which were badly chosen (and I did not take the time to change it -
    sorry.): still the contents did reveal that one optimization - which
    is interesting nonetheless

    - anon.asdf
    , Aug 14, 2007
    #3
  4. Guest

    On Aug 14, 10:47 pm, wrote:
    > I wanted an analysis of code structure (in terms of "if" and "goto")
    > and not the contents...
    > which were badly chosen (and I did not take the time to change it -
    > sorry.): still the contents did reveal that one optimization - which
    > is interesting nonetheless


    Here is an example with better "content":

    /*******************/

    /* think of var_other_thread
    as increasing steadily from 0 to 100
    in another thread.

    var_this_thread is handled in this code!
    Think of it as 0 initially.
    */

    #define NEARBY_BELOW \
    (var_this_thread >= var_other_thread - 2) \
    && (var_this_thread <= var_other_thread) \

    #define NOT_NEARBY_BELOW \
    (var_this_thread < var_other_thread - 2) \
    || (var_this_thread > var_other_thread)

    /* only limited range is used -
    we're not going to fall of (wrap around)
    the (overflow) ends :)
    */

    void myfuncA(void)
    {
    if (NEARBY_BELOW) goto label2;

    label1:
    var_this_thread = var_other_thread - 2;

    label2:
    array[var_this_thread] = 1;
    if (NOT_NEARBY_BELOW) goto label1;

    var_this_thread++;
    }
    /*******************/

    (one goto could be removed - as was shown in the original post /
    **B**/)

    - Albert
    , Aug 14, 2007
    #4
  5. Army1987 Guest

    On Tue, 14 Aug 2007 16:00:38 -0400, Eric Sosman wrote:

    > wrote On 08/14/07 15:33,:
    >> Hi!
    >>
    >> The following code is a snippet where the goto's cannot be removed
    >> "without increasing code-size, or decreasing performance".
    >>
    >> /*********A**************/
    >> int var_other_thread;
    >> // value changed by another thread
    >>
    >> int var_this_thread;
    >>
    >> int array[100];
    >>
    >> #define EQUAL \
    >> var_this_thread == var_other_thread
    >>
    >> #define NOT_EQUAL \
    >> var_this_thread != var_other_thread
    >>
    >> void myfuncA(void)
    >> {
    >> if (EQUAL) goto label2;
    >>
    >> label1:
    >> var_this_thread = var_other_thread;
    >>
    >> label2:
    >> array[var_this_thread] = 1;
    >> if (NOT_EQUAL) goto label1;
    >> }
    >> /***********************/

    >
    > void myfuncA(void)
    > {
    > do {
    > array[var_this_thread = var_other_thread] = 1;
    > } while (NOT_EQUAL);
    > }
    >
    > Argument: The test for EQUAL is wasted, because if
    > the two variables are equal it does no harm to copy one
    > to the other. Yes, it takes time -- but eliminating the
    > test and the conditional jump saves time, so it is by no
    > means obvious that there's a net loss.
    >
    > <off-topic>
    >
    > Of course, neither the original nor my rewrite is
    > any use at all in an actual multi-threaded program. And
    > before anybody mentions it, no: `volatile' doesn't help.
    >
    > </off-topic>

    Why doesn't it?
    --
    Army1987 (Replace "NOSPAM" with "email")
    No-one ever won a game by resigning. -- S. Tartakower
    Army1987, Aug 14, 2007
    #5
  6. Eric Sosman Guest

    Army1987 wrote On 08/14/07 17:11,:
    > On Tue, 14 Aug 2007 16:00:38 -0400, Eric Sosman wrote:
    > [...]
    >>
    >><off-topic>
    >>
    >> Of course, neither the original nor my rewrite is
    >>any use at all in an actual multi-threaded program. And
    >>before anybody mentions it, no: `volatile' doesn't help.
    >>
    >></off-topic>

    >
    > Why doesn't it?


    <off-topic>

    In a system with multiple CPU's, multiple paths to
    multiple levels of memory (possibly NUMA), reordering of
    memory transactions, and all the other go-fast gimmickry,
    how long does it take for CPU 0 to observe that CPU 17
    has written a new value to location X? If CPU 17 writes
    to X and then to Y, will CPU 0 necessarily observe X
    change before Y, or might it see Y change before X?

    Visit comp.programming.threads for more details on
    why `volatile' is neither necessary nor sufficient for
    thread synchronization.

    </off-topic>

    --
    Eric Sosman, Aug 14, 2007
    #6
  7. On Aug 14, 9:47 pm, wrote:

    > Thank's for your kind reply. I hit send, since I wanted to know if the
    > code structure (in terms of "if" and "goto") could be reformed, to an
    > equivalent that does not use goto.
    > (It is not possible.)


    Of course the code can be written without goto's. It has been proven
    more than 30 years ago that any bit of code using goto's can be
    rewritten without them (however, it is not necessarily an
    improvement :)
    christian.bau, Aug 14, 2007
    #7
  8. Flash Gordon Guest

    wrote, On 14/08/07 22:01:
    > On Aug 14, 10:47 pm, wrote:
    >> I wanted an analysis of code structure (in terms of "if" and "goto")
    >> and not the contents...
    >> which were badly chosen (and I did not take the time to change it -
    >> sorry.): still the contents did reveal that one optimization - which
    >> is interesting nonetheless

    >
    > Here is an example with better "content":


    <snip>

    > void myfuncA(void)
    > {
    > if (NEARBY_BELOW) goto label2;
    >
    > label1:
    > var_this_thread = var_other_thread - 2;
    >
    > label2:
    > array[var_this_thread] = 1;
    > if (NOT_NEARBY_BELOW) goto label1;
    >
    > var_this_thread++;
    > }
    > /*******************/
    >
    > (one goto could be removed - as was shown in the original post /
    > **B**/)
    >
    > - Albert
    >


    Well, if I've not made any mistakes...
    void myfuncA(void)
    {
    switch (NEARBY_BELOW) {
    do {
    case 0: var_this_thread = var_other_thread - 2;
    default: array[var_this_thread] = 1;
    } while (NOT_NEARBY_BELOW);
    }
    var_this_thread++;
    }

    Not even one goto statement. Of course, it is late at night so I probabl
    have made a mistake. No repeated conditions. A loop construct to
    implement the loop.
    --
    Flash Gordon
    Flash Gordon, Aug 14, 2007
    #8
  9. JimS Guest

    On Tue, 14 Aug 2007 23:11:59 +0200, Army1987 <>
    wrote:

    >On Tue, 14 Aug 2007 16:00:38 -0400, Eric Sosman wrote:
    >


    >> void myfuncA(void)
    >> {
    >> do {
    >> array[var_this_thread = var_other_thread] = 1;
    >> } while (NOT_EQUAL);
    >> }
    >>
    >> Argument: The test for EQUAL is wasted, because if
    >> the two variables are equal it does no harm to copy one
    >> to the other. Yes, it takes time -- but eliminating the
    >> test and the conditional jump saves time, so it is by no
    >> means obvious that there's a net loss.
    >>
    >> <off-topic>
    >>
    >> Of course, neither the original nor my rewrite is
    >> any use at all in an actual multi-threaded program. And
    >> before anybody mentions it, no: `volatile' doesn't help.
    >>
    >> </off-topic>

    >Why doesn't it?


    volatile doesn't guarantee atomicity of operations.
    If I write

    volatile int x = 0;
    x++;

    That might likely come out as

    mov reg,[x]
    inc reg
    mov [x],reg

    then there's no reason that another thread can't come along in between
    those operations and change [x].

    Jim
    JimS, Aug 15, 2007
    #9
  10. Guest

    On Aug 15, 12:25 am, Flash Gordon <> wrote:
    > Well, if I've not made any mistakes...
    > void myfuncA(void)
    > {
    > switch (NEARBY_BELOW) {
    > do {
    > case 0: var_this_thread = var_other_thread - 2;
    > default: array[var_this_thread] = 1;
    > } while (NOT_NEARBY_BELOW);
    > }
    > var_this_thread++;
    >
    > }
    >
    > Not even one goto statement. Of course, it is late at night so I probabl
    > have made a mistake. No repeated conditions. A loop construct to
    > implement the loop.


    Hi Flash! That's really good! -Albert
    , Aug 15, 2007
    #10
  11. Flash Gordon Guest

    wrote, On 15/08/07 08:18:
    > On Aug 15, 12:25 am, Flash Gordon <> wrote:
    >> Well, if I've not made any mistakes...
    >> void myfuncA(void)
    >> {
    >> switch (NEARBY_BELOW) {
    >> do {
    >> case 0: var_this_thread = var_other_thread - 2;
    >> default: array[var_this_thread] = 1;
    >> } while (NOT_NEARBY_BELOW);
    >> }
    >> var_this_thread++;
    >>
    >> }
    >>
    >> Not even one goto statement. Of course, it is late at night so I probabl
    >> have made a mistake. No repeated conditions. A loop construct to
    >> implement the loop.

    >
    > Hi Flash! That's really good! -Albert


    No it isn't, it's absolutely horrible :)
    It actually breaks one thing I would expect to be in any serious coding
    standard, namely it jumps in to a loop.
    If you like it I suggest you search for Duffs Device which was my
    inspiration.
    --
    Flash Gordon
    Flash Gordon, Aug 15, 2007
    #11
    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. Robert Smith
    Replies:
    0
    Views:
    4,924
    Robert Smith
    Dec 8, 2005
  2. Kunal
    Replies:
    24
    Views:
    826
    Naren
    Dec 12, 2005
  3. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    831
    Thad Smith
    Nov 24, 2008
  4. higer
    Replies:
    8
    Views:
    316
  5. Me
    Replies:
    2
    Views:
    226
Loading...

Share This Page