How I Got a 2x Speedup With One Line of Code

I&#x27;m sad to see that the one line of code, with its magic number and comparatively inscrutible contents, is entirely undocumented. Please, if doing things like that: a good commit message is necessary but not sufficient. (Yes, `git blame` exists, but you&#x27;re not so likely to use it as a comment in the code.) A blog post is handy but not sufficient. A good inline comment is invaluable when returning to the code later if the situation changes, as it typically will in time for such precise, empirically derived performance tweaks.<p><pre><code> &#x2F;&#x2F; This single line boosts performance by a factor of around 2 on GCC. &#x2F;&#x2F; The optimal lookahead distance i+3 was chosen by experimentation. &#x2F;&#x2F; See http:&#x2F;&#x2F;www.naftaliharris.com&#x2F;blog&#x2F;2x-speedup-with-one-line-of-code&#x2F;</code></pre>

You can get another 2x speedup if you choose the pivot better. Right now it seems you&#x27;re doing median of 3.<p>When you&#x27;re doing Order Statistics (ie Selection&#x2F;Quickselect) with 1M elements you should be very very close to the theoretical optimum (1.5N) for complexity. See my comment here:<p><a href="https://news.ycombinator.com/item?id=6629117" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=6629117</a><p>If you&#x27;re interested in choosing the best strategy.<p>HTH

Great article. But it seems somehow unfair to characterize this as a &#x27;one-line change&#x27;. He had to run various performance experiments that will be invisible to someone else reading the code, and the optimal prefetch distance might silently shift over time, like say if each object grows larger. It&#x27;s a little like the Carmack magic number in that respect: <a href="https://en.wikipedia.org/wiki/Fast_inverse_square_root" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Fast_inverse_square_root</a><p>I&#x27;ve had this idea for some time that our <i>representation</i> of programs is fundamentally broken, because it excludes a detailed characterization of the <i>input</i> space. I took a first stab at a solution with <a href="http://akkartik.name/post/tracing-tests" rel="nofollow">http:&#x2F;&#x2F;akkartik.name&#x2F;post&#x2F;tracing-tests</a>, which lets me write all my unit tests at the top level, showing how each piece of functionality augments the space of inputs my program can address. See, for example, <a href="https://github.com/akkartik/wart/blob/3039fe6d03/literate/023tokenize#L83" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;akkartik&#x2F;wart&#x2F;blob&#x2F;3039fe6d03&#x2F;literate&#x2F;02...</a>. I suspect reading other people&#x27;s &#x27;code&#x27; could be an order of magnitude easier and more convenient if &#x27;code&#x27; included the right information. I&#x27;m still working to flesh this idea out.

&gt; No way, substantial speedups can really only come from algorithm changes.<p>I&#x27;ve often found the reverse to be true; that implementation details matter most.<p>The best fixes tend to be altering my code so that the compiler&#x2F;cpu can be smarter. In this case, the author hinted the cache. Other times, I&#x27;ve found that looping in a different order helps my cache hit rate. Other times, properly naming variables and not reusing the same name allows the compiler to do smarter things.<p>Other times, when I&#x27;ve tried a new algorithm, it&#x27;s slower because of bad constants or I&#x27;ve accidentally messed up the implementation to negate all benefits.<p>As a complete side note, you need to be careful when using &quot;older&quot; algorithms, ie those published pre-2000. I once implemented, based on a Hoare paper, a doubly linked list for spare matrices, and it was significantly slower then the naive method, simply because CPU cache lines have gotten really good while being able to predict linked list memory locations had not.

I don&#x27;t think this gain came from pre-fetching anything. The compiler may simply have decided to treat the entire function, or even the entire file, differently because of that one line.<p>I compiled (x86, GCC 4.8) lazysort.c both with and without the prefetch intrinsic, and there were substantial differences in code surrounding calls in to Python, but no change at all to the guts of the partition or sorting routines.<p>Regardless of what is responsible, it&#x27;s not good to leave something like this in your code without really understanding what it did. There may have something else that occurred incidentally from this change, that could have lead you to a better solution.

There are only two really difficult problems in computer science: naming things, cache invalidation, and off-by-one errors.

&gt;&gt; The moral of the story, at least for me, is that you can occasionally get substantial improvements by understanding what is actually happening under the hood of your application, rather than fundamentally changing your application itself.<p>Also known as the rule of leaky abstractions, as in all abstractions are leaky.

Note that `ob_item[i+3]` could read past the end of the array.

I got a 1000 X speedup by removing a sleep(100000) line once. Not as impressive though.

I would expect that that magic number 3 is related to the size of a cache line relative to the size of an array element and the time spent in each loop. You will want to prefetch the next cache line so that it is just available by the time you want to start processing it (and, ideally, not a moment earlier because that would push data from the cache that still could be used before the requested data is needed)<p>A robust implementation should figure out the size of a cache line and the load delay, and derive the magic offset from that.

Er, are you aware of the C++ standard library&#x27;s std::nth_element() function? (Even my &quot;pure C&quot; programs tend to be compiled with g++ to gain access to that and std::sort().)

<i>Now, I didn&#x27;t just &quot;know&quot; to prefetch the PyObject three indices forward in the array. I arrived at this value through experimentation.</i><p>There is a good chance that 3 is specific to the hardware you tested on. Different systems will have different memory latencies (and NUMA systems can make it even more complicated). It isn&#x27;t likely that 3 will turn into a pathological case on any other hardware, but it may well end up being less optimal than say 2 or 4.

This sort of thing is why porting naive x86 code to the GPU programming model (scalar programs aka &#x27;kernels&#x27; streamed through on the device using a configuration) often results in amazing 15-20x speedup over 6 core, while the expected speedup is only 5-7x. x86 compilers often don&#x27;t get the pre-fetching right in loops, only using their heuristics, so you have to talk to them. Then you you begin to doubt the compiler more and more, carving out a few percentage points here and there by adding vector intrinsics, loop unrolling and so on. And before you notice, your codebase is now bigger, more complex and more error prone than if you had ported it to GPU from the beginning.<p>Please note - of course this insight doesn&#x27;t apply in your case since your algorithm is meant for general purpose usage, not HPC programming meant for systems where you have the hardware under your control. I&#x27;m simply urging people where the latter applies to think about whether their algorithms might be suitable for GPU instead - doing lots of prefetch instructions and loop unrolls is a sign of that.

Nice article.<p>One thing that wasn&#x27;t clear to me in your explanation is that you&#x27;re sorting a list of pointers to objects. To sort that list you&#x27;re comparing two of the objects themselves.<p><pre><code> &#x2F;&#x2F; follows pointer to access *ob_item[i] IF_LESS_THAN(ob_item[i], pivot) </code></pre> So the point of __builtin_prefetch is to deference this pointer in advance and so avoid the latency of the 12 million reads scattered all over memory. Nice.<p>Another useful thing to do here is to see if you can find a &quot;streaming operator&quot; to dismiss *ob_item[i] and ob_item[i] from cache after the comparison. They won&#x27;t be needed again for a while.<p>Another good article on this optimisation (mentioned by OP)<p><a href="http://scripts.mit.edu/~birge/blog/accelerating-code-using-gccs-prefetch-extension/" rel="nofollow">http:&#x2F;&#x2F;scripts.mit.edu&#x2F;~birge&#x2F;blog&#x2F;accelerating-code-using-g...</a>

This is a great post. I guess the idea here is that you can start bringing future objects to be compared up through the cache hierarchy while you are doing the comparison on the current object. If that&#x27;s the case, then I think the speedup from prefetching will depend on the speed of the comparison which in turn will depend on the type of objects in the collection.<p>In your post it says you have a collection of 10MM elements but you didn&#x27;t say what they were. Are they just ints or something else?

Funny, I just experimented with __builtin_prefetch this week, and got no speedup. Does anyone know whether the kernel list.h always triggers hardware prefetching when going over a list?<p>BTW, my case wasn&#x27;t the problem the kernel maintainers encountered with small lists, detailed here:<p><a href="http://lwn.net/Articles/444336/" rel="nofollow">http:&#x2F;&#x2F;lwn.net&#x2F;Articles&#x2F;444336&#x2F;</a>

I&#x27;m pretty sure you could have saved yourself a lot of work by just using profile guided optimisation (PGO). It&#x27;s mature &amp; ready to go in GCC at least.<p>(Integrating it into you build process is a little bit more challenging, I admit. I&#x27;ve set it up in a large dev environment used by multiple large projects, and it was well, well worth the effort.)

its one of those things... micro optimisation becomes the big one once you do enough algorithm optimisation. even the humble memory copy becomes faster from prefetching and clever use of registers... and actually making the algorithm theoretically worse. :P<p>also, note that it is possible to remove the magic from your magic number with some thought about latency, the size and alignment of your data etc. fetching a cache line takes a fairly predictable amount of cycles.<p>opposite to the prefetch is the non temporal read&#x2F;writes where you don&#x27;t pollute cache to prevent big one off copies from damaging the performance of other code...

Interesting post! I wonder if the author experimented with different gcc command-line optimisation options as well? gcc <i>might</i> be able to insert some prefetches by itself with some settings?

Came expecting <a href="http://thedailywtf.com/Articles/The-Speedup-Loop.aspx" rel="nofollow">http:&#x2F;&#x2F;thedailywtf.com&#x2F;Articles&#x2F;The-Speedup-Loop.aspx</a>, was disappointed...

also, read this: <a href="http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/graphics-programming-black-book-r1698" rel="nofollow">http:&#x2F;&#x2F;www.gamedev.net&#x2F;page&#x2F;resources&#x2F;_&#x2F;technical&#x2F;graphics-p...</a>

I get at least that good with<p><pre><code> DEFINT A-Z</code></pre>