4 ms·

I wondered why they used TZCNT instead of BSF. If their algorithm has correctly located the word with the jth bit set, the output of PDEP shouldn't be zero, and

by derf_ 8y ago

I wondered why they used TZCNT instead of BSF. If their algorithm has correctly located the word with the jth bit set, the output of PDEP shouldn't be zero, and these should be equivalent (but BSF doesn't require a dependency on BMI1 support, though if you already require BMI2 for PDEP, maybe this doesn't matter). But then I found <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50168> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50168>.

BeeOnRope 8y ago
Aside from that bug, it's like you said: might as well use tzcnt from BMI1 if you are already using BMI2 since there are no CPUs implementing the latter but not the former (and IIRC the reverse is even true). Using tzcnt in principle is faster than bsf in many cases since bsf always has a dependency on the output register (due to the zero input case), but tzcnt doesn't. In practice tzcnt had a false dependency anyways, at least until Skylake where that was fixed (again IIRC, I recall that one of these bit manipulation didn't have their false report fixed, but the rest did).
- nkurz 8y ago
  What did you think of their explanation of "memory parallelism" in section 4.3? I read it quickly, but thought it was pretty accurate. I liked that they made explicit the link between the number of instructions and the degree of parallelism. I was a little disappointed by the final statement that they "suspect" that the CPU is capable of only 8 parallel requests.
  - BeeOnRope 8y ago
    The analysis looks exactly right to me (they don't explain how they calculated MLP, but the numbers look about as expected for x86 ROB sizes/FB sizes). One thing they don't mention is that the low MLP isn't inherent in the other algorithms! With the default/obvious implementation of a benchmark loop using each method you hit this issue, but in principle I think you could re-write almost any algorithm which is "instruction count MLP limited" like this into another one that isn't. A simple sketch is to simply do a batch of N loads up front, storing them into a temporary buffer, then do the computation part. The loading part will have maximum MLP (after all, it's pure loads) and then the computation part will get all L1 hits unless you picked N wrong. It loses a bit because the loads aren't as effectively overlapped with computation, but if the loads time "dominates" as presented here, it would work well. A more sophisticated approach would still try to overlap computation and loads, at max MLP. You could do this by inserting additional prefetches or actual loads into the computation stream, enough to get the required MLP. This is actually kind of complicated and more dependent on the actual hardware parameters which is why I mentioned the other way first.
- BeeOnRope 8y ago
  Just double checked and the false dependency problem is fixed for tzcnt and lzcnt, but not popcnt, in Skylake. So that's one (slightly) good reason to use tzcnt over bsf if possible, as of Skylake.

by derf_ 8y ago

BeeOnRope 8y ago

Aside from that bug, it's like you said: might as well use tzcnt from BMI1 if you are already using BMI2 since there are no CPUs implementing the latter but not the former (and IIRC the reverse is even true). Using tzcnt in principle is faster than bsf in many cases since bsf always has a dependency on the output register (due to the zero input case), but tzcnt doesn't. In practice tzcnt had a false dependency anyways, at least until Skylake where that was fixed (again IIRC, I recall that one of these bit manipulation didn't have their false report fixed, but the rest did).

nkurz 8y ago
What did you think of their explanation of "memory parallelism" in section 4.3? I read it quickly, but thought it was pretty accurate. I liked that they made explicit the link between the number of instructions and the degree of parallelism. I was a little disappointed by the final statement that they "suspect" that the CPU is capable of only 8 parallel requests.
- BeeOnRope 8y ago
  The analysis looks exactly right to me (they don't explain how they calculated MLP, but the numbers look about as expected for x86 ROB sizes/FB sizes). One thing they don't mention is that the low MLP isn't inherent in the other algorithms! With the default/obvious implementation of a benchmark loop using each method you hit this issue, but in principle I think you could re-write almost any algorithm which is "instruction count MLP limited" like this into another one that isn't. A simple sketch is to simply do a batch of N loads up front, storing them into a temporary buffer, then do the computation part. The loading part will have maximum MLP (after all, it's pure loads) and then the computation part will get all L1 hits unless you picked N wrong. It loses a bit because the loads aren't as effectively overlapped with computation, but if the loads time "dominates" as presented here, it would work well. A more sophisticated approach would still try to overlap computation and loads, at max MLP. You could do this by inserting additional prefetches or actual loads into the computation stream, enough to get the required MLP. This is actually kind of complicated and more dependent on the actual hardware parameters which is why I mentioned the other way first.
BeeOnRope 8y ago
Just double checked and the false dependency problem is fixed for tzcnt and lzcnt, but not popcnt, in Skylake. So that's one (slightly) good reason to use tzcnt over bsf if possible, as of Skylake.