473,320 Members | 2,097 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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

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
Nov 14 '05 #1
3 2243
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.

--
Er*********@sun.com

Nov 14 '05 #2
mrhicks wrote:

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.

--
"Churchill and Bush can both be considered wartime leaders, just
as Secretariat and Mr Ed were both horses." - James Rhodes.
"We have always known that heedless self-interest was bad
morals. We now know that it is bad economics" - FDR

Nov 14 '05 #3
CBFalconer <cb********@yahoo.com> wrote in message news:<41***************@yahoo.com>...
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
Nov 14 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Tim Chmielewski | last post by:
For an auto-generated form I have the following order of fields: savevalues userid productcode PrintColour1_1 Colour1_1 Quantity_1 " " " " " " " ...
12
by: Ney André de Mello Zunino | last post by:
Hello. I have been having some trouble dealing with bit fields. The following is a simple program that demonstrates it. #include <iomanip> #include <iostream> struct instrucao_i {
6
by: S P Arif Sahari Wibowo | last post by:
Hi! I am thinking to have a client-side script doing processing on file downloading, basically the script will process a downloaded file from the server before it received by the user. For...
3
by: google | last post by:
I have a database with four table. In one of the tables, I use about five lookup fields to get populate their dropdown list. I have read that lookup fields are really bad and may cause problems...
6
by: James Radke | last post by:
Hello, I have a multithreaded windows NT service application (vb.net 2003) that I am working on (my first one), which reads a message queue and creates multiple threads to perform the processing...
7
by: WXS | last post by:
Vote for this idea if you like it here: http://lab.msdn.microsoft.com/productfeedback/viewfeedback.aspx?feedbackid=5fee280d-085e-4fe2-af35-254fbbe96ee9...
3
by: crescent_au | last post by:
hi all, i am creating a form that returns to itself like this: <form name="form1" action="<?php echo $_REQUEST; ?>" method="post"> Upon clicking submit, I want the form to return to "itself"...
3
by: bvlmv | last post by:
Greetings, I have a simple html/asp form that submits data to an access DB. The idea is when calling a record back from the db, the page will have an option to change certain fields (drop down)...
8
by: pt36 | last post by:
I have two pages one.html two.html page one.html have a form named form1 and a textarea named text1 man one write in the textarea text 1 page two.html have a form named form2 and a...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.