Enhanced parallel partition for string quicksort(-select)

Leonor Frias (leofm.sourceforge@gmail.com)


This project provides several implementations of generic parallel partitioning algorithms that can be combined transparently with efficient string comparators. In this way, efficient parallel partitioning-based algorithms, namely quicksort and quickselect, can be built for strings.

Description

The partitioning of an array is a basic building block of many key algorithms, such as quicksort and quickselect. Besides, it is typically used in the implementation of STL partition, nth_element and sort. STL stands for Standard Template Library and constitutes the algorithmic core of the C ++ standard library. Besides, there are also several implementations of parallel partitioning algorithms, in particular, aimed at multi-core multiprocessors. For instance, the widely spread GCC compiler provides parallel partitioning through the so-called libstdc++ parallel mode.

In the case of strings, lexicographical order is commonly considered for partitioning. However, many redundant symbol comparisons might be performed when partitioning is applied repetitively and hierarchically as in quicksort and quickselect. This source of inefficiency can be avoided taking into consideration the digital structure of strings, and the relative order and outcome of comparisons. Indeed, some general techniques have been described to enhance comparison-based algorithms and data structures for strings. In particular, in order to efficiently reuse the information from comparisons, some extra data per element must be kept. The resulting implementations are amenable, and the data structures and algorithms are competitive in practice. In particular, this approach is convenient for long and skewed strings.

We provide a C ++ implementation of parallel partitioning algorithms enhanced for strings using the aforementioned techniques. Specifically, the implementation follows from the piece of work in [3] and it is the first time that such techniques are combined with parallel algorithms. The reduction on the number of character comparisons comes only into play when parallel partitioning algorithms are used repetitively as in quicksort and quickselect, using them isolatedly has no benefit. Our implementation is based in the implementation of generic parallel partitioning algorithms in https://sourceforge.net/projects/parpartition/ and described in the piece of work in [2]. In particular, the optimality of those algorithms with respect to the number of key comparisons is crucial to this task.

Our implementation consists of three pieces:

Furthermore, our implementation extend the work in [3] providing specialized comparators for strings that add redundancy or consider big alphabets. Both variations aim at decreasing the number of strings accesses, and as a result, improving the cache performance. Specifically, the piece of work in [1] shows that the number of string lookups decreases by adding redundancy to so-enhanced quicksort and quickselect for strings.

Finally, our implementation could be the base for an eventual specialization of STL partition, nth_element and sort for strings (See Section Precautions for considerations on standard C ++ strings).

Downloads

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

HowTo

The implementation consists of a set of C ++ header files, and hence it can be used by simply including it from client code. Specifically,

Furthermore, the source code for performance tests (see [3] for more information on these tests) can be retrieved from the svn repository https://stringbsts.svn.sourceforge.net/svnroot/stringbsts provided by SourceForge.net. It can also be used as an usage example.

Precautions

The provided string comparators so far assume that the strings end with an special end character. Thus, these comparators can only be used with standard C ++ string, if the specific implementation guarantees a null ended string (which the Standard does not force to). In order to guarantee full compatibility with string, new analogous string comparators should be defined relying on the string::size method instead.

Publications

1
L. Frias.
On the number of string lookups in BSTs (and related algorithms) with digital access.
Technical report LSI-09-14-R, Universitat Politècnica de Catalunya, Departament de Llenguatges i Sistemes Informàtics, 2009.

2
L. Frias and J. Petit.
Parallel partition revisited.
In Experimental Algorithms, 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30-June 1, 2008, Proceedings, volume 5038 of Lecture Notes in Computer Science, pages 142-153, Berlin, Heidelberg, 2008. Springer.

3
L. Frias and J. Petit.
Combining digital access and parallel partition for quicksort and quickselect.
In IWMSE '09: Proceedings of the 2009 ICSE Workshop on Multicore Software Engineering, pages 33-40, Washington, DC, USA, 2009. IEEE Computer Society.



2010-05-12