Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang?

by

Several of the answers in the question you link talk about rewriting the code to be branchless and thus avoiding any branch prediction issues. That’s what your updated compiler is doing.

Specifically, clang++ 10 with -O3 vectorizes the inner loop. See the code on godbolt, lines 36-67 of the assembly. The code is a little bit complicated, but one thing you definitely don’t see is any conditional branch on the data[c] >= 128 test. Instead it uses vector compare instructions (pcmpgtd) whose output is a mask with 1s for matching elements and 0s for non-matching. The subsequent pand with this mask replaces the non-matching elements by 0, so that they do not contribute anything when unconditionally added to the sum.

The rough C++ equivalent would be

sum += data[c] & -(data[c] >= 128);

The code actually keeps two running 64-bit sums, for the even and odd elements of the array, so that they can be accumulated in parallel and then added together at the end of the loop.

Some of the extra complexity is to take care of sign-extending the 32-bit data elements to 64 bits; that’s what sequences like pxor xmm5, xmm5 ; pcmpgtd xmm5, xmm4 ; punpckldq xmm4, xmm5 accomplish. Turn on -mavx2 and you’ll see a simpler vpmovsxdq ymm5, xmm5 in its place.

The code also looks long because the loop has been unrolled, processing 8 elements of data per iteration.

More Related Contents:

  1. Why won't clang compile this source code that works in VS2012?
  2. Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly?
  3. What is a “cache-friendly” code?
  4. Modular arithmetics and NTT (finite field DFT) optimizations
  5. Is there any advantage of using map over unordered_map in case of trivial keys?
  6. Static linking vs dynamic linking
  7. Deoptimizing a program for the pipeline in Intel Sandybridge-family CPUs
  8. Efficient string concatenation in C++
  9. Using scanf() in C++ programs is faster than using cin?
  10. Avoid stalling pipeline by calculating conditional early
  11. Relative performance of std::vector vs. std::list vs. std::slist?
  12. Is inline assembly language slower than native C++ code?
  13. Error enabling openmp – “ld: library not found for -lgomp” and Clang errors
  14. How to generate assembly code with clang in Intel syntax?
  15. Performance of dynamic_cast?
  16. C++ cout printing slowly
  17. Are C++17 Parallel Algorithms implemented already?
  18. What is the performance cost of having a virtual method in a C++ class?
  19. Why is iterating though `std::vector` faster than iterating though `std::array`?
  20. c++11 regex slower than python
  21. Does hardware memory barrier make visibility of atomic operations faster in addition to providing necessary guarantees?
  22. Clang C++ Cross Compiler – Generating Windows Executable from Mac OS X
  23. Which is faster: x
  24. What is a good random number generator for a game?
  25. Why do lambda functions drop deduced return type reference by default?
  26. How to use CMAKE_EXPORT_COMPILE_COMMANDS?
  27. Benefits of using reserve() in a vector – C++
  28. Which is faster/preferred: memset or for loop to zero out an array of doubles?
  29. C++ Serialization Performance
  30. Why is pow(int, int) so slow?

Leave a Comment