Matt's Amazing Developer Blog 3000 Comments

Manish: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (Manish) — Sat, 23 Aug 2008 12:07:02 -0400

Good article. About memory pools, I think the book Modern C++ Design (http://www.amazon.com/Modern-Design-Programming-Patterns-Depth/dp/0201704315/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1219507495&sr=8-1_ already has good abstraction and template implementation for pools (See chapter "Small Object Allocation")

Hadi Moshayedi: Practicing Programming

nospam@example.com (Hadi Moshayedi) — Mon, 14 Jul 2008 04:36:51 -0400

There are some interviews with start topcoders at: http://www.topcoder.com/tc?module=Static&d1=features&d2=archive
You may find some other resources and ways to practice by reading those articles.
There are some very good Algorithm Tutorials at http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index .
I usually use acm.sgu.ru , acm.zju.edu.cn , acm.pku.edu.cn , acm.timus.ru for practicing.
I don't usually choose problems to solve randomly, I usually choose a past contest, and solve problems of that contest as much as I can. I think this way I can learn more and have a more accurate assessment of my skills.

You can also do Component Development competitions at topcoder, and earn some money while competing (I haven't done this)

Andrew: Practicing Programming

nospam@example.com (Andrew) — Sun, 25 May 2008 03:51:56 -0400

Googled practice programming projects and got here. thanks for the cool post. here's another one:

http://www.pythonchallenge.com/

Matt Kimmel: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (Matt Kimmel) — Mon, 18 Feb 2008 10:11:37 -0500

When I say cache coherency, what I mean is attempting to keep related data, and hopefully entire data structures, in contiguous memory so that when it's accessed by your code, it can all load into the CPU cache at once (or close to all at once) and reduce the number of cache misses you encounter while performing operations on it. This is critical on modern game consoles, where memory access is quite slow relative to cache access.

You have a good point, though--there are other meanings to the term "cache coherency" as well.

Peter Lund: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (Peter Lund) — Mon, 18 Feb 2008 05:46:01 -0500

This is not cache coherency!

(It is important stuff, though.)

Cache coherency is about the hardware making sure that all the entities that talk to memory (be they CPUs or devices) have the same idea of what's actually /in/ the memory. That's not easy when caches are involved but it's crucial for keeping down the complexity of operating systems (and user-space programs that try to be smart).

Matt Kimmel: Practicing Programming

nospam@example.com (Matt Kimmel) — Tue, 04 Dec 2007 10:14:38 -0500

Thanks for posting this site! I thought it was fairly buggy when I originally wrote this article, but I went back and revisited it and it looks like it's in much better shape. I believe it also contains most of the problems from the Programming Practices book I mentioned in the article.

Matt Kimmel: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (Matt Kimmel) — Tue, 04 Dec 2007 10:11:12 -0500

Good points. I'm certainly not saying that vectors are a magic bullet that are going to solve all your cache-coherency problems; I'm just saying that they're a tool in your toolbox that can be very effective when you understand the problem you're facing. A vector is certainly more likely to be contained within a page or two than a data structure made up of dynamically allocated nodes--but it depends on the size of the vector, the way you access the data structure, and all kinds of factors. It's some food for thought.

Mousa Abdullah: Practicing Programming

nospam@example.com (Mousa Abdullah) — Tue, 04 Dec 2007 10:02:58 -0500

I guess you forgot to mention about ACM UVA site: http://icpcres.ecs.baylor.edu/onlinejudge/. I was faced with programming problems here for the first time. There are simple problems to very very complex ones.

Radu: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (Radu) — Sun, 02 Dec 2007 16:51:00 -0500

Addendum: you also mention STL heap algorithms, which (like binary search) are not cache-coherent on a vector.

You also mention storing trees like red-black on top of an array. This is again far from helping the cache-coherent issues, as in general the daughters of a node will not be close to the node itself. While linearizing trees can help performance (e.g. by eliminating child pointers), it is not because it improves cache coherency.

Also, you seem to suggest that it is important for data to span contiguous memory PAGES. This is not true; in fact, contiguous virtual memory pages probably don't even correspond to contiguous physical memory pages. Caches operate in blocks, which are of sizes on the order of 32-128 bytes; you want to minimize the number of blocks you "touch". It doesn't matter if you touch 100 blocks within the same page, or 100 blocks each in a different page. So for example having a lot of arrays of size 4096 (page size) should be the same as having a single contiguous array (provided of course you can somehow ensure proper page alignment of the 4k arrays).

With these issues in mind, I am now unsure of what "advanced" things you can do with a vector to ensure cache-coherency of operations.

Radu: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (Radu) — Sun, 02 Dec 2007 16:39:04 -0500

Relted to the "Binary Search Table" structure: binary searching a vector is NOT cache-coherent; the fact that the elements are nicely put in a contiguous array is irrelevant when calling STL's lower_bound. So I don't see how binary searching on a vector is related to cache-coherent structures. Nor can I see it eve being a good idea if you have to insert or delete elements (O(n) time vs. O(log n) time for BSTs), unless of course you have a very small number of elements (though in this case, linear search might actually be better than binary search, precisely because of cache coherency).

Nick Ohrn: Practicing Programming

nospam@example.com (Nick Ohrn) — Wed, 14 Nov 2007 15:22:30 -0500

Thanks for this post. I have been wanting to hone my skills in a variety of different languages and I was looking for some generic problems to help me do so. This post helped me find some great resources for these things.

sarah: Practicing Programming

nospam@example.com (sarah) — Fri, 22 Dec 2006 16:31:41 -0500

Thank you so much. I was out of ideas for practice and I found your post very helpful. I just google searched programming practice and found this page. Thanks for your helpful resources.

Matt Kimmel: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (Matt Kimmel) — Mon, 02 Oct 2006 12:59:07 -0400

Oops, my mix-up. Noted and corrected. Thanks!

dp: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (dp) — Mon, 02 Oct 2006 09:40:50 -0400

Good article, with one exception: std::binary_search doesn't actually return an iterator to the found element, it merely returns a bool indicating if the element is found. The stl algorithm that returns an iterator to this element is std::lower_bound (which has the complexity of a binary search).

As for a free implementation of memory pools, check out boost's memory pool library.

Stephane Duguay: Cache Coherent Data Structures in C++: A Real Page-Turner

nospam@example.com (Stephane Duguay) — Mon, 02 Oct 2006 09:00:29 -0400

Good article, I like it. Very important concept for beginner-intermediate programmers, especially in peformance critical environment.