6 ms·

Keep in mind that 99% of the time, choice of algorithm determines your code's performance way more than worrying about cache lines.

• djcapelis 17y ago
  Yes, but be careful with this if your algorithms knowledge comes from a traditional algorithms course. These are often taught as if computational complexity was the only concern. Algorithms that minimize space complexity are often more of an issue. So while the choice of algorithm is a large issue, one must be careful to select an algorithm that makes the appropriate space vs. computation tradeoff. That knowledge is often guided by an awareness of where the systems bottlenecks are. Once you've chosen the correct algorithm and you're down to optimizing code, which is what this article discusses, understanding cache effects is critical and this article provides a nice view of the basics. The usual rules about not doing optimization unless one needs to applies, but I don't see why that always merits an algorithms junkie popping out of the woodwork to essentially say the same thing everyone always says: premature optimization is dumb.
  • palish 17y ago
    Man, you are reading way way too far into what I said. Aren't introverts like us supposed to always be taking statements at face value? And isn't what I said true? Attacks like "algorithms junkie", and completely shoving words into my mouth just make me not want to be here anymore. For the record, I write software rasterizers for fun. I optimize code using SSE2. I code mainly in C++. I am the target audience for this article. Maybe you were trying to illustrate a contrasting point of view, which is fine, but it is stupid to make it so personal.
    • sketerpot 17y ago
      I don't think that "algorithms junkie" is an insult; I'd happily call myself an algorithms junkie, for example. Algorithms are awesome, and so are people who write software rasterizers. (And you know what? Figuring out algorithms that work well on modern hardware is loads of fun.)
• lallysingh 17y ago
  Yeah, but keeping this stuff in mind can really help when you're ordering members in a struct/class.
  • palish 17y ago
    That is a very good point. Every C/C++ developer should be familiar with #pragma pack (Visual Studio... not sure what the GCC equivalent is).
    • JoachimSchipper 17y ago
      gcc has __attribute__((packed)), but we may be talking about different things - that's mostly used for on-the-wire protocols. For most structs, laying out the members from large to small works fine, and avoids superfluous shifting on every read and write.
• ewjordan 17y ago
  True enough. But choice of algorithm can often mean cache-awareness, too - using a random access algorithm where a sequential one could be used instead can be a 10x performance drain, and a 10x constant multiplier is pretty substantial. For a concrete example, a lot of the most important optimizations in physics simulations involve satisfying the simultaneous goals of using cache-friendly and parallel algorithms. In some cases people are even willing to accept worse big O behavior because the "worse" algorithms use a lot of sequential access and parallelize easier than the sophisticated ones, more than making up the difference for the object counts that come up in practice.
  • palish 17y ago
    You sound like you've worked on physics simulations. Care to elaborate? That sounds interesting.
• barrkel 17y ago
  I don't agree; perhaps 80% of the time. For example, the algorithmic purist may insist on using an O(1) or at least O(log n) container for maps or sets, where in practice, if the container will never hold more than a handful of items, a linear search through an array may be faster - because of cache effects. Similarly, an overemphasis of pure OO design can result in lots of fine-grained objects stored in the heap, with lots of edges needing to be traversed to accomplish productive work. If one isn't aware of how expensive following pointers can end up owing to cache effects, you can create designs that lose substantial chunks of performance in such a way that it's not obvious with e.g. a simple code-based profiler where the bottleneck is..
  • nitrogen 17y ago
    This seems to be how Qt4 is. It's a great API to work with, but unfortunately results in 50-call-deep stacks (not an exaggeration -- I have to set valgrind to --num-callers=50 to get reasonable stack traces) and a lot of latency. That plus bugs in the new QGraphicsScene API are making me consider switching to something lower level, like Clutter or my old friend OpenGL.
• ajross 17y ago
  You're explaining that poorly, I think. As written, that's only true if 99% of all software is written using poor algorithm choices. Maybe that's true in some regimes, but there is still a bunch of performance-sensitive software written in C/C++ by developers who make good algorithm and data structure choices. And so when these people get to looking at performance details, they're looking at constant factor improvements. And as described in the article and elsewhere, the constant factors due to cache effects are often on the order of, say, 6 or 10. The penalty to poor cache design can be huge, and it's important to know how they work to avoid that.