folly/Range.cpp

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