Find the first instance of a character using simd

by

You have the right idea with _mm256_cmpeq_epi8 -> _mm256_movemask_epi8. AFAIK, that’s the optimal way to implement this for Intel CPUs at least. PMOVMSKB r32, ymm is the same speed as the XMM 16-byte version, so it would be a huge loss to unpack the two lanes of a 256b vector and movemask them separately and then recombine the integer results. (Source: Agner Fog’s instruction table. See other perf links in the x86 tag wiki.)

Make the code inside the loop as efficient as possible by leaving the ffs until after you’ve identified a non-zero result from _mm256_movemask_epi8.

TEST/JCC can macro fuse into a single uop, but BSF/JCC doesn’t, so it takes an extra instruction. (And you’d be hard-pressed to get a C compiler to emit BSF/JCC anyway. More likely branching on the result of ffs would give you some kind of test for the input being non-zero, then BSF, then add 1, then compare-and-branch. That’s obviously horrible compared to just testing the movemask result.)

(Update, in C++20, use std::countr_zero. It can compile to a single tzcnt, instead of the off-by-one of ffs. Since you’ve already checked for the mask being non-zero, hopefully can optimize to a single (rep) bsf instruction if it isn’t sure all CPUs running the code will support tzcnt. If you can assume BMI1 in your target CPUs, which you usually can for AVX2 code, then enable that so you’ll reliably get an efficient tzcnt.)

Also note that for similar problems, comparing the movemask (e.g. to check that it’s 0xFFFFFFFF) is just as efficient as branching on it being non-zero.

As Paul R suggested, looking at some strlen, strchr, and memchr implementations may be informative. There are multiple hand-written asm implementations in open-source libc implementations, and other places. (e.g. glibc, and Agner Fog’s asmlib.)

Many of glibc’s versions scan up to an alignment boundary, then use an unrolled loop that reads 64B at a time (in 4 SSE vectors, since I don’t think glibc has an AVX2 version).

To optimize for long strings, reduce overhead from testing the compare results by ORing the compare results together, and check that. If you find a hit, go back and re-test your vectors to see which vector had the hit.

It may be somewhat more efficient to do the ffs on one 64-bit integer that you built up out of multiple movemask results (with shift and |). I’m not sure about doing this inside the loop before testing for zero; I don’t remember if one of glibc’s strlen strategies did that or not.

Everything I’ve suggested here is stuff can be seen in asm in various glibc strategies for strlen, memchr, and related functions. Here’s sysdeps/x86_64/strlen.S, but I there may be another source file somewhere using more than baseline SSE2. (Or not, I might be thinking of a different function, maybe there’s nothing to be gained beyond SSE2, until AVX (3-operand insns) and AVX2 (256b integer vectors).

See also:

  • glibc’s strchr-avx2.S (Woboq.org has a nice source browser with a useful search for filenames / symbols).
  • glibc’s memchr-avx2.S

glibc’s memchr uses PMAXUB instead of POR. I’m not sure if that’s useful for some arcane microarchitectural reason, but it runs on fewer ports on most CPUs. Perhaps that’s desired, to avoid resource conflicts with something else? IDK, seems weird, since it competes with PCMPEQB.

More Related Contents:

  1. How to efficiently convert an 8-bit bitmap to array of 0/1 integers with x86 SIMD [duplicate]
  2. Fastest Implementation of Exponential Function Using AVX
  3. Fastest way to unpack 32 bits to a 32 byte SIMD vector
  4. Convention for displaying vector registers
  5. Fastest way to do horizontal vector sum with AVX instructions [duplicate]
  6. Load address calculation when using AVX2 gather instructions
  7. What are the best instruction sequences to generate vector constants on the fly?
  8. is there an inverse instruction to the movemask instruction in intel avx2?
  9. How to perform the inverse of _mm256_movemask_epi8 (VPMOVMSKB)?
  10. Loading 8 chars from memory into an __m256 variable as packed single precision floats
  11. Fastest way to compute absolute value using SSE
  12. Header files for x86 SIMD intrinsics
  13. Sum reduction of unsigned bytes without overflow, using SSE2 on Intel
  14. Per-element atomicity of vector load/store and gather/scatter?
  15. SSE multiplication of 4 32-bit integers
  16. How to efficiently perform double/int64 conversions with SSE/AVX?
  17. Vectorizing with unaligned buffers: using VMASKMOVPS: generating a mask from a misalignment count? Or not using that insn at all
  18. What is the meaning of “non temporal” memory accesses in x86
  19. How to merge a scalar into a vector without the compiler wasting an instruction zeroing upper elements? Design limitation in Intel’s intrinsics?
  20. practical BigNum AVX/SSE possible?
  21. How do I enable SSE for my freestanding bootable code?
  22. What’s missing/sub-optimal in this memcpy implementation?
  23. Using ymm registers as a “memory-like” storage location
  24. Transpose an 8×8 float using AVX/AVX2
  25. Get sum of values stored in __m256d with SSE/AVX
  26. SIMD math libraries for SSE and AVX
  27. Difference between MOVDQA and MOVAPS x86 instructions?
  28. Efficient sse shuffle mask generation for left-packing byte elements
  29. How to convert 32-bit float to 8-bit signed char? (4:1 packing of int32 to int8 __m256i)
  30. Half-precision floating-point arithmetic on Intel chips

Leave a Comment