Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Faster bit map lookup #38

Closed
benhj opened this issue Feb 16, 2016 · 1 comment
Closed

Faster bit map lookup #38

benhj opened this issue Feb 16, 2016 · 1 comment

Comments

@benhj
Copy link
Owner

benhj commented Feb 16, 2016

E.g. this allocator code:

int64_t bmp_alloc(uint64_t *bmp, int64_t slots){
  // search for the first 0 bit, set it to 1,
  // then return the slot
  // return -1 if nothing found
  slots /= 64; // checking 64 slots at a time
  for (int64_t loop = 0; loop < slots; loop++){
    if (*bmp == 0xFFFFFFFFFFFFFFFFLL){
      // this area is full, go to the next area
      bmp++;
      continue;
    }
    // we're guaranteed at least one bit is 0
    int pos = ffsll(~*bmp) - 1;
    *bmp |= 1LL << pos; // set the bit at pos
    return loop * 64 + pos;
  }
  return -1;
}

From http://syntheti.cc/article/kongs-garbage-collector/

Could be similarly used to do far quicker bitmap lookup. Presently, I'm checking bit by bit

@benhj
Copy link
Owner Author

benhj commented Feb 27, 2016

Done. (Note: if not in master, in debuggingSeek dev branch)

@benhj benhj closed this as completed Feb 27, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant