What is the ninja performance gap, why is it so large, and how can we overcome it?

Question

According to this abstract:

The "Ninja gap" [...] is the performance gap between naively written C/C++ code that is parallelism unaware (often serial) and best-optimized code on modern multi-/many-core processors.

It appears that they are saying that a programmer who can skilfully handle concurrency can write much more efficient code than a programmer who cannot. As I am beginning to write multithreaded programs, I am starting to gain an intuition for this myself.

After a reread of the abstract, they appear to argue that applying well known algorithms can close the gap. I find the question intriguing.

So, in the interest of having this question asked here on Programmers:

• What is the "ninja performance gap?" (and were these words chosen well? I think perhaps not.)
• Why is it so large? (Or do we question the size of it? )
• How can it be overcome? (How do we learn to overcome it? Should we learn skillful concurrency or learn algorithms?)

Answer 1

What is the "ninja performance gap?"

A naive approach finishing many tasks might be to start one task, wait for it to finish, and only then to start the next task. Suppose one wanted to retrieve many networked resources. The naive approach would be to send a request for the first resource, wait for the request to complete, then send the next.

If a good programmer is skilled at concurrency, such a programmer could write a program that executes many actions at a single time using all the resources of the computer on which it runs (processors, system memory, etc.). Using the network resource example above, the optimal approach would be to attempt to get many resources at the same time.

The gap between the naive approach and the most optimal approach is what these authors (and apparently others) are calling the "ninja performance gap."

Were these words chosen well?

They were likely chosen for promotional and novelty value. As the phenomenon appears to be a very real problem, I would have preferred a term that focused on the problem as opposed to the actors on one side of the gap.

Perhaps "optimized concurrency gap" would have been a better choice in words.

Why is it so large?

The naive approach to solving many problems with computers can be quite inefficient relative to known improvements.

My own experience with Project Euler demonstrated this to me, with some solutions not completing in any reasonable amount of time (minutes, hours), but other solutions to the same problem finishing blazingly fast (within a few seconds).

Bubble sort is known to be quite inefficient relative to other sorting algorithms.

Do we question the size of it?

Based on the above knowledge, I do not question the size as stated.

How can it be overcome?

The naive solution would be for the programmer to study threading and all of the relevant skills to close this gap. Closing the gap in this manner would take a lot of time and effort, both to gain the skills and to write the programs.

How do we learn to overcome it? Should we learn skillful concurrency or learn algorithms?

The paper's abstract states that using better algorithms combined with better compilers can relatively minimize the gap with much less effort required. I am inclined, without direct knowledge, to believe them.

Answer 2

Note that the difference is between "naïvely written and parallelism unaware code" and optimised code. Your conclusion that there is a difference in quality between the developers responsible is completely unjustified. Naïvely written and parallelism unaware code is much easier and cheaper to write, and it is much easier and cheaper to make reliable.

At some point (and before we start optimising) a decision has to be made whether optimisation is worthwhile. The code may run 10 times faster, but does this actually result in value that is equal or higher than the cost of the optimisation? Not to everyone, but to the ones paying for the optimisation? That decision will often be that optimisation isn't paying off. In many places, the cost of running unoptimised software is much less than the cost of optimising it.

At home, I often go into "Ninja mode" because it is fun. Improving the speed of code that I've written myself by a factor 10 is usually not a big problem. It has happened that I took handwritten SIMD assembler code and improved it by a factor 10 with C code. However, I haven't encountered a situation in commercial programming in the last years where there was any need for this. (There was an occassional need to replace stupid code with naïve code, which made it ten times faster or more).

For most situations, there is no need for optimisation. There is definitely no need for everyone to be able to write optimised code.

Answer 3

If you put the title of the paper into Google Scholar you'll get a link to where IBM hosts the paper: https://software.intel.com/sites/default/files/article/386514/isca-2012-paper.pdf

Or you can use Google directly and get a link to where one of the author's host institution's has a full version of the paper: http://web.eecs.umich.edu/~msmelyan/papers/isca-2012-paper.pdf

The short answer is you'll need to read up on algorithms designed for parallelism (the paper lists a number of them and related techniques), but there is in a nutshell no silver bullet presently available. Techniques that are most commonly used in programming today - default sort methods, access patterns, etc - are not able to take advantage of most performance improvements possible with parallel computation. To take advantage of multiple processors requires learning new techniques, adapting existing tools, and using bench marking to see if what you are doing is working as you expect.

Answer 4

The paper refers to maximizing performance from both SIMD and multicore parallelism, along with other techniques such as loop-unrolling and cache performance. So it is not just parallelism alone.

"Ninja" refers to expert programmers. In other words, the "Ninja gap" is the performance difference between a masterpiece and an apprentice's work.

The paper goes on to explain how to incrementally transform (rewrite) an apprentice's work into a masterpiece.

Quoted from the abstract (emphasis mine):

We show how a set of well-known algorithmic changes coupled with advancements in modern compiler technology can bring down the Ninja gap to an average of just 1.3X.

In other words, it is not about using well-known algorithms; it is about applying well-known algorithm refactoring techniques for performance gains.

Some of the algorithm refactoring techniques mentioned in the paper are:
(The paper only mentions the terms without explanation; my explanations might be wrong.)

• Cache blocking (when an algorithm iterates through one or more dimensions, introduce intermediate loops into the iteration in order to maximize cache locality (spatial and temporal locality) and therefore cache hit rates)
• Changing memory layouts of data to improve bandwidth and SIMD performance. In particular, switching between AOS and SOA (array-of-structs and structs-of-arrays), alignment of data to cachelines and/or SIMD alignment requirements, etc.
• Switching to alternative algorithms which give equivalent results but are more SIMD friendly.

Note that the paper does not attribute all of the performance gains to the use of these techniques. The authors also experimented with many compiler features such as auto-vectorization (into SIMD code generation), auto-parallelization (over multiple cores), and loop-unrolling.