Coding for the CPU cache?

[emerth]

Hello all:

I have read references to optimizing C code to exploit
the CPU cache of <insert your favourite CPU>.

Can anyone point me towards some info on the 'net
that gets into techniques for this kind of thing in C
(or C++) in some depth?

I imagine this can get specific to the CPU in question.
I'm not terribly worried about having access to specific
CPUs. I am more interested in the techniques in general,
than, say, in optimizing for my notebook's Duron...

Thanks in Advance!

Eric

 

[E. Robert Tisdale]

I have read references to optimizing C code to exploit
the CPU cache of <insert your favorite CPU>.

Can anyone point me towards some info on the 'net
that gets into techniques for this kind of thing in C
(or C++) in some depth?

I imagine this can get specific to the CPU in question.
I'm not terribly worried about having access to specific
CPUs. I am more interested in the techniques in general,
than, say, in optimizing for my notebook's Duron...

Automatically Tuned Linear Algebra Software (ATLAS)

http://www.netlib.org/atlas/

 

[Jack Klein]

Hello all:

I have read references to optimizing C code to exploit
the CPU cache of <insert your favourite CPU>.

Can anyone point me towards some info on the 'net
that gets into techniques for this kind of thing in C
(or C++) in some depth?

I imagine this can get specific to the CPU in question.
I'm not terribly worried about having access to specific
CPUs. I am more interested in the techniques in general,
than, say, in optimizing for my notebook's Duron...

Thanks in Advance!

Eric

The C language standard defines an abstract machine that has neither a
CPU nor a cache. All such concepts are completely compiler and
hardware specific, and hence completely off-topic in this group. It
is simply not a language issue.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Thomas Matthews]

Hello all:

I have read references to optimizing C code to exploit
the CPU cache of <insert your favourite CPU>.

Can anyone point me towards some info on the 'net
that gets into techniques for this kind of thing in C
(or C++) in some depth?

I imagine this can get specific to the CPU in question.
I'm not terribly worried about having access to specific
CPUs. I am more interested in the techniques in general,
than, say, in optimizing for my notebook's Duron...

Thanks in Advance!

Eric

A CPU may have more than one Cache: instruction cache
and data cache. In either case, here is how you code
to optimize a cache.

The biggest wast of CPU cycles (in a CPU that has
a cache) is the reloading of the cache. You want to
reduce or minimize it. For an instruction cache, this
would involve unrolling code in loops and reducing
"if" statements into conditional logic, perhaps
even boolean arithmetic. For data cache, keep your
data accesses sequential. A binary search would
play havoc on a cache (depending on its size and
the search size). Also, reduce the number of
acesses to memory variable and objects that cannot
be containined in a register, accumulator or your
processors data handling device.

As always, use a profiler before optimizing any
code. Optimize the design before the code.
Optimize the requirements before optimizing the
design.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[emerth]

Thanks!

Automatically Tuned Linear Algebra Software (ATLAS)

http://www.netlib.org/atlas/

 

[emerth]

Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.absolutely.specifically.related.to.the.C.language.to.the.exclusion
of.any.other.possible.line.of.inquiry,
and given that there *is* a comp.std.c news group devoted to the
language standard, I thought I might ask here.

I can't imagine that my little post has introduced corruption into the
topic space of comp.lang.c beyond the ability of thinking human beings
to cope with.

Perhaps Mr. Klein - knowing as he so clearly does the proper place for
posts of various subjects - might deign to suggest an appropriate
place to ask?

Eric

 

[Thomas Matthews]

Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.absolutely.specifically.related.to.the.C.language.to.the.exclusion
of.any.other.possible.line.of.inquiry,
and given that there *is* a comp.std.c news group devoted to the
language standard, I thought I might ask here.

I can't imagine that my little post has introduced corruption into the
topic space of comp.lang.c beyond the ability of thinking human beings
to cope with.

Perhaps Mr. Klein - knowing as he so clearly does the proper place for
posts of various subjects - might deign to suggest an appropriate
place to ask?

Eric

1. Read the FAQ below, proper netiquette is not to top-post.
I have placed these comments after (or at the bottom) of
your post.

2. Since caches depend on the processor (many don't have
caches), a _good_ place to start is with a newsgroup
dedicated to your operating system or processor.

3. The C language has no facilities, definitions or
requirements of a CPU cache. The theme of this newsgroup
is the _standard_ C language. Thus CPU cache issues are
off-topic (as are windows, USART, USB and I2C issues).

4. There are _many_ different platforms which run programs
written in C. Don't ever assume that everybody uses the
same platform as you. I don't post issues about the ARM
processor or the 8051 here; I go to a different newsgroup.
However, I can ask questions about offsetof() or bitfields
in a union, here.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Dan Pop]

Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.absolutely.specifically.related.to.the.C.language.to.the.exclusion
of.any.other.possible.line.of.inquiry,
and given that there *is* a comp.std.c news group devoted to the
language standard, I thought I might ask here.

I can't imagine that my little post has introduced corruption into the
topic space of comp.lang.c beyond the ability of thinking human beings
to cope with.

Perhaps Mr. Klein - knowing as he so clearly does the proper place for
posts of various subjects - might deign to suggest an appropriate
place to ask?

Once you realize that the cache friendly programming techniques are mostly
language independent, the answer becomes obvious: comp.programming.

The one issue that is language specific is the layout of a
"multidimensional" array in memory, because it affects the optimal way of
inspecting an array. C and Fortran do it in opposite ways.

Dan

 

[Christian Bau]

3. The C language has no facilities, definitions or
requirements of a CPU cache. The theme of this newsgroup
is the _standard_ C language. Thus CPU cache issues are
off-topic (as are windows, USART, USB and I2C issues).

One difference is that you can write code that is cache-friendly or
cache-unfriendly using perfectly standard C code.

 

[Dik T. Winter]

> The biggest wast of CPU cycles (in a CPU that has
> a cache) is the reloading of the cache. You want to
> reduce or minimize it. For an instruction cache, this
> would involve unrolling code in loops and reducing
> "if" statements into conditional logic, perhaps
> even boolean arithmetic.

This depends very much on how the instruction cache works. Jumps are
in general a bad idea, but unrolling a tight loop might also be a bad
idea.

 

[Richard Bos]

One difference is that you can write code that is cache-friendly or
cache-unfriendly using perfectly standard C code.

Can you? For all kinds of caches, or just for the kind that happens to
be fashionable today?

Richard

 

[Christian Bau]

Can you? For all kinds of caches, or just for the kind that happens to
be fashionable today?

I don't know how caches will work twenty years from now, but I am quite
sure I will be able to write cache-friendly code twenty years from now
in Standard C, and I am sure it will be important for the performance of
some code.

There is also a good chance that Standard C code that is cache-friendly
today will be cache-friendly twenty years from now. But it is most
likely that any code that I write today wouldn't be performance critical
in twenty years (actually what I am writing now will _definitely_ not be
used in twenty years), so I don't care.

 

[Dan Pop]

Can you? For all kinds of caches, or just for the kind that happens to
be fashionable today?

All the data caches I'm familiar with exploit the fact that memory is
accessed quite often in a sequential manner. Therefore, walking an
array the "right" way is going to be cache friendly on any kind of cache
and doing it the "wrong" way is going to be cache unfriendly.

The gotcha is that certain cache-less memory architectures have completely
different rules for optimising memory accesses. But these days, such
systems are mostly history.

Of course, there is little one can do about being code cache friendly,
without intimate knowledge of the processor and compiler.

Dan