summaryrefslogtreecommitdiff
path: root/util
diff options
context:
space:
mode:
authorOri Bernstein <ori@markovcorp.com>2017-01-04 16:43:43 -0800
committerOri Bernstein <ori@markovcorp.com>2017-01-09 13:25:22 -0800
commit7f4f1776a930dc9b80f099ca869b0827bbc54383 (patch)
tree0bbbb0e07a9e09a6063034af58de94e360587c1f /util
parent6f1419495d556e914f5a4afa05c5f3cc8b0e1849 (diff)
downloadmc-7f4f1776a930dc9b80f099ca869b0827bbc54383.tar.gz
Speed up bitset.
Merge back Quentin's perf hacks.
Diffstat (limited to 'util')
-rw-r--r--util/bitset.c51
-rw-r--r--util/util.h1
2 files changed, 42 insertions, 10 deletions
diff --git a/util/bitset.c b/util/bitset.c
index 6e85c33..31049bf 100644
--- a/util/bitset.c
+++ b/util/bitset.c
@@ -106,6 +106,31 @@ size_t bscount(Bitset *bs)
return n;
}
+inline static int firstbit(size_t b)
+{
+ int n;
+
+ n = 0;
+ if (!(b & 0xffffffff)) {
+ n += 32;
+ b >>= 32;
+ }
+ if (!(b & 0xffff)) {
+ n += 16;
+ b >>= 16;
+ }
+ if (!(b & 0xff)) {
+ n += 8;
+ b >>= 8;
+ }
+ if (!(b & 0xf)) {
+ n += 4;
+ b >>= 4;
+ }
+ n += (char[16]){4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}[b & 0xf];
+ return n;
+}
+
/* A slightly tricky function to iterate over the contents
* of a bitset. It returns true immediately if 'elt' is in
* the bitset, otherwise it seeks forward to the next value
@@ -125,19 +150,25 @@ size_t bscount(Bitset *bs)
*/
int bsiter(Bitset *bs, size_t *elt)
{
- size_t i;
-
- for (i = *elt; i < bsmax(bs); i++) {
- while (i < bsmax(bs) && !bs->chunks[i / Sizetbits])
- i = (i + Sizetbits) & ~(Sizetbits - 1);
- if (bshas(bs, i)) {
- *elt = i;
- return 1;
- }
+ size_t b, t, i;
+
+ i = *elt;
+ t = i/Sizetbits;
+ if (t >= bs->nchunks)
+ return 0;
+ b = bs->chunks[t];
+ b &= ~((1ull << (i%Sizetbits)) - 1);
+ while (!b) {
+ ++t;
+ if (t >= bs->nchunks)
+ return 0;
+ b = bs->chunks[t];
}
- return 0;
+ *elt = Sizetbits*t + firstbit(b);
+ return 1;
}
+
/* Returns the largest value that the bitset can possibly
* hold. It's conservative, but scanning the entire bitset
* is a bit slow. This is mostly an aid to iterate over it. */
diff --git a/util/util.h b/util/util.h
index 80887f8..60a344b 100644
--- a/util/util.h
+++ b/util/util.h
@@ -83,6 +83,7 @@ int bsisempty(Bitset *set);
int bsiter(Bitset *bs, size_t *elt);
size_t bsmax(Bitset *bs);
size_t bscount(Bitset *bs);
+
/* inline for speed */
static inline int bshas(Bitset *bs, size_t elt)
{