Language:

The Free and Open Productivity Suite
Apache OpenOffice 4.1.4 released

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

Apache Software Foundation

Copyright & License | Privacy | Contact Us | Donate | Thanks

Apache and the Apache feather logo are trademarks of The Apache Software Foundation. OpenOffice, OpenOffice.org and the seagull logo are registered trademarks of The Apache Software Foundation. Other names appearing on the site may be trademarks of their respective owners.