bitfields

From: Pink Floyd (floyd@south.mit.edu)
Date: 11/25/95


Does anyone know if bitfields are much less efficient than bitvectors?
For various reasons, I was considering the idea of switching all the
bitvectors over to bitfields, something like this:
currently, chars have an int affected_by, where each affect is predefined
to be a certain bit..  (e.g., AFF_SANCTUARY is (1 << 2) which is the third
bit).. you can have up to 32 bits if your system is 32 bit ints. (btw, 
don't take these literally, I don't remember what the actual value of 
AFF_SANC is, this is just example).  To see if a player is affected by a
certain affect, you do a bitwise AND:
 if (ch->affected_by & AFF_SANCTUARY)
   ...
This allows for easy checks of multiple affects:
 if (ch->affected_by & (AFF_1 | AFF_2 | AFF_3))
   /* will return true if affected_by has any of those bits set */

The way this would be done with bitfields would be to change the 
int affected_by to a bitfield:

#typedef unsigned int us;
struct affected_by_bitfield {
  us aff_sanctuary : 1;  /* this field is to take up 1 bit */
  us aff_hide      : 1;
  us aff_invis     : 1;
  ...
};
/* in char_data */
 ...
struct affected_by_bitfield affected_by;
 ...

Then, to test an affect you would do this:
 if (ch->affected_by.aff_invis)
 ...
To check multiple entries, you would use
 if (ch->affected_by.aff_invis || ch->affected_by.aff_hide)
   ...

I realize this would require a complete rewrite of many macros, but there
are some benefits to this.  One is that you can add an arbitrary number of
new affects, and if you break 32 you don't have to worry about dealing with
int affected_by1;
int affected_by2;
...
Also, you can put in many blanks for future expansion by doing this:
...
 aff_hide : 1
 extras   : 100
}
 then to add a new one, simply:
...
 aff_hide : 1
 aff_new  : 1
 extras   : 99  /* pfile is not corrupted */
}
 The size of the bitfield in bytes will be the number of bits allocated, 
divided by 8, rounded up.
None of this would be visible to the user, but it could make your code more
structured.
My question for you more experienced C programmers is, how do you think that 
this would affect efficiency?  I get the feeling that it could actually 
improve efficiency, as well as produce smaller code.
For the bitvectors, the operations required to check are this:
if (ch->affected_by & aff_bit)
 1. dereference ch pointer
 2. bitwise AND it with a constant (fast, but also required storage of that
	constant in memory)
 3. test if the result is true

for bitfield:
if (ch->affected_by.aff_bit)
 1. dereference ch pointer
 2. calculate offset of aff_bit (probably the bottleneck)
 3. test is result is true

Is this a correct analysis?  What are other reasons (not) to switch to 
bitfields?



This archive was generated by hypermail 2b30 : 12/07/00 PST