Find first zero in bitrare
I have a bitmap
uint64_t bitmap[10000]
keep track of the resources allocated on the system. Now the question is how to efficiently find the first bit of unset (zero) in this bitmap?
I am aware that glibc has ffsll(unsigned long long)
to look up the first bit of the set, which I assume is using hardware instructions to do this.
To use this function in my case, first I need to initialize the array to set each bit to 1, and then when I do resource allocation I have to linearly search the array for the first not a single word. then use ffsll () to find the first bit of the set.
How can I make it faster?
Update: I am on an x86-64 processor.
source to share
You can maintain a bitmap tree to find the least significant bit efficiently. On a 64-bit processor, you only need to have a tree depth of 3 to keep track of 4096 64-bit elements, which means only three calls ffsll
.
Basically, this works by dividing the array into 64-word chunks and assigning each 64-bit index to each chunk. A little index word is set if the corresponding bit word has all bits. When you change a bit in a bitet, you adjust the corresponding index word.
Then you can build another array of indices on top to form the tree.
Each bit change requires a little extra work, but the total amount of extra work (and storage) is negligible compared to the savings you get from not having to linearly search your bitset when you need a free bit.
source to share
I'm not sure how you get much faster than this, but I am open to being proven wrong:
uint64_t bitmap[10000];
unsigned int i;
for (i = 0; i < (sizeof(bitmap) / sizeof(*bitmap)) && 0xFFFFFFFFFFFFFFFF == bitmap[i]; ++i);
const int bitInWord = ffsll(bitmap[i]);
const unsigned int firstZeroBit = bitInWord ? i * sizeof(*bitmap) * CHAR_BIT + bitInWord : 0;
source to share
If you are using a 32 bit processor, you do not want to do this. Rather use arrays of 32 bit ints. The loop over the array will be faster.
Also you can encode each value for 1 byte and then pre-store which is the first bit set in the byte. So when you find an integer that's not all 0xFFFFFFFF, you can just compare the bytes. If the first byte is not 0xFF, it is in that byte, etc.
So, if a byte is not 0xFF, that means it is one of 255 possible values for a byte. And each value has the first bit.
Another way to look at the problem is to break it down into chunks if possible. I don't know what your resource is, so I can't tell.
Also note that on the previous scan for the unfinished bit, it loops forward. If you keep the index of the previous result, you can simply start at the same index on the next search. Call this pos index and use it every time.
You can also create a small array of "free" indices every time you set a bit to zero, so when your "pos" reaches the end of the array, just start at one of the stored indices.
In other words, you really don't want to run such a long loop every time. This is your problem, not the last instruction to get the bits. Use index tracking as described above and it will run hundreds of times faster.