[comment] Lemire's string escape check

[prlw1]

Just for your amusement...

I was intrigured by Daniel Lemire's blog post on checking whether a string needs escaping, in which he provides a benchmark including optimised SSE2 code.

For fun I tried what I hope is the rather more readable equivalent using <simd>:

#include <simd>
inline bool stdsimd_needs_escaping(std::string_view view) {
  using V = std::datapar::simd<std::string_view::value_type, 16>;
  if (view.size() < V::size()) {
    return simple_needs_escaping(view);
  }
  auto it = view.begin();
  std::datapar::simd_mask<std::string_view::value_type, 16> running{false};
  for (; it + V::size() <= view.end(); it += V::size) {
    V word(std::datapar::unchecked_load<V>(it, V::size()));
    running = running || (word == V{34});
    running = running || (word == V{92});
    //running = running || (std::sub_sat(word,V{31}) == V{0});
    running = running || (word <  V{32});
  }
  if (it < view.end()) {
    V word(std::datapar::unchecked_load<V>(view.data() + view.length() - V::size(), V::size()));
    running = running || (word == V{34});
    running = running || (word == V{92});
    //running = running || (std::sub_sat(word,V{31}) == V{0});
    running = running || (word <  V{32});
  }
  return std::datapar::any_of(running);
}

and obtained a pleasing

simple_needs_escaping                    :   0.74 GB/s   32.4 Ma/s  30.82 ns/d 
branchless_needs_escaping                :   0.89 GB/s   39.1 Ma/s  25.58 ns/d 
table_needs_escaping                     :   2.39 GB/s  104.5 Ma/s   9.57 ns/d 
SIMD implementation is correct: 1 1
simd_needs_escaping                      :   4.90 GB/s  214.8 Ma/s   4.66 ns/d 
std::SIMD implementation is correct: 1 1
std:simd_needs_escaping                  :   4.31 GB/s  188.9 Ma/s   5.29 ns/d 

[prlw1]

Just amended the above to try with your libstdc++ version in gcc 16.0.1:

#include <simd>
inline bool stdsimd_needs_escaping(std::string_view view) {
  using V = std::simd::vec<std::string_view::value_type, 16>;
  if (view.size() < (unsigned)V::size()) {
    return simple_needs_escaping(view);
  }
  auto it = view.begin();
  std::simd::mask<std::string_view::value_type, 16> running{false};
  for (; it + V::size() <= view.end(); it += V::size) {
    V word(std::simd::unchecked_load<V>(it, V::size()));
    running = running || (word == V{34});
    running = running || (word == V{92});
    //running = running || (std::sub_sat(word,V{31}) == V{0});
    running = running || (word <  V{32});
  }
  if (it < view.end()) {
    V word(std::simd::unchecked_load<V>(view.data() + view.length() - V::size(), V::size()));
    running = running || (word == V{34});
    running = running || (word == V{92});
    //running = running || (std::sub_sat(word,V{31}) == V{0});
    running = running || (word <  V{32});
  }
  return std::simd::any_of(running);
}

the only noticeable change being V:size() is now signed? and obtained

simple_needs_escaping                    :   0.73 GB/s   31.8 Ma/s  31.49 ns/d 
branchless_needs_escaping                :   2.58 GB/s  113.1 Ma/s   8.84 ns/d 
table_needs_escaping                     :   1.96 GB/s   85.8 Ma/s  11.66 ns/d 
SIMD implementation is correct: 1 1
simd_needs_escaping                      :   5.07 GB/s  222.0 Ma/s   4.51 ns/d 
std::SIMD implementation is correct: 1 1
stdsimd_needs_escaping                   :   4.70 GB/s  205.8 Ma/s   4.86 ns/d 

Interestingly the branchless case improved markedly - so other compiler improvement. (Same hardware as previous)

[mattkretz]

Nice! Thank you! I took your last version and played with it: https://compiler-explorer.com/z/3bvYc1E49.

1. This doesn't need a fallback to a char-by-char function.
2. It uses the range overloads of unchecked_load by simply making the string_view smaller and smaller.
3. It uses character constants because LEWG & LWG decided they don't want to allow conversion from constexpr int to vec<char>. Long story. But I have a patch to GCC 16 ready to break your code above.
4. I made it scale with the target SIMD width.

[prlw1]

... and your version is the fastest :-)

simple_needs_escaping                    :   0.73 GB/s   31.9 Ma/s  31.37 ns/d 
branchless_needs_escaping                :   2.67 GB/s  116.9 Ma/s   8.56 ns/d 
table_needs_escaping                     :   2.07 GB/s   90.8 Ma/s  11.01 ns/d 
SIMD implementation is correct: 1 1
simd_needs_escaping                      :   5.04 GB/s  220.5 Ma/s   4.54 ns/d 
std::SIMD implementation is correct: 1 1
stdsimd_needs_escaping                   :   4.70 GB/s  205.8 Ma/s   4.86 ns/d 
Matt's implementation is correct: 1 1
mksimd_needs_escaping                    :   5.61 GB/s  245.7 Ma/s   4.07 ns/d 

(bottom row)
and your

include/bits/simd_vec.h (basic_vec deduction guide): Explicit cast to simd-size-type from range size type.

patch will presumably also sort out my signedness query.

Thanks!

[mattkretz]

Cool!
The deduction guide change is more or less a no-op. Only following the letter of the standard more closely.
I believe your issue is that simd-size-type is a signed integer type. This is motivated by the intrinsics behind mask reductions, which return int on all compilers I know of. Similarly, the <bit> functions countl_zero, etc and popcount return int. Since these values are useful as input to operator[] and thus closely related to the size(), we get signed integers for std::simd widths.
In theory there's never a problem because SIMD widths are way below $2^{31}$ (INT_MAX). The only problem is the "too big of a hammer" -Wconversion warnings and that C++ still doesn't have a good answer to safer integers.