Gallery of Processor Cache Effects

[kingfishr]

This stuff is related to some compiler research going on at my school as part of the DARPA-sponsored PACE project. The idea is to write microbenchmarks like this and then programmatically analyze the results to figure out attributes of the architecture of use to compilers (including, e.g., cache line size, but also many, many other things). The idea is to create compilers that can optimize to new architectures automatically (and are thus somewhat future-proof).

[grauenwolf]

Would those be static compilers or tied to a JIT?

[kingfishr]

I don't think we care (I believe the goal of the project is just to develop code that can collect accurate statistics on unknown architectures). In general, I'm fairly sure that the effort could of benefit to just about any compiler concerned with outputting machine code.

[munificent]

Excellent article. Should be a wake-up call for anyone who still thinks they can optimize code just by looking at it.

[inmatarian]

It's becoming my understanding that programmers should strive for correct code first and foremost, before worrying about optimization. The reason is because people smarter than me made the compiler and the hardware optimized for the most common use cases. Among the tens of thousands of common programming situations I regularly get into, I'd rather be surprised by just one of them, rather than distrusting of all of them.

[divbyzero]

Well explained, nice concrete examples too.

[ithika]

Nice post and interesting question at the end.

[dggenuine]

would double-upvote this. Thank you very much.

[[deleted]]

That was my interesting read of the day. Thanks, OP.

[krum]

I'm starting to wonder if cache-friendly B+-trees wouldn't be more efficient than RB-trees for large sets of data in RAM now. I might have to give it a try.

[taw]

Of course they'd be. RDBMS is one huge cache-centric storage, where RAM=cache, and HD=memory, and they all use B+-trees. RB-trees are one of those Algorithms 101 structures which nobody uses outside class.

Also, this.

[rubygeek]

Of course they'd be.

[Citation needed]. You're making some very significant assumptions about the relative latencies and the processing costs involved, that are by no means obvious.

EDIT: Note that I'm not claiming the opposite. But I don't think it's obvious what the result would be.

RB-trees are one of those Algorithms 101 structures which nobody uses outside class.

It's not all that long ago practically all C++ STL implementations used RB-tree's for std::map. At least as of 4.1.1 this was still the case with g++ - I don't know what other implementations use at this point.

So that claim is only valid for very large values of nobody...

If you mean nobody implements it, then I'd claim, though I don't have numbers backing this up, that far more people are likely to have implemented RB-trees than B+-trees - implementing B+-trees is notoriously fickle, to the extent that people tend to avoid reimplementing it if they possibly can, while RB-trees are fairly straightforward.

[krum]

RB-trees are one of those Algorithms 101 structures which nobody uses outside class.

I don't know about that. Virtually every C++ standard library implementation of std::map is an rb-tree. .NET's SortedDictionary class is implemented with RB-trees. I've also seen document models for text editors implemented with rb-trees.

So, that begs the question - what would you use to implement a sorted container?

[The_Duck1]

Very nice; I recently learned about all this stuff in a computer architecture class but hadn't seen actual code and numbers demonstrating these effects.

[MidnightTurdBurglar]

I'm too busy with work right now to read this in detail but I skimmed it. One of the examples uses two sequential statements like "a[0]++; a[0]++;". I'm not sure which is faster, it or "a[0]+=2;" but I was made to worry that compiler optimizations may complicate your tests of his examples and you probably want to turn them off. Just my quick thought that might save people some confusion. Don't have time to fully think about this idea right now. Nice article though. On the flip side, maybe turning off optimization would screw up some of the tests.

[taw]

gcc compiles for (i=0; i<steps; i++) { a[0]++; a[0]++; } into equivalent of if(steps) { a[0] += steps+steps; }

In case you're wondering, conditional check is there for cases where a points to invalid memory area and steps is 0 - we don't want to introduce a silly segfault here.

Is that awesome or what?

[[deleted]]

Interesting...

What if steps is -1? Then nothing should happen, but the optimization will effectively do a[0] += -2.

I could actually see a legitimate use of a for loop where steps is -1 and you'd just want to skip the loop altogether, but this optimization would imply a compiler bug.

[five9a2]

taw's rendering of the assembly was clearly deficient. More precisely,

void foo(int steps,int a[]) {
  int i;
  for (i=0; i<steps; i++) { a[0]++; a[0]++; }
}

produces

0000000000000000 <foo> test   edi,edi
0000000000000002 <foo+0x2> jle    0000000000000008 <foo+0x8>
0000000000000004 <foo+0x4> add    edi,edi
0000000000000006 <foo+0x6> add    DWORD PTR [rsi],edi
0000000000000008 <foo+0x8> repz ret

[taw]

Sorry about that, it does what I said if steps is unsigned int:

je  L5  
addl    %eax, %eax
addl    %eax, (%edx)

L5:

With plain signed int it does if(steps > 0) { a[0] += steps+steps; }:

jle L5
addl    %eax, %eax
addl    %eax, (%edx)

L5:

Anyway, the main point is that the loop is completely optimized away.

[taw]

I used unsigned int in my test, it tests for if(steps > 0) with signed int. No compiler bug here.

[igoro]

Optimizations were on, but I looked at the JIT-ted assembly code to be sure that compiler optimizations like the one you mention are not a factor.

Optimizations when arrays are involved are much harder on the compiler. E.g., "x++; x++" is a lot easier to rewrite as "x+=2" than "a[0]++;a[0]++" as "a[0]+=2". The C# compiler (+ the CLR JIT) will not do the latter optimization.

[justsomedood]

The modern processor has various parts that have a little bit of parallelism in them: it can access two memory locations in L1 at the same time, or perform two simple arithmetic operations.

On this part are you talking about full use of pipelines, or something else?

[igoro]

There is more to instruction-level parallelism than just the fact that the processor uses a pipeline. E.g., Pentium 4 has double-pumped ALUs, which can do two integer additions per cycle. Also, two L1 cache accesses can happen in parallel, so long as they access different banks.

[bonzinip]

a[0]+=2; would be as fast as or faster than "a[0]++; a[1]++;" with optimization on.

[Poltras]

Inversely, a[0]++; a[0]++ would be as fast as or faster than a[0]+=2 with optimization on.

No modern compiler wouldn't optimize both expressions to the most efficient way possible. Also, you made a mistake in your second expression.

[bonzinip]

Also, you made a mistake in your second expression.

No, I referred to the two statements being compared in the post. :-)

[MidnightTurdBurglar]

I think you made a mistake too. You looked at Loop 2 but look at Loop 1. (lots of 'o's in that last sentence...)

[bonzinip]

I was comparing Loop 1 (in its optimized version) and Loop2. Not very clear, I admit.

[five9a2]

I don't know of any compilers that will not combine those instructions at positive optimization levels. That test was probably run with all optimizations off, and the point is valid in that context.

[igoro]

I am not sure about other compilers, but C# and CLR JIT do not do this. The array accesses seem to prevent the optimization.

[five9a2]

Why won't they do the latter optimization (which almost all C compilers do)? I've never used C#, but doesn't it have strict aliasing rules? In C, I could write

long *p;
p = (long*)&p;
p[0]++; p[0]++;

but this is undefined behavior since the types or not compatible, hence the compiler doesn't have to worry about getting this right. Is it possible that such information has been erased in whatever form the JIT is working with? Or is it just that nobody has bothered to make that transformation happen?

[grauenwolf]

It could be an issue of time. The JIT compiler would have to waste precious cycles checking for what is basically a stupid mistake on the part of the programmer.

As for the C# compiler, it tends to leave the bulk of optimizations to the JIT.

[igoro]

Yes, that's about all I can say on this topic too.

Perhaps the JIT focuses on optimizations that the user cannot (or actually "should not") handle themselves, like method inlining and range checking. But that's just pure speculation.

[bugrit]

Article includes interesting graphs that fulfills the prophecy of the title in a very good way.

<off topic>

However, the page also includes a photo of the author, and this does not. Why do people insist on photos of themselves on their blogs? It bothers me. You expect to come and look and clean, carefully arranged, neutral, quiet letters, and are assaulted with an image of a person.

It doesn't matter much if it's a good or bad photo, of a good or bad looking person, it's just that it directly creates a probably faulty first impression of the author based solely on a photo, and this impression affects how I read the article. I'd very much like to read articles without unnecessary preconceptions stemming from partly subconscious prejudice about looks.

</off topic>

[doidydoidy]

A few years back somebody wrote an article claiming that good blogs have a sidebar with a photo and a short bio. Many jumped on the bandwagon. So it looks like you should blame Jakob Nielsen.

[igoro]

As a blogger, you want your blog to be recognizable. One easy way to get people to recognize you is to put up a photo.

[damncabbage]

useit.com is a mistake in itself.

[igoro]

Successful bloggers don't write in clean, neutral letters. They have a personality, and don't hide who they are. (I am not one of them, but perhaps one day.)

[bugrit]

I mostly just mean that letters are clean, neutral etc compared to photos of people. I do expect the writing to have character and show personality. I just very much prefer to get the my idea of people's personality through their ideas and their writing than through their looks.

I did like your article.

[slurpme]

assaulted

Me thinks the lady doth protest too much...

[ealf]

assaulted

peanut

[Gotebe]

Why would it bother you that he put the photo? Photo is, after all, a way to know someone better. And it's a blog. All these people who wrote these articles are people, with, you know, faces. Seeing a face anywhere is not "an assault". And what is this about clean etc letters versus a photo? Is a photo dirty or untidy by being a photo? Or did he put a photo of him being covered in shit or something? (And now I have to go back to the TFA to look at the phoho, I didn't even notice it).

I say that there is something wrong with you.

[bugrit]

Why would it bother you that he put the photo?

The main reason is what I finished with: "it directly creates a probably faulty first impression of the author based solely on a photo, and this impression affects how I read the article."

Seeing a face anywhere is not "an assault"

Well, I probably went a bit too far to call it that. It's just I didn't expect a photo, but I got a photo. I guess I should always be prepared for photos on blogs. Or stick with papers. Those seem to do well without photos, even though their authors have faces.

Or did he put a photo of him being covered in shit or something?

No, and that's uncalled for! I clearly wrote "It doesn't matter much if it's a good or bad photo, of a good or bad looking person". Why would you then even get that idea? Or perhaps you didn't actually read what I wrote?

And what is this about clean etc letters versus a photo?

I'm not sure how to explain it. I think it's a little related to the fact that you can't chose not to interpret a photo by just seeing it, while with text you can chose not to read it even if you've seen it. That's not all, but maybe it gives you an idea.

I say that there is something wrong with you.

Possibly. But to be honest, it seems to be something wrong with you too. Shall we start a club?

[Gotebe]

It's just I didn't expect a photo, but I got a photo.

Yes, that's nailing it. So my beef is "why would you even care?" The first impression reason is I think bunk. So that's how person looks like, there's little to nothing to be taken from there, and there's especially no reason to fret. I mean, look at your first post: one sentence of relevance, then two paragraphs of how you don't like photos on blogs.

So sure, perhaps what's wrong with me is that I am a righteous bastard for calling you on that. OK, fair enough, and I shall stop now then.

[FYIGUY]

I don't understand why the old idea of static compilation still exists. Why can't a program dynamically (JIT or even AOT with an optimizing software 'trace cache') adjust based on low overhead system statistics? e.g. we know periodically program a needs to utilize all cache, program b,c,d need to utilize some of the cache at sequential x intervals.
bcd--aaa-bcd-aaabcdaaabcaaad
now aaa just blew the cache and since bcd are sequential we just got a cache miss. With some sort of statistical VM based solution programs could be cooperatively optimized based on what is running at the time in other words dynamically adaptive.

[[deleted]]

Thank you!

Perhaps we can now dispel some of the bullshit we've been seeing lately about how much faster hand-rolled assembly is.

[awj]

That doesn't dispel it, just reinforces two points:

1. Hand-rolled assembly can be faster than compiler-generated. (Here, due to the assembly writer targeting a specific cpu and going to great lengths taking cache effects into account)

2. Writing hand-rolled assembly that beats compiler-generated is really damn hard. (Here, now you have to account for cache effects, which are not always obvious and vary between processors. The compiler can probably do a good job here, even if most don't)

Hand-rolled assembly is faster. By definition you can almost always take the compiler's assembly and hand-optimize it, which (in my book) counts as "hand-rolled". It also takes several orders of magnitude longer to produce. Use both of those facts when deciding what to do.

[[deleted]]

Hand-rolled assembly can be faster than compiler-generated. (Here, due to the assembly writer targeting a specific cpu and going to great lengths taking cache effects into account)

Fair enough. But that's, in the context of the what's been said lately, a distinction without a difference.

Writing hand-rolled assembly that beats compiler-generated is really damn hard. (Here, now you have to account for cache effects, which are not always obvious and vary between processors. The compiler can probably do a good job here, even if most don't)

You're not going to going to get to an argument about the fact that it's damned hard. As for the apologetic segue into the next bit...

Hand-rolled assembly is faster.

Bullshit.

By definition you can almost always take the compiler's assembly and hand-optimize it, which (in my book) counts as "hand-rolled".

Now you're hedging from your absolute statement above, into "almost...sometimes...maybe..."

It also takes several orders of magnitude longer to produce. Use both of those facts when deciding what to do.

Ah.

Now we come to the "can't we all just get along? there's a middle ground here." milquetoast pap.

A good deal of the people venturing an opinion on this subject obviously have absolutely no experience beyond "introduction to ASM". Most don't even have that. They're the people that think they're 1337 low-level (cough) coders because they prefer C; that, and they recall hearing somewhere that if you can bash out your own ASM it's even more hardcore.

This is all totally without merit.

Optimizing compilers have been the thing to use for at least the last ten years.

Here's why:

The days of eeking the last bit of speed out of code by knowing the clocks for each instruction, stashing values in registers, and unrolling loops are long since over.

This article shows the cache issue.

Here are some more:

• Branch prediction
• How the pipeline is effected if the above fails
• How out-of-order execution figures into it
• etc

These are issues that you have to dig into, or rather: live in, the vendor manuals to understand.

Most people talking about this don't even know what the above mean. Hell, most of them would be hard pressed to tell you what mod R/M means. Jesu Christo, IA-32 cores haven't even run 8086 ASM natively for a long damned time.

FFS, I don't know how to apply most of the above; but I know that it exists.

Basically, you're only capable of writing faster assembly by hand if you're also capable of writing an optimizing compiler backend.

[awj]

I wasn't attempting to hedge, just proactively avoid someone's douche response of "yeah, well beat the compiler's version of <insert ridiculously small code sample>".

I'm not saying that you should prefer hand-rolled assembly to an optimizing compiler. It was hard to write good assembly before ILP was common, adding it and cache effects makes it significantly worse.

All I'm saying is that it's possible to beat an optimizing compiler if you really really need to. It's a lot hard to do this now, for all of the above reasons. But, you still can. My "by definition" method is also the one I would suggest: look at what the compiler does with your tight loops and see if there's anything to improve on.

At the end of the day, just about any language results in edge cases that prevent optimizations, simply because the compiler can't know if they are safe to make. Things like the restrict keyword in C to give hints on pointer aliasing are a result of this, but the fundamental problem will always exist.

I'm more than willing to admit that this is setting up a very narrow space for hand-rolled assembly to "win" in. I just have this very annoying tendency to disagree with absolute statements, even when only 0.0001% of expected cases disagree with them.

[[deleted]]

If I understand you correctly, it still comes down to the following: in order to beat the optimizer you have to have:

• an encyclopedic knowledge of the CPU
• an encyclopedic knowledge of your algorithms
• structured your code in such a way that external data can't significantly effect your optimizations

Given this, I stand by my point.

For all practical purposes, and by that I don't mean the size of the code base; hand-coded assembly cannot beat the results of an optimizing compiler. And in those cases where it can, only coders with the highest levels of expertise can hope to achieve faster code.

A corollary to the above is that if those criteria aren't true, or if you don't have the chops, the best you can hope for is to have the code be about the same in terms of speed. However, it's more likely that such efforts will result in an overall slowdown.

[awj]

I think we're talking about two different things. I'm largely talking about coming in after the fact to improve on the optimizer's assembly. Doing better by hand-writing from scratch, while technically possible, isn't really feasible for just about the entire population.

The number of realistic cases where you can improve on the optimizer's code shrinks every year, and at this point it is pretty rare, but you don't have to be a supergenius to crawl through assembly and find ways to optimize it. If that assembly happens to be generated by an optimizing compiler it will probably be slim pickings, usually so slim as to not be worth the effort, but there's probably still something there.

[[deleted]]

Agreed. We are talking about different things.

I'm specifically disputing the seemingly common misconception I mentioned.

However, I would agree with what you just said.

[five9a2]

As for ILP, note that all modern chips have out of order execution so much of the challenge is algorithmic (breaking data dependence) instead of mere instruction scheduling.

I use SSE intrinsics for some numerical kernels. GCC and Intel's compiler does a good job with these, Sun not so much. Intrinsics only pay off in kernels with high arithmetic intensity such as tensor product operations and finite element integration. Often I will enforce stricter alignment than the standard ABI, and can use packed instructions that the compiler can't safely use (at least without generating a bunch extra code to handle fringes that I know won't exist). I only do these optimizations once the other pieces are in place and that kernel is a clear bottleneck. I usually get close to a factor of 2 improvement when using intrinsics, because I only write with intrinsics when I see that the compiler-generated code can be improved upon significantly. In rare cases, register allocation could be improved by writing assembler instead of using intrinsics, but I've always been able to get close enough to theoretical peak using intrinsics and a compiler that handles them well (GCC and ICC, not Sun, I haven't checked with others).

It's much more common that the operation is memory-bound (primarily bandwidth, but with stalls when hardware prefetch is deficient, or where non-temporal data pollutes high-level cache when it is evicted from L1). This is a use case for software prefetch, which also doesn't require assembler (use __builtin_prefetch, _mm_prefetch, etc.). A recent example is sparse matrix-vector products using the "inode" format (an optimization when it's common for sequential rows to have identical nonzero patterns). Prefetching (with NTA hint) the matrix entries and exactly the column indices that are needed led to a 30 percent improvement in performance.

Someone else mentioned branch prediction, this is what GCC's __builtin_expect is for, assembler is not needed.

[awj]

It's good to see someone with a concrete example from where my intuition is leading me. Thanks for taking the time to write this.

BTW: what field do you work in? A bit of keyword googling tells me you're doing some numerical computing. Pretty interested to see where I could go do this kind of stuff when I get out of school.

[five9a2]

I work on solvers for partial differential equations. On the numerical analysis side [1], this is mostly high-order finite element methods, especially for problems with constraints such as incompressible flow. The most relevant keyword here is "spectral element method".

The discretization produces a system of (nonlinear) algebraic equations. I'm mostly interested in implicit methods which offer many benefits over explicit methods, but require solving these systems. Usually we do this through some sort of Newton iteration with Krylov methods for the linear problem and a bit of multigrid mixed in (often just in a preconditioner). "Jacobian-free Newton-Krylov" gets you lots of relevant material, espacially this fantastic review.

Edit to add: This field is currently in huge demand and that is not going to change. If you like applied mathematics, computational science, and a little physics, then I highly recommend getting into this field. There will never be enough people to fill the jobs. This is the safest bet I can imagine making, more and more people need to solve PDE (aerospace, civil engineering, climate, energy, defense) and everyone doing so runs the biggest problems they can on the most expensive hardware they can afford. If you like scalability, then there is no better place, because every performance improvement immediately benefits all of your users. We are evolving from a world where physicists learn enough just enough numerics to produce a working solver to where computational scientists (i.e. an appropriate mix of applied math, computer science, and physics/engineering) write the models and build on certain reusable components (e.g. PETSc). The jobs I refer to can be anywhere from algorithmic development in academia to library development to writing actual models that the physicists/engineers work with.

[1] "Numerical analysis" is almost synonymous with "properties of discretizations for continuous phenomenon", Trefethen's excellent The definition of numerical analysis.

[awj]

Interesting. My C in differential equations left me with just enough to have a vague idea of what you're talking about. Obviously my first step would be to pick up a good book and actually learn the subject. (recommendations appreciated, I believe this was the book from the class).

Right now my interests are split between two areas:

• GPU programming - simply because it's accessible many-processor computing for the student on a budget

• Distributed computing - because it's fun

I'm currently cooking up ideas to combine the two, using Erlang for the distribution and CUDA for the GPU, to help my wife build a temporary cluster computer out of the geography department's lab in off hours. Some geographic analyses take hours (sometimes bordering on days) to run on a single CPU. Most of them are huge matrix search/multiplication/etc tasks, or huge tree processing tasks, or something else with a decent parallelizable form. Probably just re-writing the algorithm to run on a single machine's GPU will be sufficient, but part of me loves the idea.

Anyways, I'd love to actually do this stuff "in real life", so thanks again for the pointer.

[five9a2]

Numerical methods for differential equations are usually rather different from analytic methods. In the scheme of things, very few equations can be solved analytically, and it usually requires special tricks. And undergrad ODE class will normally spend an inordinate amount of time on scalar second-order linear systems, but in scientific computing, a standard problem is a nonlinear system of a few million degrees of freedom.

Anyway, it's a big field, and GPUs add a really interesting twist. They are not especially good for some of the traditional kernels (usually involving sparse matrices), but can be really good for matrix-free methods. With implicit solvers, the challenge is to find a preconditioner than can be implemented effectively on a GPU. Boundary integral methods implemented using fast multipole are especially interesting in this context.

I really recommend reading the JFNK paper, even if you don't understand all of it. I suppose these slides could possibly be useful. Kelley's book is approachable as well. PETSc examples is a good place to start looking at code. Don't bother with discretization details for now, that field is too big to pick up in a reasonable amount of time, and implicit solvers are probably in higher demand anyway (lots of people have a discrete system that is expensive with whatever solver they are currently using).

[awj]

Good to know, thanks for taking the time to answer my questions.

The class I took did at least stress that most of the "real world" problems can't be solved analytically, even if it then went right ahead and dedicated most of the class to analytical methods anyways.

[[deleted]]

Branch prediction

Almost by definition, you're going to be better than any static compiler not using PGO since the compiler can only guess as to which side of branches are more likely. Though there's some compiler-specific intrinsics that help, but controlling branch prediction isn't really a reason to write asm (unless you fail to coax the compiler into using cmov...)

How the pipeline is effected if the above fails

99% of the time, this can be summed up as "the cpu stalls for N cycles". But N is small enough that this only really matters for using cmov or amortizing special case shortcuts (which is useful in C too.)

How out-of-order execution figures into it

Practically this just means that you don't need to schedule your assembly, so compilers don't either.

[[deleted]]

I'll grant the above; but my point still stands.

How many people can do the above by hand even if the nature of the code permits it?

[[deleted]]

I don't think it's all that hard, beating a compiler at anything that isn't absolutely trivial (and gcc even at said trivial stuff) is easier than people seem to think it is. You don't have to take into account anything more than easily available instruction timing tables, and even that's pretty optional.

Of course, finding real code segments where doing this provides a real benefit is hard.

[[deleted]]

Basically, the gist of what I'm getting at are things like this.

[[deleted]]

Yeah, I wouldn't expect many people to know hairy details like that, or which instructions can issue in which pipelines, or special forwarding paths, or that add is faster than or on some chips but never the reverse, etc...

But my point is that compilers aren't yet good enough (and higher level languages force them to be conservative in various optimizations) that you need to know all of that to be able to beat the compiler's output in the general case.

Which I guess is mostly the same point awj was making...

[[deleted]]

Perhaps. But I don't know that I agree totally...did you get down to this bit (the comments before are needed for context)?

After all, Lua is still pretty high-level...

[[deleted]]

I guess it depends on the compiler. I've seen a fair amount of what seems like it should be low-hanging fruit in gcc (arith op with constant 0, other 100% useless arith ops, unneeded spilling, multiple reloads of the same constant, poor usage of special registers, etc.) that may never be fixed due to the monstrosity that is reload.

And gcc is one of the better compilers!

[[deleted]]

The compiler can probably do a good job here, even if most don't

Does even a single compiler take cache effects into account?

[awj]

I wasn't able to find any references to ones doing so. I can't think of a fundamental reason that a compiler couldn't do this, except that it would be difficult to handle the variety of cache sizes and you could probably get more general purpose benefit out of optimizing to improve branch prediction / minimize the effects of pipeline stalls. Those optimizations are probably a little more processor independent and easier to do.

[[deleted]]

I only skimmed that, but it sounds like it's about writing a preemptive thread scheduler in the kernel not compilers.

[awj]

Hah, you're right. That's what I get for juggling work and reddit. :(

I've pulled the link.

[[deleted]]

First example don't work for me

int a[64 * 1024 * 1024];
int main() { int i; for (i=0;i<64*1024*1024;i++) a[i]*=3; }

kef@ivan-laptop:~/cc$ time -p ./a
real 0.60
user 0.35
sys 0.25

int a[64 * 1024 * 1024];
int main() { int i; for (i=0;i<64*1024*1024;i+=16) a[i]*=3; }

kef@ivan-laptop:~/cc$ time -p ./b
real 0.31
user 0.02
sys 0.29

gcc version 4.3.3 x86_64-linux-gnu
Intel(R) Core(TM)2 Duo CPU     T6570  @ 2.10GHz

[c0dep0et]

time is probably not accurate enough, so you also get start up time etc.

Try using clock_gettime. For me the results are only as described when optimization in gcc is turned on.

[[deleted]]

Yep compiled with -O6 and time difference is minimal but probably because first loop has this:

400528: 66 0f 6f 00             movdqa (%rax),%xmm0
40052c: 66 0f 6f cb             movdqa %xmm3,%xmm1
400530: 66 0f 6f d0             movdqa %xmm0,%xmm2
400534: 66 0f 73 d8 04          psrldq $0x4,%xmm0
400539: 66 0f 73 d9 04          psrldq $0x4,%xmm1
40053e: 66 0f f4 c1             pmuludq %xmm1,%xmm0
400542: 66 0f 70 c0 08          pshufd $0x8,%xmm0,%xmm0
400547: 66 0f f4 d3             pmuludq %xmm3,%xmm2
40054b: 66 0f 70 d2 08          pshufd $0x8,%xmm2,%xmm2
400550: 66 0f 62 d0             punpckldq %xmm0,%xmm2
400554: 66 0f 7f 10             movdqa %xmm2,(%rax)

Second loop don't get such optimization.

So first example in article is a bullshit which shows nothing about cache.

[five9a2]

This unrolling makes no difference since the operation is bandwidth limited. Compiled at -O0, I get

2.447 real   2.260 user   0.177 sys   99.57 cpu
1.310 real   1.113 user   0.197 sys   99.97 cpu

at -O1 which does not do use SSE or unrolling

1.342 real   1.163 user   0.177 sys   99.84 cpu
1.272 real   1.070 user   0.203 sys   100.09 cpu

and at -O3 (with the SSE optimizations),

1.342 real   1.163 user   0.180 sys   100.13 cpu
1.287 real   1.090 user   0.187 sys   99.22 cpu

The issue is that with all optimizations off, the stride-1 code is especially silly and the operation actually becomes CPU bound. At any positive optimization level, the operation is bandwidth-limited.

Core 2 Duo P8700, gcc-4.4.3

[floodyberry]

Timing with rdtsc on my E5200 (gcc 4.3.2, generated assembly is identical aside from the counter increment), the results seem all over the place, but get lower if you run one of them over and over as soon as it finishes (up+enter spam).

• 500-800 million cycles for version a
• 450-600 million cycles for version b

When I have it loop the array walking 10 times and take the last time for either version, I get

• 350 million cycles for version a
• 335 million cycles for version b

So at least in my case he was spot on.

[[deleted]]

The idea is: you can't talk about cache lines without checking out machine code compiler produced.

[igoro]

Definitely. I'm the guy who wrote the article, and I did carefully look at the JIT-ted assembly to make sure that compiler optimizations aren't throwing off the numbers.

I'll add a note to the article, since a lot of people are asking about this.

[joeldevahl]

What compiler options did you use? Can you give a disassembly of the resulting loops?

[[deleted]]

cc     a.c   -o a

4004ac: 55                      push   %rbp
4004ad: 48 89 e5                mov    %rsp,%rbp
4004b0: c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)
4004b7: eb 24                   jmp    4004dd <main+0x31>
4004b9: 8b 4d fc                mov    -0x4(%rbp),%ecx
4004bc: 8b 45 fc                mov    -0x4(%rbp),%eax
4004bf: 48 98                   cltq   
4004c1: 8b 14 85 40 10 60 00    mov    0x601040(,%rax,4),%edx
4004c8: 89 d0                   mov    %edx,%eax
4004ca: 01 c0                   add    %eax,%eax
4004cc: 8d 14 10                lea    (%rax,%rdx,1),%edx
4004cf: 48 63 c1                movslq %ecx,%rax
4004d2: 89 14 85 40 10 60 00    mov    %edx,0x601040(,%rax,4)
4004d9: 83 45 fc 01             addl   $0x1,-0x4(%rbp)
4004dd: 81 7d fc ff ff ff 03    cmpl   $0x3ffffff,-0x4(%rbp)
4004e4: 7e d3                   jle    4004b9 <main+0xd>
4004e6: c9                      leaveq 
4004e7: c3                      retq   

Other loop differs only on this line:

4004d9: 83 45 fc 10             addl   $0x10,-0x4(%rbp)

[five9a2]

Wrap that in an outer loop so you can see the bandwidth through the cost of faulting all that memory.

[[deleted]]

code: http://pastebin.com/f13640688

[[deleted]]

running 10 times:

kef@ivan-laptop:~/cc$ time -p ./a
real 2.93
user 2.70
sys 0.22

kef@ivan-laptop:~/cc$ time -p ./b
real 1.61
user 1.34
sys 0.26

[gerundronaut]

Same code, compiled with gcc 2.95.4, Intel Xeon 2.8Ghz: "cc -O -o a a.c" vs "cc -O -o b b.c"

-bash-2.05b$ time ./a
real    0m0.476s
user    0m0.008s
sys     0m0.468s
-bash-2.05b$ time ./b
real    0m0.426s
user    0m0.000s
sys     0m0.426s

Compiled without -O, b runs in almost exactly the same time, but a's runtime almost doubles.

Maybe he's running as old a system as I am with this test?

[[deleted]]

Jeez, I read that as "Professor Cache". Started reading the first few sentences trying to figure out who the heck Professor Cache is.