static
| 58 | |
| 59 | // static |
| 60 | int32_t StringView::linearSearch( |
| 61 | StringView key, |
| 62 | const StringView* strings, |
| 63 | const int32_t* indices, |
| 64 | int32_t numStrings) { |
| 65 | #if XSIMD_WITH_AVX2 |
| 66 | constexpr int64_t kBatch = xsimd::batch<uint64_t>::size; |
| 67 | bool isInline = key.isInline(); |
| 68 | bool headOnly = key.size() <= 4; |
| 69 | const char* body = key.data() + 4; |
| 70 | int32_t bodySize = key.size() - 4; |
| 71 | int32_t limit = numStrings & ~(kBatch - 1); // round down to full batches. |
| 72 | if (indices) { |
| 73 | uint64_t head = *reinterpret_cast<const uint64_t*>(&key); |
| 74 | uint64_t inlined = reinterpret_cast<const uint64_t*>(&key)[1]; |
| 75 | xsimd::batch<int32_t, xsimd::sse2> indexVector; |
| 76 | |
| 77 | for (auto i = 0; i < limit; i += kBatch) { |
| 78 | indexVector = simd::loadGatherIndices<uint64_t, int32_t>(indices + i) |
| 79 | << 1; |
| 80 | auto heads = |
| 81 | simd::gather(reinterpret_cast<const uint64_t*>(strings), indexVector); |
| 82 | uint16_t hits = simd::toBitMask(heads == head); |
| 83 | if (LIKELY(!hits)) { |
| 84 | continue; |
| 85 | } |
| 86 | if (headOnly) { |
| 87 | return i + __builtin_ctz(hits); |
| 88 | } |
| 89 | while (hits) { |
| 90 | auto offset = bits::getAndClearLastSetBit(hits); |
| 91 | if (isInline ? inlined == |
| 92 | reinterpret_cast<const uint64_t*>( |
| 93 | &strings[indices[i + offset]])[1] |
| 94 | : simd::memEqualUnsafe( |
| 95 | body, |
| 96 | strings[indices[i + offset]].data() + 4, |
| 97 | bodySize)) { |
| 98 | return i + offset; |
| 99 | } |
| 100 | } |
| 101 | } |
| 102 | return linearSearchSimple( |
| 103 | key, strings, indices + limit, numStrings - limit); |
| 104 | } else { |
| 105 | StringView key2[2]; |
| 106 | memcpy(&key2[0], &key, sizeof(key)); |
| 107 | memcpy(&key2[1], &key, sizeof(key)); |
| 108 | auto keyVector = xsimd::load_unaligned(reinterpret_cast<uint64_t*>(&key2)); |
| 109 | for (auto i = 0; i < limit; i += kBatch, strings += kBatch) { |
| 110 | // Compare 4 StringViews in 2 loads of 2 each. |
| 111 | int32_t bits = |
| 112 | simd::toBitMask( |
| 113 | xsimd::load_unaligned( |
| 114 | reinterpret_cast<const uint64_t*>(strings)) == keyVector) | |
| 115 | (simd::toBitMask( |
| 116 | xsimd::load_unaligned( |
| 117 | reinterpret_cast<const uint64_t*>(strings + 2)) == keyVector) |
nothing calls this directly
no test coverage detected