3 ms·
Good article, but here’s a few minor things. > we combine the vector masks using the packs instruction and readily extract it using movemask just once Blend i
by Const-me 5y ago
Good article, but here’s a few minor things.
> we combine the vector masks using the packs instruction and readily extract it using movemask just once
Blend instructions are generally slightly faster than pack instructions, _mm256_blend_epi16 in that case. The order is not the same so the permute() function needs different shuffle vector, but otherwise it should work the same way.
> B-tree from Abseil to the comparison, which is the only widely-used B-tree implementation I know of
Another one: https://github.com/tlx/tlx/tree/master/tlx/container https://github.com/tlx/tlx/tree/master/tlx/container It’s not using any SIMD but the code quality is OK, I didn’t have much issues vectorizing the performance-critical pieces in my projects.
- sereja 5y agoHmm... using blend is actually a good suggestion. You can pre-shuffle elements [1 3 5 7] [2 4 6 8], do a comparison against the search key, and then blend the low 16 bits of the first register with the high 16 bits of the second. Will add that to the article, thanks!
- Const-me 5y agoSpeaking about pre-shuffling and blending, you can try doing twice as much work with vectors. Pre-shuffle slices of 32 keys into [ 0, 4, 8, 12 .. ], [ 1, 5, 9, 13.. ] etc, then when searching combine 0-2 and 1-3 pairs of vectors with _mm256_blend_epi16(a, b, 0b10101010), then merge with _mm256_blendv_epi8 using _mm256_set1_epi16((short)0xFF00) for the blending mask. This way _mm256_movemask_epi8 will get you a bitmap of 32 bits for 32 integer keys you can scan with _mm_tzcnt_32. Especially good on AMD where vpblendvb completes in a single cycle, Zen 3 can even run 2 of them per clock.
- sereja 5y agoI've already implemented a 32-byte version. But, as mentioned in the article, it's not faster (in terms of throughput) because it needs to fetch two cache lines.