3 ms·
Construction of n-dimensional Morton codes of an arbitrary bit length is regular enough that you can generate optimal shift/mask sequences at compile-time. Ther
by jandrewrogers 3y ago
Construction of n-dimensional Morton codes of an arbitrary bit length is regular enough that you can generate optimal shift/mask sequences at compile-time. There are also simpler generator algorithms that are slightly less optimal (e.g. in a few cases there may be an unnecessary shift/mask step).
Intel microarchitectures added fast ALU instructions (PDEP/PEXT) that can directly effect this as long ago as Haswell (2013) but AMD only very recently added comparable instruction implementations so portability of these instructions is an issue. Also, depending on the dimensionality and bit length of the code, there may be a few cases where the optimal shift/mask version will be about as fast without the portability concerns.
- jart 3y agoAMD introduced BMI2 in Excavator c. 2015.
- jandrewrogers 3y agoAMD did not have useful implementation of PDEP/PEXT instructions until Zen 3, which is barely more than 3 years old. All prior AMD implementations were microcoded for compatibility purposes only. If you cared about performance it was faster to do it in software for most applications. The Zen 2 implementation was something like 6-7x slower than the original Haswell implementation. For all practical purposes, you had to write performance code like AMD did not support PDEP/PEXT.
- mlochbaum 3y agoIt's much worse than that: based on measurements these use a loop that goes one set bit of the mask argument at a time. uops.info and so on measure a mask that's almost all zero so they vastly underreport. Worst case is in the hundreds of cycles. Do not use pdep/pext before Zen 3. https://twitter.com/uops_info/status/1202950247900684290 https://twitter.com/uops_info/status/1202950247900684290