On Thu, Nov 09, 2023 at 08:50:19PM -0800, Eric Biggers wrote: > On Thu, Nov 09, 2023 at 09:06:08PM +0000, Matthew Wilcox (Oracle) wrote: > > Replace the shift with a divide, which is probably cheaper than first > > calculating the shift. > > No. The divs are almost certainly more expensive on most CPUs, especially when > doing two of them. On x86_64 for example, it will be two div instructions > instead of one bsr and two shr instructions. The two divs are much more costly. > The block size is always a power of 2; we should take advantage of that. I just looked it up and it's more expensive than I thought, but I don't see a huge difference here. DIV has a 23-cycle latency on Skylake (just to pick a relatively recent CPU). But it has reciprocal throughput of 6, so two DIVs have latency of 29, not 46. Unless the second DIV depends on the result of the first (it doesn't). BSF (the ffs instruction) has latency 3. SHRD has latency 4, but the SHR is going to depend on the output of the BSF, so they necessarily add to 7 cycles latency. SHR has reciprocal latency of 2, so BSF,SHR,SHR will be 9 cycles. So I've cost 20 cycles, which is about the cost of missing in the L1 cache and hitting in the L2 cache. That doesn't feel too bad to me? Would you want to invest more engineering time in changing it?
