3 ms·
I discovered a really cool ARM64 trick today. One thing about x86 that I've found useful on so many occasions is the PCMPEQB + PMOVMSKB + BSF trick that lets me
by jart 3y ago
I discovered a really cool ARM64 trick today. One thing about x86 that I've found useful on so many occasions is the PCMPEQB + PMOVMSKB + BSF trick that lets me scan the bytes of a string 10x faster. I couldn't find any information on Google for doing PMOVMSKB with ARM, so I've been studying ARM's "Optimized Routines" codebase where I stumbled upon the answer in their strnlen() implementation. It turns out the trick is to use `shrn dst.8b, src.8h, 4` which turns a 128-bit mask into a 64-bit mask. You can then get the string offset index with fmov, rbit, clz and finally shift by 2.
- danlark 3y agoI am the author of this trick as well You can read about it in https://community.arm.com/arm-community-blogs/b/infrastructure-solutions-blog/posts/porting-x86-vector-bitmask-optimizations-to-arm-neon https://community.arm.com/arm-community-blogs/b/infrastructu...
- jart 3y agoWow. I love your work. Thank you for coming here and talking about it. You could write Hacker's Delight 2nd edition for a new generation.
- tr33house 3y agowould totally love to read a modern `Hacker's Delight`. My mind was so blown away the first time I learned about low-level optimizations. I wish I did more of that on a day to day
- spicymaki 3y agoHacker's Delight already has a 2nd edition. https://www.oreilly.com/library/view/hackers-delight-second/9780133084993/ https://www.oreilly.com/library/view/hackers-delight-second/...
- zX41ZdbW 3y agoLet's add it to ClickHouse: https://github.com/ClickHouse/ClickHouse/blob/master/base/base/find_symbols.h https://github.com/ClickHouse/ClickHouse/blob/master/base/ba... It should significantly improve the performance on ARM.
- jeffreygoesto 3y ago> However, developers often encounter problems with Arm NEON instructions being expensive to move to scalar code and back. I remember talking to an ARM engineer easily 10 years ago and he told us in that nice british accent: "You know, NEON is like 'back in the yard'" :-D. This has changed a lot, but not enough from what you wrote... Bit sad that these SIMD optimizations are still hand written...
- Sesse__ 3y agoThe VSHRN trick is nice (I used it only two hours ago!), but it really does feel like a crutch; I don't understand why they couldn't simply implement a PMOVMSKB-like instruction to begin with (it cannot possibly be very expensive in silicon, at least not if it moved into a vector register). One-bit-per-byte is really the sweet spot for almost any kind of text manipulation, and often requires less setup/post-fixup on either side of the POVMSKB/VSHRN.
- camel-cdr 3y agoI found the following article about the topic really good: https://branchfree.org/2019/04/01/fitting-my-head-through-the-arm-holes-or-two-sequences-to-substitute-for-the-missing-pmovmskb-instruction-on-arm-neon/ https://branchfree.org/2019/04/01/fitting-my-head-through-th... In my experience using a 512 wide movemask (to uint64_t) is the fastest on both x86 and arm64. (Edit: just yo clarify, I meant the fastest for iteration, things like SwissMap are better off using 128 wide movemask) With rvv you don't really what to go from a vector mask to a general purpose non vector register, because the vector length may vary. But I found it really useful that vector masks are always packed into v0. So even with LMUL=8, you can just to a vmseq, switch to LMUL=1 and use vfirst & vmsif & vmandn to iterate through all indices. (Alternatively vfirst & vmsof & vmclr would also work, I'm not sure which one would be faster)