473,326 Members | 2,680 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Coding for the CPU cache?

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
Nov 13 '05 #1
17 4796
emerth wrote:
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/

Nov 13 '05 #2
On 23 Sep 2003 18:21:55 -0700, em****@hotmail.com (emerth) wrote in
comp.lang.c:
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
Nov 13 '05 #3
emerth wrote:
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

Nov 13 '05 #4
Thanks!

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message news:<3F**************@jpl.nasa.gov>...
emerth wrote:
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/

Nov 13 '05 #5
Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.abso lutely.specifically.related.to.the.C.language.to.t he.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

Jack Klein <ja*******@spamcop.net> wrote in message news:<vr********************************@4ax.com>. ..
On 23 Sep 2003 18:21:55 -0700, em****@hotmail.com (emerth) wrote in
comp.lang.c:
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.

Nov 13 '05 #6
Thanks!

"E. Robert Tisdale" <E.**************@jpl.nasa.gov> wrote in message news:<3F**************@jpl.nasa.gov>...
emerth wrote:
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/

Nov 13 '05 #7
Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.abso lutely.specifically.related.to.the.C.language.to.t he.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

Jack Klein <ja*******@spamcop.net> wrote in message news:<vr********************************@4ax.com>. ..
On 23 Sep 2003 18:21:55 -0700, em****@hotmail.com (emerth) wrote in
comp.lang.c:
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.

Nov 13 '05 #8
emerth wrote:
Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.abso lutely.specifically.related.to.the.C.language.to.t he.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

Nov 13 '05 #9
emerth wrote:
Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.abso lutely.specifically.related.to.the.C.language.to.t he.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

Nov 13 '05 #10
In <a9**************************@posting.google.com > em****@hotmail.com (emerth) writes:
Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.abso lutely.specifically.related.to.the.C.language.to.t he.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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #11
In <a9**************************@posting.google.com > em****@hotmail.com (emerth) writes:
Hmmm... given that there is no group named
comp.lang.c.optimization.techniques,
or comp.hardline.correct.place.for.questions.not.abso lutely.specifically.related.to.the.C.language.to.t he.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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #12
In article <jk****************@newssvr16.news.prodigy.com>,
Thomas Matthews <Th**********************@sbcglobal.net> wrote:
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.
Nov 13 '05 #13
In article <jk****************@newssvr16.news.prodigy.com>,
Thomas Matthews <Th**********************@sbcglobal.net> wrote:
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.
Nov 13 '05 #14
In article <Xi*****************@newssvr32.news.prodigy.com> Th**************************@sbcglobal.net writes:
....
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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Nov 13 '05 #15
Christian Bau <ch***********@cbau.freeserve.co.uk> wrote:
In article <jk****************@newssvr16.news.prodigy.com>,
Thomas Matthews <Th**********************@sbcglobal.net> wrote:
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.


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

Richard
Nov 13 '05 #16
In article <3f****************@news.nl.net>,
rl*@hoekstra-uitgeverij.nl (Richard Bos) wrote:
Christian Bau <ch***********@cbau.freeserve.co.uk> wrote:
In article <jk****************@newssvr16.news.prodigy.com>,
Thomas Matthews <Th**********************@sbcglobal.net> wrote:
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.


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.
Nov 13 '05 #17
In <3f****************@news.nl.net> rl*@hoekstra-uitgeverij.nl (Richard Bos) writes:
Christian Bau <ch***********@cbau.freeserve.co.uk> wrote:
In article <jk****************@newssvr16.news.prodigy.com>,
Thomas Matthews <Th**********************@sbcglobal.net> wrote:
> 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.


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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #18

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

102
by: RFox | last post by:
I date back to the early days of the web when HTML was limited but very managable, and have always maintained that hand-coding HTML gives you far better control and cleaner HTML markup than any...
55
by: Jonas Smithson | last post by:
I've seen a few attractive multi-column sites whose geometry is based on pure CSS-P, but they're what you might call "code afficionado" sites, where the subject matter of the site is "coding...
3
by: martin | last post by:
Hi, I am storing a dataset in cache, which is happening fine. I can easily retrive it at postback from the cache, cast it to a dataset and reuse it. However I have specified that the cache...
14
by: Tom.PesterDELETETHISSS | last post by:
Hi, I think this question requires an in depth understanding of how a browser cache works. I hope I can reach an expert here. I may have found a quirk in the asp.net documentation or I don't...
60
by: Dave | last post by:
I'm never quite sure whether to use "this." or not when referring to fields or properties in the same class. It obviously works just fine without it but sometimes I wonder if using this....
0
by: mateipuiu | last post by:
When a try to run a client build on 2005, which uses the Microsoft.ApplicationBlocks.Cache.dll reference, when using a Microsoft.ApplicationBlocks.Cache.dll created on Debug mode, the client works...
0
by: Julian Snitow | last post by:
Here is a more visual example of the technique presented in Logan Koester's article, "Live Coding in Python" (http://www.logankoester.com/mt/2006/07/live_coding_with_python_1.html). It's very...
1
ganesanji
by: ganesanji | last post by:
hi all, I am new to xml. I have written a html file in the extension of ".script".Now I want to convert the file into xml from html script. I have attached my coding given below. <html>...
4
by: Stubbo of Oz | last post by:
I want to put a link on my web pages to allow the user to click and refresh the page. I have seen twqo ways to do this:- <a href="javascript:location.reload(true)"> <a...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.