Cache-conscious STL lists

Leonor Frias (leofm.sourceforge@gmail.com)


This project provides a cache-conscious partial implementation of STL lists.

Motivation

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].

Figure 1: Time measurements for list traversal before and after shuffling the links by sorting the list. The vertical axis is scaled to the list size.
Image traverse-9-30-353-OP-TRAVERSE-AFTER-CHANGE-RANDOM-list000

Downloads

Implementation at SourceForge.net: http://sourceforge.net/projects/cachelists/

HowTo

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.

Caveats

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.

Publications

1
L. Frias, J. Petit, and S. Roura.
Lists Revisited: Cache Conscious STL Lists.
In Experimental Algorithms, 5th International Workshop, WEA 2006, Cala Galdana, Menorca, Spain, May 24-27, 2006, Proceedings, volume 4007 of Lecture Notes in Computer Science, pages 121-133, Berlin, Heidelberg, May 2006. Springer.
[pdf]

2
L. Frias, J. Petit, and S. Roura.
Lists Revisited: Cache Conscious STL Lists.
Journal of Experimental Algorithmics, 14:3.5-3.27, 2009.
[pdf]


2010-04-21