#include <iostream>

int main() {
    int _3 {0};
    int _5 {0};

    for (int i = 1; i <= 100; ++i) {
        ++_3;
        ++_5;

        if (_3 == 3) {
            _3 = 0;
            std::cout << "Fizz";
        }

        if (_5 == 5) {
            _5 = 0;
            std::cout << "Buzz";
        }

        if (_3 > 0 && _5 > 0) {
            std::cout << i;
        }

        std::cout << " ";
    }
}

Drink up, and let the debate begin.

Interface

Now that we have the overall design, it’s time to consider what interface to provide for users of the cache. Let’s consider the methods and properties that a cache type might provide.

• Methods
  • Store items in the cache
  • Retrieve items from the cache
  • Query for the presence of an item by key
  • Remove items from the cache
• Properties
  • Count of items in the cache
  • Capacity of the cache
  • Number of sets in the cache
  • Number of items (ways) in each set

The cache should also provide the means to enumerate over cache items, as well as enumerate keys and value independently. In other words, it should function like an standard .NET generic collection. That means we should implement the interfaces that will allow the cache to work with several extension methods as well as standard enumeration patterns like foreach. Generic collections in the .NET library implement the ICollection<T> interface, and that interface is derived from IEnumerable<T> and IEnumerable. If we derive our cache interface from ICollection<T>, we’ll get a few of the methods and properties that we need, and we’ll be prepared to interoperate with existing .NET code that uses the ICollection, IEnumerable<T>, and IEnumerable interfaces.

Following is the ICollection<T> interface and the two interfaces it derives from, IEnumerable<T> and IEnumerable:

namespace System.Collections {
    // Exposes an enumerator, which supports a simple iteration over a non-generic collection.
    public interface IEnumerable {
        // Returns an enumerator that iterates through a collection.
        IEnumerator GetEnumerator();
    }
}

namespace System.Collections.Generic {
    // Exposes the enumerator, which supports a simple iteration over a collection of a specified type.
    public interface IEnumerable<out T> : IEnumerable {
        // Returns an enumerator that iterates through the collection.
        new IEnumerator<T> GetEnumerator();
    }

    // Defines methods to manipulate generic collections.
    public interface ICollection<T> : IEnumerable<T>, IEnumerable {
        // Gets the number of elements contained in the collection.
        int Count {
            get;
        }

        // Gets a value indicating whether the collection is read-only.
        bool IsReadOnly {
            get;
        }

        // Adds an item to the collection.
        void Add(T item);

        // Removes all items from the collection.
        void Clear();

        // Determines whether the collection contains a specific value.
        bool Contains(T item);

        // Copies the elements of the collection to an array, starting at a particular array index.
        void CopyTo(T[] array, int arrayIndex);

        // Removes the first occurrence of a specific object from the System.Collections.Generic.ICollection`1.
        bool Remove(T item);
    }
}

We could derive our cache interface directly from ICollection<T>, since it provides several of the methods and properties in the list above. That’s definitely something we want for interoperability, but the problem for day-to-day users is that the methods accept a single generic object type, and our cache is designed to function as a dictionary, which uses keys to store and retrieve values. In part 1, we considered using a KeyValuePair<TKey,TValue> type to store the cache data. Let’s look at how adding a cache item would work in practice using the ICollection<T> interface:

// We have to create a new KeyValuePair for every method call.
coupleCache.Add(new KeyValuePair("Brad", "Angelina"));

// Maybe we could minimize the constructor...
coupleCache.Add(new("Brad", "Angelina"));

It works, but it’s clunky. As for Contains and Remove, those are effectively useless because we would either have to know the value of the cache item in order to use those methods (which defeats the entire purpose of the cache), or we would have to specify that those methods would ignore the value. Neither approach is workable.

In part 1, we noted that the cache works a lot like the .NET generic Dictionary type. That collection implements the IDictionary<TKey,TValue> interface:

namespace System.Collections.Generic {
    // Represents a generic collection of key/value pairs.
    public interface IDictionary<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>>, 
                                                 IEnumerable<KeyValuePair<TKey, TValue>>, 
                                                 IEnumerable 
    {
        // Gets or sets the element with the specified key.
        TValue this[TKey key] {
            get;
            set;
        }

        // Gets an ICollection containing the keys of the IDictionary.
        ICollection<TKey> Keys {
            get;
        }

        // Gets an ICollection containing the values in the IDictionary.
        ICollection<TValue> Values {
            get;
        }

        // Adds an element with the provided key and value to the IDictionary.
        void Add(TKey key, TValue value);

        // Determines whether the IDictionary contains an element with the specified key.
        bool ContainsKey(TKey key);

        // Removes the element with the specified key from the System.Collections.Generic.IDictionary`2.
        bool Remove(TKey key);

        // Gets the value associated with the specified key.
        bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value);
    }
}

That looks like exactly what we need. It gives us a method to add an item with the key and value in separate parameters, a method to check for the presence of an item by key, a method to remove an item by key, and a method to retrieve an item’s value by key.

There are two other advantages to using this interface as the basis of our cache. First, it’s a standard interface that would be familiar to experienced .NET developers. Second, it would interoperate with standard .NET libraries, idioms, and extension methods. On the strength of these advantages, we’ll derive our cache interface from IDictionary<TKey, TValue> (and, by extension, from ICollection<T>, IEnumerable<T>, and IEnumerable as well).

The remaining properties that aren’t provided by IDictionary<TKey, TValue> are the capacity, the number of sets, and the number of ways. We’ll add these to our cache interface.

There is also one other method that might be useful. Remember that when we add a new cache item, it might evict an existing cache item. Most of the time it won’t matter what item gets evicted, but there may be scenarios in which we would want to know which item would be evicted if a new cache item were added. To that end, we’ll add a method to support such a scenario and call it TryGetEvictKey, following the pattern of TryGetValue.

Now we can finally define our cache interface, ISetAssociativeCache<TKey, TValue>.

using System.Collections.Generic;

namespace ParksComputing.SetAssociativeCache {
    // Represents a generic set-associative cache of key/value pairs.
    public interface ISetAssociativeCache<TKey, TValue> : IDictionary<TKey, TValue> {
        // Gets the capacity of the cache.
        int Capacity { get; }

        // Gets the number of sets in the cache.
        int Sets { get; }

        // Gets the capacity in each set.
        int Ways { get; }

        // If the given key would cause an existing cache item to be evicted, returns true and sets 
        // evictKey to the key of the cache item that would be evicted if the new key were added.
        bool TryGetEvictKey(TKey key, out TKey evictKey);
    }
}

This interface will be implemented by concrete classes which provide the behavior of the set-associative cache.

Implementing Cache-Eviction Policies

We discussed in part 1 how cache items are evicted when a new cache item is added to a set which is already full, and there are several policies that can be implemented, depending on the specific use case for the cache. So far we have not addressed how those policies will be provided or implemented.

One method that I played with early on was inspired by Andrei Alexandrescu’s C++ policy-based design as described in Modern C++ Design. It involved supplying a policy class as a generic parameter to the concrete class that implemented ISetAssociativeCache<TKey, TValue>. In practice, instantiating a cache instance would look like the following:

ISetAssociativeCache<string, string> = new SetAssociativeCache<string, string, LruPolicy>(4, 2);

Implementing it was a fun exercise, but after playing with it a while I realized that it didn’t really gain me anything. There was no practical difference between the code above and the following code, in terms of what clients had to write:

ISetAssociativeCache<string, string> = new LruCache<string, string>(4, 2);

In other words, it made more sense to just put the policy into a concrete class that implemented the cache interface.

The only other variation I could come up with was the scenario of changing the policy at runtime:

ICachePolicy lruPolicy = new LruCachePolicy();
ISetAssociativeCache<string, string> cache = new FlexCache<string, string>(4, 2, LruCachePolicy);

// some time later, for some reason...
cache.Policy = new LfuCachePolicy();

I couldn’t come up with a specific reason to do this, but I could at least imagine that it could happen in practice. Even so, that is an implementation detail can be left to specific implementations, so the ISetAssociativeCache<TKey, TValue> interface already provides enough functionality for most mainstream use cases.

The three policies that I’ve implemented so far are least-recently used (LRU), most-recently used (MRU), and least-frequently used (LFU). All three of them ultimately derive from a common class that implements nearly all of the cache code.

There are some key differences in behavior between policies based on recency of use (LRU, MRU) and policies based on frequency of use. The xRU policies based on how recently a cache item was stored, updated, or accessed can be managed by sorting the keys in a set so that the most recently stored, updated, or accessed cache item is moved to the lowest index in the set, pushing the least-recently used item to the highest index. No other metadata needs to be stored. For other policies, such as ones based on how frequently a cache item is used, some data to track the implementation of the policy must be provided.

In order to keep as much common code as possible in a single class, let’s re-evaluate how the key array is stored. In part 1 we considered this layout:

int[] keyArray;

I hinted at the time that we would change this definition, and this is why. We need to provide another bit of data alongside the index into the value array. Let’s change the definition to the following:

KeyValuePair<int, int>[] keyArray;

Even though LRU and MRU policies don’t use the second int, most other policies will make use of it. LFU will increment it each time a cache item is accessed. Policies based on a cache item’s age might use the second int to store a date/time stamp.

The Class Structure

Given that xRU policies and xFU policies diverge on how they track aging of cache items, but otherwise share the vast majority of the rest of their code, we can consider a class structure like the following:

The only class here that we haven’t discussed is IReadOnlyDictionary<TKey, TValue>. This allows clients to share the cache in a read-only manner, such that clients may access the data in the cache without being able to modify it.

Coming Up

In the next and final article, we’ll finally implement the class structure above and try the cache in some sample code.

The first thing I learned is that a set-associative cache is more of a hardware concept than a software one, but that they do exist in software. The second thing I learned is that they’re a topic of a fair amount of academic study — I slogged through one paper and queued up a few more in some browser tabs before, ultimately, I decided to implement something fairly straightforward and make it extensible. I find that I learn better by doing than by reading.

Once the project was on my GitHub repository, I decided to write this series of articles, where I walk through the code, describe how the cache works, explain why I made the design decisions I made, and generally show the process of writing a professional-grade data structure for .NET in C#.

In part 1, we’ll try to understand how set-associative caches work and come up with a basic design. In part 2, we’ll expand on the design a bit more and define a code interface for the cache. In part 3, we’ll turn the design into working code.

A Few Words About the Design Process

While these articles will appear to present a somewhat linear process of design and implementation, the actual process was a more iterative and exploratory. I followed the basic steps in this series of articles, but I didn’t do so rigidly. My general approach to designing and developing a new bit of software is the following:

• Analysis: Understand the problem
  • Sketch it out on the whiteboard
  • Define the data involved in the problem
  • Discover the algorithms and step through them manually
  • Consider how the software will be used in production
• Design: Propose a solution
  • More of the steps above, but at a lower level this time
  • Consider platforms, languages, libraries
  • Examine and compare alternative designs
  • Consider usability, performance, testability, and all such requirements
  • Look for existing designs and implementations so that I don’t re-invent the wheel
  • Talk about and write about the problem and the proposed solution
• Implementation: Bring the design into reality to solve the problem
  • If I get stuck, reconsider the design or the analysis and see if I missed something

“OMG! That’s… that’s… WATERFALL!” No, no, it’s careful consideration of the problem before committing to an implementation. These aren’t rigid phases of any development process handed down from on high. It’s just a reasonable way to approach software development. I may even write exploratory, proof-of-concept code during analysis, and some of that code (maybe all, if I’m lucky) may find its way into the final implementation. I may get all the way into implementation and discover that I need to redo the design. In my experience, the more carefully I understand the problem, and the more diligently I design the solution, the smoother the implementation will be.

Even while writing these articles, I would update the implementation as better ideas occurred to me, and I fixed a few design and implementation bugs along the way as well. If you’re new to software development, don’t worry if you find yourself in a similar kind of loop. A little patience up front, and a willingness to admit later that you didn’t understand something as well as you thought you did, will pay dividends over the course of your career.

How Does a Set-Associative Cache Work?

I’m not going to dive too deeply into caching theory here. As I said earlier, it’s a topic of study for computer scientists. I’ll just present an overview of set-associative caches, and I’ll give you a few links along the way where you can dig deeper.

A set-associative cache is a cache that is split into sets of cache entries, or cache lines. This is a compromise between two other extremes: a direct-mapped cache and a fully associative cache. Each set may have one or more “ways”, where each “way” is single cache entry.

In order to make it easier to visualize how such a cache works, I’m going to use tables that represent a cache with 3 sets and 3 ways per set. Such a cache would be laid out as follows:

When a new cache item is added to the cache, it is assigned to a set, either via an intrinsic tag (like an address range) or some other algorithm, such as a hash function. I won’t get into all the ways that this can happen; instead, I’ll focus on this C# implementation, which uses a hash function on the key in order to choose which set the key/value pair is stored in.

Let’s say, for example, that we want to cache pairs of celebrity couples. Why you would want to do this in real life, I have no idea, but they’re a much more compact form of data to draw on whiteboards or type into WordPress than HTTP responses or database results. When we add an item to the cache with the key “Brad” and the value “Angelina”, the key is hashed using a Fowler-Noll-Vo 1a hash function (FNV-1a). This returns the 64-bit value 7469233897810807560. This huge number isn’t terribly helpful on its own, so we take the number modulo the number of sets (in this example, 3) to determine which set, from 0 to 2, that the item should be placed into. This gives us the number 0, so this key/value pair will go into set 0. There are three ways in each set, but all are empty at the start, so Brad and Angelina will go into the first way (way 0) in the first set (set 0).

Let’s add another pair: “Kanye” and “Kim”. “Kanye” hashes to 12815697388183119611 which, modulo 3, yields 2, so Kanye and Kim go into the first empty way in set 2:

We can keep adding couples until, eventually, we encounter a situation where all three ways in a set are full. If we have added Brad & Angelina, Kanye & Kim, Ben & Jennifer, and Burt & Loni, the cache will look like the following:

What happens if we try to add Kurt & Goldie? Since the hash for “Kurt” modulo 3 is 0, that couple should go into set 0, but that set is already full. What do we do?

This is where the cache replacement policy comes into effect. The cache needs a policy for how to remove existing cache items to make room for new ones. There are several policies to choose from, such as least-recently used (LRU), least-frequently used (LFU), most-recently used (MRU), and many others. If we use a least-recently used, or LRU, policy, then we should remove the item that hasn’t been stored or accessed as recently as any other item in the set. In our example, that will be Brad & Angelina, so they are evicted to make way for Kurt & Goldie:

We can carry on adding couples to the cache and evicting other couples as necessary until the cache is finally full.

If we add a new couple now, then no matter what set the couple ends up in, they will evict the least-recently used couple in that set.

Design

If you’re familiar with the design and implementation of hash tables, you may see some resemblance between the description above and the way that hash tables work. (If you’d like a good introduction to hash table implementation, read Ben Hoyt’s excellent article on implementing a hash table in C.) The key difference here is that in a hash table, the table expands to accommodate new key/value pairs, whereas in a cache there is a fixed capacity for elements and a policy for removing elements when the cache is full.

From the user’s point of view, I decided to make using the cache feel like using hash table (or, more generally, a dictionary). Inserting an element into the cache might be done using the same kind of indexing syntax used in a .NET dictionary, and retrieval of an element might be done with a TryGetValue method.

coupleCache["Brad"] = "Angelina";
string value;
bool hasBrad = coupleCache.TryGetValue("Brad", out value);

These are probably the two most common operations on a cache, and they need to be really, really fast. Let’s look at what’s involved in making these operations work.

First of all, consider testing for the presence of a key in the cache. We need to be able to quickly hash the key, find the set the key is in, then search the set for the key. This needs to be done when adding an item to the cache, and it also needs to be done when retrieving a value from the cache. Did I mention that this needs to be really, really fast? If it isn’t significantly faster to find and retrieve an item from the cache than from the original data source, then the cache is pointless.

Let’s consider some possible data structures and algorithms. A naïve implementation might use a linked list of key/value pairs to represent a single set, where the capacity of the linked list would be the number of ways in the set. Here are some pros:

• We can use the existing LinkedList<T> class to store our key/value pairs (using the KeyValuePair<TKey, TValue> class).
• Adding, removing, and inserting items is fairly simple.
• We can easily reorder the linked list if we need to (for example, to maintain removal policy).

There are cons, however:

• We would be using a general purpose class, LinkedList, for a very special purpose.
• Adding, removing, and inserting items is simple, and it’s generally faster in the worst case, but in the normal case it might not be as fast as we need it to be.
• Cache data would be co-located with housekeeping data, which might limit our implementation and performance options.
• Speaking of caches, linked lists are not very friendly to CPU caches.

Let’s look again at the constraints of the cache specification.

• We need to create caches with a fixed numbers of sets, where each set has a fixed number of ways.
• We need to allow clients to tune the numbers of sets and ways to obtain the best performance for their specific scenarios.
• We need to store any type of key and any type of value.
• We need to be FAST!

Let’s consider how users might want to create a cache in the first place. Much like the generic Dictionary type, users may want to provide the specific key and value types, so we’ll design for a generic interface. For our earlier example, which is a cache with string keys, string values, 3 sets of 3 items per set, and a least-recently used replacement policy, the code defining the cache instance might look like the following:

LruCache<string, string> coupleCache = new (sets: 3, ways: 3);

If we presume this usage pattern, then we can see that, at compile time, we know the both the total capacity of the cache and the replacement policy for evicting cache items. A fixed capacity is a hint than instead of linked lists, maybe we should consider arrays.

Many of you may already be saying, “NO! Inserting and rearranging items in arrays is SLOW!” Some of you, however, may be nodding and saying, “Haha array go brrrrr.”

Consider what we need to store, and what state we need to maintain, in order to make the cache work:

• Store the key/value pairs for the cache items.
• Track what items are in what sets.
• Track metadata in each set for maintaining the cache eviction policy.
• Track whether a given set is full.

We know that finding and retrieving a key/value pair has to be as fast as possible. Let’s step through the process again:

1. Hash the key
2. Find the set that stores the key
3. Find which way in the set contains the key
4. Use the key to get the value

We’ll consider step 1 to be a fixed cost, although it’s something we can possibly optimize later. Step two is just a modulo operation. Step three implies that we have to search the set for the key, and this is where the proverbial rubber meets the road. One of the advantages of using a set-associative cache is that it can minimize the impact of this step. Rather than searching every element in the cache, we only have to search the number of ways in a set, and we don’t want too many ways in a set anyway.

Let’s consider two arrays. The first array stores the actual data:

KeyValuePair<TKey, TValue>[] valueArray;

In our example of celebrity couples, we used a 3-set, 3-way cache. That would mean our value array would have nine elements (3 times 3) when the cache is instantiated, and it would stay that size. When a key/value pair is placed into a location in the array, we want it to stay there until it needs to be removed to make room for another item. We definitely don’t want to do any sorting or insertion on this array, since there is a potential for storing arbitrarily large value types in the array. That means we need to manage the bookkeeping in a separate data structure. Since we already have the keys in this array, we only need to keep track of the indices into this array so that we can quickly find them when needed. Let’s make another array of integers.

int[] keyArray;

This array stores the indices to items in valueArray. It is partitioned by set. It doesn’t matter where the actual key/value pairs are stored in the value array, as long as we track them here. (To be completely honest, we’re going to change this slightly in the implementation, but for simplicity we’ll stick with this definition for now.)

Let’s walk through our earlier examples above using this design.

When we create the key array and size it as sets times ways, we get this by default:

That isn’t very helpful, since all of the elements point at the first index in the value array. We need a sentinel value to tell us when a location in the key array is available. We’ll fill the empty array with int.MaxValue when the cache is created or cleared, so that the fresh key array looks like the following in memory:

That’s a little bit better. This array will easily fit into the CPU cache, which means we can operate on it very quickly.

Now, when we add Brad and Angelina, we can quickly see that the first element in set 0, which also happens to be key-array index 0, is empty. Next, we just need to find an empty spot in the value array where we can place the key/value pair. Uh-oh… how do we do that? Remember, KeyValuePair<TKey,TValue> is a value type, so a fresh array of KeyValuePair<string,string> would look like the following:

That might work if you assume that a null key, or maybe a null value, indicates an empty slot, but what if your key and value types are integers?

It’s entirely possible that zero is a valid key and/or value in such a cache. This definition won’t work. We need to make the array items nullable by adding a ? after the type and before the array brackets so that we can distinguish an empty cache slot from an occupied one.

KeyValuePair<TKey, TValue>?[] valueArray; // The ? makes this nullable

That way, by default, the value array is initialized thus:

Following these steps to add Brad & Angelina, we get the following contents for the key array, where element 0 contains the index in the value array where Brad & Angelina are stored (which also happens to be element 0).

Likewise, for the value array:

After we add Kanye & Kim, we get the following contents for the key array, where now element 6 contains the index for the location of Kanye & Kim in the value array (which, again, also happens to be element 6):

Likewise, for the value array:

So far it just looks like we have an unnecessary level of indirection to the value array, since the key array elements contain the corresponding indices into the value array, but let’s look at the case where we add another item to a set. Suppose that we want to add Ben & Jennifer. They will end up in set zero next to Brad & Angelina. However, we will need to do some bookkeeping now. If we’re using a least-recently used cache eviction policy, then we need to re-arrange the elements in the key array that correspond to the set so that, if we need to evict a cache item, we can easily find the least-recently used key. Let’s presume that we’ll always put the most-recently used key at the lowest index in the set, and we’ll move the other items to higher indices in the set up to make room for it. That will push the least-recently used key to the highest index in the set.

When we place Ben & Jennifer into set 0 (elements 0, 1 and 2), then in the key array we shift the contents of element 1 into element 2 and element 0 into element 1, and we put the new value index into element 0. That makes Ben & Jennifer the least-recently used cache item in the set. However, when we search for the next available value index in the value array, we find that Ben & Jennifer will be stored at element 1. That means our key array will look like the following:

The value array, however, will look like the following:

When we add Burt & Loni into set 0, we do another shift in the key array so that the value index for Brad & Angelina is stored in the key array’s highest index for set zero, meaning they’ll be up for eviction when another item is added to set zero, unless their key is accessed before then. The key array would look like the following:

The value array would look like the following:

We also need to adjust the indices when cache items are retrieved. With the LRU policy, every time a cache item is accessed, its key should be moved into the lowest index, pushing the rest of the items higher. Consider what would happen if the client code retrieved the item with the key “Brad.” That item’s index (index 0) would be moved into the spot for the most-recently used item:

The actual cache data in the value array would not change, however.

You can now see that the indices in the key array float around independently of the actual values in the value array. Because the key array just contains integers and is quite compact, it’s blazing fast to reorder elements in the array, much faster than with a linked list. I know, I’ve tried it.

Let me add a disclaimer for the Yeahbutters and the Whataboutists. I’m not saying that linked lists are never a good idea, or that they never out-perform arrays. I’m saying that in this particular usage scenario, where arrays can make better use of CPU cache and optimizations and intrinsics, arrays generally perform better. One should, however, always benchmark one’s code and test one’s assumptions with real-world data under real-world conditions.

Now that we have the overall design, in the next article we’ll dig a little deeper into the design and look at how to handle alternative cache-eviction policies. Then, we’ll consider what code interface to provide for users of the cache.

“Hello, hello again.”

This web site has languished long enough. It’s finally time to dust off those eleven draft posts that have been sitting around for years and start producing content again.

Over the last couple of months I’ve been working on my wife’s web site for her psychology practice, a WordPress site similar to this one, and it got me thinking that I should update my web development skills. I started writing HTML in 1995, but I’m just now learning things like ReactJS and modern JavaScript and all of the new tooling involved in professional web development.

Here are some of the things that are in the pipeline:

• A refresh of my web apps, implemented with ReactJS, especially my JavaScript implementation of Conway’s Game of Life.
• A web implementation of my virtual 64-bit CPU.
• Maybe a web version of the pbrain compiler.
• Those eleven draft articles I mentioned earlier.

Of course, I might get into that list, get inspired, and make a left turn somewhere on the road between Serendipity and Distraction. We’ll see.

Whatever happens, it’s good to be back.

I take my barbecue seriously, so I awoke at 4:00 this morning to start smoking a pork butt for a party this evening. I’m also rather old-fashioned about preparing barbecue, so I use a barrel smoker with a firebox rather than an electric smoker or an automatic pellet feeder. Not only do I like the end product better, but I also enjoy the process of smoking with an actual fire.

Preparing barbecue this way isn’t easy, though. There’s a lot of craft involved. I have to select the right kind of wood, with the right amount of seasoning (not too green, not too dry). I have to keep the fire just low enough to keep the temperature in the smoker in a narrow range. I also have to keep the fire burning and not smoldering to impart the best flavor to the meat.

Going through this process got me thinking about a few parallels with project management, particularly in the field of software development.

The temperature trend is more important than the current temperature.

Keeping the fire in the right range isn’t just about the current temperature. It’s about knowing which way the temperature is headed. If it’s headed up, I need to prepare to open the vent to let out a little more heat in case it gets too high. If it’s headed down, I might need to add a bit more wood. That’s not the whole story, though. I need to see where the temperature might settle before I do anything drastic. If it’s above 300° F or below 200° F, it’s clearly in a bad place, but I still need to know where it’s heading before I get too excited.

Parallel: It’s difficult to jump into a project and know just how it stands until you get a sense of what kind of progress, or lack of progress, is being made. A metric may tell a story, but multiple metrics tell a more complete story.

Have a stack of wood chopped, split, and ready to add to the fire.

I started working on my stack of wood yesterday afternoon, and even this morning I’m chopping, splitting, inspecting, and sourcing more wood. I don’t want to get caught with a dying fire and no prepared wood to add to it.

Parallel: When a project is critically understaffed, that’s the wrong time to start recruiting, interviewing, hiring, and training. A well-tended talent pipeline is critical for handling staffing disruptions on a long-running project.

Add wood to the fire before you need it, not after.

If I add a perfectly seasoned, quarter-split piece of wild cherry log to a dying bed of coals, the temperature in the smoker is going to drop precipitously, and I’ll find myself furiously blowing on the embers to “inspire” the fire to light so it can cook the meat.

Parallel: Adding an qualified, experienced hire to a staff that is overworked (and, like an ember, “burned out”) will not yield as effective a result as adding the same hire to a staff that is fully engaged. The new hire can get up to speed on the project more quickly when the team can take the time to train the hire and share their unique team culture.

Add the right kind of wood, in the right amount.

Different kinds or cuts of meat call for different kinds of wood. Hickory will impart a strong flavor to a couple of racks of ribs smoked for an afternoon. A large pork butt or brisket may call for a little bit milder smoke flavor, since those have to be smoked for several hours. Poultry may call for an even milder smoke. Even with the right wood, too little may not keep the fire going, and too much may either smother it or overheat it.

Parallel: Staffing a project, at the start and especially when it’s in-progress, calls for the same kind of care. Most of us probably have seen a project with too many bodies thrown at it, or without the right amount or mix of talent at inception.

Messing with the fire makes the temperature go down before it goes up.

Whenever I lift the lid on the firebox to check on the fire, I lose about 20° F of temperature in the smoker. It’s better to watch the trend on the thermometer or peek inside the firebox vent to see if it’s burning properly. Even so, I do have to open the lid to stoke the fire or add fuel. I can’t get too worked up when the fire’s “productivity” drops immediately after I’ve taken action to improve it. I have to trust that I’ve made the right change and let it take effect.

Parallel: Whenever a project is in trouble, managers tend to institute process changes and add status meetings and reports to track the effects of the changes. It’s not uncommon for those new reports to show that productivity has actually worsened. This can happen if there is overhead in learning the new process, or if the staff has to be trained on a new technology, or if there are additional meetings that initially take away from time that could be spent doing actual work. If the right changes have been made, however, productivity should eventually increase. A little trust and patience may be required.

 “Planning is bringing the future into the present so that you can do something about it now.” —  Alan Lakein

Late last year, I published an article entitled “How I Plan Every Minute of My Day to Stay Productive,” where I described my personal daily workflow of planning the tasks that I need to accomplish and then adjusting that plan as necessary throughout the day. I have a new job now, so I want to post an update on how well the approach is working in a new environment with new responsibilities, and how I’ve made a few tweaks to the process.

I’m now working in a vendor role embedded with the software-development team of a client company, and it’s easy to get pulled into many different directions. As with my previous position, I’m still working across time zones since my new employer is headquartered in the Pacific time zone and I’m three hours away in the Eastern time zone. There are also several more standing meetings and conference calls in this job, so finding large blocks of time for deep work is even more challenging.

Dealing With Email and Instant Messages

I still have a lot of email to read and respond to every morning, most of it having arrived late the previous evening from the west-coast team. As before, I schedule time to dig through it in the morning and respond to whatever’s urgent, but mostly I flag items for review or response and schedule time later in the day to deal with them. One thing that I’ve started doing is taking a little more time between tasks to deal with emails, like peeking at my inbox to see if there’s anything urgent to be dealt with before I dive into the next task. I did this because I’ve disabled email notifications, both on my laptop and my phone. That way, I don’t have a constant barrage of bells and popups drawing my attention away from what I’m working on, like sirens calling me to the shoals of low productivity.

My new company makes more extensive use of instant messaging, which brings its own challenges. I usually prefer IM over phone calls, but again, I don’t want to have notifications popping up all the time. I’ll check my messages between tasks and give a quick response before starting the next task. If I’m working on a task that requires concentration over a long stretch of time, I’ll set my IM status to “busy” or even “do not disturb” to discourage frivolous interruptions.

Scheduling Time for Recurring Tasks

Besides dealing with email, I now make a weekly plan to set aside time during each day to deal with other recurring tasks. These tasks are usually at the end of the day (in the case of code reviews) or just before daily meetings (updating status). Once all the recurring tasks and meetings are scheduled, I fill in the open spaces with either important daily tasks or ongoing tasks that need to be chipped away.

The image below shows what my calendar looks like for the coming week, which will be particularly busy since I have a deliverable due (I’ve blurred some sensitive details). The first task of the day is 15 minutes spent on planning. The gold tasks are recurring tasks that need to be dealt with every day. I start by working through my email backlog, and I finish with code reviews. The brown blocks are meetings or meeting-related tasks, gray blocks are personal items such as lunch or commuting, and green items are administrative tasks unrelated to the customer.

The orange blocks represent tasks related to the larger deliverable that is due by the end of the week. These are the items that I need to spend as much time on as possible, for as long a stretch of time as I can schedule. Some of the blocks are two hours or longer, which is a long time to sit at a laptop, so as I plan each day throughout the week I will probably break these down into one-hour chunks to give myself a chance to stand up, walk around, get a cup of fresh coffee, etc.

Multi-Desktop Approach

There is a risk to this approach. As I described in my first article, I will re-arrange tasks throughout the day as priorities change and new tasks appear. This can create a distraction of it’s own, with the temptation to switch to Outlook throughout the day and constantly fiddle with my schedule. To fight this, I create a new desktop in Windows 10 and keep my Outlook calendar window there. This way, I’m more likely to only change the schedule in between tasks.

Scheduling Serendipity

During weeks when there are not quite as many urgent tasks to be managed, I’ll schedule time for serendipity. This may sound like a contradiction, but finding innovative approaches to software development is a big part of my job and my career. A lot of these discoveries happen when reading articles linked from a few favorite web sites (lately, Hacker News has been a great source of these). If I allow myself to sneak a peek at these articles in between tasks, I run the risk of being pulled into a half-hour or more of link chasing. Instead, I’ll schedule time to peruse headlines or read articles that I’ve saved.

Serendipity may also derive from chance encounters with colleagues, so if you work in a field that tends to keep you chained to your desk (like software development), make a point of getting up and moving around periodically to connect with others around you. Schedule such time, if it helps. Besides, it’s good for you to get up from your desk and move.

Moving Toward Deep Work

My earlier article mentioned Cal Newport’s research into what he calls “deep work,” and I’ve been trying to move my schedule toward that model. Anything I can do to reserve large blocks of time throughout the day to get completely engrossed in my work helps with this goal.

The modern work environment, with its open floorplans and tendency toward meetings and conference calls of little value, seems almost designed for shallowness. Look for ways to adjust your schedule and your environment so that you can get completely engrossed in a task. You’ll get more done, and the work you produce will be of a higher quality.

Applying It To Your Schedule

Here are a few ideas that have helped me with this approach:

1. Schedule at a finer resolution. For me, it’s fifteen-minute increments. Thirty minutes is too coarse for squeezing in everything I want to do. If I plan a thirty-minute block for a fifteen-minute task, I’ll be tempted to waste the remaining time or to expand the task to fill the reserved block.
2. Use a calendar that works for you. I happen to like Outlook for a number of reasons, but you should use something that fits your style and your approach to your work. Maybe it’s a paper notebook, or a smart phone, or a different calendar application, or even a bare-bones text editor. As long as it’s something you can use easily that lets you make changes quickly, it’s good enough.
3. Start on time – especially meetings! The biggest uncontrollable time sink I have every day is dealing with meetings that don’t start promptly. That topic is probably worth its own article, but starting tasks and meetings on time, and then finishing them on time or even earlier than scheduled, might net you an hour or more over the course of a day.
4. Schedule flexibly, but not too flexibly. No schedule will remain perfect over the course of a day unless you’re able to work in isolation, and that’s a rare gig, indeed. Leave space in your schedule to deal with distractions and randomization, and allow yourself the freedom to adjust your schedule throughout the day. This is why I like to use Outlook, since I can drag and drop tasks around during the day with ease. This can be dangerous, however, if you let yourself get pulled into constantly tweaking your schedule. Be firm, and let your colleagues know when you have time scheduled for getting things done. Don’t be afraid to say, “No.”
5. Review your schedule. Looking back over your schedule, especially if you carefully adjust it during the day to reflect what you actually did, is a great way to learn about your working style and adjust it to be more productive. Look for random items that crept in, and try to find ways to move those to a block of time where you can deal with them together so that you have more large blocks of time for concentrating on what you really need to do.

I’d love to hear from you about how you plan your day, and what tips and tricks have worked for you.

The quality of your company’s software will never exceed the quality of your company’s software developers.
— Paul M. Parks

If you’re not recruiting the best developers you can possibly afford and training the ones you have, you’re losing to the companies that are.

Here are some links to interesting board layouts:

The basic page, which implements a glider.

A Gosper glider gun

A Gosper glider gun running at top speed, probably faster than your screen’s refresh rate.

A set of cells that devolves into a single spinner.

A pair of gliders which follow each other endlessly.

A large board with a long-running pattern

“In preparing for battle I have always found that plans are useless, but planning is indispensable.” — Dwight D. Eisenhower

Over the years, I have progressed from being a software developer who focuses on code all day, to a designer who designs and codes, to a technical lead who communicates a design and technical strategy to a team of developers, to a technical and project lead who leads developers in the implementation of a project while communicating with customers and other stakeholders. At each level the demands on my time have increased, while the expectations of improved productivity and reliable delivery have also increased.

I’ve played with various ways of planning and scheduling, but the method that has proven to be most effective so far is a variation of  Cal Newport’s tips for scheduling, particularly what he discusses in the article “Deep Habits: The Importance of Planning Every Minute of Your Work Day”. The idea is to lay out a plan for my day in my calendar, at the start of each day before I’ve jumped into any other activity. The plan isn’t rigid, but rather a guide for what I tasks need to accomplish and how I would like to get them done.

To show you how this works, I’ll walk you through a typical working day for me. While the tasks described are entirely fictional, they are still quite representative of what you would find in my real OneNote and Outlook files.

I usually start my working day just before 6:30 AM, after I’ve made breakfast for the family and I’ve wandered upstairs to my home office with a large mug of coffee. I’ll take a few moments to look over my OneNote file, where I keep meticulous notes on everything that happens on a daily basis: what meetings were held, what decisions were made, what questions are open, and what actions need to be taken. For my own actions, I use OneNote’s CTRL-1 keyboard shortcut to put a check box by each action so that I can easily see what needs to be done. Any actions that aren’t due on the current day end up at the top of my file, under the heading “The Future”, and as I create a new entry in the file for each new day, I’ll move the items I need to accomplish under that day’s heading.

For example, by the end of the previous day my general notes file in OneNote might look like the following:

As you can see, I’m in the middle of a particularly busy week where a lot of to-do items have piled up. Some are little more than annoying administrative tasks, while others require some deep work and concentration to complete. When I create an entry in OneNote for the new day, I’ll use the ALT-UpArrow and ALT-DownArrow keyboard shortcuts to move the most important to-do items to the current day, and then I’ll review notes from the last few days to see if any unchecked or unidentified actions were lurking in those entries. When I finish, the OneNote file might look like the following:

Now I’ll open my Outlook calendar and start blocking off time during the day for the various tasks I need to accomplish. Since I work on several concurrent projects, I put a project identification code on each task, and I even color-code the tasks by project so that I can see at a glance where my time is going. There will probably already be some entries for pre-scheduled meetings and conference calls, so I also need to be careful to plan my day around those fixed items.

Next, I block off time for the annoying tasks that just need to be cleared out. For me, mornings are the best time to do this because that’s the noisiest time of my day, and I can move these items around as needed. They usually don’t require a lot of concentration or other resources, so it’s no big loss to reschedule them or to be interrupted while doing them. Consequently, you’ll notice that most of these tasks are shown as free time in Outlook, in case someone needs to schedule me for a meeting during the times that I’ve blocked off to complete these tasks.

With that done, I start my day. The first half hour or so is usually reserved for dealing with email. Currently, my customers and project managers are in the UK, and my development teams are split between the Philippines and India, so I usually wake up to a bulging inbox in Outlook. I read and respond to what I can, and I flag the items that need to be dealt with later, perhaps creating a calendar entry for them.

One of the emails sitting in my inbox is from the QA lead, saying that she has some questions about the spec and how it relates to her test plan. I had already reserved some time later in the day to drop in and chat with her, so I expand that entry in the calendar to make time for what needs to be discussed.

Next, I have a conference call scheduled with the development team from 7:00 to 8:00. Then, I start to look over a customer requirements document, after which I plan to finish a code review that’s been assigned to me in Crucible.

Most of the way through the requirements document, however, I get a call from the programme manager in London asking if I can participate in an urgent discussion about some changes that a customer stakeholder requires in a PowerPoint slide deck that we sent last week. “No problem,” I say, and soon I see a meeting request appear in my calendar from 9:00 to 9:30. That’s when I had planned to knock out the code review, but that’s okay. I just drag the code review to another part of the day and do some quick shuffling of tasks, taking no more than a minute or two to do so. The review moves down, the time I plan to drop in on the QA lead moves, and some less urgent tasks get pushed to later in the day or maybe even to tomorrow. The large block of time I reserved for the development task, however, stays in the afternoon, since that’s when my distractions usually diminish and I can concentrate on difficult tasks.

The meeting with the customer ends with an urgent action to update the slide deck and get that back to the customer, so I do a little more shuffling and start that task right away. By the time that task is complete, I’ve finished the portion of my day that I usually spend at my home office, so I get cleaned up and drive to the real office. That’s the time I have blocked off from 10:30 to 11:30 as “Out of office” so that nobody tries to schedule me for that time.

Once in the office, I get the code review done, hop onto the intranet travel-booking web site to reserve a hotel for an upcoming trip, and then make a cup of tea and go find the QA lead. It’s a productive meeting, and some of the outputs dovetail nicely into my next scheduled task to update the dependency table for an upcoming project. Now I’ve cleared out most of my “busy” work, so I make another cup of tea and spend the rest of my afternoon getting lost in code.

My Outlook settings automatically generate a 5-minute reminder for upcoming tasks, so as I near the end of each scheduled task I’ll get a notification to wrap up what I’m doing, take a little break, and then dive into the next task. As I start each new task, I know that since I only have a set amount of time in which to complete it I have to stay focused and get the task done in the allotted time, so that I can get through all of what I want to get done for the day.

For ongoing tasks, where I’m just trying to allocate time to work on them rather than complete them, I fight the urge to work “just a little longer” when the reminder pops up, again so that I can keep knocking out those tasks that really do have to get done today. This is another reason I like to schedule ongoing tasks for the end of the day.

I have found that, generally, how productive I am in a given week is dependent on how closely I stick to this method of planning and recording my day. Planning, because it gives me a clear image of what I want to get done and how much time I have to work with. Recording, because I make sure that as I complete tasks I go back and expand or contract the actual time spent so that I can look back through previous days and get an idea of how much time to reserve for new tasks based on how long similar tasks have taken in the past. It’s also great for when I have to submit my time-tracking reports at the end of the week, since everything I’ve done is laid out very clearly, along with who gets the bill for that time.

I’d like to hear how you plan your days, and what little hacks make you more productive.