folly/Range.cpp

   1 /*
   2  * Copyright 2015 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 // @author Mark Rabkin (mrabkin@fb.com)
  18 // @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
  19
  20 #include <folly/Range.h>
  21
  22 #if FOLLY_HAVE_EMMINTRIN_H
  23 #include <emmintrin.h>  // __v16qi
  24 #endif
  25 #include <iostream>
  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 namespace {
  36
  37 // It's okay if pages are bigger than this (as powers of two), but they should
  38 // not be smaller.
  39 constexpr size_t kMinPageSize = 4096;
  40 static_assert(kMinPageSize >= 16,
  41               "kMinPageSize must be at least SSE register size");
  42 #define PAGE_FOR(addr) \
  43   (reinterpret_cast<uintptr_t>(addr) / kMinPageSize)
  44
  45
  46 // Earlier versions of GCC (for example, Clang on Mac OS X, which is based on
  47 // GCC 4.2) do not have a full compliment of SSE builtins.
  48 #if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6)
  49 inline size_t nextAlignedIndex(const char* arr) {
  50    auto firstPossible = reinterpret_cast<uintptr_t>(arr) + 1;
  51    return 1 +                       // add 1 because the index starts at 'arr'
  52      ((firstPossible + 15) & ~0xF)  // round up to next multiple of 16
  53      - firstPossible;
  54 }
  55
  56 // build sse4.2-optimized version even if -msse4.2 is not passed to GCC
  57 size_t qfind_first_byte_of_needles16(const StringPiece haystack,
  58                                      const StringPiece needles)
  59   __attribute__ ((__target__("sse4.2"), noinline))
  60   FOLLY_DISABLE_ADDRESS_SANITIZER;
  61
  62 // helper method for case where needles.size() <= 16
  63 size_t qfind_first_byte_of_needles16(const StringPiece haystack,
  64                                      const StringPiece needles) {
  65   DCHECK(!haystack.empty());
  66   DCHECK(!needles.empty());
  67   DCHECK_LE(needles.size(), 16);
  68   if ((needles.size() <= 2 && haystack.size() >= 256) ||
  69       // must bail if we can't even SSE-load a single segment of haystack
  70       (haystack.size() < 16 &&
  71        PAGE_FOR(haystack.end() - 1) != PAGE_FOR(haystack.data() + 15)) ||
  72       // can't load needles into SSE register if it could cross page boundary
  73       PAGE_FOR(needles.end() - 1) != PAGE_FOR(needles.data() + 15)) {
  74     return detail::qfind_first_byte_of_nosse(haystack, needles);
  75   }
  76
  77   auto arr2 = __builtin_ia32_loaddqu(needles.data());
  78   // do an unaligned load for first block of haystack
  79   auto arr1 = __builtin_ia32_loaddqu(haystack.data());
  80   auto index = __builtin_ia32_pcmpestri128(arr2, needles.size(),
  81                                            arr1, haystack.size(), 0);
  82   if (index < 16) {
  83     return index;
  84   }
  85
  86   // Now, we can do aligned loads hereafter...
  87   size_t i = nextAlignedIndex(haystack.data());
  88   for (; i < haystack.size(); i+= 16) {
  89     void* ptr1 = __builtin_assume_aligned(haystack.data() + i, 16);
  90     auto arr1 = *reinterpret_cast<const __v16qi*>(ptr1);
  91     auto index = __builtin_ia32_pcmpestri128(arr2, needles.size(),
  92                                              arr1, haystack.size() - i, 0);
  93     if (index < 16) {
  94       return i + index;
  95     }
  96   }
  97   return StringPiece::npos;
  98 }
  99 #endif // FOLLY_HAVE_EMMINTRIN_H && GCC 4.6+
 100
 101 // Aho, Hopcroft, and Ullman refer to this trick in "The Design and Analysis
 102 // of Computer Algorithms" (1974), but the best description is here:
 103 // http://research.swtch.com/sparse
 104 class FastByteSet {
 105  public:
 106   FastByteSet() : size_(0) { }  // no init of arrays required!
 107
 108   inline void add(uint8_t i) {
 109     if (!contains(i)) {
 110       dense_[size_] = i;
 111       sparse_[i] = size_;
 112       size_++;
 113     }
 114   }
 115   inline bool contains(uint8_t i) const {
 116     DCHECK_LE(size_, 256);
 117     return sparse_[i] < size_ && dense_[sparse_[i]] == i;
 118   }
 119
 120  private:
 121   uint16_t size_;  // can't use uint8_t because it would overflow if all
 122                    // possible values were inserted.
 123   uint8_t sparse_[256];
 124   uint8_t dense_[256];
 125 };
 126
 127 }  // namespace
 128
 129 namespace detail {
 130
 131 size_t qfind_first_byte_of_byteset(const StringPiece haystack,
 132                                    const StringPiece needles) {
 133   FastByteSet s;
 134   for (auto needle: needles) {
 135     s.add(needle);
 136   }
 137   for (size_t index = 0; index < haystack.size(); ++index) {
 138     if (s.contains(haystack[index])) {
 139       return index;
 140     }
 141   }
 142   return StringPiece::npos;
 143 }
 144
 145 #if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6)
 146
 147 template <bool HAYSTACK_ALIGNED>
 148 size_t scanHaystackBlock(const StringPiece haystack,
 149                          const StringPiece needles,
 150                          uint64_t idx)
 151 // inline is okay because it's only called from other sse4.2 functions
 152   __attribute__ ((__target__("sse4.2")))
 153 // Turn off ASAN because the "arr2 = ..." assignment in the loop below reads
 154 // up to 15 bytes beyond end of the buffer in #needles#.  That is ok because
 155 // ptr2 is always 16-byte aligned, so the read can never span a page boundary.
 156 // Also, the extra data that may be read is never actually used.
 157   FOLLY_DISABLE_ADDRESS_SANITIZER;
 158
 159 // Scans a 16-byte block of haystack (starting at blockStartIdx) to find first
 160 // needle. If HAYSTACK_ALIGNED, then haystack must be 16byte aligned.
 161 // If !HAYSTACK_ALIGNED, then caller must ensure that it is safe to load the
 162 // block.
 163 template <bool HAYSTACK_ALIGNED>
 164 size_t scanHaystackBlock(const StringPiece haystack,
 165                          const StringPiece needles,
 166                          uint64_t blockStartIdx) {
 167   DCHECK_GT(needles.size(), 16);  // should handled by *needles16() method
 168   DCHECK(blockStartIdx + 16 <= haystack.size() ||
 169          (PAGE_FOR(haystack.data() + blockStartIdx) ==
 170           PAGE_FOR(haystack.data() + blockStartIdx + 15)));
 171
 172   __v16qi arr1;
 173   if (HAYSTACK_ALIGNED) {
 174     void* ptr1 = __builtin_assume_aligned(haystack.data() + blockStartIdx, 16);
 175     arr1 = *reinterpret_cast<const __v16qi*>(ptr1);
 176   } else {
 177     arr1 = __builtin_ia32_loaddqu(haystack.data() + blockStartIdx);
 178   }
 179
 180   // This load is safe because needles.size() >= 16
 181   auto arr2 = __builtin_ia32_loaddqu(needles.data());
 182   size_t b = __builtin_ia32_pcmpestri128(
 183     arr2, 16, arr1, haystack.size() - blockStartIdx, 0);
 184
 185   size_t j = nextAlignedIndex(needles.data());
 186   for (; j < needles.size(); j += 16) {
 187     void* ptr2 = __builtin_assume_aligned(needles.data() + j, 16);
 188     arr2 = *reinterpret_cast<const __v16qi*>(ptr2);
 189
 190     auto index = __builtin_ia32_pcmpestri128(
 191       arr2, needles.size() - j, arr1, haystack.size() - blockStartIdx, 0);
 192     b = std::min<size_t>(index, b);
 193   }
 194
 195   if (b < 16) {
 196     return blockStartIdx + b;
 197   }
 198   return StringPiece::npos;
 199 }
 200
 201 size_t qfind_first_byte_of_sse42(const StringPiece haystack,
 202                                  const StringPiece needles)
 203   __attribute__ ((__target__("sse4.2"), noinline));
 204
 205 size_t qfind_first_byte_of_sse42(const StringPiece haystack,
 206                                  const StringPiece needles) {
 207   if (UNLIKELY(needles.empty() || haystack.empty())) {
 208     return StringPiece::npos;
 209   } else if (needles.size() <= 16) {
 210     // we can save some unnecessary load instructions by optimizing for
 211     // the common case of needles.size() <= 16
 212     return qfind_first_byte_of_needles16(haystack, needles);
 213   }
 214
 215   if (haystack.size() < 16 &&
 216       PAGE_FOR(haystack.end() - 1) != PAGE_FOR(haystack.data() + 16)) {
 217     // We can't safely SSE-load haystack. Use a different approach.
 218     if (haystack.size() <= 2) {
 219       return qfind_first_of(haystack, needles, asciiCaseSensitive);
 220     }
 221     return qfind_first_byte_of_byteset(haystack, needles);
 222   }
 223
 224   auto ret = scanHaystackBlock<false>(haystack, needles, 0);
 225   if (ret != StringPiece::npos) {
 226     return ret;
 227   }
 228
 229   size_t i = nextAlignedIndex(haystack.data());
 230   for (; i < haystack.size(); i += 16) {
 231     auto ret = scanHaystackBlock<true>(haystack, needles, i);
 232     if (ret != StringPiece::npos) {
 233       return ret;
 234     }
 235   }
 236
 237   return StringPiece::npos;
 238 }
 239 #endif // FOLLY_HAVE_EMMINTRIN_H && GCC 4.6+
 240
 241 size_t qfind_first_byte_of_nosse(const StringPiece haystack,
 242                                  const StringPiece needles) {
 243   if (UNLIKELY(needles.empty() || haystack.empty())) {
 244     return StringPiece::npos;
 245   }
 246   // The thresholds below were empirically determined by benchmarking.
 247   // This is not an exact science since it depends on the CPU, the size of
 248   // needles, and the size of haystack.
 249   if ((needles.size() >= 4 && haystack.size() <= 10) ||
 250              (needles.size() >= 16 && haystack.size() <= 64) ||
 251              needles.size() >= 32) {
 252     return qfind_first_byte_of_byteset(haystack, needles);
 253   }
 254   return qfind_first_of(haystack, needles, asciiCaseSensitive);
 255 }
 256
 257 }  // namespace detail
 258 }  // namespace folly