 |
The Standard Template Library (STL) is the algorithmic core of the C ++ standard library. From a theoretical point of view, the knowledge required to implement the STL is
well laid down on basic textbooks on algorithms and data structures.
In particular, doubly linked lists are commonly used to implement STL lists, e.g., in the GCC compiler. Doubly linked lists can easily keep up with all the requirements in the C ++ Standard Library. However, they do not use the cache hierarchy effectively. Cache hierarchies rely on the locality of data, whereas in doubly linked lists (as in any pointer-based data structure), the logical and physical element positions are independent. Nodes in a doubly linked list are allocated using memory allocators, which typically answer consecutive memory requests with consecutive addresses of memory. Thus, if elements are only inserted at one point, there is a good chance that good cache performance is obtained when elements are traversed. However, if elements are inserted at random points or if the list is shuffled or if different lists are constructed, logically consecutive elements will rarely be at nearby physical locations. Therefore, a traversal may incur in a cache miss per access, thus dramatically increasing the execution time. Figure 1 illustrates this fact for a list of integers built by inserting each element one after the other.
Taking into account that list is used when elements are often reorganized or inserted and deleted at arbitrary positions, it is worth to try to improve the performance of list using a cache-conscious approach.
Our implementation combines cache efficiency with STL list requirements, paying special attention to iterator constraints. In particular, our implementation corresponds to the one described in [1,2].
|
Implementation at SourceForge.net: http://sourceforge.net/projects/cachelists/
The implementation consists of a set of C ++ header files, and hence it can be used by simply including them from client code. In particular, the header cache-list.h from the desired version must be included. In all cases, the class name is cache_list, so that it can be used together with the built-in list implementation.
Besides, the source code for performance tests (see [1,2] for more information on these tests) can be retrieved from the svn repository https://cachelists.svn.sourceforge.net/svnroot/cachelists provided by SourceForge.net. It can also be used as an usage example.
The current implementation is partial. It includes insert, push_back, push_front, sort, and iterator operations. The rest of operations could be implemented keeping up with cost and functionality requirements.
Note that the implementation is not thread safe.