6 ms·
wow, what an interesting optimization! how would you even figure out that that if is what's needed to make it faster?
by pillmillipedes 2mo ago
wow, what an interesting optimization! how would you even figure out that that if is what's needed to make it faster?
- purplesyringa 2mo agoI knew the loop was latency-bound and I couldn't easily decrease the latency, so I knew I had to somehow avoid the dependency chain at all. I remembered that CPUs predict some properties of memory accesses (e.g. they might predict that a store and then a load from different addresses likely don't intersect), but not addresses, so I thought about another way to force it to predict `j` well. Branch prediction turned out to be the simplest way to do so. Actually, since then I've found out that I could reduce latency by replacing a load on the critical chain with a vector shuffle instruction (`pshufb`, takes just 1 cycle on x86). Ironically, if I realized that sooner, I probably wouldn't have tried to use branch prediction at all!