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

Discussion in 'C Programming' started by mrhicks, Aug 30, 2004.

  1. mrhicks

    mrhicks Guest

    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
    mrhicks, Aug 30, 2004
    #1
    1. Advertising

  2. mrhicks

    Eric Sosman Guest

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

    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, Aug 30, 2004
    #2
    1. Advertising

  3. mrhicks

    CBFalconer Guest

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

    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
    CBFalconer, Aug 31, 2004
    #3
  4. Re: Processing Bit Fields (flag) that represent request as quickly/efficient as possible...is there better approach?

    CBFalconer <> wrote in message news:<>...
    > 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
    James Dow Allen, Sep 1, 2004
    #4
    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. lucianodebarros
    Replies:
    3
    Views:
    4,628
    John O'Conner
    Feb 16, 2006
  2. Replies:
    3
    Views:
    1,719
    Timothy Bendfelt
    Jan 19, 2007
  3. Replies:
    9
    Views:
    941
    Juha Nieminen
    Aug 22, 2007
  4. Replies:
    10
    Views:
    471
    Chris Gonnerman
    Dec 14, 2007
  5. Mike -- Email Ignored

    Bit Order in Bit Fields

    Mike -- Email Ignored, May 2, 2009, in forum: C++
    Replies:
    0
    Views:
    367
    Mike -- Email Ignored
    May 2, 2009
Loading...

Share This Page