5 ms·
Checking for the absence of a string, naive AVX-512 edition
- rwmj 4y agoUnfortunately the real world version of this would have to deal with at least case folding, and most likely the oddities of specific languages and unicode (like all the ways to represent the "same" letters and numbers, ß in German, narrow and wide katakana etc). I wonder if SIMD can help with this or if it's just too complicated?
- burntsushi 4y agoIt would not. Real world versions of what you speak would use different algorithms. If you're concerned about different normalization forms for example, the typical way to do that is to normalize both your needle and haystack before doing a search. For case folding, you can enumerate at least all the possible prefixes of small length, scan for those using a SIMD algorithm like Teddy (from Hyperscan) and then use a finite state machine to confirm or reject the match. That's how Rust's regex crate (and consequently, ripgrep) works for example. Regardless of those cases, exact string match is still very much desirable to optimize and is extremely useful in the real world.
- kgbcia 4y agoAre there libraries (c, Python,etc) that just exploit avx without caring for compatibility with other platforms?
- cmrdporcupine 4y agoThere are several, but I found this one is quite useful: https://github.com/vectorclass/version2 https://github.com/vectorclass/version2 Very minimal API, header only, so easily imported ... I then wrapped up in my own classes for my own purposes: https://github.com/rdaum/sidebands_vst/blob/main/source/dsp/oscbuffer.cc https://github.com/rdaum/sidebands_vst/blob/main/source/dsp/...
- the8472 4y agoMany data-/number-crunching C libraries already do dynamic-link-time or runtime cpu feature detection and select appropriate implementations. E.g. glibc already has bunch of specialized assembly impls for many of the string operations https://github.com/bminor/glibc/tree/master/sysdeps/x86_64/multiarch https://github.com/bminor/glibc/tree/master/sysdeps/x86_64/m...
- stabbles 4y agoSee also http://0x80.pl/articles/simd-strfind.html http://0x80.pl/articles/simd-strfind.html The basic idea there is: - mask_start = (64 chars from idx i) & (first letter) - mask_end = (64 chars from idx i + len - 1) & (last letter) if mask_start & mask_end is nonzero, you can now memcmp at the nonzero mask indices (which could also be done with AVX512 if the needle length is big enough) That should give better performance for long needles, since you can immediately check 64 chars of the needle against the first character match, whereas OP's version does one load per needle character (ok, it does check multiple matches in a 64-char window in parallel though). I wonder though if Boyer-Moore type of optimizations are possible (e.g. if the match breaks at substring length i, that means you can skip forward j chars from a precomputed table)
- the8472 4y agoMany string search impls are adaptive and use different algorithms depending on needle and haystack lengths and possibly also contents of the needle. E.g. https://github.com/BurntSushi/memchr#user-content-algorithms-used https://github.com/BurntSushi/memchr#user-content-algorithms...