SimCList – A C library for Lists

l.u. 04/11/2007

SimCList is a high quality C (C++ embeddable) library for handling lists. It exploits several advanced techniques for improving performance, including freelists, sentinels, automatic sort algorithm selection, sort randomization, mid pointer and optional multithreading.

SimCList is available for free, under restrictions imposed by the BSD license.

The SimCList API

SimCList API is good because:

it is simple, yet powerful
it makes elegant and consistent use of information hiding
it abstracts the actual data type to store
it is fairly total

The library itself is very performant and makes a good compromise between performance in terms of time and space:

insertion is O(n) [typically n/8]
extraction and deletion are O(n) [typically n/8]
iteration is O(1)
sorting is always O(n logn), without worst case

Documentation

Have a look at a sneak peak into the API for an example-driven introduction to SimCList.

The library header file simclist.h itself is fully documented.

An automatically generated html prospect of the API is also available.

Thread safety

The SimCList library is thread safe, meaning that many threads can run SimCList operators on different lists concurrently without hurt, or also read operations on the same list.

However, of course, no safety guarantee is made for performing concurrently write+write or read+write operations on the same list (eg: insertion, deletion, sorting, ...). For performance and portability reasons, protecting such operations from concurrency is left to the library adopter.

Performance

SimCList has been designed with ease of use and performance in mind. There is some example factors that have been taken into account, and against which the code has been optimized when implementing SimCList:

overhead of function calls
cache locality
number of branches, possible CPU stalls or pipeline flushes
dynamic memory allocation weight on the OS
other mathematic/probabilistic optimizations for avoiding worst-case or improving average case behaviours in algorithms

Many parts of SimCList's code have been deeply improved with profiling analysis.

These are some results:

description	time	code
10 million insertions of one same element, without element copy	0m1.382s	ins.c
insertion of 1M elements with autocopy, then extraction of 1k elements at random positions	0m1.224s	ext.c
insertion of 1M random elements with autocopy, then sorting	0m1.094s	sort.c
insertion of 1M random elements with autocopy, then sorting, with SimCList threading enabled	0m0.897s	sort.c

Test bench:

hardware: MacBook Pro Core2 Duo 2.16GHz, 1G Ram
software: Mac OS X 10.4.8, compiler: gcc 4.0.1 (flags -O2)

License, Getting & Installing, Bugs

License

SimCList is licensed BSD. See the BSD license content for details.

Getting & Installing

You can embed simclist into your source code (because of the BSD license) or use it as a dynamic link library.
For the former: just download simclist and include the simclist.c and simclist.h files into your package.
For the latter: there is a buildfile in the package that makes it automatically.

download the latest SimCList package (Changes)
decompress it and get into its top dir
run cmake . there (mind the dot). This generates Makefiles for your platform.
run make there. This provides a libsimclist.so or libsimclist.dylib library file in the current dir.

Bugs and the rest

One bug has been found in simclist-1.0 in list_concat(), whose output could become inconsistent after element deletion. One bug in simclist-1.1 in list_insert_at(), whose output could become inconsistent when inserting in even-sized lists in position 0.
If you encounter new bugs, or you have a comment or feature request, please report to mij@bitchx.it.

When reporting bugs like crashes, a core dump describing the the event in detail is desirable. For better tracking, debug symbols should be enabled in SimCList. They can be easily activated by uncommenting the apposite line in SimCList makefile and recompiling.