4 ms·
Show HN: Faking SIMD to Search and Sort Strings 5x Faster
I want to share a really dumb, but very practical project I have packaged this summer, to perform operations on strings much faster. I was using Python to work with a multi-terabyte newline-delimited file. Reading, splitting, and shuffling it was a nightmare. So, I wrapped a trivial hardware-friendly heuristic I've been using for the last few years into a CPython library.
The part I enjoyed the most is implementing SIMD behavior without SIMD instructions... Using 64-bit words to work at 8-bit granularity. Unlike conventional SIMD, the code would remain the same for ~~almost~~ any hardware. Let this library be a reminder of how awesome bit-level hacks are! Feel free to use it when working with CommonCrawl or any other sizeable textual dataset.
- itkent 3y agoI took a look at Stringzilla (https://github.com/ashvardanian/stringzilla https://github.com/ashvardanian/stringzilla), and in addition to the impressive benchmarks, the API looks pretty straightforward. It's a new star in my collection! Thanks for open-sourcing this project!
- ashvardanian 3y agoThank you too! Once I have time to implement rsplit/rfind and similar reverse functions, it should be a drop-in replacement for the Python string.
- gwittel 3y agoCool library. This sounds like SWAR (simd within a register). I’ve seen these techniques give a nice speed up especially when SIMD isn’t available or a pain (eg in Java pre-Panama). One random sample: https://lemire.me/blog/2022/01/21/swar-explained-parsing-eight-digits/?amp https://lemire.me/blog/2022/01/21/swar-explained-parsing-eig...
- djmips 3y agoYes SWAR - even hardware supported is called SWAR though? https://en.wikipedia.org/wiki/SWAR https://en.wikipedia.org/wiki/SWAR We used this as far back as the eighties on 68000 machines you could do 8 bit SWAR with the 32 bit registers!
- ashvardanian 3y agoYes, in the past those tricks were much more common