8 ms·
Using the most unhinged AVX-512 instruction to make fastest phrase search algo
- nxobject 2y agoSpoiler if you don’t want to read through the (wonder but many) paragraphs of exposition: the instruction is `vp2intersectq k, zmm, zmm`.
- bri3d 2y agoAnd, as noted in the article, that's an instruction which only works on two desktop CPU architectures (Tiger Lake and Zen 5), including one where it's arguably slower than not using it (Tiger Lake). Meaning... this entire effort was for something that's faster on only a single kind of CPU (Zen 5). This article is honestly one of the best I've read in a long time. It's esoteric and the result is 99.5% pointless objectively, but in reality it's incredibly useful and a wonderful guide to low-level x86 optimization end to end. The sections on cache alignment and uiCA + analysis notes are a perfect illustration of "how it's done."
- tpm 2y agoPresumably Zen 5 cores will also get used in Threadripper and EPYC processors.
- josephg 2y agoYep. And the feature will probably be available on all AMD CPUs manufactured from here on. It might be an esoteric feature today. But if it'll become an ubiquitous feature in a few years, its nice to learn about using it.
- nine_k 2y agoNot just that, but the fact that Intel CPUs execute it 20-30 times slower than AMD Zen 5 CPUs. Also, the fact that it's deprecated by Intel.
- mycall 2y agoNow the question is if Intel will revive it now that Zen 5 has it.
- iamnotagenius 2y agoImo the most "unhinged" cpus for AVX-512 are early batches of Alder Lakes which is the only cpu family that has nearly full coverage of all existing avx-512 subsets.
- fuhsnn 2y agoDo they cover anything Sapphire Rapids Xeon's don't? I thought they share the same arch (Golden Cove).
- iamnotagenius 2y agoYes, you are right; I meant "consumer grade cpu".
- suzumer 2y agoAccording to this [1] wikipedia article, the only feature Sapphire Rapids doesn't support is VP2INTERSECT. [1]:https://en.wikipedia.org/wiki/Advanced_Vector_Extensions https://en.wikipedia.org/wiki/Advanced_Vector_Extensions
- nextaccountic 2y agoIt seems that there are faster alternatives to it https://arxiv.org/abs/2112.06342 https://arxiv.org/abs/2112.06342 https://www.reddit.com/r/asm/comments/110pld0/fasterthannative_alternatives_for_x86/ https://www.reddit.com/r/asm/comments/110pld0/fasterthannati...
- hogwarts2025 2y agoOr Zen 5. :-p
- janwas 2y agoNote that the article mentions using both outputs of the instruction, whereas the emulation is only able to compute one output efficiently.
- 2y ago
- jonstewart 2y agoThe most unhinged AVX-512 instruction is GF2P8AFFINEQB.
- pclmulqdq 2y agoWhat about GF2P8AFFINEINVQB?
- jonstewart 2y agopotato, potato, tomato, tomato
- LarsKrimi 2y agoIt has a fixed polynomial, so not really that useful for anything but AES The only case where I've had use of GF(2^8) inverses is in FEC algorithms (Forney's algorithm) and then you need some kind of weird polynomial. But all of those needs are rarely in the hot-path, and the FEC algo's are way outdated
- pclmulqdq 2y agoI think the AFFINE and AFFINEINV instructions are specifically for FEC and maybe compression algorithms. I also think they smell like something requested by one of the big customers of Intel (e.g. the government).
- LarsKrimi 2y agoHmm of course erasure codes would always need to solve these problems. Not sure what modern applications need that in the X86 world I really think it's only AES since thats the only place I've seen that polynomial used. But of course maybe there's an obscure tape backup FEC algo used somewhere in datacenters?
- Sesse__ 2y agoThe forward affine matrix is useful for all sorts of bit manipulation, e.g. something as simple as a bit reversal.
- nine_k 2y agoWhat a post. It should have taken a week just to write it, never mind the amount of time it took to actually come up with all this stuff and overcome all the obstacles mentioned. What a dedication to improving the performance of phrase search.
- rkagerer 2y agoIs the first example under The genius idea heading missing entry #3 below? mary: docs: - 0: posns: [0, 8] - 1: posns: [2] - 3: posns: [1]
- rstuart4133 2y agoI thought it's missing. However, he does introduce it with: > The inverted index will look something like this: He isn't wrong. It is indeed "something like".
- nemoniac 2y agoFascinating blog post. Having said that, it may seem like nitpicking but I have to take issue with the point about recursion, which is often far too easily blamed for inefficiency. The blog post mentions it as one of the reasons for the inefficiency of the conventional algorithm. A glance at the algorithm shows that the recursion in question is a tail call. This means that any overhead can be readily eliminated using a technique known for nearly fifty years already. Steele, Guy Lewis (1977). "Debunking the "expensive procedure call" myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO". Proceedings of the 1977 annual conference on - ACM '77.
- queuebert 2y agoDumb question: does modern stack layout randomization affect the efficiency of recursion? On first glance I would be worried about cache misses.
- bri3d 2y agoNot specifically address space layout randomization in the way it's usually implemented; ASLR as applied in most modern production OSes randomizes each stack's base address, but each stack is still laid out and used in a normal way. There are some research projects towards actual stack layout randomization (involving stack rearrangement via static analysis, randomly sized stack padding frames, and other techniques) which would also definitely blow up cache, but none that are mainstream in a production system as far as I know. However, for the naive case where the recursion is a full-blown function call, without some kind of optimization, other security mitigations than ASLR will significantly affect the efficiency of recursion by adding function call overhead (and possible cache side effects) - for example, the stack cookie will still be verified and control-flow guard checks and the shadow/return stack will still be in play, if present.
- slashdev 2y agoA lot of modern programming languages do not do tail call optimization, often citing keeping accurate stack history for debugging as an excuse. Regardless of how valid the excuse is, for such an obvious and old optimization, it’s very poorly supported.
- ltbarcly3 2y agoVery cool blog post, but the fastest phrase search would just use a suffix array, which would make any phrase search take double digit nanoseconds.
- yorwba 2y ago> Why are you merging up to one rare token at the beginning or at the end? Let’s consider that someone searched for C_0 R_1 C_2 C_3. If we don’t do this merge, we would end up searching for C_0, R_1, C_2 C_3, and this is bad. As established, intersecting common tokens is a problem, so it’s way better to search C_0 R_1, C_2 C_3. I learned this the hard way… But since R_1 C_2 C_3 is in the index as well, instead of searching for C_0 R_1, C_2 C_3 with a distance of 2, you can instead search for C_0 R_1, R_1 C_2 C_3 with a distance of 1 (overlapping), which hopefully means that the lists to intersect are smaller.
- csense 2y agoI'm trying to follow the example and getting lost. > Imagine the scenario where "mary had" occurs in the following positions: [1, 6] and "a" appears in the position [2], so "mary had a" occurs in the positions [2] Okay so basically this means "mary had a" ends at token position 2 (assuming "mary" is token position 0), and you're trying to create an efficient algorithm to do this backwards linking process. It's not entirely clear from the article what's pre-computed ahead of time (when documents are added / indexed by the system) and what's done on-the-fly (in response to a user's specific search query). Based on skimming the article it appears that you're doing this backwards linking process on the fly for a specific phrase the user enters (but I could be wrong about that). > allows us to decompose this value What value is being decomposed? It is not clear what "this value" refers to. > one representing the group and the other the value Ctrl+F is telling me that's the first occurrence of the word "group" in this post. What is the "group" being represented? > pos = group * 16 + value Okay so you're bit-packing two fields into pos. One of the things being packed is called "group," and it seems to be 16 bits. The other thing being packed is "value," and it seems to be 4 bits. So in total "pos" has 20 bits. > the maximum document length is 1048576 tokens It seems that "pos" simultaneously corresponds to a token position and our two-field bit-packed thing above. I can't figure out how these two things are in one-to-one correspondence. I stopped reading there, given my confusion so far it seems unlikely I'll really be able to really understand much of what follows. PS: I skimmed the article on roaring bitmaps. Seems they're basically bitmaps where each 1k (8192-bit) chunk has a storage format (dense, sparse, or RLE), and algorithms for quickly doing intersection, union, etc. with various optimized cases chosen roughly by the number of 1's. (Intersecting two dense bitmaps with say ~50% randomly distributed 1's you can't get faster than ANDing together the bit vectors. But if you're, say, intersecting a small sparse bitmap with ~5 1's against a big dense bitmap with ~4k 1's you can iterate over the 1's in the sparse bitmap checking whether each 1 is in the big bitmap.) So in my mind I'm basically just blackboxing roaring bitmaps as "java.util.BitSet or vector<bool> with some extra optimizations that kick in if your data has sections where most of the bits are the same".