Ring Buffer Index

Discussion in 'C Programming' started by David Merposa, Apr 8, 2009.

  1. Hello,

    We have some code that runs on Linux and Windows. The code uses a ring
    buffer. To "increment" the index of the ring buffer, the following
    construct is used:

    index = ++index % N;

    We recently had a review of this code, and my co-worker Tony and I
    pointed out to the guy who wrote this code--Sporty--that it is undefined
    behavior. The code currently "works" on both Linux and Windows, so he
    told us that if it works, don't fix it.

    While we agree with Sporty that it currently "works" on both Linux and
    Windows, we're a bit concerned that it may not "work" in the future.
    Sporty is like an old dog, and it is difficult if not impossible to
    teach him "new tricks".

    Here is an example program that demonstrates what I am talking about. It
    outputs the same (currently "correct") results (3 and 0) on Linux and
    Windows.

    #include <stdio.h>
    int main(void)
    {
    int x = 2;
    x = ++x % 32;
    printf("x = %d\n", x);
    x = 31;
    x = ++x % 32;
    printf("x = %d\n", x);
    return 0;
    }

    My question is: What to do about this? On the one hand, it's currently
    not a problem. But on the other hand, it seems like a time bomb waiting
    to go off.

    One thing to keep in mind is that our management recently told us to
    focus on the high priority tasks. Sporty says this is not a high
    priority task, and that we're wasting time whenever we bring it up. I
    fear that if we keep bringing this up, our jobs might be at risk. In
    this day and age, jobs are hard to come by, so having a job is a pretty
    fortunate thing. Still, it bugs me.

    Thanks
    --
    David
    David Merposa, Apr 8, 2009
    #1
    1. Advertising

  2. David Merposa

    Chris Dollin Guest

    Richard wrote:

    (re: `index = ++index % N;`)

    > I wonder if the pre-increment is as undefined as the post increment ....


    It is. In both cases, the same location is written to more than once
    before a sequence point, viz, the semicolon, resulting in explicitly
    undefined behaviour.

    > I don't see why it should since the pre increment is done before any
    > overwriting as part of the assignment in this case.


    What's your evidence? All that's required, as I understand it, is that
    the update implied by `++index` be complete before the next sequence
    point. /When/ before that sequence point is (deliberately) not specified.

    > Had there been another instance of a in the expression then yes.


    Don't you mean `index`, or have I missed something?

    > Just thinking out loud and inviting ridicule I know.


    I trust not.

    --
    "Why do our plans never work?" Ka D'Argo, /Farscape/

    Hewlett-Packard Limited registered no:
    registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England
    Chris Dollin, Apr 8, 2009
    #2
    1. Advertising

  3. On Apr 8, 8:25 am, Richard <> wrote:
    > (Gordon Burditt) writes:
    > >>We have some code that runs on Linux and Windows. The code uses a ring
    > >>buffer. To "increment" the index of the ring buffer, the following
    > >>construct is used:

    >
    > >>index = ++index % N;

    >
    > > index = (index+1) % N;

    >
    > > is quite clear and it removes the undefined behavior.

    >
    > I wonder if the pre-increment is as undefined as the post increment ....


    Yes, it is.

    >
    > I don't see why it should since the pre increment is done before any
    > overwriting as part of the assignment in this case. Had there been
    > another instance of a in the expression then yes. Just thinking out loud
    > and inviting ridicule I know.


    What makes you think that the result of the increment must be written
    to memory before the result of the assignment?

    This is a perfectly correct assembly translation of the line 'x = ++x
    % 32;':

    MOV [x], R0
    INC R0
    MOV R0, R1
    AND R1, 31
    MOV R1, [x]
    MOV R0, [x]

    Here, the result of '++x' is written to memory *last* and has the
    effect that the modulo operator is canceled.

    Comparatively, the correct version 'x = (x+1) % 32' could have
    resulted in the *shorter* assembly listing:

    MOV [x], R0
    INC R0
    AND R0, 31
    MOV R0, [x]

    This saves two MOV operations (one register-register and one to
    memory) and it clobbers fewer registers.

    Bart v Ingen Schenau
    Bart van Ingen Schenau, Apr 8, 2009
    #3
  4. David Merposa

    Eric Sosman Guest

    David Merposa wrote:
    > Hello,
    >
    > We have some code that runs on Linux and Windows. The code uses a ring
    > buffer. To "increment" the index of the ring buffer, the following
    > construct is used:
    >
    > index = ++index % N;
    >
    > We recently had a review of this code, and my co-worker Tony and I
    > pointed out to the guy who wrote this code--Sporty--that it is undefined
    > behavior. The code currently "works" on both Linux and Windows, so he
    > told us that if it works, don't fix it.


    Fix it. Even if it happens to do what's desired (just by
    chance), you're at the mercy of the compiler's whim. Install
    a new compiler version, or change the optimization level, or
    even just add an innocent-looking printf() twelve lines earlier,
    and all bets are off.

    Remember how those silent-movie villains would tie helpless
    damsels to the railroad tracks? The "nothing bad has happened
    yet" viewpoint calls for leaving the damsel where she is until
    after the train rolls over her.

    > While we agree with Sporty that it currently "works" on both Linux and
    > Windows, we're a bit concerned that it may not "work" in the future.
    > Sporty is like an old dog, and it is difficult if not impossible to
    > teach him "new tricks".


    I've not met your Sporty, but I'll take a guess that I'm
    an even older dog than he is. But I'm still capable of learning
    from experience (especially from bad experience), and you won't
    find *me* sniffing at the intake end of the running snow-blower,
    no, never again!

    --
    Eric Sosman
    lid
    Eric Sosman, Apr 8, 2009
    #4
  5. David Merposa

    user923005 Guest

    On Apr 7, 10:49 pm, David Merposa <> wrote:
    > Hello,
    >
    > We have some code that runs on Linux and Windows. The code uses a ring
    > buffer. To "increment" the index of the ring buffer, the following
    > construct is used:
    >
    > index = ++index % N;
    >
    > We recently had a review of this code, and my co-worker Tony and I
    > pointed out to the guy who wrote this code--Sporty--that it is undefined
    > behavior. The code currently "works" on both Linux and Windows, so he
    > told us that if it works, don't fix it.


    The correct version of that expression is:
    "If it ain't broke, don't fix it!"

    Unfortunately, it's broke. So fix it.

    > While we agree with Sporty that it currently "works" on both Linux and
    > Windows, we're a bit concerned that it may not "work" in the future.
    > Sporty is like an old dog, and it is difficult if not impossible to
    > teach him "new tricks".
    >
    > Here is an example program that demonstrates what I am talking about. It
    > outputs the same (currently "correct") results (3 and 0) on Linux and
    > Windows.
    >
    > #include <stdio.h>
    > int main(void)
    > {
    >    int x = 2;
    >    x = ++x % 32;
    >    printf("x = %d\n", x);
    >    x = 31;
    >    x = ++x % 32;
    >    printf("x = %d\n", x);
    >    return 0;
    >
    > }
    >
    > My question is: What to do about this? On the one hand, it's currently
    > not a problem. But on the other hand, it seems like a time bomb waiting
    > to go off.
    >
    > One thing to keep in mind is that our management recently told us to
    > focus on the high priority tasks. Sporty says this is not a high
    > priority task, and that we're wasting time whenever we bring it up. I
    > fear that if we keep bringing this up, our jobs might be at risk. In
    > this day and age, jobs are hard to come by, so having a job is a pretty
    > fortunate thing. Still, it bugs me.


    Relying upon undefined behavior to do what you hope is not a good
    idea.
    user923005, Apr 8, 2009
    #5
  6. Richard Heathfield wrote:

    <snip>

    > Getting rid of bugs ought to be a high priority task. Getting rid of
    > those who stop you getting rid of bugs is an even higher priority
    > task. If Sporty can't accept facts that contradict his point (see
    > 3.3 EXPRESSIONS: "Between the previous and next sequence point an
    > object shall have its stored value modified at most once by the
    > evaluation of an expression. Furthermore, the prior value shall be
    > accessed only to determine the value to be stored."), then getting
    > rid of /him/ is an even higher priority task.


    Good news. The short story is that Tony and I showed Sporty your post
    and convinced him that what he coded was really a problem. He has agreed
    to change it to the following form:

    index = (index + 1) % N;

    I should also point out that Sporty has a copy of the book C Unleashed,
    and has used it as a reference for some of the code he has written. If
    I'm not mistaken, you are one of the co-authors of that book?
    Regardless, I think he assumed that and it played a part in his
    "paradigm shift". I guess you really can teach an old dog new tricks.

    Thanks
    --
    David
    David Merposa, Apr 10, 2009
    #6
  7. David Merposa

    Flash Gordon Guest

    David Merposa wrote:
    > Richard Heathfield wrote:
    >
    > <snip>
    >
    >> Getting rid of bugs ought to be a high priority task. Getting rid of
    >> those who stop you getting rid of bugs is an even higher priority
    >> task. If Sporty can't accept facts that contradict his point (see 3.3
    >> EXPRESSIONS: "Between the previous and next sequence point an object
    >> shall have its stored value modified at most once by the evaluation of
    >> an expression. Furthermore, the prior value shall be accessed only to
    >> determine the value to be stored."), then getting rid of /him/ is an
    >> even higher priority task.

    >
    > Good news. The short story is that Tony and I showed Sporty your post
    > and convinced him that what he coded was really a problem. He has agreed
    > to change it to the following form:
    >
    > index = (index + 1) % N;


    That's good. You should also look at the warning options for the
    compiler. gcc at least can warn about the original code whan properly
    prompted, and I'm sure other compilers can as well.

    > I should also point out that Sporty has a copy of the book C Unleashed,
    > and has used it as a reference for some of the code he has written. If
    > I'm not mistaken, you are one of the co-authors of that book?
    > Regardless, I think he assumed that and it played a part in his
    > "paradigm shift". I guess you really can teach an old dog new tricks.


    He is one of the authors, and not the only one to post here. We also
    sometimes have members of the ISO C committee posting here, authors of
    other excellent books on C, and even sometimes a certain well known
    person with the initials DMR.
    --
    Flash Gordon
    Flash Gordon, Apr 10, 2009
    #7
    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. Ben Collingsworth

    need ring buffer source code

    Ben Collingsworth, Sep 5, 2003, in forum: C Programming
    Replies:
    6
    Views:
    8,701
    Kevin Easton
    Sep 6, 2003
  2. Mathematician
    Replies:
    0
    Views:
    559
    Mathematician
    Dec 24, 2006
  3. Roedy Green

    OT ring ring

    Roedy Green, Aug 5, 2007, in forum: Java
    Replies:
    4
    Views:
    371
    Mike Schilling
    Aug 5, 2007
  4. KSR
    Replies:
    4
    Views:
    1,945
  5. Andrea Crotti

    Ring Buffer & templates

    Andrea Crotti, Oct 28, 2010, in forum: C++
    Replies:
    8
    Views:
    1,134
    Andrea Crotti
    Oct 31, 2010
Loading...

Share This Page