LWN: Comments on "Memory part 5: What programmers can do"

Memory part 5: What programmers can do

iulianm — 2007-11-02T17:20:19+00:00

...ignore the cache dirtying part... I meant loading more cache lines to access mul2 in the
innermost loop, when only one is needed

Memory part 5: What programmers can do

iulianm — 2007-11-02T15:34:06+00:00

Referring to the optimized matrix multiplication code, the text reads:

> k2 and j2 loops are in a different order. This is done since, in the actual 
> computation, only one expression depends on k2 but two depend on j2

I believe that a better reason for changing the order of the two loops is that this way the
mul2 matrix is traversed by rows instead of by columns, which is the whole point of the
example since it prevents cache dirtying when accessing the elements of this matrix.

Memory part 5: What programmers can do

wingo — 2007-10-31T10:40:23+00:00

I thought the same.

matrix multiply optimization

giraffedata — 2007-10-27T22:41:11+00:00

Aha. Perfectly clear now. The article neglects to explain this; I'd probably say, "the original traverses mul2 in this expensive nonsequential way 1000 times, whereas the improved version does it only once."

matrix multiply optimization

bartoldeman — 2007-10-27T21:55:06+00:00

Because transposition uses O(N^2) accesses and multiplication O(N^3). The accesses in the
transposition are more expensive but there are N times fewer than in the multiplication...

matrix multiply optimization

giraffedata — 2007-10-27T21:44:09+00:00

Only about a factor of 5 is due to memory optimization. The vector instruction optimization is simply applying more CPU horsepower.

What I can't figure out is how the transposition speeds anything up. The article points out that it removes 1000 non-sequential accesses per column from the multiplication loop, but I see that same 1000 non-sequential accesses per column added to the transposition loop.

76.6% speedup

giraffedata — 2007-10-27T21:32:20+00:00

I think it's ambiguous. While it's clear that it's a 427% increase in speed and a 77% decrease in slowness, "speed-up" might refer to either of those, and also to the 77% reduction in execution time.

For practical use, I believe per centages of execution time are more useful than per centages of speed because time is the limited resource.

Memory part 5: What programmers can do

bartoldeman — 2007-10-27T14:15:50+00:00

It is even 20 times faster if you use ATLAS 3.8:
http://math-atlas.sourceforge.net/
Its DGEMM routine does the job in around 708,000,000 cycles, another factor of 2 faster (my
other numbers, also on a Core 2 (a Duo, but single threaded), were very similar to Ulrich's so
I can state this with some confidence). Of course there's been a lot of research and tweaking
to obtain this score.

ATLAS' SUMMARY.LOG reports for DGEMM:
 Performance: 4846.05MFLOPS (302.88 percent of of detected clock rate)
and this is on a 1.6GHz Core 2 Duo, not 2.66GHz!

GOTOBLAS may also be worth looking at, for comparison. It looks more into TLB misses than
ATLAS does.

Cache-oblivious algorithms

akapoor — 2007-10-26T13:30:56+00:00

i guess it's worth mentioning harald-prokop's 1999 thesis on "cache oblivious algorithms"
(http://citeseer.ist.psu.edu/prokop99cacheobliviou.html).

Memory part 5: What programmers can do

avassalotti — 2007-10-26T02:42:41+00:00

                Original        Transposed
    Cycles	16,765,297,870  3,922,373,010
    Relative	100%            23.4%

Through the simple transformation of the matrix we can achieve a 76.6% speed-up!

I could wrong, but I think that is a speedup of 427.4%, not 76.6%

Missing: conventional wisdom turned into lie

mmutz — 2007-10-25T10:48:22+00:00

> If the array all fits in cache, binary search wins: both linear and
> binary search, at most, load the data into cache once. If the array is
> extremely large, binary search still wins despite the wasted reads of
> entire cache lines, because at some point N/log(N) exceeds the miss
> penalty.

This is exactly the conventional wisdom I think isn't true anymore for 
some realistic examples. You're missing the effect of the hardware 
prefetcher, which will, for some sizes, and esp. for cold caches lead to a 
performance increase for the linear search, as opposed to binary search, 
which looks like random access to the prefetcher, and therefore incurs the 
RAM->cache latency cost typically hidden by the prefetcher.

On very small arrays binary search loses - did so for years

khim — 2007-10-24T20:29:42+00:00

If you just have 4-5 elements in the array then initial complexity of binary search will dominate - with or without memory access effects. At some point binary search will win - but it'll be good exercise to find this point today...

Actually it's true for most algorithms: bubble sort also wins for small arrays, for example. Usually trivial algorithms work well for small sizes but not-so-well for medium-to-large sizes. Usually it's not worth the effort to optimize for small sizes: it's fast not matter what algorithm you are using. If your program is spending 90% of time searchive 5-element arrays - it's different story, of course, but it's rare in practice...

Missing: conventional wisdom turned into lie

JoeBuck — 2007-10-24T16:21:17+00:00

If the array all fits in cache, binary search wins: both linear and binary search, at most, load the data into cache once. If the array is extremely large, binary search still wins despite the wasted reads of entire cache lines, because at some point N/log(N) exceeds the miss penalty. There may be intermediate values where binary search loses, when the random access causes the cache miss rate to soar and this isn't compensated for adequately by the reduced expected number of element accesses.

Missing: conventional wisdom turned into lie

mmutz — 2007-10-24T12:48:35+00:00

One thing I miss (but that maybe comes later) is the effect of all this on 
common-sense optimizations such as binary search. E.g., it would 
be interesting for what kind of working sets binary search (having to look 
random to even current prefetchers) actually starts to perform better than 
linear search.

It would be a nice example of how a O(N) algorithm can dramatically
outperform a O(log N) algorithm, due to memory effects. I'm sure there's 
lots more of common wisdom that turns into a lie on modern processors.

cachegrind

JoeBuck — 2007-10-24T04:55:03+00:00

I would expect to see some mention of cachegrind and related tools, for helping to identify where the cache misses are and getting a good estimate of what they are costing you. Maybe Uli will address that in a different section.

Memory part 5: What programmers can do

alangley — 2007-10-24T04:54:33+00:00

In Table 6.1, are not the numbers in the second column the wrong way round? The commentary
just below it suggests that the non-temporal case should be faster.

Cache-oblivious algorithms

ncm — 2007-10-24T02:55:32+00:00

It is worth mentioning here what are now called "cache-oblivious" algorithms -- ways to code that get most of the benefits of torturing your code to match all the cache and cache-line sizes without actually knowing what any of those sizes are. The approach involves traversing data sets in an order that noodles around using a maximally-folded curve, to improve locality regardless of cache boundaries.

The general approach was first applied to matrix operations by Todd Veldhuizen in 1996. Veldhuizen used it in his Free matrix library Blitz++, which he demonstrated running 60% faster than IBM's own Fortran running on an IBM vector machine. Harold Prokop proposed the name that stuck in a paper in 1998. (Oddly, Prokop et al. have refused to acknowledge Veldhuizen's prior work.) Veldhuizen is now a professor at U. Waterloo. The technique is used in the "FFTW" FFT library, and in every modern C++ matrix library, and graduate students everywhere are writing theses on adapting various algorithms to use it.

(Cache-oblivious sorting, by the way, was developed in the '70s, but at the time the "cache" was main memory, of a size similar to the L2 caches today, which spilled to disk or tape.)

As a consequence of its ability to encapsulate these techniques (and many others) in easy-to-use libraries, since about 2000 C++ has been the preferred language for serious numeric computation. In another recent advance, the (GPL'd) VSIPL++ library encapsulates parallel processing (using e.g. MPI), making it easy to write portable, automatically parallelized matrix and image processing programs.

Memory part 5: What programmers can do

Coren — 2007-10-23T22:32:15+00:00

10 times faster on a simple plain matrix multiplication. Amazing.
With optimizing only memory access. 

I did not realise, before this series of articles, that memory can take a such place in
optimisation.

Thanks a lot, it's so interesting and well written.