From: Giuseppe Ottaviano <ott@fb.com>
Date: Wed, 3 May 2017 21:58:40 +0000 (-0700)
Subject: Do not store inner_ in EliasFanoReader and BitVectorReader
X-Git-Tag: v2017.05.08.00~16
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=commitdiff_plain;h=71ca4d5eab4bfb45649e6338b6ff20c081ccc9f0

Do not store inner_ in EliasFanoReader and BitVectorReader

Summary: It is not used anywhere except for `previousValue`, but there it can be computed from the other fields. This reduces the `EliasFanoReader` size by 8 bytes.

Reviewed By: philippv, yfeldblum

Differential Revision: D4976704

fbshipit-source-id: 62bc63248b66649e483b59cb9ddf48dfd2c0e992
---

diff --git a/folly/experimental/BitVectorCoding.h b/folly/experimental/BitVectorCoding.h
index e2290fcd..a2985d9d 100644
--- a/folly/experimental/BitVectorCoding.h
+++ b/folly/experimental/BitVectorCoding.h
@@ -260,7 +260,6 @@ class BitVectorReader {
   void reset() {
     block_ = (bits_ != nullptr) ? folly::loadUnaligned<uint64_t>(bits_) : 0;
     outer_ = 0;
-    inner_ = -1;
     position_ = -1;
     value_ = kInvalidValue;
   }
@@ -276,10 +275,10 @@ class BitVectorReader {
     }
 
     ++position_;
-    inner_ = Instructions::ctz(block_);
+    auto inner = Instructions::ctz(block_);
     block_ = Instructions::blsr(block_);
 
-    return setValue();
+    return setValue(inner);
   }
 
   bool skip(size_t n) {
@@ -306,7 +305,6 @@ class BitVectorReader {
 
       reposition(dest);
       n = position_ + 1 - steps * Encoder::forwardQuantum;
-      // Correct inner_ will be set at the end.
     }
 
     size_t cnt;
@@ -319,10 +317,10 @@ class BitVectorReader {
 
     // Skip to the n-th one in the block.
     DCHECK_GT(n, 0);
-    inner_ = select64<Instructions>(block_, n - 1);
-    block_ &= (uint64_t(-1) << inner_) << 1;
+    auto inner = select64<Instructions>(block_, n - 1);
+    block_ &= (uint64_t(-1) << inner) << 1;
 
-    return setValue();
+    return setValue(inner);
   }
 
   bool skipTo(ValueType v) {
@@ -371,10 +369,10 @@ class BitVectorReader {
       block_ = folly::loadUnaligned<uint64_t>(bits_ + outer_);
     }
 
-    inner_ = Instructions::ctz(block_);
+    auto inner = Instructions::ctz(block_);
     block_ = Instructions::blsr(block_);
 
-    setValue();
+    setValue(inner);
     return true;
   }
 
@@ -410,8 +408,8 @@ class BitVectorReader {
   constexpr static ValueType kInvalidValue =
     std::numeric_limits<ValueType>::max();  // Must hold kInvalidValue + 1 == 0.
 
-  bool setValue() {
-    value_ = static_cast<ValueType>(8 * outer_ + inner_);
+  bool setValue(size_t inner) {
+    value_ = static_cast<ValueType>(8 * outer_ + inner);
     return true;
   }
 
@@ -425,7 +423,6 @@ class BitVectorReader {
   constexpr static size_t kLinearScanThreshold = 4;
 
   size_t outer_;
-  size_t inner_;
   size_t position_;
   uint64_t block_;
   ValueType value_;
diff --git a/folly/experimental/EliasFanoCoding.h b/folly/experimental/EliasFanoCoding.h
index 98ac516e..66679ca1 100644
--- a/folly/experimental/EliasFanoCoding.h
+++ b/folly/experimental/EliasFanoCoding.h
@@ -347,7 +347,6 @@ class UpperBitsReader {
   void reset() {
     block_ = start_ != nullptr ? folly::loadUnaligned<block_t>(start_) : 0;
     outer_ = 0;
-    inner_ = std::numeric_limits<size_t>::max();
     position_ = std::numeric_limits<size_t>::max();
     value_ = 0;
   }
@@ -363,10 +362,10 @@ class UpperBitsReader {
     }
 
     ++position_;
-    inner_ = size_t(Instructions::ctz(block_));
+    size_t inner = Instructions::ctz(block_);
     block_ = Instructions::blsr(block_);
 
-    return setValue();
+    return setValue(inner);
   }
 
   ValueType skip(size_t n) {
@@ -383,7 +382,6 @@ class UpperBitsReader {
 
       reposition(dest + steps * Encoder::forwardQuantum);
       n = position_ + 1 - steps * Encoder::forwardQuantum; // n is > 0.
-      // Correct inner_ will be set at the end.
     }
 
     size_t cnt;
@@ -396,10 +394,10 @@ class UpperBitsReader {
 
     // Skip to the n-th one in the block.
     DCHECK_GT(n, 0);
-    inner_ = select64<Instructions>(block_, n - 1);
-    block_ &= (block_t(-1) << inner_) << 1;
+    size_t inner = select64<Instructions>(block_, n - 1);
+    block_ &= (block_t(-1) << inner) << 1;
 
-    return setValue();
+    return setValue(inner);
   }
 
   // Skip to the first element that is >= v and located *after* the current
@@ -417,8 +415,7 @@ class UpperBitsReader {
       reposition(dest + Encoder::skipQuantum * steps);
       position_ = dest - 1;
 
-      // Correct inner_ and value_ will be set during the next()
-      // call at the end.
+      // Correct value_ will be set during the next() call at the end.
 
       // NOTE: Corresponding block of lower bits sequence may be
       // prefetched here (via __builtin_prefetch), but experiments
@@ -470,8 +467,9 @@ class UpperBitsReader {
     DCHECK_GT(position(), 0);
 
     size_t outer = outer_;
+    auto inner = size_t(value_) - 8 * outer_ + position_;
     block_t block = folly::loadUnaligned<block_t>(start_ + outer);
-    block &= (block_t(1) << inner_) - 1;
+    block &= (block_t(1) << inner) - 1;
 
     while (UNLIKELY(block == 0)) {
       DCHECK_GT(outer, 0);
@@ -479,7 +477,7 @@ class UpperBitsReader {
       block = folly::loadUnaligned<block_t>(start_ + outer);
     }
 
-    auto inner = 8 * sizeof(block_t) - 1 - Instructions::clz(block);
+    inner = 8 * sizeof(block_t) - 1 - Instructions::clz(block);
     return static_cast<ValueType>(8 * outer + inner - (position_ - 1));
   }
 
@@ -488,8 +486,8 @@ class UpperBitsReader {
   }
 
  private:
-  ValueType setValue() {
-    value_ = static_cast<ValueType>(8 * outer_ + inner_ - position_);
+  ValueType setValue(size_t inner) {
+    value_ = static_cast<ValueType>(8 * outer_ + inner - position_);
     return value_;
   }
 
@@ -505,7 +503,6 @@ class UpperBitsReader {
   const unsigned char* const start_;
   block_t block_;
   size_t outer_;  // Outer offset: number of consumed bytes in upper.
-  size_t inner_;  // Inner offset: (bit) position in current block.
   size_t position_;  // Index of current value (= #reads - 1).
   ValueType value_;
 };