Changeset d0c804297259976d08303935ebc0332aec812118

Timestamp:

05/01/08 15:21:03 (8 months ago)

Author:

krayouva <krayouva@…>

Parents:

1bc545c8942b47e034f824644b4834a991178afc

Children:

208885f7930551213d294117aa06fa7ebb1cf8b1

git-committer:

krayouva <krayouva@gmail.com> / 2008-05-01T01:21:03Z-0400

Message:

* Inlined bitwise vector operations + added benchmarks

Location:

c

Files:

• benchmark/bm_bitvector.c (modified) (3 diffs)
• include/bitvector.h (modified) (10 diffs)
• src/bitvector.c (modified) (2 diffs)

c/benchmark/bm_bitvector.c

@@ -36 +36 @@
 }
 
+static void cpp_bs_and_sparse()
+{
+    std::bitset<SCAN_SIZE> *_bs = new std::bitset<SCAN_SIZE>(bs);
+    *_bs &= bs;
+    delete _bs;
+}
+static void cpp_bs_or_sparse()
+{
+    std::bitset<SCAN_SIZE> *_bs = new std::bitset<SCAN_SIZE>(bs);
+    *_bs |= bs;
+    delete _bs;
+}
+static void cpp_bs_xor_sparse()
+{
+    std::bitset<SCAN_SIZE> *_bs = new std::bitset<SCAN_SIZE>(bs);
+    *_bs ^= bs;
+    delete _bs;
+}
+static void cpp_bs_not_sparse()
+{
+    std::bitset<SCAN_SIZE> *_bs = new std::bitset<SCAN_SIZE>(bs);
+    _bs->flip();
+    delete _bs;
+}
+static void cpp_bs_and_dense()
+{
+    cpp_bs_and_sparse();
+}
+static void cpp_bs_or_dense()
+{
+    cpp_bs_or_sparse();
+}
+static void cpp_bs_xor_dense()
+{
+    cpp_bs_xor_sparse();
+}
+static void cpp_bs_not_dense()
+{
+    cpp_bs_not_sparse();
+}
+
 static void cpp_bs_set_dense()
 {
@@ -72 +113 @@
 }
 
+static void ferret_bv_and_sparse()
+{
+    FrtBitVector * _bv = frt_bv_and(bv, bv);
+    free(_bv);
+}
+static void ferret_bv_or_sparse()
+{
+    FrtBitVector * _bv = frt_bv_or(bv, bv);
+    free(_bv);
+}
+static void ferret_bv_xor_sparse()
+{
+    FrtBitVector * _bv = frt_bv_xor(bv, bv);
+    free(_bv);
+}
+static void ferret_bv_not_sparse()
+{
+    FrtBitVector * _bv = frt_bv_not(bv);
+    free(_bv);
+}
+static void ferret_bv_and_dense()
+{
+    ferret_bv_and_sparse();
+}
+static void ferret_bv_or_dense()
+{
+    ferret_bv_or_sparse();
+}
+static void ferret_bv_xor_dense()
+{
+    ferret_bv_xor_sparse();
+}
+static void ferret_bv_not_dense()
+{
+    ferret_bv_not_sparse();
+}
+
 static void ferret_bv_set_sparse()
 {
@@ -124 +202 @@
     BM_ADD(cpp_bs_set_sparse);
     BM_ADD(cpp_bs_scan_sparse);
+    BM_ADD(cpp_bs_and_sparse);
+    BM_ADD(cpp_bs_or_sparse);
+    BM_ADD(cpp_bs_not_sparse);
+    BM_ADD(cpp_bs_xor_sparse);
+
     BM_ADD(cpp_bs_set_dense);
     BM_ADD(cpp_bs_scan_dense);
+    BM_ADD(cpp_bs_and_dense);
+    BM_ADD(cpp_bs_or_dense);
+    BM_ADD(cpp_bs_not_dense);
+    BM_ADD(cpp_bs_xor_dense);
 #endif
     BM_ADD(ferret_bv_set_sparse);
     BM_ADD(ferret_bv_scan_sparse);
+    BM_ADD(ferret_bv_and_sparse);
+    BM_ADD(ferret_bv_or_sparse);
+    BM_ADD(ferret_bv_not_sparse);
+    BM_ADD(ferret_bv_xor_sparse);
+
     BM_ADD(ferret_bv_set_dense);
     BM_ADD(ferret_bv_scan_dense);
+    BM_ADD(ferret_bv_and_dense);
+    BM_ADD(ferret_bv_or_dense);
+    BM_ADD(ferret_bv_not_dense);
+    BM_ADD(ferret_bv_xor_dense);
     BM_TEARDOWN(teardown);
 }

c/include/bitvector.h

@@ -218 +218 @@
  *   set
  */
-extern int frt_bv_recount(FrtBitVector *bv);
+extern FRT_ATTR_ALWAYS_INLINE
+int frt_bv_recount(FrtBitVector *bv)
+{
+    unsigned int extra = ((bv->size & 31) >> 3) + 1;
+    unsigned int len   = bv->size >> 5;
+    unsigned int idx, count = 0;
+
+    if (bv->extends_as_ones) {
+        for (idx = 0; idx < len; ++idx) {
+            count += frt_count_zeros(bv->bits[idx]);
+        }
+        switch (extra) {
+            case 4: count += frt_count_zeros(bv->bits[idx] | 0x00ffffff);
+            case 3: count += frt_count_zeros(bv->bits[idx] | 0xff00ffff);
+            case 2: count += frt_count_zeros(bv->bits[idx] | 0xffff00ff);
+            case 1: count += frt_count_zeros(bv->bits[idx] | 0xffffff00);
+        }
+    }
+    else {
+        for (idx = 0; idx < len; ++idx) {
+            count += frt_count_ones(bv->bits[idx]);
+        }
+        switch (extra) {
+            case 4: count += frt_count_ones(bv->bits[idx] & 0xff000000);
+            case 3: count += frt_count_ones(bv->bits[idx] & 0x00ff0000);
+            case 2: count += frt_count_ones(bv->bits[idx] & 0x0000ff00);
+            case 1: count += frt_count_ones(bv->bits[idx] & 0x000000ff);
+        }
+    }
+    return bv->count = count;
+}
 
 /**
@@ -341 +371 @@
 extern unsigned long frt_bv_hash(FrtBitVector *bv);
 
+extern FRT_ATTR_ALWAYS_INLINE
+void frt_bv_capa(FrtBitVector *bv, int capa, int size)
+{
+    int word_size = (size >> 5) + 1;
+    FRT_REALLOC_N(bv->bits, frt_u32, capa);
+    bv->capa = capa;
+    bv->size = size;
+    memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0),
+           sizeof(frt_u32) * (capa - word_size));
+}
+
+extern FRT_ATTR_ALWAYS_INLINE
+void frt_bv_recapa(FrtBitVector *bv, int new_capa)
+{
+    if (bv->capa < new_capa) {
+        FRT_REALLOC_N(bv->bits, frt_u32, new_capa);
+        memset(bv->bits + bv->capa, (bv->extends_as_ones ? 0xFF : 0),
+               sizeof(frt_u32) * (new_capa - bv->capa));
+        bv->capa = new_capa;
+    }
+}
+
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_and_i(FrtBitVector *bv, FrtBitVector *bv1,
+                           FrtBitVector *bv2)
+{
+    int i, size, word_size, capa = 4;
+
+    bv->extends_as_ones = (bv1->extends_as_ones & bv2->extends_as_ones);
+
+    if (bv1->extends_as_ones || bv2->extends_as_ones)
+         size = frt_max2(bv1->size, bv2->size);
+    else size = frt_min2(bv1->size, bv2->size);
+
+    word_size = (size >> 5) + 1;
+    capa = frt_max2(frt_round2(word_size), 4);
+
+    frt_bv_recapa(bv1, capa);
+    frt_bv_recapa(bv2, capa);
+    frt_bv_capa(bv, capa, size);
+
+    for (i = 0; i < word_size; i++)
+        bv->bits[i] = bv1->bits[i] & bv2->bits[i];
+
+    frt_bv_recount(bv);
+    return bv;
+}
+
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_or_i(FrtBitVector *bv,
+                          FrtBitVector *bv1, FrtBitVector *bv2)
+{
+    int i;
+    int max_size = frt_max2(bv1->size, bv2->size);
+    int word_size = (max_size >> 5) + 1;
+    int capa = frt_max2(frt_round2(word_size), 4);
+
+    bv->extends_as_ones = (bv1->extends_as_ones | bv2->extends_as_ones);
+    frt_bv_recapa(bv1, capa);
+    frt_bv_recapa(bv2, capa);
+    frt_bv_capa(bv, capa, max_size);
+
+    for (i = 0; i < word_size; i++) {
+        bv->bits[i] = bv1->bits[i] | bv2->bits[i];
+    }
+    frt_bv_recount(bv);
+    return bv;
+}
+
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_xor_i(FrtBitVector *bv,
+                           FrtBitVector *bv1, FrtBitVector *bv2)
+{
+    int i;
+    int max_size = frt_max2(bv1->size, bv2->size);
+    int word_size = (max_size >> 5) + 1;
+    int capa = frt_max2(frt_round2(word_size), 4);
+
+    bv->extends_as_ones = (bv1->extends_as_ones ^ bv2->extends_as_ones);
+    frt_bv_recapa(bv1, capa);
+    frt_bv_recapa(bv2, capa);
+    frt_bv_capa(bv, capa, max_size);
+
+    for (i = 0; i < word_size; i++) {
+        bv->bits[i] = bv1->bits[i] ^ bv2->bits[i];
+    }
+    frt_bv_recount(bv);
+    return bv;
+}
+
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_not_i(FrtBitVector *bv, FrtBitVector *bv1)
+{
+    int i;
+    int word_size = (bv1->size >> 5) + 1;
+    int capa = frt_max2(frt_round2(word_size), 4);
+
+    bv->extends_as_ones = !bv1->extends_as_ones;
+    frt_bv_capa(bv, capa, bv1->size);
+
+    for (i = 0; i < word_size; i++) {
+        bv->bits[i] = ~(bv1->bits[i]);
+    }
+    frt_bv_recount(bv);
+    return bv;
+}
+
 /**
  * ANDs two BitVectors (+bv1+ and +bv2+) together and return the resultant
@@ -349 +486 @@
  * @return A FrtBitVector with all bits set that are set in both bv1 and bv2
  */
-extern FrtBitVector *frt_bv_and(FrtBitVector *bv1, FrtBitVector *bv2);
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_and(FrtBitVector *bv1, FrtBitVector *bv2)
+{
+    return frt_bv_and_i(frt_bv_new(), bv1, bv2);
+}
 
 /**
@@ -359 +500 @@
  * @return A FrtBitVector with all bits set that are set in both bv1 and bv2
  */
-extern FrtBitVector *frt_bv_or(FrtBitVector *bv1, FrtBitVector *bv2);
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_or(FrtBitVector *bv1, FrtBitVector *bv2)
+{
+    return frt_bv_or_i(frt_bv_new(), bv1, bv2);
+}
+
 
 /**
@@ -369 +515 @@
  * @return A FrtBitVector with all bits set that are equal in bv1 and bv2
  */
-extern FrtBitVector *frt_bv_xor(FrtBitVector *bv1, FrtBitVector *bv2);
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_xor(FrtBitVector *bv1, FrtBitVector *bv2)
+{
+    return frt_bv_xor_i(frt_bv_new(), bv1, bv2);
+}
 
 /**
@@ -377 +527 @@
  * @return A FrtBitVector with all bits set that are set in both bv1 and bv2
  */
-extern FrtBitVector *frt_bv_not(FrtBitVector *bv);
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_not(FrtBitVector *bv)
+{
+    return frt_bv_not_i(frt_bv_new(), bv);
+}
 
 /**
@@ -387 +541 @@
  * @return bv1 with all bits set that where set in both bv1 and bv2
  */
-extern FrtBitVector *frt_bv_and_x(FrtBitVector *bv1, FrtBitVector *bv2);
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_and_x(FrtBitVector *bv1, FrtBitVector *bv2)
+{
+    return frt_bv_and_i(bv1, bv1, bv2);
+}
 
 /**
@@ -396 +554 @@
  * @return bv1
  */
-extern FrtBitVector *frt_bv_or_x(FrtBitVector *bv1, FrtBitVector *bv2);
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_or_x(FrtBitVector *bv1, FrtBitVector *bv2)
+{
+    return frt_bv_or_i(bv1, bv1, bv2);
+}
 
 /**
@@ -405 +567 @@
  * @return bv1
  */
-extern FrtBitVector *frt_bv_xor_x(FrtBitVector *bv1, FrtBitVector *bv2);
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_xor_x(FrtBitVector *bv1, FrtBitVector *bv2)
+{
+    return frt_bv_xor_i(bv1, bv1, bv2);
+}
 
 /**
@@ -413 +579 @@
  * @return A +bv+ with all it's bits flipped
  */
-extern FrtBitVector *frt_bv_not_x(FrtBitVector *bv);
+extern FRT_ATTR_ALWAYS_INLINE
+FrtBitVector *frt_bv_not_x(FrtBitVector *bv)
+{
+    return frt_bv_not_i(bv, bv);
+}
 
 #ifdef __cplusplus

c/src/bitvector.c

@@ -35 +35 @@
     bv->count = 0;
     bv->size = 0;
-}
-
-int bv_recount(BitVector *bv)
-{
-    unsigned int extra = ((bv->size & 31) >> 3) + 1;
-    unsigned int len   = bv->size >> 5;
-    unsigned int idx, count = 0;
-
-    if (bv->extends_as_ones) {
-        for (idx = 0; idx < len; ++idx) {
-            count += frt_count_zeros(bv->bits[idx]);
-        }
-        switch (extra) {
-            case 4: count += frt_count_zeros(bv->bits[idx] | 0x00ffffff);
-            case 3: count += frt_count_zeros(bv->bits[idx] | 0xff00ffff);
-            case 2: count += frt_count_zeros(bv->bits[idx] | 0xffff00ff);
-            case 1: count += frt_count_zeros(bv->bits[idx] | 0xffffff00);
-        }
-    }
-    else {
-        for (idx = 0; idx < len; ++idx) {
-            count += frt_count_ones(bv->bits[idx]);
-        }
-        switch (extra) {
-            case 4: count += frt_count_ones(bv->bits[idx] & 0xff000000);
-            case 3: count += frt_count_ones(bv->bits[idx] & 0x00ff0000);
-            case 2: count += frt_count_ones(bv->bits[idx] & 0x0000ff00);
-            case 1: count += frt_count_ones(bv->bits[idx] & 0x000000ff);
-        }
-    }
-    return bv->count = count;
 }
 
@@ -129 +98 @@
 }
 
-static INLINE void bv_capa(BitVector *bv, int capa, int size)
-{
-    int word_size = (size >> 5) + 1;
-    REALLOC_N(bv->bits, u32, capa);
-    bv->capa = capa;
-    bv->size = size;
-    memset(bv->bits + word_size, (bv->extends_as_ones ? 0xFF : 0),
-           sizeof(u32) * (capa - word_size));
-}
-
-static INLINE void bv_recapa(BitVector *bv, int new_capa)
-{
-    if (bv->capa < new_capa) {
-        REALLOC_N(bv->bits, u32, new_capa);
-        memset(bv->bits + bv->capa, (bv->extends_as_ones ? 0xFF : 0),
-               sizeof(u32) * (new_capa - bv->capa));
-        bv->capa = new_capa;
-    }
-}
-
-static BitVector *bv_and_i(BitVector *bv, BitVector *bv1, BitVector *bv2)
-{
-    int i;
-    int size;
-    int word_size;
-    int capa = 4;
-
-    bv->extends_as_ones = (bv1->extends_as_ones & bv2->extends_as_ones);
-
-    if (bv1->extends_as_ones || bv2->extends_as_ones)
-         size = max2(bv1->size, bv2->size);
-    else size = min2(bv1->size, bv2->size);
-
-    word_size = (size >> 5) + 1;
-    capa = max2(frt_round2(word_size), 4);
-
-    bv_recapa(bv1, capa);
-    bv_recapa(bv2, capa);
-    bv_capa(bv, capa, size);
-
-    for (i = 0; i < word_size; i++) {
-        bv->bits[i] = bv1->bits[i] & bv2->bits[i];
-    }
-
-    bv_recount(bv);
-    return bv;
-}
-
-BitVector *bv_and(BitVector *bv1, BitVector *bv2)
-{
-    return bv_and_i(bv_new(), bv1, bv2);
-}
-
-BitVector *bv_and_x(BitVector *bv1, BitVector *bv2)
-{
-    return bv_and_i(bv1, bv1, bv2);
-}
-
-static BitVector *bv_or_i(BitVector *bv, BitVector *bv1, BitVector *bv2)
-{
-    int i;
-    int max_size = max2(bv1->size, bv2->size);
-    int word_size = (max_size >> 5) + 1;
-    int capa = max2(frt_round2(word_size), 4);
-
-    bv->extends_as_ones = (bv1->extends_as_ones | bv2->extends_as_ones);
-    bv_recapa(bv1, capa);
-    bv_recapa(bv2, capa);
-    bv_capa(bv, capa, max_size);
-
-    for (i = 0; i < word_size; i++) {
-        bv->bits[i] = bv1->bits[i] | bv2->bits[i];
-    }
-    bv_recount(bv);
-    return bv;
-}
-
-BitVector *bv_or(BitVector *bv1, BitVector *bv2)
-{
-    return bv_or_i(bv_new(), bv1, bv2);
-}
-
-BitVector *bv_or_x(BitVector *bv1, BitVector *bv2)
-{
-    return bv_or_i(bv1, bv1, bv2);
-}
-
-static BitVector *bv_xor_i(BitVector *bv, BitVector *bv1, BitVector *bv2)
-{
-    int i;
-    int max_size = max2(bv1->size, bv2->size);
-    int word_size = (max_size >> 5) + 1;
-    int capa = max2(frt_round2(word_size), 4);
-
-    bv->extends_as_ones = (bv1->extends_as_ones ^ bv2->extends_as_ones);
-    bv_recapa(bv1, capa);
-    bv_recapa(bv2, capa);
-    bv_capa(bv, capa, max_size);
-
-    for (i = 0; i < word_size; i++) {
-        bv->bits[i] = bv1->bits[i] ^ bv2->bits[i];
-    }
-    bv_recount(bv);
-    return bv;
-}
-
-BitVector *bv_xor(BitVector *bv1, BitVector *bv2)
-{
-    return bv_xor_i(bv_new(), bv1, bv2);
-}
-
-BitVector *bv_xor_x(BitVector *bv1, BitVector *bv2)
-{
-    return bv_xor_i(bv1, bv1, bv2);
-}
-
-static BitVector *bv_not_i(BitVector *bv, BitVector *bv1)
-{
-    int i;
-    int word_size = (bv1->size >> 5) + 1;
-    int capa = max2(frt_round2(word_size), 4);
-
-    bv->extends_as_ones = !bv1->extends_as_ones;
-    bv_capa(bv, capa, bv1->size);
-
-    for (i = 0; i < word_size; i++) {
-        bv->bits[i] = ~(bv1->bits[i]);
-    }
-    bv_recount(bv);
-    return bv;
-}
-
-BitVector *bv_not(BitVector *bv1)
-{
-    return bv_not_i(bv_new(), bv1);
-}
-
-BitVector *bv_not_x(BitVector *bv1)
-{
-    return bv_not_i(bv1, bv1);
-}