11–16 of 16 posts
This explanation was a bit unsatisfying. This works because 0x09 and 0x0D differ by a single bit, and 0xFB masks that bit (and only that bit) out.
If they differed by more than one bit, the fact that they & the same would be necessary but not sufficient.
I don't know ARM, but an alternate approach, if it's available, is to store the query constants as bitmasks in SIMD registers; and use the input bytes as indices into those constants, using a shuffle instruction. Two levels, to pull out a bit from a 256-bit mask: part of an input byte is used to index a byte (SIMD shuffle), and another part indices a bit within the byte (bit shifts). Idea being, this is constant in t…
This describes a few algorithms: http://0x80.pl/notesen/2018-10-18-simd-byte-lookup.html
Both the alternative version by Geoff Langdale, and the special case for small sets, are substantially similar to the algorithms used in Hyperscan (truffle and shufti). https://github.com/intel/hyperscan
Having something hard coded for spaces can be much faster, especially since 5 of the 6 characters are a range: a wrap-around subtraction and an unsigned less-than does the first 5; an equality compare does the other.
You can avoid hard-coding the whitespace symbols and have a generic byte-set search kernel via `vpshufb` AVX512BW-capable CPUs [1] or via `tbl` instructions on NEON-capable CPUs [2]. [1]: https://github.com/ashvardanian/StringZilla/blob/2f4b1386ca2... [2]: https://github.com/ashvardanian/StringZilla/blob/2f4b1386ca2...
On semi-related note, it's worth noting that if you're trying to make a Python script run faster and don't have the know-how to re-write your program in C or how to write SIMD (if applicable), you can always try to run the script through pypy, merely replacing python3 with pypy3 in bench.sh, with no other changes, brings the runtime of the first program down from 104s to 9s on my machine: Benchmark 1: python3 0_mvp.p…
On semi-related note, it's worth noting that if you're trying to make a Python script run faster and don't have the know-how to re-write your program in C or how to write SIMD (if applicable), you can always try to run the script through pypy, merely replacing python3 with pypy3 in bench.sh, with no other changes, brings the runtime of the first program down from 104s to 9s on my machine: Benchmark 1: python3 0_mvp.p…
Thanks for the advice - I never heard of pypy. Are there any downsides to making puppy the default Python interpreter? Thanks!
With that being said, when it works, it works great but you have to evaluate whether it's suitable on a per-project/script basis.