Algorithms and Data Structures

ADS is a header-only C++20 library of the algorithms and the data structures of the (Italian) textbook

A. Montresor, Algoritmi e Strutture Dati, 2025, https://algoritmicamente.it (CC BY-NC 4.0)

(a revision of A. A. Bertossi and A. Montresor, Algoritmi e Strutture di Dati, 3rd edition, Città Studi, 2014), in which each exercise of the book is a test. It also has the structures and the algorithms that a course on the subject usually adds, and a few engineered ones meant for speed. An abstract data type is a C++20 concept whose realizations follow the pseudocode and the names of the book (empty(), head(), next(), read(), push(), enqueue(), and so on), and hence the code can be read side by side with the text. Where the book leaves a choice open, or its pseudocode has a defect (a few figures, too, disagree with the formulae they illustrate), the header states the choice made and the reason for it.

Performance

The table below compares the engineered structures of ADS with those of the standard library (libstdc++), of Boost 1.83, of GMP 6.3.0, of FFTW 3.3.10 and of pocketfft and ducc0, as measured by the benchmarks in bench/ (make bench). These were run twice on an otherwise idle Intel Xeon Gold 5120 at 2.2 GHz, on one core pinned by taskset, with g++ 13.3 at -O3 -march=native; GMP was configured for that processor, and FFTW was built with SSE2, AVX, AVX2 and AVX-512. Each cell of a benchmark is the median of 11 runs, and the clock does not include the building of the input nor the planning of FFTW and of ADS (measured apart in the row “fft plan”). A row gives the time of the library divided by that of ADS (above 1 when ADS is faster), as the median and the range over the cells of the benchmark, i.e., its cases (e.g., random, sorted or few distinct keys for the sorts) and its sizes (\(10^5\) and \(10^6\) items for the containers). When a library has more than one candidate, the time of a cell is that of the fastest of them (e.g., the faster of boost::pdqsort and boost::spreadsort). The same code measured twice differs by 1.1% in the median cell and by 4.3% at the 90th percentile, over the 1544 cells of the two runs; the largest differences, up to 50%, are in cells of a few hundred nanoseconds, where they are the resolution of the clock. Hence, a ratio between 0.95 and 1.05 is usually a tie.

benchmark	ADS	against	cells	median	range
sort double	`ADS::sort`	std	12	8.83	1.95 to 32
	`ADS::sort`	Boost	12	2.20	0.93 to 14
	`ADS::stableSort`	std	12	4.35	1.67 to 25
	`ADS::stableSort`	Boost	12	1.20	0.88 to 3.01
sort int64	`ADS::sort`	std	12	14	1.95 to 39
	`ADS::sort`	Boost	12	3.52	0.84 to 17
	`ADS::stableSort`	std	12	13	2.33 to 32
	`ADS::stableSort`	Boost	12	1.40	0.71 to 26
sort record	`ADS::sort`	std	12	2.33	1.10 to 6.60
	`ADS::sort`	Boost	12	1.00	0.98 to 1.02
	`ADS::stableSort`	std	12	5.53	0.75 to 32
	`ADS::stableSort`	Boost	12	0.98	0.57 to 1.16
sort string	`ADS::sort`	std	12	3.36	1.67 to 5.15
	`ADS::sort`	Boost	12	1.45	0.90 to 2.20
	`ADS::stableSort`	std	12	2.37	1.68 to 6.10
	`ADS::stableSort`	Boost	12	2.76	1.34 to 5.62
sort uint32	`ADS::sort`	std	12	15	3.90 to 36
	`ADS::sort`	Boost	12	3.93	0.75 to 16
	`ADS::stableSort`	std	12	13	1.34 to 41
	`ADS::stableSort`	Boost	12	1.03	0.63 to 36
dictionaries	`ADS::FlatHashTable`	std	8	5.47	4.32 to 16
	`ADS::FlatHashTable`	Boost	8	0.93	0.75 to 1.16
	`ADS::RedBlackTree`	std	8	1.45	1.00 to 2.38
priority	`ADS::DaryHeap d=4`	std	6	1.62	1.38 to 2.17
	`ADS::DaryHeap d=4`	Boost	6	1.04	0.87 to 1.68
	`ADS::FibonacciHeapPriorityQueue`	Boost	6	0.61	0.54 to 0.86
sequences	`ADS::ArraySequence`	std	6	1.05	1.00 to 1.12
	`ADS::List`	std	6	1.02	0.99 to 1.10
	`ADS::SinglyList`	std	6	0.98	0.86 to 1.03
bignum	`ADS::BigInteger`	Boost	12	4.04	1.00 to 91
	`ADS::BigInteger`	GMP	12	0.33	0.20 to 1.25
	`ADS::Rational`	Boost	3	4.74	1.93 to 6.03
	`ADS::Rational`	GMP	3	0.42	0.40 to 0.46
fft	`ADS::fft`	FFTW	44	1.11	0.84 to 2.41
		pocketfft	44	3.18	1.44 to 21
		ducc0	37	1.97	1.09 to 17
fft plan	`ADS::fft`	FFTW	7	0.22	0.07 to 1290

ADS::sort() and ADS::stableSort() are faster than the standard library in almost all the cells, by 2 to 15 times in the median (the radix sorts accounting for most of it), and they are often as fast as Boost or faster. However, boost::spinsort is 1.4 to 1.8 times faster on the stable sort of records, of sorted 32-bit keys and of reversed 64-bit keys at \(10^5\), and boost::spreadsort is 1.3 times faster on sorted 32-bit keys. FlatHashTable is 4 to 16 times faster than std::unordered_map, and it is on a par with boost::unordered_flat_map on the lookups, but for the misses among \(10^5\) keys (where Boost is 1.15 times faster). Boost is also 1.3 times faster on the insertions and the visits of \(10^5\) keys, and 1.16 times slower on the insertions of \(10^6\). It is fair to remark that the libraries built on hand-written kernels stay ahead. GMP is 2 to 5 times faster than BigInteger on products, quotients and decimal conversion (twice as fast already at 16 limbs, where both use the schoolbook algorithms), and mpq_class is 2.2 to 2.5 times faster than Rational; ADS::fft (complex, real and single precision data, the cosines of type 2, many transforms, 2 dimensions and convolutions, on powers of 2 and on other sizes) is faster than the faster plan of FFTW in the median cell, by 1.11, and 1.4 to 3 times faster than pocketfft and ducc0; FFTW stays ahead by 1.15 to 1.2 times on the real transform of \(2^{14}\) points, by 1.1 on the transform of 32 x 32 points and by 1.06 to 1.23 on the real one of \(2^{20}\), the other cells below 1 (0.94 to 0.99 in one of the two runs, at least 1 in the other) being ties. The plans of ADS, which time 4 factorizations up to \(2^{17}\) points, cost up to 0.4 µs per point, against up to 900 µs of FFTW_MEASURE and 3 µs of FFTW_ESTIMATE. Also, the Fibonacci heap of Boost is 1.2 to 1.9 times faster than that of ADS, which follows the pseudocode of the book. The tables of all the structures, those of the book included, are in results/ together with the raw files of the two runs.

Parallelism

The parallel algorithms of ADS take an executor as their first argument, i.e., any object that runs the calls f( 0 ), …, f( n - 1 ) of a function on its threads and returns when they have returned (bulk()), and that tells how many threads it has (concurrency()); the sequential algorithms, which take none, are unchanged, and an algorithm called with one thread, or on a small input, is the sequential one. The executors are Sequential, ThreadPool, the pool of ADS on std::thread (a deque of work stealing of Chase and Lev per thread, the idle threads asleep on an event count after 2 ms), and, as options, OpenMPExecutor, TBBExecutor and FastFlowExecutor, which run the same calls on the threads of OpenMP, oneTBB and FastFlow, so that a program that already has one of these runtimes (e.g., SMS++, which depends on FastFlow) does not start a second one. On them parallel/Executor.h builds the loops, the reductions (whose blocks do not depend on the threads, so that a sum of doubles is the same on every executor) and the prefix sums in one pass over the memory (the decoupled look-back of Merrill and Garland), and the other headers of parallel/ the algorithms below, each with the results of its sequential version (bit for bit for the products of matrices, up to the rounding for the transform).

What	Header
executors: the pool of ADS, OpenMP, oneTBB, FastFlow	`parallel/ThreadPool.h`, `parallel/OpenMPExecutor.h`, `parallel/TBBExecutor.h`, `parallel/FastFlowExecutor.h`
parallel loops, reductions and prefix sums, fork and join	`parallel/Executor.h`
`sort()` and `stableSort()` by distribution (radix classifier for the numbers, tree of splitters with buckets of equality for the rest)	`parallel/ParallelSort.h`
`multiwayMerge()` by exact multisequence selection	`parallel/ParallelMerge.h`
products of `CsrMatrix`, `SellMatrix` and `gemm()`	`parallel/ParallelNumeric.h`
`fft()` by the four steps of Bailey	`parallel/ParallelFFT.h`
visit in breadth that optimizes its direction, connected components by Afforest	`parallel/ParallelGraph.h`
LCP array by the permuted LCP	`parallel/ParallelText.h`
union-find with no lock, for many threads	`concurrent/ConcurrentUnionFind.h`
sort over the processes of MPI by regular sampling	`distributed/DistributedSort.h`

#include "ADS/parallel/ParallelSort.h"
#include "ADS/parallel/ThreadPool.h"

ADS::ThreadPool pool( 8 );               // 8 threads, the caller included
ADS::sort( pool , A );                   // the result of ADS::sort( A )

The pool needs nothing but the threads of the standard library (with CMake, ADS::ADS links them). The other executors are compiled only when asked for: with CMake, -DADS_WITH_OPENMP=ON, -DADS_WITH_TBB=ON and -DADS_WITH_FASTFLOW=ON (all off by default) link OpenMP and oneTBB and take the headers of FastFlow from FASTFLOW_DIR or, if it is not given, from its repository, as SMS++ does; without CMake, -fopenmp, -DADS_WITH_TBB -ltbb and -DADS_WITH_FASTFLOW -I<fastflow>. The header of FastFlow defines NO_DEFAULT_MAPPING (unless ADS_FASTFLOW_MAPPING is defined), since FastFlow otherwise pins its threads to the first cores of the machine whatever the affinity of the process. The sort over the processes of MPI, ADS::distributed::sort(), is a layer of its own, on -DADS_WITH_MPI=ON (Open MPI or MPICH found by CMake), tested on 1 to 4 processes by ctest or by make test-mpi.

The benchmark of the parallel algorithms, bench/parallel.cpp, runs each of them on 1, 2, 4 and 8 threads. The competitors are the parallel versions of oneTBB, of std::execution (libstdc++ on oneTBB), of the parallel mode of libstdc++, of OpenMP, of ParlayLib, of IPS4o and IPS2Ra, of FastFlow (its ParallelFor, ParallelForReduce and ff_DC), of tlx, of Eigen and OpenBLAS, of FFTW and of the GAP benchmark suite; for the hash tables, the concurrent tables of oneTBB, libcuckoo and ParlayLib. Each structure runs in a process of its own, since the threads that a runtime keeps spinning between its calls would slow down the next structure. The benchmark was run twice on 8 cores of the Xeon Gold 5120 of the table above, with 5 runs per cell, while other programs ran on the remaining cores. Their use of the memory and of the third level of the cache was not under control, and the same code measured twice differs by 1.7% in the median cell and by 8.3% at the 90th percentile. The ratios below are those of 8 threads, the time of the library divided by that of the pool of ADS (the median, and the range over the cells in parentheses). The sorts of ADS are faster than IPS4o and IPS2Ra by 1.5 to 1.8 times in the median (0.8 to 15). They are faster than ParlayLib by 2.3 to 2.8 times, and than tbb::parallel_sort and std::sort on std::execution::par by 6 to 7 times. They lose on few cells: 16 sorted runs of \(10^6\) integers, which the integer sort of ParlayLib sorts 1.3 times faster, few distinct strings and vectors already sorted, on which IPS4o is up to 1.3 times faster. On 2 threads the distribution costs more than the second thread saves (0.8 times the speed of the sequential sort in the median), and the sorts run the sequential one there. The parallel multiwayMerge() is 1.7 times faster than those of libstdc++ and tlx, and 7.4 times faster than its sequential version; gemm() is 1.2 times faster than Eigen on OpenMP and 7.3 times faster than on one thread. The connected components are 2.3 times faster than Afforest of the GAP benchmark suite, and the prefix sums 1.3 to 1.6 times faster than those of OpenMP, ParlayLib and oneTBB, since they read the input once. It is fair to remark, however, that FFTW with its threads is faster than the parallel fft() (by 8% on 8 threads, and by 1.4 to 1.6 times on 2 and 4, where the three transpositions of the four steps cost more than they save). Also, the visit in breadth of the GAP benchmark suite, which follows the same algorithm, is 4% faster than bfsDistances(), and the product of sparse matrices by rows of oneTBB is 7% faster than that of CsrMatrix. The tables of libcuckoo and ParlayLib (the latter open addressing on keys alone) find keys 2 and 5 times faster than ConcurrentCuckooTable on 8 threads, since its lookups do not scale as well; it inserts them 1.4 times faster than libcuckoo, in a single run of \(10^6\) and \(4 \cdot 10^6\) keys. The same algorithms on the executors of OpenMP and oneTBB run within a few percent of the pool. On the executor of FastFlow they are 4% to 70% slower on 8 threads, and up to twice as slow on 2, since its caller waits without working while its idle workers spin.

License

This software is released under the GNU Lesser General Public License version 3.0 (see the file LICENSE). The book is by Alberto Montresor, under CC BY-NC 4.0.