Show HN: Faking SIMD to Search and Sort Strings 5x Faster (ashvardanian.com)

29 points by ashvardanian 2y ago ↗ HN

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.

5 comments

[ 3.5 ms ] story [ 26.6 ms ] thread

itkent 2y ago ↗

I took a look at 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 2y ago ↗

Thank 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 2y ago ↗

Cool 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-eig...

djmips 2y ago ↗

Yes SWAR - even hardware supported is called SWAR though?

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 2y ago ↗

Yes, in the past those tricks were much more common