The C++ Standard Library provides the std::map container for collections of items that need to be looked up by a "key" identifier. This is much more flexible that an array container like std::vector that can only look items up by a contiguous set of integer indexes. While std::map and std::unordered_map have some admirable complexity guarantees they have much worse performance than an array. For fast technical applications we would love to have the semantics and syntax of std::map but the performance of an array. Happily, there are a number of situations where, with a little work, we can craft such a solution.
The C++ map containers are designed to provide good complexity guarantees for large containers with an arbitrary mix of insertion, lookup, and deletion operations. Achieving this asymptotic complexity comes at the cost of a large time and space overhead that is wasteful for collections that don't fall in this category.
Collections that are small or where lookups dominate insertion/deletion are common in scientific and engineering applications. An example that is prominent in ObjexxSISAME is vectors and matrices indexed by the axes for the model's degree of freedom set (ObjexxSISAME supports any meaningful 1, 2, or 3D model DOF set): these have only up to 6 keys and the key set is fixed once they are initialized. Or we may be modeling proteins where we need to look up the 20 canonical amino acids by a named key. Using a std::map for lookups on such containers is taking a massive, yes massive, performance hit.
So, how do we create this fast map-like container? Well, there are variations depending on the specifics but the basic ingredients are:
- A lightweight key class that holds an internal index value.
- The index type could be an appropriately small integer type for the number of possible keys.
- The key will usually have an associated name that is either stored in the key or determined by lookup in an external container when many containers with the same key set are expected.
- The key class may contain an enumeration the defines the possible index values and a static mechanism for looking up the name from that index and vice versa.
- The key class must define an order via operator< and an operator that does conversion to the index type.
- The key type is normally small enough that it is fastest to pass it by value rather than const reference.
- A container with map (and optionally vector) semantics that holds a contiguous vector of the actual values and holds or has access to another vector that maps key indexes to indexes in this internal vector.
- This second vector has room for all possible keys and uses a sentinel flag value to indicate a non-present key.
- When this mapping from keys to indexes is common to many containers it can be held externally to the container and accessed via a stored pointer.
- The container provides operator[] and/or operator() that take key arguments and use a two-step lookup for the value for a given key, of the form return vals_[idxs_[key]]. This two-step lookup is a bit slower than a normal one-step vector lookup but is still dramatically faster than std::map.
- If useful, the container can also expose index-based lookup operators for faster one-step lookup by client code.
The performance impact of using a custom key map system can be dramatic, as the benchmark results shown here demonstrate.
The specific design can vary depending on such criteria as whether the key-to-index map is common to many containers and whether it is small enough that repeating it is worth the space cost to avoid the extra indirection, whether the key-to-index map is known at compile time (and thus can be a template argument, avoiding both space and indirection costs).
Additional notes:
- Operations over the whole container can be performed internally over the underlying vector, avoiding even the fast key-based lookup step.
- Multidimensional key-accessed "matrix" containers can be created along the same lines, built on top of a vector of vectors, for example.
- An obvious question is how large does the key set (and thus container) have to be for std::map to start to be competitive again. The precise answer to this depends on the specific platform and compiler but in our experience map isn't faster until you are up to thousands of possible keys.
- You may want different containers depending on whether the value being stored for each key is a small/built-in type that is fastest if passed by value or a larger object that is best passed by const reference.
- Normally we have the internal vector hold just the values but in some cases you may want a container that holds std::pair
- If your container must support frequent insertion/deletion operations note that for sufficiently small containers it will be faster to hold just an unordered vector of std::pair
The takeaway from this is that use of std::map and similar containers should be limited in technical software and that there are much faster containers for many situations where maps get used. Objexx has developed a suite of fast key map containers for various scenarios that we have used with great results in our in-house and client applications.