Settings Multiple bits at Once in a Bitset

Question

I am working on a toy file system, I am using a bitset to keep track of used and unused pages. I am using an array of ints (in order to use GCC's built in bit ops.) to represent the bitset. I am not using the std::bitset as it will not be available on the final environment (embedded system.).

Now according to Linux perf during the tests allocating files takes 35% of runtime of this, 45% of the time is lost setting bits using,

#define BIT_SET(a,b) ((a) |= (1ULL<<(b)))

inside a loop. According to perf 42% of the time is lost in or. Deleting is a bit faster but then most time is lost in and operation to clear the bits toggling the bits using xor did not made any difference.

Basically I am wondering if there are smarter ways to set multiple bits in one go. If user requests 10 pages of space just set all bits in one go, but the problem is space can span word boundries. or any GCC/Clang instrinsics that I should be aware of?

can't you just OR with a value representing all 10 bits set? — Psi
I can create the mask no problem but request may span word boundaries in the bit set i.e 3 pages from the end of 1 word and 4 pages from the beginning of one word. I am wondering if there some old school tricks to handle it other than bunch of if statements to check word boundaries. — Hamza Yerlikaya
I think we need more context here. Examples of usage. Data structure. Translation from "page number" to bit position — Support Ukraine
Don't use 1ULL << b, use the machine size. And I suspect that the problem is in the cycle you use to set the bits. If you want the solution in plain C, use that tag - C++ is only colloquial it seems. — linuxfan says Reinstate Monica
Good point by @linuxfan Use of 1ULL seems wrong when setting bits in an array of int But again - we just need more context (aka code) to help you — Support Ukraine

AShelly AShelly · Accepted Answer · 2019-02-22T19:54:57

You should be able to use a function like this to set multiple bits in a bitset at once:

void set_mask(word_t* bitset, word_t mask, int lowbit) {
  int index= lowbit / sizeof(word_t);
  int offset = lowbit % sizeof(word_t);
  bitset[index] |= (mask << offset);
  mask >>= (sizeof(word_t) - offset);
  bitset[index+1] |= mask
}

If the mask does not span a boundary, the 2nd word is ORd with 0, so it is unchanged. Doing it unconditionally may be faster than the test to see if it needs to be done. If testing shows otherwise, add an if (mask) before the last line.

Settings Multiple bits at Once in a Bitset

1 Answers