0

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?

Hamza Yerlikaya
  • 49,047
  • 44
  • 147
  • 241
  • 2
    can't you just OR with a value representing all 10 bits set? – Psi Jan 28 '19 at 18:26
  • 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 Jan 28 '19 at 18:29
  • Yeah - "can span word boundaries" - so you set say 4 bits in the first word and 6 in the next: just take an all-bits-on value and shift it once to leave those bits you need to OR in. Yes you could use some ifs or looping to handle N bits that may cross words, so - just do it. – Tony Delroy Jan 28 '19 at 18:29
  • 2
    I think we need more context here. Examples of usage. Data structure. Translation from "page number" to bit position – Support Ukraine Jan 28 '19 at 18:32
  • I think that "page number" means "which integer is being accessed" – Tim Randall Jan 28 '19 at 18:33
  • The obvious ways to speed it up are to combine the shift terms for multiple values and then do a single or operation with the variable. But that might mean you'd need to use a variadic macro that can take a list of bit positions. We will need more context. Crossing word boundaries is a separate problem. What size words are you using? (I could imagine they're smaller than 64-bit words given an embedded target.) . But you'll need to segregate bits so that you access the correct parts of a single word at a time — I don't think there's a way around that. – Jonathan Leffler Jan 28 '19 at 18:35
  • @4386427 Data structure is an array of `int`s. I use gcc intrinsics to search the array for free space. – Hamza Yerlikaya Jan 28 '19 at 18:39
  • @HamzaYerlikaya ok - but how do the user "access" this - you must have some function that the user call and some code that translate the users input into a call of BIT_SET. We need to see that code in order to help – Support Ukraine Jan 28 '19 at 18:41
  • 1
    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 Jan 28 '19 at 18:49
  • 1
    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 Jan 28 '19 at 18:55
  • Not sure but maybe this could be of interest: https://stackoverflow.com/questions/39321580/fastest-way-to-produce-a-mask-with-n-ones-starting-at-position-i – Support Ukraine Jan 28 '19 at 19:00
  • Some candidates: *[How to replace bits in a bitfield without affecting other bits using C (2011)](https://stackoverflow.com/q/5925755)*, and *[How do you set only certain bits of a byte in C without affecting the rest?](https://stackoverflow.com/q/4439078)* (2010) – Peter Mortensen Sep 13 '22 at 10:38

1 Answers1

0

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.

AShelly
  • 34,686
  • 15
  • 91
  • 152