Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Ring Buffer Index

Reply
Thread Tools

Ring Buffer Index

 
 
David Merposa
Guest
Posts: n/a
 
      04-08-2009
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
 
Reply With Quote
 
 
 
 
Chris Dollin
Guest
Posts: n/a
 
      04-08-2009
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

 
Reply With Quote
 
 
 
 
Bart van Ingen Schenau
Guest
Posts: n/a
 
      04-08-2009
On Apr 8, 8:25*am, Richard <(E-Mail Removed)> wrote:
> (E-Mail Removed) (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
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      04-08-2009
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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
user923005
Guest
Posts: n/a
 
      04-08-2009
On Apr 7, 10:49*pm, David Merposa <(E-Mail Removed)> 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.
 
Reply With Quote
 
David Merposa
Guest
Posts: n/a
 
      04-10-2009
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
 
Reply With Quote
 
Flash Gordon
Guest
Posts: n/a
 
      04-10-2009
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
RING RING RING Dashing through the wind, In a four dog dragged sleigh. Oh the street we go, laughing all the way Mathematician C++ 0 12-24-2006 02:26 PM
Ring Ring This Away strawberry.lina@gmail.com Computer Support 3 11-05-2005 09:12 PM
Ring Ring This Away strawberry.lina@gmail.com Computer Support 0 11-05-2005 08:01 PM
Digi-slave L-Ring Ultra II LED Ring Light Jim Hawkins Digital Photography 0 08-16-2005 12:12 PM
Ring ring....ring ring.... Slumpy Computer Support 1 07-06-2003 10:57 PM



Advertisments