last day (15 days later) » 

10:07 PM
991
A: Replacing a 32-bit loop count variable with 64-bit introduces crazy performance deviations

MysticialCulprit: False Data Dependency (and the compiler isn't even aware of it) On Sandy/Ivy Bridge and Haswell processors, the instruction: popcnt src, dest appears to have a false dependency on the destination register dest. Even though the instruction only writes to it, the instruction will wait ...

 
So is there a place where you can file a bug report for Intel's processor?
 
@C.R. Or rather a bug to GCC and MSVC. It's easier to update the compiler than to fix a bunch of hardware that is already released. Since the work-around is so simple (xor reg reg), I don't expect Intel to "fix" this anytime soon. If it was a correctness issue, then it would need to be fixed. In this case it's just a moderate performance drop on an uncommon instruction.
 
@Mysticial: Very nice explanation, thanks. But a few more questions: Why does breaking the inter-iteration dependency yield such a huge benefit? I mean, there are still the intra-iteration dependencies, but it seems that these do make almost no difference, why? In addition, what would be the best way to get a reliably good popcount? Should I always use inline assembly and xor the output register before the popcnt?
 
@geixide: The processor behaves as if popcount calculated not dest = pocount (src), but for example dest = popcount (src + 0*dest). If popcount has a latency of three cycles, and always uses the same register for dest, then you can only perform one popcount every three cycles. Setting that register to 0 means that still in one iteration the popcount's are 3 cycles apart. But the processor has massive out-of-order capabilities, so the popcounts from two iterations can run in parallel. If there were no other instructions, then without the break in dependencies would start at ...
... cycle (0, 3, 6, 9) for iteration 0, (12, 15, 18, 21) for iteration 1, (24, 27, 30, 33) for iteration 2 and so on. If the dependency is broken and assuming one popcount can execute per cycle, they happen at cycle (0, 3, 6, 9), (1, 4, 7, 10), (2, 5, 8, 11), (12, 15, 18, 21) and so on.
 
@gexicide gnasher729 is spot on. The xor doesn't make a single iteration faster, but it allows the next iteration to start before the first iteration finishes. The dependency on rax forces the iterations to be sequentialized. Once you break the dependency with an xor, the processor will be able to run multiple iterations in parallel. You could also put an xor before each popcnt, but that doesn't provide much additional speedup since the processor already found a way to use all those execution units by parallelizing across iterations.
@gexicide Until GCC is fixed, yes, the only reliable way is to use inline assembly and clear the output register before issuing popcnt. Alternatively, you can use the same register for both src and dest.
 
10:07 PM
How did I know it was @Mysticial when I read the 1st line? :)
 
Not sure if this is a problem with GCC. Looks more like a problem with Intel to me. There is no reason why the code that GCC produces would be slow, except for a very strange problem in the processor.
 
This implies that the real fix is to use an AMD processor ;-)
 
Report this as GCC bug and somebody will surely fix/work around it.
 
@VáclavZeman Looks like somebody did: comments.gmane.org/gmane.comp.gcc.bugs/421045
 
10:07 PM
@gnasher729 It's definitely a design flaw in the CPU, but it is also a bug in the compiler, because it has always been a major part of the compiler's job to work around design flaws in the CPU.
 
Awesome find, Sir. Thanks for the detailed answer.
 
@Mysticial I wonder where one reports a gmane width/content-wrapping bug..
 
Has anyone checked in the Intel compiler works around this issue?
 
If you want to follow the state of this bug in GCC, this is the correct link: gcc.gnu.org/bugzilla/show_bug.cgi?id=62011
 
This has been reported to the VC++ team now, as well.
 
10:07 PM
Seems a fix has made it into GCC. From the GCC bugtracker: "Fixed for 4.9.2+."
 
@gexicide Yeah, that's pretty damn fast. It took 3+ years for someone (us) to discover this errata and under 3 weeks for GCC to work around it.
 
Could this not possibly be addressed with a microcode update?
 
@JonathonReinhart I don't think it's that simple. Intel probably can't do anything other than disable to the instruction like they did with TSX. Of course you can't just do that since the chip would no longer support SSE4.2. So you'd also have to unset the cpuid for SSE4.2 and beyond otherwise you'd break programs that use popcnt but check for the AVX feature bit. For something that's not a correctness issue, it's far too much collateral damage.
 
Excellent answer. Well, my question now to you is: how did you know that?
 
Wow. There were at least a 100 comments between here and on the question that got deleted. They would've explained everything. Lemme ask the mods about that.
@MikeNakis How I came across the answer was in the comments under the question which haven't been revived. But to summarize, I've heard of the false dependency before. And it was one of several things I suspected to be the case here. The hard part was coming up with a test to prove it.
 
 
2 hours later…
11:48 PM
@Mysticial ok, thanks
 

last day (15 days later) »