folly/Range.cpp

   1 /*
   2  * Copyright 2013 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 //
  18 // @author Mark Rabkin (mrabkin@fb.com)
  19 // @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
  20 //
  21
  22 #include "folly/Range.h"
  23
  24 #include "folly/CpuId.h"
  25 #include "folly/Likely.h"
  26
  27 namespace folly {
  28
  29 /**
  30  * Predicates that can be used with qfind and startsWith
  31  */
  32 const AsciiCaseSensitive asciiCaseSensitive = AsciiCaseSensitive();
  33 const AsciiCaseInsensitive asciiCaseInsensitive = AsciiCaseInsensitive();
  34
  35 std::ostream& operator<<(std::ostream& os, const StringPiece& piece) {
  36   os.write(piece.start(), piece.size());
  37   return os;
  38 }
  39
  40 namespace detail {
  41
  42 size_t qfind_first_byte_of_memchr(const StringPiece& haystack,
  43                                   const StringPiece& needles) {
  44   size_t best = haystack.size();
  45   for (char needle: needles) {
  46     const void* ptr = memchr(haystack.data(), needle, best);
  47     if (ptr) {
  48       auto found = static_cast<const char*>(ptr) - haystack.data();
  49       best = std::min<size_t>(best, found);
  50     }
  51   }
  52   if (best == haystack.size()) {
  53     return StringPiece::npos;
  54   }
  55   return best;
  56 }
  57
  58 }  // namespace detail
  59
  60 namespace {
  61
  62 // build sse4.2-optimized version even if -msse4.2 is not passed to GCC
  63 size_t qfind_first_byte_of_needles16(const StringPiece& haystack,
  64                                      const StringPiece& needles)
  65   __attribute__ ((__target__("sse4.2"), noinline));
  66
  67 // helper method for case where needles.size() <= 16
  68 size_t qfind_first_byte_of_needles16(const StringPiece& haystack,
  69                                      const StringPiece& needles) {
  70   DCHECK_LE(needles.size(), 16);
  71   if (needles.size() <= 2 && haystack.size() >= 256) {
  72     // benchmarking shows that memchr beats out SSE for small needle-sets
  73     // with large haystacks.
  74     // TODO(mcurtiss): could this be because of unaligned SSE loads?
  75     return detail::qfind_first_byte_of_memchr(haystack, needles);
  76   }
  77   auto arr2 = __builtin_ia32_loaddqu(needles.data());
  78   for (size_t i = 0; i < haystack.size(); i+= 16) {
  79     auto arr1 = __builtin_ia32_loaddqu(haystack.data() + i);
  80     auto index = __builtin_ia32_pcmpestri128(arr2, needles.size(),
  81                                              arr1, haystack.size() - i, 0);
  82     if (index < 16) {
  83       return i + index;
  84     }
  85   }
  86   return StringPiece::npos;
  87 }
  88
  89 size_t qfind_first_byte_of_sse42(const StringPiece& haystack,
  90                                  const StringPiece& needles)
  91   __attribute__ ((__target__("sse4.2"), noinline));
  92
  93 size_t qfind_first_byte_of_sse42(const StringPiece& haystack,
  94                                  const StringPiece& needles) {
  95   if (UNLIKELY(needles.empty() || haystack.empty())) {
  96     return StringPiece::npos;
  97   } else if (needles.size() <= 16) {
  98     // we can save some unnecessary load instructions by optimizing for
  99     // the common case of needles.size() <= 16
 100     return qfind_first_byte_of_needles16(haystack, needles);
 101   }
 102
 103   size_t index = haystack.size();
 104   for (size_t i = 0; i < haystack.size(); i += 16) {
 105     size_t b = 16;
 106     auto arr1 = __builtin_ia32_loaddqu(haystack.data() + i);
 107     for (size_t j = 0; j < needles.size(); j += 16) {
 108       auto arr2 = __builtin_ia32_loaddqu(needles.data() + j);
 109       auto index = __builtin_ia32_pcmpestri128(arr2, needles.size() - j,
 110                                                arr1, haystack.size() - i, 0);
 111       b = std::min<size_t>(index, b);
 112     }
 113     if (b < 16) {
 114       return i + b;
 115     }
 116   };
 117   return StringPiece::npos;
 118 }
 119
 120 typedef decltype(qfind_first_byte_of_sse42) Type_qfind_first_byte_of;
 121
 122 // Aho, Hopcroft, and Ullman refer to this trick in "The Design and Analysis
 123 // of Computer Algorithms" (1974), but the best description is here:
 124 // http://research.swtch.com/sparse
 125 class FastByteSet {
 126  public:
 127   FastByteSet() : size_(0) { }  // no init of arrays required!
 128
 129   inline void add(uint8_t i) {
 130     if (!contains(i)) {
 131       dense_[size_] = i;
 132       sparse_[i] = size_;
 133       size_++;
 134     }
 135   }
 136   inline bool contains(uint8_t i) const {
 137     DCHECK_LE(size_, 256);
 138     return sparse_[i] < size_ && dense_[sparse_[i]] == i;
 139   }
 140
 141  private:
 142   uint16_t size_;  // can't use uint8_t because it would overflow if all
 143                    // possible values were inserted.
 144   uint8_t sparse_[256];
 145   uint8_t dense_[256];
 146 };
 147
 148 }  // namespace
 149
 150 namespace detail {
 151
 152 size_t qfind_first_byte_of_byteset(const StringPiece& haystack,
 153                                    const StringPiece& needles) {
 154   FastByteSet s;
 155   for (auto needle: needles) {
 156     s.add(needle);
 157   }
 158   for (size_t index = 0; index < haystack.size(); ++index) {
 159     if (s.contains(haystack[index])) {
 160       return index;
 161     }
 162   }
 163   return StringPiece::npos;
 164 }
 165
 166 size_t qfind_first_byte_of_nosse(const StringPiece& haystack,
 167                                  const StringPiece& needles) {
 168   if (UNLIKELY(needles.empty() || haystack.empty())) {
 169     return StringPiece::npos;
 170   }
 171   // The thresholds below were empirically determined by benchmarking.
 172   // This is not an exact science since it depends on the CPU, the size of
 173   // needles, and the size of haystack.
 174   if (haystack.size() == 1 ||
 175       (haystack.size() < 4 && needles.size() <= 16)) {
 176     return qfind_first_of(haystack, needles, asciiCaseSensitive);
 177   } else if ((needles.size() >= 4 && haystack.size() <= 10) ||
 178              (needles.size() >= 16 && haystack.size() <= 64) ||
 179              needles.size() >= 32) {
 180     return qfind_first_byte_of_byteset(haystack, needles);
 181   }
 182
 183   return qfind_first_byte_of_memchr(haystack, needles);
 184 }
 185
 186 auto const qfind_first_byte_of_fn =
 187   folly::CpuId().sse42() ? qfind_first_byte_of_sse42
 188                          : qfind_first_byte_of_nosse;
 189
 190 size_t qfind_first_byte_of(const StringPiece& haystack,
 191                            const StringPiece& needles) {
 192   return qfind_first_byte_of_fn(haystack, needles);
 193 }
 194
 195 }  // namespace detail
 196 }  // namespace folly