Store pointers in EliasFanoReader and BitVectorReader only if quantum > 0

Summary:
No need to store the pointers to forward and skip arrays if
they're not used.

Reviewed By: luciang

Differential Revision: D4977014

fbshipit-source-id: 2ed13fdcd1561da1a294f5895f3a5e1b77f1701c

diff --git a/folly/Makefile.am b/folly/Makefile.am
index 6d93decd75ed2dc212a8cbae2902faf7f9d3fd89..e45325730976e11bc3c40399f5e630f501fe1fd6 100644 (file)
--- a/folly/Makefile.am
+++ b/folly/Makefile.am
@@ -107,6 +107,7 @@ nobase_follyinclude_HEADERS = \
        experimental/ThreadedRepeatingFunctionRunner.h \
        experimental/Bits.h \
        experimental/BitVectorCoding.h \
        experimental/ThreadedRepeatingFunctionRunner.h \
        experimental/Bits.h \
        experimental/BitVectorCoding.h \

+       experimental/CodingDetail.h \

        experimental/DynamicParser.h \
        experimental/DynamicParser-inl.h \
        experimental/ExecutionObserver.h \
        experimental/DynamicParser.h \
        experimental/DynamicParser-inl.h \
        experimental/ExecutionObserver.h \

diff --git a/folly/experimental/BitVectorCoding.h b/folly/experimental/BitVectorCoding.h
index d359293754a9faec152107e1e7cd8e6a70bf1fab..7561ae6c94e6dbf73407aabe0462e6a04d527c35 100644 (file)
--- a/folly/experimental/BitVectorCoding.h
+++ b/folly/experimental/BitVectorCoding.h
@@ -25,6 +25,7 @@
 #include <folly/Portability.h>
 #include <folly/Range.h>
 #include <folly/experimental/Bits.h>
 #include <folly/Portability.h>
 #include <folly/Range.h>
 #include <folly/experimental/Bits.h>

+#include <folly/experimental/CodingDetail.h>

 #include <folly/experimental/Instructions.h>
 #include <folly/experimental/Select64.h>
 #include <glog/logging.h>
 #include <folly/experimental/Instructions.h>
 #include <folly/experimental/Select64.h>
 #include <glog/logging.h>


@@ -233,10 +234,12 @@ struct BitVectorEncoder<Value, SkipValue, kSkipQuantum, kForwardQuantum>::
   size_t forwardPointers = 0;
 };
 
   size_t forwardPointers = 0;
 };
 

-template <class Encoder,
-          class Instructions = instructions::Default,
-          bool kUnchecked = false>
-class BitVectorReader {
+template <
+    class Encoder,
+    class Instructions = instructions::Default,
+    bool kUnchecked = false>
+class BitVectorReader : detail::ForwardPointers<Encoder::forwardQuantum>,
+                        detail::SkipPointers<Encoder::skipQuantum> {

  public:
   typedef Encoder EncoderType;
   typedef typename Encoder::ValueType ValueType;
  public:
   typedef Encoder EncoderType;
   typedef typename Encoder::ValueType ValueType;


@@ -245,10 +248,10 @@ class BitVectorReader {
   typedef typename Encoder::SkipValueType SkipValueType;
 
   explicit BitVectorReader(const typename Encoder::CompressedList& list)
   typedef typename Encoder::SkipValueType SkipValueType;
 
   explicit BitVectorReader(const typename Encoder::CompressedList& list)

-      : size_(list.size),
+      : detail::ForwardPointers<Encoder::forwardQuantum>(list.forwardPointers),
+        detail::SkipPointers<Encoder::skipQuantum>(list.skipPointers),

         bits_(list.bits),
         bits_(list.bits),

-        skipPointers_(list.skipPointers),
-        forwardPointers_(list.forwardPointers) {
+        size_(list.size) {

     reset();
 
     if (kUnchecked || UNLIKELY(list.size == 0)) {
     reset();
 
     if (kUnchecked || UNLIKELY(list.size == 0)) {


@@ -303,7 +306,7 @@ class BitVectorReader {
     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
       const size_t steps = position_ / Encoder::forwardQuantum;
       const size_t dest = folly::loadUnaligned<SkipValueType>(
     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
       const size_t steps = position_ / Encoder::forwardQuantum;
       const size_t dest = folly::loadUnaligned<SkipValueType>(

-          forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
+          this->forwardPointers_ + (steps - 1) * sizeof(SkipValueType));

 
       reposition(dest);
       n = position_ + 1 - steps * Encoder::forwardQuantum;
 
       reposition(dest);
       n = position_ + 1 - steps * Encoder::forwardQuantum;


@@ -347,7 +350,7 @@ class BitVectorReader {
     if (Encoder::skipQuantum > 0 && v - value_ > Encoder::skipQuantum) {
       size_t q = v / Encoder::skipQuantum;
       auto skipPointer = folly::loadUnaligned<SkipValueType>(
     if (Encoder::skipQuantum > 0 && v - value_ > Encoder::skipQuantum) {
       size_t q = v / Encoder::skipQuantum;
       auto skipPointer = folly::loadUnaligned<SkipValueType>(

-          skipPointers_ + (q - 1) * sizeof(SkipValueType));
+          this->skipPointers_ + (q - 1) * sizeof(SkipValueType));

       position_ = static_cast<SizeType>(skipPointer) - 1;
 
       reposition(q * Encoder::skipQuantum);
       position_ = static_cast<SizeType>(skipPointer) - 1;
 
       reposition(q * Encoder::skipQuantum);


@@ -429,6 +432,7 @@ class BitVectorReader {
 
   constexpr static size_t kLinearScanThreshold = 4;
 
 
   constexpr static size_t kLinearScanThreshold = 4;
 

+  const uint8_t* const bits_;

   uint64_t block_;
   SizeType outer_;
   SizeType position_;
   uint64_t block_;
   SizeType outer_;
   SizeType position_;


@@ -436,9 +440,6 @@ class BitVectorReader {
 
   SizeType size_;
   ValueType upperBound_;
 
   SizeType size_;
   ValueType upperBound_;

-  const uint8_t* const bits_;
-  const uint8_t* const skipPointers_;
-  const uint8_t* const forwardPointers_;

 };
 
 }}  // namespaces
 };
 
 }}  // namespaces

diff --git a/folly/experimental/CodingDetail.h b/folly/experimental/CodingDetail.h
new file mode 100644 (file)
index 0000000..10de64c
--- /dev/null
+++ b/folly/experimental/CodingDetail.h
@@ -0,0 +1,63 @@
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ * @author Giuseppe Ottaviano <ott@fb.com>
+ *
+ * Shared utils for BitVectorCoding.h and EliasFanoCoding.h.
+ */
+
+#pragma once
+
+namespace folly {
+namespace compression {
+namespace detail {
+
+/**
+ * Helpers to store pointers to forward and skip pointer arrays only
+ * if they are used, that is, the quantum is nonzero. If it is 0, the
+ * class is empty, and the member is static to keep the syntax valid,
+ * thus it will take no space in a derived class thanks to empty base
+ * class optimization.
+ */
+template <size_t>
+class ForwardPointers {
+ protected:
+  explicit ForwardPointers(const unsigned char* ptr) : forwardPointers_(ptr) {}
+  const unsigned char* const forwardPointers_;
+};
+template <>
+class ForwardPointers<0> {
+ protected:
+  explicit ForwardPointers(const unsigned char*) {}
+  constexpr static const unsigned char* const forwardPointers_{};
+};
+
+template <size_t>
+class SkipPointers {
+ protected:
+  explicit SkipPointers(const unsigned char* ptr) : skipPointers_(ptr) {}
+  const unsigned char* const skipPointers_;
+};
+template <>
+class SkipPointers<0> {
+ protected:
+  explicit SkipPointers(const unsigned char*) {}
+  constexpr static const unsigned char* const skipPointers_{};
+};
+}
+}
+}

diff --git a/folly/experimental/EliasFanoCoding.h b/folly/experimental/EliasFanoCoding.h
index 9276f96072d5a9e7eb2aa1b3f567d34b1477b28c..f7bef3a4f38eae8817b57387dfce555eea1d87a9 100644 (file)
--- a/folly/experimental/EliasFanoCoding.h
+++ b/folly/experimental/EliasFanoCoding.h
@@ -33,6 +33,7 @@
 #include <folly/Likely.h>
 #include <folly/Portability.h>
 #include <folly/Range.h>
 #include <folly/Likely.h>
 #include <folly/Portability.h>
 #include <folly/Range.h>

+#include <folly/experimental/CodingDetail.h>

 #include <folly/experimental/Instructions.h>
 #include <folly/experimental/Select64.h>
 #include <glog/logging.h>
 #include <folly/experimental/Instructions.h>
 #include <folly/experimental/Select64.h>
 #include <glog/logging.h>


@@ -332,14 +333,15 @@ struct EliasFanoEncoderV2<Value,
 namespace detail {
 
 template <class Encoder, class Instructions, class SizeType>
 namespace detail {
 
 template <class Encoder, class Instructions, class SizeType>

-class UpperBitsReader {
+class UpperBitsReader : ForwardPointers<Encoder::forwardQuantum>,
+                        SkipPointers<Encoder::skipQuantum> {

   typedef typename Encoder::SkipValueType SkipValueType;
  public:
   typedef typename Encoder::ValueType ValueType;
 
   explicit UpperBitsReader(const typename Encoder::CompressedList& list)
   typedef typename Encoder::SkipValueType SkipValueType;
  public:
   typedef typename Encoder::ValueType ValueType;
 
   explicit UpperBitsReader(const typename Encoder::CompressedList& list)

-      : forwardPointers_(list.forwardPointers),
-        skipPointers_(list.skipPointers),
+      : ForwardPointers<Encoder::forwardQuantum>(list.forwardPointers),
+        SkipPointers<Encoder::skipQuantum>(list.skipPointers),

         start_(list.upper) {
     reset();
   }
         start_(list.upper) {
     reset();
   }


@@ -380,9 +382,8 @@ class UpperBitsReader {
     // Use forward pointer.
     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
       const size_t steps = position_ / Encoder::forwardQuantum;
     // Use forward pointer.
     if (Encoder::forwardQuantum > 0 && n > Encoder::forwardQuantum) {
       const size_t steps = position_ / Encoder::forwardQuantum;

-      const size_t dest =
-        folly::loadUnaligned<SkipValueType>(
-            forwardPointers_ + (steps - 1) * sizeof(SkipValueType));
+      const size_t dest = folly::loadUnaligned<SkipValueType>(
+          this->forwardPointers_ + (steps - 1) * sizeof(SkipValueType));

 
       reposition(dest + steps * Encoder::forwardQuantum);
       n = position_ + 1 - steps * Encoder::forwardQuantum; // n is > 0.
 
       reposition(dest + steps * Encoder::forwardQuantum);
       n = position_ + 1 - steps * Encoder::forwardQuantum; // n is > 0.


@@ -412,9 +413,8 @@ class UpperBitsReader {
     // Use skip pointer.
     if (Encoder::skipQuantum > 0 && v >= value_ + Encoder::skipQuantum) {
       const size_t steps = v / Encoder::skipQuantum;
     // Use skip pointer.
     if (Encoder::skipQuantum > 0 && v >= value_ + Encoder::skipQuantum) {
       const size_t steps = v / Encoder::skipQuantum;

-      const size_t dest =
-        folly::loadUnaligned<SkipValueType>(
-            skipPointers_ + (steps - 1) * sizeof(SkipValueType));
+      const size_t dest = folly::loadUnaligned<SkipValueType>(
+          this->skipPointers_ + (steps - 1) * sizeof(SkipValueType));

 
       reposition(dest + Encoder::skipQuantum * steps);
       position_ = dest - 1;
 
       reposition(dest + Encoder::skipQuantum * steps);
       position_ = dest - 1;


@@ -507,8 +507,6 @@ class UpperBitsReader {
   // so a type that can hold either sizes or values is sufficient.
   using OuterType = typename std::common_type<ValueType, SizeType>::type;
 
   // so a type that can hold either sizes or values is sufficient.
   using OuterType = typename std::common_type<ValueType, SizeType>::type;
 

-  const unsigned char* const forwardPointers_;
-  const unsigned char* const skipPointers_;

   const unsigned char* const start_;
   block_t block_;
   SizeType position_; // Index of current value (= #reads - 1).
   const unsigned char* const start_;
   block_t block_;
   SizeType position_; // Index of current value (= #reads - 1).