Processing Bit Fields (flag) that represent request as quickly/efficient as possible...is there bett

[mrhicks]

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,
flag36 :1,
flag35 :1,
...
flag2 :1,
flag1 :1;
} flag_def_t;

typedef union {
flag_def_t flags;
uint32 packedData[ sizeof( flag_def_t ) ];
} 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. 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. 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 ) ) )
{

//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...

Mark

 

[Eric Sosman]

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.

 

[CBFalconer]

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,
flag36 :1,
flag35 :1,
...
flag2 :1,
flag1 :1;
} flag_def_t;

To start with, your struct is not valid. Bit fields are packed
into ints, not longs. The result of a set of bit fields is not
portable if you have to dump it to files, etc. You would be
better off simply defining a set of mask values for the various
fields.

 

[James Dow Allen]

You would be better off simply defining a set of mask values
for the various fields.

I agree that bit fields are nuisances that should be avoided,
since there is a simple straightforward alternative.

There is at least one exception however, where bit fields are
appropriate. The Motorola 68020 has special instructions that
process bit fields and save a few nanoseconds. Sun's compiler
would generate those opcodes only for data declared as bitfields.

James