Re: Processing Bit Fields (flag) that represent request as quickly/efficient as possible...is there better approach?
From: Eric Sosman (Eric.Sosman_at_sun.com)
Date: 08/31/04
- Next message: CBFalconer: "Re: C 99 compiler access"
- Previous message: Alan Balmer: "Re: -= No Line Wrap Curses.h =-"
- In reply to: mrhicks: "Processing Bit Fields (flag) that represent request as quickly/efficient as possible...is there better approach?"
- Next in thread: CBFalconer: "Re: Processing Bit Fields (flag) that represent request as quickly/efficient as possible...is there better approach?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 30 Aug 2004 18:38:02 -0400
mrhicks wrote:
> Hello all,
>
> I have a question regarding efficeny and how to find the best
> approach when trying to find flag with in a structure of bit fields. I
> have several structures which look similar to
>
>
> typedef unsigned long int uint32; /* 32 bits */
>
> // Up to 36 request flags, so this will take up to 3
> typedef struct {
> uint32 notUsed :24,
It may not be a concern, but this isn't portable. Only
signed and unsigned `int' (and `_Bool', in C99) are guaranteed
to work as bit-field base types; compilers are permitted to
accept other types, but aren't required to. Your `long' may
fall foul of this restriction if you ever change compilers.
Also, I'm not at all sure what purpose the `notUsed'
bit-field fulfils. In particular, it's very strange that
the width of `notUsed' plus the widths of the `flags??'
fields don't add to a multiple of 32. Why bother with
`notUsed' at all?
> flag36 :1,
> flag35 :1,
> ...
> flag2 :1,
> flag1 :1;
> } flag_def_t;
>
> typedef union {
> flag_def_t flags;
> uint32 packedData[ sizeof( flag_def_t ) ];
This array is almost certainly bigger than you want it
to be, possibly four or eight times bigger.
> } request_flags_t;
>
>
> For this project we are using what my lead calls Input and Output
> Data Stores. Data that needs to be transmitted or used elsewhere in
> the project are placed in my module's Output Data Store, which is a
> structure containing all outpust of my module. All data the module
> needs to process its logic is contained in the Input Data Stores. All
> the data for the Input Data Store is collected via a Data Router. The
> piece of information that is important to realize is that my module is
> part of the communications layer that is called at a rate of 100 Hz,
> while the other module may only be called at a rate of 10 Hz.
100Hz and 10Hz don't seem terribly demanding rates. What
sort of a CPU are you using? Data point: Long ago I got my
4MHz 8-bit Z80 to handle input at almost 2KHz, with plenty of
cycles left over for screen management and stuff. So you ought
to be able to service 100Hz with, say, a four-bit CPU operating
at around 200KHz.
> So my
> data router will pull in data from other module's Output Data Stores.
> So for the request flags these are or'd assignments like the
> following..
>
>
> //Module Level Globals
> request_flags_t idsComm;
>
> idsComm.flag2 |= odsModule1.flag2;
> idsComm.flga2 |= odsModule2.flag2.
> ...
>
> Okay, now what I need to do is determine if a flag for a request has
> been raised and issue that request as quickly as possible.
Again, I question the emphasis on speed when servicing
such an apparently undemanding load. If you speed everything
up fourfold, the only change may be to increase the CPU's
idle time from 99.5% to 99.9%.
> For now, I
> have some code that looks like
>
>
> void getStatusIfFlagPresent( void ) {
> static int iStarvedState = 0; // So lower request flags don't get
> starved
>
> // Determine if a flag is present, if not exist...
> if( idsComm.packedData[0] == 0x00 && idsComm.packedData[1] == 0x00
> )
> return;
>
> /*
> * Determine if a request needs to be submitted. To prevent
> starvation
> * for lower level each level, excluding last level, needs two
> conditions
> * to be met. For the lowest level the 2nd condition doesn't need
> to be met.
> *
> * 1) Check Request Flag is high
> * 2) If Current Starved State is greater than level starved no
> * flag must be present on the lower starved levels
> *
> */
> // Starved State 1
> if( idsComm.flags.flag36 == 0x1 &&
> ( (iStarvedState < 1) ||
> ( (idsComm.packedData[0] & 0x0007) == 0x00 &&
> (idsComm.packedData[1] & 0xFFFF) == 0x00 ) ) )
This appears to make a lot of unjustified assumptions about
how the compiler has arranged the bit-fields. You may have
verified those assumptions for the particular compiler you're
using at the moment, but the next compiler may do things in a
different way. It's also *very* strange to be applying 16-bit
mask constants to 32-bit integers; are you sure you haven't
overlooked something?
> {
>
> //Set up specific comm cmd router data
> iStarvedState = 0; // Starved State is incremented when
> command
> // is placed into the queue. Sometimes the
> // queue may be full, so we want to attempt
> // queue the same message on the next pass,
> // hence the starved state is equal to the
> // "Starved State 1" - minus one
> } else
>
> // Starved State 2
> if( idsComm.flags.flag35 == 0x1 &&
> ( (iStarvedState < 2) ||
> ( (idsComm.packedData[0] & 0x0003) == 0x00 &&
> (idsComm.packedData[1] & 0xFFFF) == 0x00 ) ) )
> {
>
> //Set up specific comm cmd router data
> iStarvedState = 1;
> } else
>
> // etc.....
>
> // Starved State 35
> if( idsComm.flags.flag2 == 0x1 &&
> ((iStarvedState < 36) || ((idsComm.packedData[1] & 0x1) ==
> 0x00)) ) {
>
> //Set up specific comm cmd router data
> iStarvedState = 35;
> } else
>
> // Starved State 36
> if( idsComm.flags.flag1 == 0x1 ) {
>
> //Set up specific comm cmd router data
> iStarvedState = 36;
> }
>
> }
>
>
> As you can see this can get quite long for all conditions. I was
> hoping for a more efficient way of performing all these checks. I need
> to make sure each request is serviced and that no starvation of other
> request flags happens, hence the starvation levels. Do anyone see a
> better approach that is faster? Thanks...
Faster and slower are, of course, implementation-dependent.
The only way to be sure is to measure -- and to realize that
your measurement is valid only for the measured configuration.
However, I think I can say with confidence that almost any
other approach would be "better" than writing out thirty-six
copies of essentially the same code and then trying to debug
it for subtle typos. See "Programming Pearls" by Jon Bentley.
The logic of what you're trying to do with these "starved
state" magic numbers escapes me; I think there may be something
going on elsewhere that you haven't shown. Or maybe my feeble
brain just rebels at trying to read this monstrosity ...
A few suggestions: First, abandon the bit-fields and just
use a couple of unsigned `int's or `long's or whatever you like.
You'll find it *far* easier to iterate over the bits in a single
object than to manage all those individual bit-fields -- as you've
apparently discovered by now, you can't make arrays of bit-fields.
Second, can your anti-starvation policy be reduced to a
simple mask? You'd start with a mask indicating that all
events are "eligible." Then when event 7, say, gets serviced
you'd make it "ineligible" for a while by turning off its bit
in the mask; this gives all the other events a chance and
prevents event 7 from hogging things. Events keep occurring
and getting serviced and becoming ineligible, and eventually
you AND the eligibility mask with the flags mask and get a
zero result. At that point you make all the events eligible
again and repeat the AND to see if a formerly-ineligible event
now wants attention. Pseudocode:
eligible = 0xFFF....;
for (;;) {
service_me = eligible & flags;
if (service_me != 0) {
/* find a set bit in `service_me', handle the
* corresponding event, and clear that bit
* out of `eligible'.
*/
}
else {
/* all flags have had at least one chance at
* service; make everybody eligible again.
*/
eligible = 0xFFF....;
}
}
Fancier anti-starvation policies could probably be built
out of just a few more masks, if needed. But at 100Hz, I don't
think very much sophistication is justifiable.
-- Eric.Sosman@sun.com
- Next message: CBFalconer: "Re: C 99 compiler access"
- Previous message: Alan Balmer: "Re: -= No Line Wrap Curses.h =-"
- In reply to: mrhicks: "Processing Bit Fields (flag) that represent request as quickly/efficient as possible...is there better approach?"
- Next in thread: CBFalconer: "Re: Processing Bit Fields (flag) that represent request as quickly/efficient as possible...is there better approach?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
