3 ms·
Stringzilla: Fastest string sort, search, split, and shuffle using SIMD
- jmatthews 3y agoI realize "speed is a feature", but it's rare when that is THE feature. :)
- tbalsam 3y agoI love programs that minimize the trifecta of code complexity, code length, and runtime. Ugh, such a good practice. Wish we did it more. We need more single-file, well-purposed and commented, editable and hackable libraries. :'))))
- ashvardanian 3y agoI agree, that is the core idea behind most projects we build and maintain at Unum. Otherwise it would have been impossible with just 10 devs: https://github.com/unum-cloud https://github.com/unum-cloud
- LoganDark 3y agoIs this usable from native code, or are these super fast SIMD algorithms really only usable from Python...?
- em3rgent0rdr 3y agoQuick skim of repo shows the vectorized functions which seems like they could be simply called from regular C, e.g.: https://github.com/ashvardanian/Stringzilla/blob/fab854dc4fd99a072fba1319810ad3ccf682238a/stringzilla/stringzilla.h#L315C15-L315C15 https://github.com/ashvardanian/Stringzilla/blob/fab854dc4fd...
- LoganDark 3y agoOh, a header file! Thank you <3
- ashvardanian 3y agoI've updated the main README with a basic C example
- ashvardanian 3y agoYes, it’s intended as a C99 library, to be easily pluggable into different runtimes. NodeJS is next in line :)
- ashvardanian 3y agoOpened an issue in case someone wants to contribute: https://github.com/ashvardanian/Stringzilla/issues/25 https://github.com/ashvardanian/Stringzilla/issues/25
- signa11 3y agothe presentation: https://github.com/ashvardanian/Stringzilla/blob/main/bench/presentation.pdf https://github.com/ashvardanian/Stringzilla/blob/main/bench/... provides more information (just in case you may have missed it)
- ashvardanian 3y agoThere is also a video, but it's in Russian :( https://youtu.be/6Sh9QWdzo58?si=BvLHW1TKI2hBY84z&t=130 https://youtu.be/6Sh9QWdzo58?si=BvLHW1TKI2hBY84z&t=130
- signa11 3y agoyeah, fwiw, i kind-a-sorta followed along with auto-translate + slides, was a bit wary of recommending the video though.
- Aardwolf 3y agoPython factorial on big integer is natively as fast as a good C++ implementation of factorial. So clearly the interpreter supports using fast underlying implementations of things Any idea why python str.find is 100x-1000x slower? Seems like something the interpreter should also hand to an underlying implementation, which could not be that slow.
- ashvardanian 3y agoYes, I have an idea, cause I’ve implemented it :) This simulates substring search as if it was implemented in Python. In reality the Python str calls LibC function from cstring.h, that would work at 1.5GB/s. Still 10x slower than what the simple heuristic provides :)
- Aardwolf 3y agoOh good, the way it was compared with C++ std::string::find made it seem like a direct cross language std lib comparison. Also initially I misread the unit (MB vs GB) and thought python was 10x faster than C++ instead of 100x slower :)
- burntsushi 3y agoCopying my feedback from reddit[1], where I discussed it in the context of the `memchr` crate.[2] I took a quick look at your library implementation and have some notes: * It doesn't appear to query CPUID, so I imagine the only way it uses AVX2 on x86-64 is if the user compiles with that feature enabled explicitly. (Or uses something like [`x86-64-v3`](https://en.wikipedia.org/wiki/X86-64#Microarchitecture_levels https://en.wikipedia.org/wiki/X86-64#Microarchitecture_level...).) The `memchr` crate doesn't need that. It will use AVX2 even if the program isn't compiled with AVX2 enabled so long as the current CPU supports it. * Your substring routines have multiplicative worst case (that is, `O(m * n)`) running time. The `memchr` crate only uses SIMD for substring search for smallish needles. Otherwise it flips over to Two-Way with a SIMD prefilter. You'll be fine for short needles, but things could go very very badly for longer needles. * It seems quite likely that your [confirmation step](https://github.com/ashvardanian/Stringzilla/blob/fab854dc4fd99a072fba1319810ad3ccf682238a/stringzilla/stringzilla.h#L353-L358 https://github.com/ashvardanian/Stringzilla/blob/fab854dc4fd...) is going to absolutely kill performance for even semi-frequently occurring candidates. The [`memchr` crate utilizes information from the vector step to limit where and when it calls `memcmp`](https://github.com/BurntSushi/memchr/blob/46620054ff25b16d22e6e7ab563a6bde6791ee60/src/arch/generic/packedpair.rs#L243-L254 https://github.com/BurntSushi/memchr/blob/46620054ff25b16d22...). Your code might do well in cases where matches are very rare. I took a quick peek at your benchmarks and don't see anything that obviously stresses this particular case. For substring search, the `memchr` crate uses a variant of the "[generic SIMD](http://0x80.pl/articles/simd-strfind.html#first-and-last http://0x80.pl/articles/simd-strfind.html#first-and-last)" algorithm. Basically, it takes two bytes from the needle, looks for positions where those occur and then attempts to check whether that position corresponds to a match. It looks like your technique uses the first 4 bytes. I suspect that might be overkill. (I did try using 3 bytes from the needle and found that it was a bit slower in some cases.) That is, two bytes is usually enough predictive power to lower the false positive rate enough. Of course, one can write pathological inputs that cause either one to do better than the other. (The `memchr` crat benchmark suite has a [collection of pathological inputs](https://github.com/BurntSushi/memchr/blob/46620054ff25b16d22e6e7ab563a6bde6791ee60/benchmarks/definitions/memmem/pathological.toml https://github.com/BurntSushi/memchr/blob/46620054ff25b16d22...).) It would actually be possible to hook Stringzilla up to `memchr`'s benchmark suite if you were interested. :-) [1]: https://old.reddit.com/r/rust/comments/163ph8r/memchr_26_now_uses_simd_for_substring_search_on/jy7zuwo/ https://old.reddit.com/r/rust/comments/163ph8r/memchr_26_now... [2]: https://github.com/BurntSushi/memchr https://github.com/BurntSushi/memchr