Matt's Amazing Developer Blog 3000

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

nospam@example.com (Matt Kimmel) — 2006-09-29T02:27:00Z

Once upon a time, cache coherency was a problem that, for the most part, was faced by game programmers and systems programmers. The basic problem is this: given an application that requires a large amount of memory, an operating system that supports virtual memory, and a very small amount of physical memory, the application can experience "death by swapping". If the data that the application needs to operate on at any given time is scattered all over the app's memory space, rather than stored contiguously in memory, and physical memory can't store all the pages that the data is found on at the same time, then the operating system will constantly be swapping memory in and out of physical memory, causing major slowdown due to disk access. If you happen to be iterating on data that's in this situation--well, you're sunk.

Now days, with the growing presence of multi-core processors, the same problem is cropping up for everyone, albeit in a different context and on a different scale. In a multi-core environment, access to main memory becomes a bottleneck. When assigning work to different cores, you want to have all of the data a particular core is working on in the processor's on-chip caches, so the core isn't constantly waiting for memory to be moved between cache and main memory. Given the size of caches on today's processors, it's not always possible to have all your data in the cache at one time--but you can still minimize the amount of time spent moving memory. Again, if your data is scattered all over the place, the core that's operating on it is likely to spend most of its time waiting for data to be fetched from main memory--kinda defeating the purpose of multiple cores.

Luckily, a good general solution to both of these problems is to use cache-coherent data structures, and it's generally pretty easy to do so. Cache-coherent data structures are data structures that cause your data to be stored contiguously in memory--meaning that instead of scattering your data over thousands of virtual pages, you can ensure that it gets written to just a few. This also optimizes memory prefetch on most modern processors, which fetch blocks of main memory into cache at a time rather than just the bytes you ask for.

With that in mind, here are some easy ways to use cache-coherent data structures to keep your app out of disk and processor cache-miss hell:

Prefer Array-Based Data Structures Over Pointer-Linked Data Structures

Yep, turns out everything they said was good for you in your college Data Structures class is bad for you. When storing like data elements in a collection, the type of pointer-linked data structures in which you grow the collection by allocating one data element at a time and linking it to the rest of the collection are bad news. Because you're allocating a large amount of small bits of memory over time, you're likely to spread your data over many, many pages.

Instead, it's best to implement your data structures using arrays as the underlying storage mechanism. As you probably remember from that same Data Structures class, just about any data structure that can be implemented using pointers can be implemented using arrays--you just link between array indices rather than memory locations. You can grow the array as necessary using realloc() (or your operating system's equivalent). This way, all of your data is stored contiguously in memory and will span the minimum number of pages possible.

The downside to this is that implementing complex data structures on top of arrays is a big pain. Ever try to implement a red-black tree on top of an array? Not fun. And of course you have to manage "holes" in your array caused by deleted elements--either by shifting array elements around and fixing up links, or by reusing array elements. But for simple data structures, it's not such a bad thing--replacing that pointer-based linked list, stack or queue with an array-based implementation will give you a big cache win for not too much effort. For more complex data structures, the STL can help you out a bit, as we'll see below.

Let STL Vectors Help You Out

STL Vectors are probably one of the most underrated classes in the Standard Library. They're amazingly flexible, and especially handy for our purposes, since in the vast majority of STL implementations, they use an array as their underlying storage mechanism.

The standard library specification says that vectors have the following properties: O(1) insertion and deletion at the end of the vector, O(n) insertion and deletion anywhere else in the vector, O(1) element access, and of course O(n) search (unless you apply some tricks, as mentioned below). The only exception to this is when the vector has to expand and reallocates the array; depending on your STL implementation and your operating system's realloc implementation, that operation may take O(n) when it happens. If you're good about presizing the vector and managing its capacity, you can avoid this cost a lot of the time.

With that in mind, let's take a look at some advanced functionality you can implement with a vector, while still maintaining cache coherency:

Stack: This comes for free--just use those O(1) push_back and pop_back methods.
Ordered List: To insert an element, use push_back and then the STL sort algorithm. This isn't a great example, though, since insert will cost O(n log n), delete will cost O(n), and search will cost O(n). So how about...
Binary Search Table: When inserting, use push_back and then sort, as above, for O(n log n). When searching, use the STL lower_bound algorithm for O(log n). When deleting, find your element with lower_bound and then use the vector's usual erase, for O(n). Now you have a search time comparable to a binary search tree, with the trade-off of increased insert time.
Keyed Binary Search Table: Missing STL maps? Try the Binary Search Table above, but store STL pairs populated with your key and value.

Even more interesting possibilities open up in certain situations when you start to look at the STL heap algorithms, but, for the sake of brevity, I'll leave that as an exercise for the reader.

Use Memory Pools

Memory pools are a great way to ensure cache coherency in situations where you need to allocate a lot of small objects. The basic idea of a memory pool is that you allocate a large number of fixed-sized objects (probably using an array or vector). Then, as you need those objects, you request them from the memory pool, which gives you a pointer to an unused object in its object store. When you're done with the object, you notify the memory pool and it "frees" that object. Using this technique, you can use new/delete semantics and maintain cache coherency. It's almost like having your cake and eating it too!

There are a few requirements, of course. Nothing's free--that's why this is only like having your cake and eating it too. First of all, the objects in your pool need the ability to return to a freshly initialized state. Since they will most likely be reused, but you can't re-construct them, you'll have to write code to reset them to pristine condition. In addition to this, you will need to keep track of which objects in your memory pool are in use and which aren't; this can be achieved in a number of ways, such as maintaining a free list or a bitfield indicating the state of each object in the pool. You'll also have to decide whether your memory pool can grow or not; if it can, that implies some additional coding.

The good news is that it's relatively easy to implement a memory pool as a template class, and instantiate it on any class you want to pool that follows the guidelines above. An actual implementation of that is beyond the scope of this article--but might make a good blog entry later on (or perhaps readers can point me to an existing, free implementation).

What If I Really, Really, Really Want to Use STL?

Simple: use vector! Seriously, if you have a burning need to use the pointer-linked STL classes and want to ensure some measure of cache coherency, it can be done. My suggestion is to employ memory pooling. As mentioned above, memory pools preserve some of the new/delete semantic; therefore, it should be possible to write a custom STL allocator that uses a memory pool as storage.

Conclusion

There you have it--some ways to ease the pain of working on a system with low physical memory, or on a multicore system. Of course, there are many other techniques for cache coherency, and I encourage all of you to comment with any that you know about/recommend.

Before I send you forth into the world with your new-found knowledge, some advice: remember that there are situations where cache coherency is critical, and some where it's not. If you've got plenty of physical memory and/or aren't worried about your processor cache, using these techniques is overkill. Linked lists, sets, maps, and pointers will do just fine. Custom data structures are always more difficult to maintain then pre-existing data structures like those provided by STL. So make your choices wisely.

Practicing Programming

nospam@example.com (Matt Kimmel) — 2006-09-16T15:47:46Z

Lately, I've been thinking a lot about practicing programming. By that I don't mean the practices of programming--I mean actually programming for the purpose of honing my skills. I used to think that I didn't need to "practice"; after all, I program all the time at my job, right? I even do extra-curricular projects. Isn't that "practice" in and of itself?

But recently I've realized that that's not true. When you work on a project, whether it's at work or at home, you're implicitly working within a very narrow scope. When you work within a particular industry, you're also working within a narrow scope. While you may gain a great deal of skill within that scope, you still need to maintain your skills with the "basics": the languages, techniques, algorithms, and so on that make you a well-rounded programmer. If you concentrate all of your efforts into one area, your skills in other areas will atrophy.

Practicing programming doesn't just help you maintain your existing skills, either. It helps you to pick up and understand new skills that may be applicable to your current area of focus. For example, when I first was learning Test-Driven Development, I didn't want to plunge into a huge project without ever having written an xUnit test; that seemed pretty overwhelming. Instead, I found it very helpful to write a bunch of small practice programs and solve some exercises using TDD. By the time I started to apply TDD to a large work-related project, I felt pretty confident.

That last bit about writing small programs ties into something that I think is essential to getting the most out of programming practice: making it practical. If practicing programming means you have to embark on a full-scale project in order to exercise one or two concepts, and you're lazy like me, you're not gonna get it done. Even if you do get it done, you're going to spend more time worrying about the logistics of the project than boning up on a particular technique. Programming practice should be focused and easy to do. When I'm practicing, I like to work on problems of a scale that I can solve in a few hours--bite-sized programs that I can write in an evening, or on my laptop while I'm on a train ride or plane flight.

So where do you find these kinds of problems? I suppose you could make them up. I find, though, that the best practice comes from solving problems that come out of left field, not things that you've already thought about. I like to find exercises that somebody else, with a completely different perspective than my own, has come up with. That maximizes the extent to which you think outside your own areas of focus, and leads you to a broader experience.

With that in mind, where can you find exercises to practice with? I've been doing quite a bit of research on this, and have found a lot of sources. Here are a few big ones:

Code Katas. Those of you who read a lot of development blogs have probably encountered these; they've become very popular in the last few years. A code kata is a small problem or exercise that you are encouraged to code from scratch periodically. The idea is that, similarly to a martial arts kata, every time you go through the motions of solving that problem, you'll gain new insights into it. I think that's true, but I also think that there's value in doing code katas even if you only solve them once. They provide small but interesting problems to solve. I first encountered code katas when I went to an Agile Development seminar given by Bob Martin, in which he walked us through a couple of katas. Indeed, Bob Martin's blog contains a number of interesting code katas. Dave Thomas also has a great page of code katas at the Pragmatic Programmers site. The Coding Dojo also offers a number of interesting katas. Many others exist on the net, including a lot of language-specific ones (all the katas I've linked to here are language-neutral). Your best bet is to Google "code kata".

Coding Competitions. There are a number of websites, such as TopCoder, that host programming competitions. These are typically timed matches during which programmers compete to solve a small problem in the most efficient/elegant way possible. These sites provide you with an "arena" environment that includes a code editor, compiler, test data, and typically a way to view other contestants' entries and critique them. Some competitions even include cash prizes. Even if you're not the competetive type, most of these sites have "practice arenas" in which you can solve problems from previous competitions. Not a bad way to get in some quick programming practice; you don't even need a compiler on your local machine.

Books. Remember those exercises at the end of every chapter of your Computer Science textbooks from college? Well, they're still there, and a lot of them pose interesting problems. Dig out your old Algorithms book, or an Operating Systems text, or whatever seems interesting to you, and check them out! Trust me, they're much more fun when you're not doing them for credit. There are also some books of coding puzzles out there, but they seem to be few and far between. One I did pick up recently is Programming Challenges by Steve Skiena and Miguel Revilla, a book that purports to prepare you for the aforementioned coding competitions. It includes a lot of practice problems and access to a website that will "auto-judge" your answers. Definitely worth a look.

Any thoughts on all this? Got any other resources? Please post them in comments to this entry!

Hello World!

nospam@example.com (Matt Kimmel) — 2006-09-15T22:55:49Z

Welcome to my development blog! My name is Matt, and I’ll be your enthusiastic, embattled, opinionated software developer during your stay. You can read more about me on the About page, but to summarize quickly, I’ve been working in the computer industry for about 15 years, primarily as a programmer or software engineer or whatever you want to call it, and also at times as a sysadmin, manager, author, and whatever else they’d let me do. I’ve spent the last nine years working in the video game industry, and while this isn’t specifically a game development blog, I’ll certainly be talking about it from time to time.

In this blog, I’ll be posting my thoughts and opinions on all aspects of software development, computer science, and occasionally things unrelated. With any luck, some of these thoughts and opinions will be useful to other people. Please comment on my posts if you agree with me. Please comment on my posts if you disagree with me. Please comment on my posts if you think I’m a raving lunatic. Please do not comment on my posts if you’d like to offer your body-enhancing pills to my readers.

Not too many rules here. Let’s lay off the personal attacks. I reserve the right to make fun of flame wars if they get silly.

Above all, enjoy!