A qfind_first_byte_of using a bitset in folly/Range.cpp

Summary: [Folly] A `qfind_first_byte_of` using a `bitset` in `folly/Range.cpp`.

With additions to the existing benchmark program.

Reviewed By: @nbronson

Differential Revision: D2465890

diff --git a/folly/Range.cpp b/folly/Range.cpp
index b11dfc45229b0efd4b18664e7bb6b20b6e0bfbe2..e0dcf0896cff963e9d6e84f53df4d6f2e7ae3623 100644 (file)
--- a/folly/Range.cpp
+++ b/folly/Range.cpp
@@ -22,6 +22,7 @@
 #if FOLLY_HAVE_EMMINTRIN_H
 #include <emmintrin.h>  // __v16qi
 #endif
+#include <bitset>
 #include <iostream>
 
 namespace folly {
@@ -136,6 +137,20 @@ size_t qfind_first_byte_of_byteset(const StringPiece haystack,
   return StringPiece::npos;
 }
 
+size_t qfind_first_byte_of_bitset(const StringPiece haystack,
+                                  const StringPiece needles) {
+  std::bitset<256> s;
+  for (auto needle : needles) {
+    s[(uint8_t)needle] = true;
+  }
+  for (size_t index = 0; index < haystack.size(); ++index) {
+    if (s[(uint8_t)haystack[index]]) {
+      return index;
+    }
+  }
+  return StringPiece::npos;
+}
+
 #if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6)
 
 template <bool HAYSTACK_ALIGNED>

diff --git a/folly/test/RangeFindBenchmark.cpp b/folly/test/RangeFindBenchmark.cpp
index 2194ebb45e9f83757f3dabf953df99124194f3cd..db8ce65307866da2af611987b4013017e69e9546 100644 (file)
--- a/folly/test/RangeFindBenchmark.cpp
+++ b/folly/test/RangeFindBenchmark.cpp
@@ -27,6 +27,9 @@ namespace folly { namespace detail {
 size_t qfind_first_byte_of_byteset(const StringPiece haystack,
                                    const StringPiece needles);
 
+size_t qfind_first_byte_of_bitset(const StringPiece haystack,
+                                  const StringPiece needles);
+
 size_t qfind_first_byte_of_nosse(const StringPiece haystack,
                                  const StringPiece needles);
 }}
@@ -192,6 +195,10 @@ BENCHMARK_RELATIVE(FindFirstOf1NeedlesByteSet, n) {
   findFirstOfRange(delims1, detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(FindFirstOf1NeedlesBitSet, n) {
+  findFirstOfRange(delims1, detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 const string delims2 = "bc";
@@ -212,6 +219,10 @@ BENCHMARK_RELATIVE(FindFirstOf2NeedlesByteSet, n) {
   findFirstOfRange(delims2, detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(FindFirstOf2NeedlesBitSet, n) {
+  findFirstOfRange(delims2, detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 const string delims4 = "bcde";
@@ -232,6 +243,10 @@ BENCHMARK_RELATIVE(FindFirstOf4NeedlesByteSet, n) {
   findFirstOfRange(delims4, detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(FindFirstOf4NeedlesBitSet, n) {
+  findFirstOfRange(delims4, detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 const string delims8 = "0123456b";
@@ -252,6 +267,10 @@ BENCHMARK_RELATIVE(FindFirstOf8NeedlesByteSet, n) {
   findFirstOfRange(delims8, detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(FindFirstOf8NeedlesBitSet, n) {
+  findFirstOfRange(delims8, detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 const string delims16 = "0123456789bcdefg";
@@ -272,6 +291,10 @@ BENCHMARK_RELATIVE(FindFirstOf16NeedlesByteSet, n) {
   findFirstOfRange(delims16, detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(FindFirstOf16NeedlesBitSet, n) {
+  findFirstOfRange(delims16, detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 const string delims32 = "!bcdefghijklmnopqrstuvwxyz_012345";
@@ -292,6 +315,10 @@ BENCHMARK_RELATIVE(FindFirstOf32NeedlesByteSet, n) {
   findFirstOfRange(delims32, detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(FindFirstOf32NeedlesBitSet, n) {
+  findFirstOfRange(delims32, detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 const string delims64 = "!bcdefghijklmnopqrstuvwxyz_"
@@ -313,6 +340,10 @@ BENCHMARK_RELATIVE(FindFirstOf64NeedlesByteSet, n) {
   findFirstOfRange(delims64, detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(FindFirstOf64NeedlesBitSet, n) {
+  findFirstOfRange(delims64, detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 template <class Func>
@@ -340,6 +371,10 @@ BENCHMARK_RELATIVE(FindFirstOfRandomByteSet, n) {
   findFirstOfRandom(detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(FindFirstOfRandomBitSet, n) {
+  findFirstOfRandom(detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 BENCHMARK(CountDelimsBase, n) {
@@ -358,6 +393,10 @@ BENCHMARK_RELATIVE(CountDelimsByteSet, n) {
   countHits(detail::qfind_first_byte_of_byteset, n);
 }
 
+BENCHMARK_RELATIVE(CountDelimsBitSet, n) {
+  countHits(detail::qfind_first_byte_of_bitset, n);
+}
+
 BENCHMARK_DRAW_LINE();
 
 BENCHMARK(FindFirstOfOffsetRange, n) {