Analysis of List class uses

Summary

All code that uses OOo's List class (ie DECLARE_LIST(foo, OString)) should be converted to use std::vector or std::deque since these functions are more efficient, faster, and better understood. Little work is required for this conversion as the functionality of List and std::vector/std::deque is pretty much the same.

Results Spreadsheet: ListComparison.sxc

Problem

OOo uses its internal List class (see tools/inc/list.hxx) in a fair number of places. This code was written originally in 1991/1992 and is probably pre-Standard Template Library. Its usage is a bit arcane, and the STL implementations of various list variants are probably more understood and better implemented. The Tools List class is implemented using C Macros, as such:

DECLARE_LIST( list_class_name, list_class_type )

After this statement, a class named "list_class_name" will exist, which stores objects of type "list_class_type". The List class has a number of functions that perform operations such as removal of elements, insertion of elements, and arbitrary retrieval of elements. However, this is a non-standard API (compared to the STL), and as we will see below, is not as efficient as certain STL classes.

Comparison of Classes

4 list classes were compared: OOo's Tools List class, and STLport's std::list, std::vector, and std::deque. It is fairly trivial to convert instances of the Tools List class over to equivalent STL classes, yielding better performance for the operations OOo code most uses.

Testing methodology was fairly informal, and the results of the speed tests are not absolute. They should give a best-case scenario of the efficiency and speed of which each particular list class completes certain operations. For each class, a small test program was run, which tested 5 operations 30 times each, for 10, 100, 1000, and 10000 list elements. An average was then calculated and printed to stderr. List elements were of type 'int'.

1. Creation of list with N elements
2. Deletion of list with N elements
3. Sequential removal of all elements, from Front (including dereference of iterator)
4. Sequential removal of all elements, from Back (including dereference of iterator)
5. Sequential iteration of all elements in the list, Front->Back

The test program was run 4 times, and the best average score from each of the operations from all 4 times was recorded as the final time. I.E.: run once (30-run average for each of the 5 ops), enter times. Run 3 more times and enter best time from any test for each of the 5 operations.

stl-list.cxx   stl-vector.cxx   stl-deque.cxx   ooo-list.cxx

Results

Operation	STL std::list	STL std::vector	STL std::deque	OOo List
Create 10e	8	9	6	8	Chart
Delete 10e	8	7	7	7
Remove Front 10e	8		7	8
Remove Back 10e	8	6	7	7
Iteration 10e	7	7	7	7
Create 100e	25	12	8	24	Chart
Delete 100e	24	7	8	9
Remove Front 100e	24		8	27
Remove Back 100e	24	7	8	16
Iteration 100e	7	7	7	7
Create 1000e	192	19	20	179	Chart
Delete 1000e	159	8	12	9
Remove Front 1000e	177		15	791
Remove Back 1000e	180	7	14	111
Iteration 1000e	11	7	9	7
Create 10000e	1762	231	126	1068	Chart
Delete 10000e	1513	22	56	12
Remove Front 10000e	1711		85	7975
Remove Back 10000e	1720	13	82	1064
Iteration 10000e	57	13	28	13

NOTE: all times are in u-seconds

Analysis

OOo List class: not the best choice for some operations. In fact, it does horribly at removing items from the front of the list, and not quite so badly at removing items from the rear. In fact, it was found that remove items from a loop as follows (which is done quite often in OOo) is even worse, by a factor of 10 or more:

	while(mpPageMasterInfoList->Count())
		delete mpPageMasterInfoList->Remove(mpPageMasterInfoList->Count() - 1L);

Using the Remove( N ) function is much slower than using the Remove() function. Remove() simply removes the node pointed to by the current list pointer, which is set using Front(), Back(), Next(), and Prev(). Rewriting the code as such gains a factor of 10 speed increase, at least in this limited test case:

	while(mpPageMasterInfoList->Count())
	{
		mpPageMasterInfoList->Last();
		delete mpPageMasterInfoList->Remove();
	}

In general though, the OOo list class performs poorly compared to the STL's std::vector and std::deque.

std::list: while faster than the OOo list class, it is not as ideal as std::vector or std::deque.

std::vector: while faster than the OOo list class and std::list, it is not as ideal as std::deque because it does not support head-removal (ie pop_front()).

std::deque: while not always the fastest class, it is generally in the same class as std::vector. However, it supports head-removal and also random access to its elements. It is therefore more versatile than std::vector and almost as fast.

Recommendations

Code that uses the OOo List class should gradually be converted over to either std::deque or std::vector, whichever is appropriate for the situation. This conversion yields the following benefits:

1. Faster
2. Better understood code and tradeoffs
3. More recent code