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