News for hackers. Stuff that matters.
Re:Cache Rules Everything Around Me by smcl on Thursday January 31, 2013 @09:31AM (#5145124)
Just adding a bit of background on the title - it's a play on Wu Tang's "C.R.E.A.M." ("Cash Rules Everything Around Me").
Re:Cache Rules Everything Around Me by themckman on Thursday January 31, 2013 @11:09AM (#5145600)
...You got stick up kids, corrupt cops and crack rocks and stray shots all on a block that stays hot...

Rae's and Deck's verses are 2 of my favorite in all of hip hop. There's just a certain flow, and the beat is just spooky as hell.

Re:Cache Rules Everything Around Me by bfe on Thursday January 31, 2013 @11:28AM (#5145724)
RZA must have cut the line about how being cache oblivious becomes asymptotically equivalent to being cache aware.
Re:Cache Rules Everything Around Me by joelthelion on Thursday January 31, 2013 @05:49AM (#5144386)
How do you reliably assess the cache behavior of your software? Thinking in terms of cache behavior is certainly very useful for making software that runs fast, but if you have no reliable to check what is actually happening, you're pretty much walking in the dark.
Re:Cache Rules Everything Around Me by cwzwarich on Thursday January 31, 2013 @06:00AM (#5144407)
Most CPUs have performance counters that let you determine when performance impacting events occur (e.g. pipeline flushes, reduced dispatch width, cache misses, etc.). In their simplest form they are a simple count, but there is usually some way to trigger an interrupt every N events rather than simply incrementing a counter, so that you can store the offending program counter somewhere for later aggregation. This functionality isn't always exposed very well by the OS, though. If you're using Linux then perf and oprofile are the standard ways to access performance counters.

Alternatively you can execute your code in a simulator with a cache model. Of course, this model won't actually match your hardware (unless you're using a serious cycle-accurate simulator), but it might be more insightful than performance counters alone. I don't know if any of the standard x86 emulators include a good cache model.

Re:Cache Rules Everything Around Me by zokier on Thursday January 31, 2013 @07:55AM (#5144713)
AMD has CodeAnalyst software which helps you analyze many aspects of your software performance, including cache behavior.

http://developer.amd.com/tools/heterogeneous-computing/amd-c...

Just from the front page I see a presentation "Cache Line Utilization with AMD CodeAnalyst Software" which touches the subject

http://developer.amd.com/wordpress/media/2012/10/2011_12_14_...

Re:Cache Rules Everything Around Me by forrestthewoods on Thursday January 31, 2013 @06:54AM (#5144544)
Intel VTune would be one option. Not a cheap but very high quality results.

http://software.intel.com/en-us/intel-vtune-amplifier-xe

Re:Cache Rules Everything Around Me by npsimons on Thursday January 31, 2013 @12:10PM (#5145964)
Cachegrind (part of Valgrind) will do this for you: http://valgrind.org/docs/manual/cg-manual.html
Re:Cache Rules Everything Around Me by ajuc on Thursday January 31, 2013 @06:53AM (#5144542)
kcachegrind on linux is great for that. It shows you your code annotated with number of cache misses per line of code, it also can show you callgraph with aggregated running time, etc. Internaly it uses callgrind.

Great tool for optimizing C/C++ code.

Re:Cache Rules Everything Around Me by mkilling on Thursday January 31, 2013 @05:55AM (#5144393)
Check out PAPI[1], it lets you examine CPU performance counters such as data- and instruction cache misses.

[1] http://icl.cs.utk.edu/projects/papi/wiki/Main_Page

Re:Cache Rules Everything Around Me by moconnor on Thursday January 31, 2013 @09:08AM (#5145006)
If you've got C/C++ (or Fortran!) code it's pretty straightforward - I work on a profiling tool that tracks things like CPU utilization and memory contention for HPC codes (http://www.allinea.com/products/map/). For single-machine programs you could just hack something together with the perf counters fairly easily.
Re:Cache Rules Everything Around Me by vonmoltke on Thursday January 31, 2013 @10:04AM (#5145255)
A clustered signal processing application I previously worked on used custom middleware with perfmon2[1] built into it for collecting performance counter data across all MPI nodes the application was running on. The framework for multiple nodes is not all that difficult.

[1] http://perfmon2.sourceforge.net/

Re:Cache Rules Everything Around Me by scaramanga on Thursday January 31, 2013 @05:59AM (#5144405)
indeed, or perf record -e cache-misses using the hardware performance counters
Re:Cache Rules Everything Around Me by duaneb on Thursday January 31, 2013 @06:04AM (#5144415)
There are a bunch of existing tools that use the underlying architecture's performance measuring capabilities to give you things like cache hits/misses and branch prediction performance; I really like oprofile (but it only runs on linux).

If you're using multiple threads, then you might have issues with false sharing, which is a bitch. Valgrind can help you there.

Re:Cache Rules Everything Around Me by eamsen on Thursday January 31, 2013 @08:40AM (#5144870)
I have been planning to release an article with the exact same title, so naturally I hate the title. The article gives a quick insight on cache-aware algorithms, but misses to state that it's really about the data structures. Taking the example to the extreme, assuming you had huge, sparse matrices/vectors, how would you encode them? Or more generally, when does asymptotic complexity become a secondary criterion for the choice of a data structure? Otherwise, it's short but good, there can't be enough articles on that topic.
Re:Cache Rules Everything Around Me by lautis on Thursday January 31, 2013 @07:30AM (#5144632)
If you're interested in how this could be automated, check out Polly[1]. There is also similar framework in GCC[2], but as can be seen from the blog post, there is room for improvement.

[1] http://polly.llvm.org

[2] http://gcc.gnu.org/wiki/Graphite

Re:Cache Rules Everything Around Me by signa11 on Thursday January 31, 2013 @06:10AM (#5144430)
here is harold-prokop's oldish thesis on the subject: http://supertech.csail.mit.edu/papers/Prokop99.pdf

edit: also, i guess, it never hurts to plug drepper's most excellent paper: "What every programmer should know about memory ?"

Re:Cache Rules Everything Around Me by npsimons on Thursday January 31, 2013 @12:16PM (#5145992)
Link to Drepper's article: http://lwn.net/Articles/250967/

Also informative reading: "A Memory Allocator" http://gee.cs.oswego.edu/dl/html/malloc.html

Re:Cache Rules Everything Around Me by codex on Thursday January 31, 2013 @01:36PM (#5146500)
Cache does rule everything, and the proof lies in the laws of physics.

How fast can you access a bit of memory? The lower bound is the speed of light. How do you organize your memory such that access is the fastest? In a sphere with the processor in the center. There is no more overall efficient packing of bits assuming that each bit takes up some finite "bit" of space (pun intended).

This means that random access to memory can never be O(1) at the limit, it is actually O(n^.333)--the cube root, as the volume of a sphere is 4/3 pi r^3. Yes, even for hash tables. So random access memory always gets slower the more you have of it.

Conversely, the less memory you have to access, the faster it can be. By putting more frequently accessed bits closer to the center of the sphere, you have created a cache.

[deleted]
Re:Cache Rules Everything Around Me by danso on Thursday January 31, 2013 @08:55AM (#5144940)
Actually, the title of this piece is "Cache Money Hoes"

ducks before another HN mod title debate begins

Re:Cache Rules Everything Around Me by eamsen on Thursday January 31, 2013 @10:35AM (#5145402)
You're right, but it's the hook that matters.
Re:Cache Rules Everything Around Me by martinced on Thursday January 31, 2013 @07:51AM (#5144698)
TFA is a big simplistic but, indeed, cache does rule everything.

When you need really fast algorithms and very low latencies, you have to get your hands dirty.

If you're interested in much more advanced writings on the subject I'd suggest googling for "How to do 100K+ TPS at less than 1ms latency".

It is explaining how the LMAX's disruptor pattern is now able to process 12 million events per second on a single core in... Java!

It explains, amongst other, the size and speed of the various caches and how to minimize cache misses.

Re:Cache Rules Everything Around Me by stbullard on Thursday January 31, 2013 @08:31AM (#5144844)
Re:Cache Rules Everything Around Me by brown9-2 on Thursday January 31, 2013 @10:39AM (#5145429)
The "Disruptor" library mentioned can also be found at http://lmax-exchange.github.com/disruptor/.

Funny that this was posted here as their whitepaper has been sitting in my Downloads folder for months waiting to be read.

The slides mention "Hotspot likes small compact methods". Does anyone happen to know a source or have more information on this?

Re:Cache Rules Everything Around Me by octo_t on Thursday January 31, 2013 @01:43PM (#5146541)
The hotspot inliner gives up after only 35 bytes (http://blog.headius.com/2009/01/my-favorite-hotspot-jvm-flag...)
Re:Cache Rules Everything Around Me by brown9-2 on Thursday January 31, 2013 @02:01PM (#5146650)
Fascinating, thanks!