last day (15 days later) » 

10:25 PM
846
Q: Replacing a 32-bit loop count variable with 64-bit introduces crazy performance deviations

gexicideI was looking for the fastest way to popcount large arrays of data. I encountered a very weird effect: Changing the loop variable from unsigned to uint64_t made the performance drop by 50% on my PC. The Benchmark #include <iostream> #include <chrono> #include <x86intrin.h> int main(int argc, c...

 
user395760
You seem to have hit a rather drastic bad case in one of the many heuristics powering the optimization pipeline. But what and where is hard to say without seeing the assembly code, could you add it?
 
@delnan: I will add it, give a sec!
 
You only have a very small number of useful instructions in your inner loop - you might try unrolling by a larger factor and see if that helps.
 
I can reproduce similar results on my machine, using clang++ from a few weeks back and a home-built 4.8.2 g++. The g++ code seems to use a prefetchnta instruction in the 64-bit code, but not in the 32-bit loop counter. That's the only obvious difference I can see. But I don't have a Haswell machine, and I only get about 9GB/s for the faster case, and 6GB/s in the slower case.
 
@delnan: I have added all relevant assemblies at the bottom of the post. They are really quite strange.
 
10:25 PM
You can generate assembler code before the change and after the and compare it. What was changed?
 
@MatsPetersson: I have added my assembly. I cannot reproduce the prefetchnta instruction. My fastest solution doesn't have it.
 
user395760
Very curious indeed. My best guess involves scheduling voodo (some of those permutations of instructions causing pipeline stalls).
 
How many bytes are the instructions? The 64-bit versions might simply take more bytes and take longer to decode.
 
Ok, so with some fiddling of code-gen flags (in particular -mtune=core-avx2, which generates code that works on my processor, but tunes suitable for Haswell type processor), I got rid of the extra prefetch instruction, and the result is the same [+/- a few decimals] in both variants. But that's on a rather old AMD processor, so not really strange. On my processor, clang++ also generates same speed code.
 
@MatsPetersson: So the results are even similar on AMD? That means it is not even Intel specific but the generated code is really always that strange.
 
10:25 PM
"Similar" = 9GB/s for all cases, not "faster in one variant than other".
 
@MatsPetersson: Oh, okay, then I interpreted your comment wrongly. Thanks for the clarification.
 
It would be interesting to see an output of perf stat. I would also try to compile it with other optimization flags: O0, O1, O2, maybe even Os and see how they change results.
 
M.M
by atol(argv[1])<<20; did you mean ((uint64_t)atol(argv[1])) << 20 ?
 
@MattMcNabb: No, it is like I wrote. Since the value fits into 32bits (I only measured for 1 MB), the cast to uint64_t is unnecessary.
 
Your disassembly for the "g++ / u64 / non-const bufsize" case looks incorrect. The value of RDX doesn't change on each iteration, it's always set to 0 at the start of the loop, so the four POPCNT instructions always operate on the same 4 locations in memory. There seems to be a missing inner loop, one starting after NOP instruction which would be there to align the start of that loop. Either GCC has produced bad code, or you haven't copied the disassembly correctly.
 
10:25 PM
@RossRidge Thank you for noticing this! It was indeed a copy paste error. I have fixed it now. Now, the code does no longer have two loops; the code looks even quite fine now, I think.
 
@Mysticial Take a look?
 
Can you include the clock speeds of each of the processors you tested? Including whether or not Turbo Boost might have kicked in.
 
@Mysticial: How can I check wether Turbo Boost kicked in? Judging only on usage pattern: It should have done, as the benchmark uses a single core while no other cores need to do any work.
 
I assume the the _mm_popcnt_u64 intrinsic wants the parameter aligned to an 8-byte boundary. Is it possible that in some versions, it's aligned to only a 4-byte boundary, causing the CPU to do extra work to load the value in two steps instead of one?
 
All I can say is WTF at this point. There's something funny going on with the ordering of adds and popcounts. All the slow versions have the adds/popcount fully interleaved. The fast ones are either not interleaved or only partially interleaved. Furthermore, there might be a false input dependency on the output register for popcount. Anyways, I have an appointment so I can't take another look for a while. (It repros in Windows/VS2013/Haswell. There is no difference on Windows/VS2013/Piledriver.)
 
10:25 PM
@AdrianMcCarthy: It could be, but both loops use the same buffer, so one being fast and one being slow cannot be explained by that. In addition, I am quite sure my malloc does 8byte alignment. I also tried using memalign without any difference. It really seems to be only the different assembly instructions that are generated.
@Mystical: Interesting, so does that mean that even a third compiler produces such results? What evil scenario is this? There seems to be no compiler that can grant stable results here, although all these compilers might use very different optimization techniques and orders... (or maybe this is only a hint that most optimization code in compilers is copied from each other ;)
 
@gexicide Or rather, the evidence seem to suggest it's just a performance pothole on Intel processors. They usually don't document them.
 
@BenVoigt: size
@BenVoigt: Thanks, corrected.
 
usr
I understand you want an explanation. Maybe a workaround is also useful: Compile all these versions into the binary and chose the best one at runtime by performing a short-running benchmark. That way you get the best possible performance on all machines.
 
@usr It might be easier to do inline assembly at that point. :)
 
usr
@Mysticial it looked to me that different machines had different optimal versions. Maybe I skimmed the cases too quickly.
 
10:25 PM
I think I have an answer for this. I'll post an answer once I finalize my numbers.
 
@Mysticial: Great, looking forward to it, based on your previous answers.
 
Off topic, but the words "upper case" and "lower case" in there played havoc with my own internal optimisation routines; I had to switch to a slower reading speed.
 
Hase you tried to do it not in steps of 4 but in steps of 1, 2, 3, 5, 6, 7 or 8?
 

last day (15 days later) »