Appendix C. Working with other libraries¶
[Source: include/ADS/interop/, include/ADS/parallel/TBBExecutor.h,
include/ADS/parallel/OpenMPExecutor.h, include/ADS/distributed/,
include/ADS/set/RoaringBitmap.h, test/interop_examples.cpp,
test/interop_examples_mpi.cpp, test/interop_graphs.cpp,
test/interop_columnar.cpp, python/]
We are concerned in this appendix with a program that already uses another
library and wants to call ADS from it, or to run that library on the
structures of ADS. The adapters and their design are described in
§1.8.1, §14.14,
chapter 25 and chapter
26; here we show them at work, one section per
library, by short examples that one can copy into a function of a program.
For each example we give the line of the program that changes (usually one
type), what the change costs, and the option of the build that compiles it
in. By the latter we mean the option of CMake, the component of
find_package(ADS COMPONENTS ...) that gives its target, and the variable
of the makefile.
An example whose first line is a comment // with <library> needs that
library, and it is compiled only where the library is found, whereas the
others need only the standard library. Every example is also a test,
interop_examples.<name> (or interop_examples_mpi.<name> for MPI, run on
one to four processes), whose source holds the code of the example as it is
printed here, with the checks of its result between its lines. The checker
of this manual (declcheck.py, run by make check) compiles each example
against the headers, and it also verifies that the code of the example is
still in the test. Hence a change of an interface that breaks an example
stops both the build of the manual and that of the tests.
C.1 The standard library¶
Since the containers of ADS have the interface of those of the standard
library (§1.8), the adapters of
ADS/interop/std/ only add what a container adaptor or an allocator of the
standard library requires of its argument; they need no option, as they
include no other library. In the first example a
std::flat_map of C++23 keeps its keys and its values in two
TieredVectors of chapter 2, by the alias
TieredFlatMap of FlatMap.h, and the line that changes is the type of
the map.
// with C++23
#include "ADS/interop/std/FlatMap.h"
ADS::TieredFlatMap< std::string , int > m; // was std::flat_map< ... >
m[ "pear" ] = 3;
m[ "apple" ] = 5;
m.erase( "pear" );
A key is still found by the binary search of a flat map, but each access to
a key goes through the index of its tier. A lookup may therefore
be somewhat slower than on a std::vector (we have not measured it),
whereas an insertion or an erasure moves \(O( \sqrt{n} )\) keys instead of
\(O( n )\). Of course, the alias exists only where the standard library has
<flat_map> (e.g., GCC 15), and the test is compiled as C++23 where the
compiler takes it.
Also, the algorithms of std::ranges take the dictionaries and the search
trees of ADS as they are, since their iterators model the concepts of
C++20, even those that build their item on the fly
(§1.8); the second example counts and
searches the pairs of a BTreeMap of chapter 8.
#include "ADS/tree/BTreeMap.h"
ADS::BTreeMap< int , int > b;
for( int k = 0 ; k < 100 ; ++k )
b.insert( k , ( k * 37 ) % 101 );
const auto even = std::ranges::count_if(
b , []( const auto & x ) { return( x.first % 2 == 0 ); } );
const auto top = std::ranges::max_element(
b , {} , []( const auto & x ) { return( x.second ); } );
// even is 50, and ( *top ).first is 30, whose value is 100
Note that *top is a pair built by the iterator, not a reference into the
tree; this is why the example reads ( *top ).first instead of
top->first, and also why a copy of the pairs (e.g., by
std::ranges::to< std::vector >() of C++23) holds values. In the third
example we put three adapters together: (i) the sorts of chapter
12 on a std::deque and on a part of a vector, through
its std::span; (ii) the pool of chapter 5 under a
std::pmr::map, by PmrResource; (iii) a std::priority_queue as the
frontier of the shortest paths of §14.8, by
PriorityFrontier.
#include "ADS/graph/ShortestPaths.h"
#include "ADS/graph/StaticGraph.h"
#include "ADS/interop/std/Pmr.h"
#include "ADS/sort/Sort.h"
#include <deque>
#include <memory_resource>
#include <queue>
std::deque< int > d = { 5 , 3 , 9 , 1 , 7 };
ADS::sort( d ); // 1 3 5 7 9
std::vector< int > v = { 9 , 8 , 7 , 6 , 5 , 4 };
ADS::sort( std::span< int >( v ).subspan( 2 , 3 ) ); // 9 8 5 6 7 4
ADS::PoolResource<> pool;
ADS::PmrResource<> mr( pool ); // a std::pmr::memory_resource
std::pmr::map< int , int > m( &mr ); // its nodes in the pool
for( int k = 0 ; k < 1000 ; ++k )
m[ k ] = k * k;
const ADS::StaticGraph< double > g( 4 , { { 0 , 1 , 2. } , { 1 , 2 , 1. } ,
{ 0 , 2 , 4. } , { 2 , 3 , 1. } } );
using P = std::pair< double , int >;
std::priority_queue< P , std::vector< P > , std::greater< P > > q;
ADS::PriorityFrontier S( q , g.n() ); // lazy: no decrease-key
const auto T = ADS::shortestPaths( g , 0 , S ); // T.d is { 0 , 2 , 3 , 4 }
The sort of the deque runs in place on its random-access iterators, while
PmrResource costs one virtual call per allocation, which is the price of
std::pmr (the pool is as in chapter 5). Since
std::priority_queue cannot lower a key, the frontier on it is lazy: a node
whose distance falls is pushed again, and its stale copies are skipped when
they reach the top. Hence the queue may hold up to \(m\) pairs instead of \(n\);
the heaps of ADS, and those of Boost.Heap in §C.3,
lower their keys in place.
C.2 Boost.Graph¶
We compile the adapters of Boost with ADS_WITH_BOOST. CMake turns it on
when it finds the headers of Boost 1.83 or later (-DADS_WITH_BOOST=ON
requires them, OFF leaves them out), the component Boost of
find_package(ADS COMPONENTS Boost) carries it, and the makefile defines it
by default (BOOST=<prefix> where Boost is not where the compiler looks);
no library is linked, since Boost is used by its headers. With Graph.h, a
StaticGraph of either layout of its arcs is a graph of Boost.Graph with no
copy, and a program of
Boost.Graph changes only the type of its graph (e.g., from
compressed_sparse_row_graph to ADS::StaticGraph), as in the first
example, which runs the algorithm of Dijkstra of Boost.Graph on such a
graph.
// with Boost
#include "ADS/graph/StaticGraph.h"
#include "ADS/interop/boost/Graph.h"
#include <boost/graph/dijkstra_shortest_paths.hpp>
const ADS::StaticGraph< double > g( 4 , { { 0 , 1 , 2. } , { 1 , 2 , 1. } ,
{ 0 , 2 , 4. } , { 2 , 3 , 1. } } );
std::vector< double > d( num_vertices( g ) );
std::vector< int > p( num_vertices( g ) );
boost::dijkstra_shortest_paths(
g , 0 , boost::weight_map( get( boost::edge_weight , g ) )
.distance_map( d.data() )
.predecessor_map( p.data() ) ); // d is { 0 , 2 , 3 , 4 }
A scan of the out-arcs is the scan of a row of the graph, and a weight is read
where it lies, in the array of the weights at the place of its arc. Thus the
algorithm reads the same memory as on compressed_sparse_row_graph, which
also keeps the properties of the edges apart from the heads, and the edge descriptor (the pair of its
tail and of its place in the rows) is also its edge_index. ArrayGraph is
adapted in the same way, whereas ListGraph and an ObservedGraph on it are
mutable graphs of Boost.Graph, whose weight is looked up in \(O( \deg u )\) time
(§1.8.1).
In the other direction, FromBGL of FromBGL.h is a view of a graph of
Boost.Graph as a graph of ADS, its weights read from a property map, by
which the second example runs the algorithm of Johnson of
§14.8 on a boost::adjacency_list. Then
dijkstraShortestPaths() of Dijkstra.h runs the algorithm of Dijkstra of
Boost.Graph on a heap of ADS, which boost::dijkstra_shortest_paths() does
not let the caller choose.
// with Boost
#include "ADS/graph/ShortestPaths.h"
#include "ADS/interop/boost/Dijkstra.h"
#include "ADS/interop/boost/FromBGL.h"
#include "ADS/priority/IndexedDaryHeap.h"
#include <boost/graph/adjacency_list.hpp>
using AL =
boost::adjacency_list< boost::vecS , boost::vecS , boost::directedS ,
boost::no_property ,
boost::property< boost::edge_weight_t , double > >;
AL al( 4 );
add_edge( 0 , 1 , 2. , al );
add_edge( 1 , 2 , 1. , al );
add_edge( 0 , 2 , 4. , al );
add_edge( 2 , 3 , 1. , al );
const auto w = get( boost::edge_weight , al );
const ADS::bgl::FromBGL< AL , decltype( w ) > g( al , w ); // no copy
const auto T = ADS::johnson( g , 0 ); // T.d is { 0 , 2 , 3 , 4 }
std::vector< double > d( 4 );
std::vector< int > p( 4 );
ADS::IndexedDaryHeap< double , 4 > q( 4 ); // was the 4-ary heap of Boost
ADS::bgl::dijkstraShortestPaths( al , 0 , q , p.data() , d.data() );
This view keeps one mark per vertex, and it reads the out-edges and the
weights through the traits of Boost.Graph, i.e., at the cost of the
iterators of the graph of Boost. On an adjacency_list on vecS it is
also a dynamic graph; hence an ObservedGraph on it changes the graph of
Boost while it sends its events to the observers. In
dijkstraShortestPaths() the queue may be any queue of the frontier of
§14.8, std::priority_queue and the heaps of
Boost.Heap included, and the line that changes is the declaration of the
queue.
C.3 Boost.Heap and Boost.Unordered¶
Like those of §C.2, these adapters need
ADS_WITH_BOOST. Heap.h gives the mutable
heaps of Boost.Heap the free queue_decrease() of
§1.14, by which the shortest paths and the
algorithm of Prim of ADS lower a key on the handle of Boost; the line that
changes is again the declaration of the queue. Conversely,
Boost.Unordered takes a hash function of ADS as its hasher, and FastHash of
chapter 7 declares is_avalanching, the
convention by which boost::unordered_flat_map skips the mixing that it
would otherwise apply to the hash.
// with Boost
#include "ADS/dictionary/FastHash.h"
#include "ADS/graph/ShortestPaths.h"
#include "ADS/graph/StaticGraph.h"
#include "ADS/interop/boost/Heap.h"
#include <boost/heap/fibonacci_heap.hpp>
#include <boost/unordered/unordered_flat_map.hpp>
const ADS::StaticGraph< double > g( 4 , { { 0 , 1 , 2. } , { 1 , 2 , 1. } ,
{ 0 , 2 , 4. } , { 2 , 3 , 1. } } );
using P = std::pair< double , int >;
using H = boost::heap::fibonacci_heap<
P , boost::heap::compare< std::greater< P > > >;
H h;
ADS::PriorityFrontier S( h , g.n() ); // native decrease-key
const auto T = ADS::shortestPaths( g , 0 , S ); // T.d is { 0 , 2 , 3 , 4 }
boost::unordered_flat_map< std::string , int , ADS::FastHash< std::string > >
m; // the hash of ADS, avalanching: no mixing by Boost
m[ "pear" ] = 3;
m[ "apple" ] = 5;
Since a heap of Boost keeps on top the largest item in the order of its
comparator, queue_decrease() calls increase(), which
with std::greater moves an item whose distance falls toward the top. A
heap of Boost.Heap that is not mutable (e.g., d_ary_heap without
mutable_< true >) is taken as well, but lazily, as std::priority_queue
in §C.1.
The other way round requires no change of the program: with
ADS_WITH_BOOST,
FlatHashTable keeps its items in a boost::unordered_flat_map,
PointerTable in a boost::unordered_flat_set and SmallVector in a
boost::container::small_vector, and the generators xoshiro256 run on
Boost.Random (§7.6), while their interface is
that of ADS. Defining ADS_FLATHASH_BOOST (or one of the other three
macros of §7.6) to 0 keeps the code of ADS for
one structure.
C.4 LEMON¶
We compile the headers of ADS/interop/lemon/ with ADS_WITH_LEMON,
which the target ADS::LEMON of CMake defines (the component LEMON of
find_package(ADS COMPONENTS LEMON)). The option is AUTO, i.e., it is on
where abLEMON, or another LEMON whose headers compile in C++20, is found
(LEMON_ROOT where it is not), and the makefile puts the flags of LEMON in
$(ADSLEMONINC) (LEMON=<prefix>). Unlike the backends of
§C.2, LEMON is never included by ADS::ADS, and
thus a program that does not link ADS::LEMON compiles none of it. A
program written on LEMON takes a heap of ADS by the named template
parameters of an algorithm, i.e., by one type. In the first example the
Dijkstra of LEMON runs on the DaryHeap of Heaps.h, and the shortest
paths of ADS then run on the same digraph through GraphView of
Digraphs.h.
// with LEMON
#include "ADS/graph/ShortestPaths.h"
#include "ADS/interop/lemon/Digraphs.h"
#include "ADS/interop/lemon/Heaps.h"
#include <lemon/dijkstra.h>
#include <lemon/list_graph.h>
using GR = lemon::ListDigraph;
GR g;
GR::ArcMap< int > l( g );
const GR::Node s = g.addNode() , a = g.addNode() , t = g.addNode();
l.set( g.addArc( s , a ) , 2 );
l.set( g.addArc( a , t ) , 1 );
l.set( g.addArc( s , t ) , 4 );
using H = ADS::lemon_interop::DaryHeap< int , GR::NodeMap< int > >;
lemon::Dijkstra< GR , GR::ArcMap< int > >::SetStandardHeap< H >::Create d(
g , l );
d.run( s ); // d.dist( t ) is 3
const ADS::lemon_interop::GraphView< GR , GR::ArcMap< int > > view( g , l );
const auto T = ADS::johnson( view , g.id( s ) ); // T.d[ g.id( t ) ] is 3
Each operation of DaryHeap makes one read of the cross-reference map of LEMON
more than the IndexedDaryHeap under it, i.e., one dependent load more than
the BinHeap of LEMON, which may or may not be visible (we have not measured
it). In exchange, with the policy Dynamic<> its observers receive every
change that the algorithm makes on its frontier
(§14.14.1). On the other hand, GraphView makes no
copy, since its nodes are named by the ids of LEMON; where an algorithm runs
often on the same digraph, toStatic() copies it into a StaticGraph once, in
\(\Theta( n + m )\) time.
Conversely, StaticDigraphView is a digraph of LEMON over a
StaticGraph, on which the second example runs the Preflow of LEMON.
Then a LemonTap of Observers.h passes the insertions and the erasures
of the arcs of a ListDigraph to an observer of ADS.
// with LEMON
#include "ADS/graph/StaticGraph.h"
#include "ADS/interop/lemon/Digraphs.h"
#include "ADS/interop/lemon/Observers.h"
#include <lemon/list_graph.h>
#include <lemon/preflow.h>
using V = ADS::lemon_interop::StaticDigraphView< long long >;
const ADS::StaticGraph< long long > g(
4 , { { 0 , 1 , 3 } , { 0 , 2 , 2 } , { 1 , 3 , 2 } , { 2 , 3 , 3 } } );
const V lg( g ); // no copy of the rows
const auto c = lg.weights();
lemon::Preflow< V , V::WeightMap > pf( lg , c , lg.nodeFromId( 0 ) ,
lg.nodeFromId( 3 ) );
pf.run(); // pf.flowValue() is 4
using GR = lemon::ListDigraph;
using Tap = ADS::lemon_interop::LemonTap< GR , GR::Arc >;
struct Count
{
int live = 0; ///< the arcs in the digraph
void on( const Tap::Insert & ) { ++live; }
void on( const Tap::Erase & ) noexcept { --live; }
};
GR h;
Tap tap( h );
Count k;
tap.attach( k );
const GR::Node u = h.addNode() , v = h.addNode();
const GR::Arc a = h.addArc( u , v );
h.addArc( v , u );
h.erase( a ); // k.live is 1
This view uses the rows of the StaticGraph and reads the capacities where
they lie, but it builds once the tails and the lists of the arcs into each
node, which Preflow needs and the rows lack, in \(8 a + 4 n\) bytes for
\(a\) arcs. As to the tap, it is an observer of the notifier of LEMON, and
it adds to
each insertion and erasure of an arc the calls of the observers attached to
it. Note that it does not see the changes that the notifier does not notify
(e.g., changeTarget()), which §14.14.2 lists,
while the opposite direction, a ListDigraph kept in step with an
ObservedGraph of ADS, is LemonMirror. Finally, the warm starts that ADS
writes into private copies of six headers of LEMON are described in
§14.14.4; they need the rewritten headers first
on the include path, as ADS::LEMON and $(ADSLEMONINC) arrange.
C.5 GMP¶
BigInteger and Rational of chapter 17 run on GMP
wherever it is found, by the macro ADS_WITH_GMP, AUTO with CMake (the
component GMP) and on by default with the makefile (GMP=<prefix>). With
it, the constructors from mpz_class and mpq_class, fromGmp() and
toGmp() pass a number to and from GMP without writing it as a string.
Thus a program on GMP can call an algorithm of ADS on its integers (e.g.,
one of the number theory of chapter 17) and take the
result back; the line that changes is the declaration of the number.
// with GMP
#include "ADS/numeric/BigInteger.h"
#include <gmpxx.h>
const mpz_class m( "-98765432109876543210987654321" );
const ADS::BigInteger x( m ); // no string between
const mpz_class y = ( x * x ).toGmp< mpz_class >(); // the same, in GMP
A conversion copies the limbs of the number, in time linear in its length,
which is usually small against an operation on the same numbers, and the
interface of C (mpz_t, mpq_t) is taken as well, by toGmp( z ) and
fromGmp( z ). Without GMP the constructors from its types are not
declared, and the numbers run on the algorithms of the book.
C.6 BLAS¶
gemm() of DenseMatrix.h (chapter 17) is a call
of cblas_dgemm() or cblas_sgemm() for double and float wherever a
CBLAS is found (OpenBLAS, the reference CBLAS, or Accelerate on macOS), by
the macro ADS_WITH_BLAS, AUTO with CMake (the component BLAS) and on by
default with the makefile (BLAS=<prefix>). Since a DenseMatrix keeps
its entries by rows in one contiguous vector, whose leading dimension is
the number of its columns, a program can also call any routine of BLAS or
LAPACK on its data(), as the example does before it computes the same
product by multiply().
// with BLAS
#include "ADS/numeric/DenseMatrix.h"
#include <cblas.h>
ADS::DenseMatrix< double > A( 2 , 3 , 1. ) , B( 3 , 2 , 2. ) , C( 2 , 2 );
cblas_dgemm( CblasRowMajor , CblasNoTrans , CblasNoTrans , 2 , 2 , 3 , 1. ,
A.data() , 3 , B.data() , 2 , 0. , C.data() , 2 );
const auto D = ADS::multiply( A , B ); // on cblas_dgemm() too
A CBLAS runs on the threads it is built or set for (e.g., those of
OPENBLAS_NUM_THREADS), and hence the parallel gemm( ex , ... ) of chapter
25 makes one call from the calling thread, instead
of dividing the rows among the threads of the executor. We remark that the
result of the CBLAS may differ from that of the loops of ADS in the last
bits, since the two add the terms in different orders; the bound of the
error is the same (cf. chapter 17).
C.7 oneTBB¶
Since the parallel algorithms of ADS take an executor as their first argument
(chapter 25), for a program that already runs on a
runtime the line that changes is the declaration of the executor (e.g.,
ADS::ThreadPool ex( 4 ) becomes ADS::TBBExecutor ex( arena )), so that ADS
does not start a pool beside the threads of the program. TBBExecutor is
compiled with ADS_WITH_TBB, which CMake defines with -DADS_WITH_TBB=ON (off
by default, since ADS::ADS then links oneTBB) and the makefile with
ADS_WITH_TBB=1. In the example we sort in an arena of the program, and then
call a concurrent structure of chapter 24 from a loop
of oneTBB, which needs no adapter.
// with oneTBB
#include "ADS/concurrent/ConcurrentUnionFind.h"
#include "ADS/parallel/ParallelSort.h"
#include "ADS/parallel/TBBExecutor.h"
#include <tbb/parallel_for.h>
#include <tbb/task_arena.h>
std::vector< double > A( 1000000 );
std::mt19937 r( 1 );
for( double & x : A )
x = double( r() % 1000003 );
tbb::task_arena arena( 4 ); // the arena of the program
ADS::TBBExecutor ex( arena );
ADS::sort( ex , A ); // on the threads of the arena
ADS::ConcurrentUnionFind uf( 1000 );
tbb::parallel_for( 0 , 999 , [ & ]( int i ) {
if( i % 2 == 0 )
( void )uf.unite( i , i + 1 );
} ); // the sets { 0 , 1 } , { 2 , 3 } , ...
Each call of the executor is a task of the arena; thus the constraints of
the arena (its threads, its NUMA node, its type of core) hold for ADS too,
and the calls nest as the tasks of oneTBB do. The executor adds
rather little to the cost of tbb::parallel_for, on which it runs. Also,
TBBExecutor ex( ADS::TBBExecutor::current ) runs on the arena of each
caller, whichever it is.
C.8 OpenMP¶
OpenMPExecutor is compiled where the compiler runs OpenMP, i.e., with
-fopenmp (-DADS_WITH_OPENMP=ON with CMake, off by default, and
ADS_WITH_OPENMP=1 with the makefile). Called inside a region omp
parallel of the program, it makes its calls the tasks of a taskloop of
the team that is there, where a nested region would usually get one
thread (this needs OpenMP 4.5). The line that changes is again the
declaration of the executor, inside the region.
// with OpenMP
#include "ADS/parallel/OpenMPExecutor.h"
#include "ADS/parallel/ParallelSort.h"
std::vector< double > A( 1000000 );
std::mt19937 r( 1 );
for( double & x : A )
x = double( r() % 1000003 );
#pragma omp parallel num_threads( 4 )
#pragma omp single
{
ADS::OpenMPExecutor ex; // the team of the region
ADS::sort( ex , A ); // by the tasks of the team
}
Outside a region, the executor opens a region at each call, of
omp_get_max_threads() threads unless it is built with a number, and the
concurrent structures of ADS are called from a taskloop or a parallel
for of the program as from the loop of oneTBB in
§C.7. Note also that an exception thrown by a
call is caught within the region and thrown again by bulk() after it,
since OpenMP does not let it leave a task.
C.9 std::execution¶
StdParExecutor< Policy > of interop/parallel/StdParExecutor.h runs the
calls of the executor by std::for_each of the policy on their indices
(std::execution::par by default). They run, therefore, on the threads of
the parallel algorithms of the standard library, which are those of oneTBB
with libstdc++. We compile it with ADS_WITH_STDPAR, defined by the target
ADS::StdPar of CMake (the component StdPar, the option being AUTO)
and by the makefile in $(ADSINTEROPINC).
// with std::execution
#include "ADS/interop/parallel/StdParExecutor.h"
#include "ADS/parallel/ParallelSort.h"
std::vector< double > A( 1000000 );
std::mt19937 r( 1 );
for( double & x : A )
x = double( r() % 1000003 );
ADS::StdParExecutor<> ex( 4 ); // std::execution::par
ADS::sort( ex , A );
Note that the number given to the executor is the concurrency that it
reports to the
algorithms of ADS, by which they cut their work into blocks; it does not
bound the threads of the standard library, which chooses them. Since
std::sort( std::execution::par , ... ) gives no control on the threads
either, the executor is a way to run the algorithms of ADS on the same
threads as the parallel algorithms of the program.
C.10 stdexec¶
SenderExecutor< Sch > of interop/parallel/SenderExecutor.h runs the
calls of the executor on a scheduler of the senders of stdexec (the
std::execution of C++26), by bulk and sync_wait. It is compiled with
ADS_WITH_STDEXEC, defined by the target ADS::stdexec (the component
stdexec, with STDEXEC_INCLUDE_DIR the directory of its headers) and by
the makefile in $(ADSINTEROPINC) (STDEXEC_ROOT=<dir>). In the example
we run the sort and a reduction of chapter 25 on the
static pool of stdexec.
// with stdexec
#include "ADS/interop/parallel/SenderExecutor.h"
#include "ADS/parallel/Executor.h"
#include "ADS/parallel/ParallelSort.h"
#include <exec/static_thread_pool.hpp>
std::vector< double > A( 1000000 );
std::mt19937 r( 1 );
for( double & x : A )
x = double( r() % 1000003 );
exec::static_thread_pool pool( 4 ); // the pool of the program
ADS::SenderExecutor ex( pool.get_scheduler() , 4 );
ADS::sort( ex , A );
const double s = ADS::parallelReduce(
ex , 0 , A.size() , 0.0 ,
[ & ]( std::size_t lo , std::size_t hi ) {
double t = 0;
for( std::size_t i = lo ; i < hi ; ++i )
t += A[ i ];
return( t );
} ,
std::plus<>() );
A sync_wait() holds the thread that waits, and therefore a call of
bulk() made inside a call of this executor runs in order on its thread.
Hence the fork and join of ADS (the recursion of parallelInvoke(), the
lower levels of the sorts) loses its nested parallelism here, whereas the
loops, the reductions and the top level of the sorts keep theirs. Also, the
number given with the scheduler is its concurrency, which a scheduler of
the senders does not report.
C.11 Taskflow¶
TaskflowExecutor of interop/parallel/TaskflowExecutor.h runs the calls
on the workers of a tf::Executor of the program, and it is compiled with
ADS_WITH_TASKFLOW, defined by the target ADS::Taskflow (the component
Taskflow, with Taskflow_INCLUDE_DIR the directory of its headers) and
by the makefile in $(ADSINTEROPINC) (Taskflow_ROOT=<dir>).
// with Taskflow
#include "ADS/interop/parallel/TaskflowExecutor.h"
#include "ADS/parallel/ParallelSort.h"
std::vector< double > A( 1000000 );
std::mt19937 r( 1 );
for( double & x : A )
x = double( r() % 1000003 );
tf::Executor workers( 4 ); // the executor of the program
ADS::TaskflowExecutor ex( workers );
ADS::sort( ex , A );
Unlike the executor on the senders, this one nests, since a nested call co-runs its graph on the worker that waits; its price is a graph of Taskflow built at each call, which is rather small against a sort of a million items but possibly not against a loop of a few cheap iterations.
C.12 Kokkos¶
KokkosExecutor< Space > of interop/parallel/KokkosExecutor.h runs the
calls on a space of the host of Kokkos, by default
Kokkos::DefaultHostExecutionSpace, through Kokkos::parallel_for and
fence(). We compile it with ADS_WITH_KOKKOS, defined by the target
ADS::Kokkos (the component Kokkos), which takes the flags of Kokkos from
its package of CMake (found by CMAKE_PREFIX_PATH), whereas the makefile
does not take Kokkos, whose flags depend on how it was built. A program
starts Kokkos as it does for its kernels, here by a Kokkos::ScopeGuard.
// with Kokkos
#include "ADS/interop/parallel/KokkosExecutor.h"
#include "ADS/parallel/ParallelSort.h"
std::vector< double > A( 1000000 );
std::mt19937 r( 1 );
for( double & x : A )
x = double( r() % 1000003 );
Kokkos::ScopeGuard guard; // Kokkos started, as by the program
ADS::KokkosExecutor<> ex; // on Kokkos::DefaultHostExecutionSpace
ADS::sort( ex , A );
As on the senders, a dispatch of Kokkos holds the thread that waits, and
the calls made inside a call, or inside a kernel of the program, run in
order on their thread; a kernel of the program is recognized on the backend
of OpenMP by its parallel region (omp_get_level(), since the
in_parallel() of the spaces is deprecated in Kokkos 4 and removed in
Kokkos 5), while on the other backends its nested calls run in order only
when the space has one thread. We run the test of this example in the
continuous integration, on a Kokkos built on its backend of OpenMP.
C.13 MPI¶
The sort over the processes of chapter 26, and
the executor and the mailbox of the processes, take the communicator of
the program, and they are compiled with ADS_WITH_MPI, which is off by default
(AUTO or ON with CMake, ADS_WITH_MPI=auto or 1 with the makefile),
since ADS::ADS then carries MPI to every program that links it. A
program starts MPI (by itself, or by MPIEnvironment at the funneled level
that the mailbox needs), and the line that changes is the communicator
given to ADS, e.g., one of the program instead of MPI_COMM_WORLD.
// with MPI
#include "ADS/distributed/DistributedSort.h"
#include "ADS/distributed/MPIExecutor.h"
#include "ADS/parallel/ThreadPool.h"
MPI_Comm comm; // a communicator of the program
MPI_Comm_dup( MPI_COMM_WORLD , &comm );
const ADS::MPIExecutor ex( comm );
std::vector< int > A( 1000 );
std::mt19937 r( static_cast< unsigned >( ex.rank() ) );
for( int & x : A )
x = int( r() % 100000 );
ADS::ThreadPool pool( 2 ); // the threads of each process
ADS::distributed::sort( pool , comm , A );
A program of Boost.MPI needs no adapter for this, since a
boost::mpi::communicator converts to MPI_Comm. In turn, BoostMPI.h
is compiled with ADS_WITH_BOOST_MPI (the target ADS::BoostMPI, the
component BoostMPI, which links Boost.MPI and Boost.Serialization). It
adds BoostMPICodec, by which a message that the program already
serializes by Boost.Serialization goes through the mailbox of chapter
26, by one specialization of MPICodec.
// with Boost.MPI
#include "ADS/distributed/BoostMPI.h"
#include "ADS/distributed/DistributedSort.h"
#include "ADS/parallel/ThreadPool.h"
#include <boost/mpi/communicator.hpp>
#include <boost/mpi/environment.hpp>
boost::mpi::environment env( boost::mpi::threading::funneled );
boost::mpi::communicator world;
std::vector< int > A( 1000 );
std::mt19937 r( static_cast< unsigned >( world.rank() ) );
for( int & x : A )
x = int( r() % 100000 );
ADS::ThreadPool pool( 2 );
ADS::distributed::sort( pool , world , A ); // world is an MPI_Comm
In both examples A is sorted at the end, and no item of the process \(r\)
exceeds one of the process \(r + 1\). The threads of each process sort its
part, and the messages between the processes are those of the regular
sampling of chapter 26, whichever library the
program used to start MPI. We run the two examples on one to four
processes in their tests, by mpiexec with CMake and by make test-mpi
with the makefile.
C.14 Eigen¶
A program that keeps its matrices in the structures of chapter
17 calls the solvers and the decompositions of Eigen
on them through interop/eigen/Eigen.h. We compile it with
ADS_WITH_EIGEN (AUTO, hint EIGEN3_INCLUDE_DIR), which the target and
the component Eigen define. In this header map( A ) of a DenseMatrix
is an Eigen::Map of a dense matrix by rows over the entries of \(A\), with
no copy. Also, map( A ) of a BasicCsrMatrix< T , I , I >, i.e., one
whose columns and offsets have the same signed type, is an Eigen::Map of
the row-major Eigen::SparseMatrix over its three arrays. However, the
default CsrMatrix has columns of 32 bits without sign and offsets
std::size_t, whereas Eigen takes one signed type for both (its
StorageIndex); hence toEigen() copies it, and fromEigen() copies a
sparse matrix of Eigen back into ADS. In the example we solve by the
conjugate gradient of Eigen a system whose matrix is a BasicCsrMatrix<
double , int >, read in place, and the line that changes is the type of
the matrix.
// with Eigen
#include "ADS/interop/eigen/Eigen.h"
#include "ADS/numeric/CsrMatrix.h"
#include <Eigen/IterativeLinearSolvers>
const ADS::BasicCsrMatrix< double , int > A(
3 , 3 , { { 0 , 0 , 4. } , { 0 , 1 , -1. } , { 1 , 0 , -1. } ,
{ 1 , 1 , 4. } , { 1 , 2 , -1. } , { 2 , 1 , -1. } ,
{ 2 , 2 , 4. } } );
const auto M = ADS::eigen::map( A ); // no copy of the rows
Eigen::ConjugateGradient< ADS::eigen::RowSparse< double > ,
Eigen::Lower | Eigen::Upper >
cg( M );
const Eigen::VectorXd x = cg.solve( Eigen::VectorXd::Ones( 3 ) );
const auto y = A.multiply( { x( 0 ) , x( 1 ) , x( 2 ) } ); // y is 1 1 1
const auto E = ADS::eigen::toEigen( ADS::CsrMatrix( 2 , 2 ) ); // a copy
The solver binds the map by a Ref of Eigen (cf. the documentation of
Eigen on the sparse solvers), which, as far as we can see, copies none of
the arrays of A. A copy by toEigen() costs \(\Theta( m + \mathit{nnz} )\)
time and the memory of a second matrix. A map holds the pointers of the
three vectors, and thus it must not outlive its matrix, nor see it change
its size.
C.15 METIS and KaHIP¶
ADS has no partitioner of graphs. METIS (Karypis and Kumar
1998) and KaHIP (Sanders and Schulz
2013) take as input the compressed rows
of a graph, xadj the offsets and adjncy the heads, with both arcs of an
edge. These are the rows of a StaticGraph of chapter
14, and hence partition( g , k ) of
interop/metis/Metis.h and of interop/kahip/KaHIP.h hands offsets() and
heads() to the library as they are. This requires that the index type of
the library be int (as the 32-bit idx_t of the METIS of the
distributions, and the kahip_idx of a KaHIP built without KAHIP_64BIT)
and that the graph have the separate layout; the weights of weightData()
are read in place too, if they are of that type. Otherwise CsrInput of
interop/Csr.h copies only the arrays that differ (e.g., the weights of a
StaticGraph< double >, or the heads and the weights of an interleaved
graph, which alternate in one array), and copied() gives them. The options
are ADS_WITH_METIS and ADS_WITH_KAHIP (AUTO, hints
METIS_INCLUDE_DIR, METIS_LIBRARY, KaHIP_INCLUDE_DIR and
KaHIP_LIBRARY). A partition is a Partition, i.e., the part of each node
and the weight of the edges cut; its order() numbers the nodes part by
part, and relabel() applies it.
// with METIS
#include "ADS/graph/StaticGraph.h"
#include "ADS/interop/metis/Metis.h"
std::vector< std::pair< int , int > > E; // a ring of 8 nodes
for( int u = 0 ; u < 8 ; ++u )
E.emplace_back( u , ( u + 1 ) % 8 );
const ADS::StaticGraph<> g( 8 , E , false );
const ADS::Partition P = ADS::metis::partition( g , 2 ); // rows in place
const ADS::StaticGraph<> h = g.relabel( P.order() ); // P.cut is 2
In the second example kaffpa() of KaHIP, in its mode ECO, bisects a
ring whose two light edges form the best cut. Since the weights are int
and the layout is the separate one, KaHIP reads the three arrays of the
graph in place.
// with KaHIP
#include "ADS/graph/StaticGraph.h"
#include "ADS/interop/kahip/KaHIP.h"
std::vector< std::tuple< int , int , int > > E; // a ring, two light edges
for( int u = 0 ; u < 8 ; ++u )
E.emplace_back( u , ( u + 1 ) % 8 , u % 4 == 3 ? 1 : 10 );
const ADS::StaticGraph< int > g( 8 , E , false );
ADS::kahip::Options o;
o.mode = ECO;
const ADS::Partition P = ADS::kahip::partition( g , 2 , o ); // P.cut is 2
Both libraries take their arrays as pointers to non-constant data, but
they write none of them (KaHIP builds a graph from them, and METIS reads
them with the numbering of C, which partition() sets); hence, the adapters
pass them by a const_cast. As both libraries require, the graph must be
unoriented and without loops, and its weights positive integers (a weight
of a floating type is truncated by the copy). A relabelling by order()
may then give the parallel algorithms of chapter
25 rows in which each part is contiguous, and the
processes of chapter 26 one block of
consecutive nodes each, although we have not measured what this gains.
C.16 SuiteSparse:GraphBLAS¶
GraphBLAS (Davis 2019) writes the
algorithms of graphs as products over semirings, which ADS does not have,
and interop/graphblas/GraphBLAS.h lets them run on the graphs and on the
matrices of ADS (ADS_WITH_GRAPHBLAS, AUTO, version 10 or later, hints
GraphBLAS_INCLUDE_DIR and GraphBLAS_LIBRARY). Since its version 10, a
GxB_Container holds the compressed rows of a matrix as vectors, and
GxB_Vector_load() with GxB_IS_READONLY makes a vector of an array that
its owner keeps (GraphBLAS reads it, and never writes nor frees it).
Hence, view( g ) of a StaticGraph of the separate layout (or, more
precisely, of any graph of the concept CsrArrays) is a GrB_Matrix over
offsets(), heads() and weightData(). If the graph is unweighted, the
matrix is iso-valued, i.e., all its entries are one value true. In the
same way view( A ) of a BasicCsrMatrix is the matrix of its three
arrays, whose integers GraphBLAS reads as GrB_UINT32 or GrB_UINT64 by
their size; therefore, the default CsrMatrix (offsets of 64 bits, columns
of 32) is read in place too. In the example we count the triangles of a
graph by \(\sum ( A \circ A^2 ) / 6\), the product being masked by the
graph.
// with GraphBLAS
#include "ADS/graph/StaticGraph.h"
#include "ADS/interop/graphblas/GraphBLAS.h"
GrB_init( GrB_NONBLOCKING ); // once, by the program
const ADS::StaticGraph<> g(
4 , { { 0 , 1 } , { 0 , 2 } , { 1 , 2 } , { 2 , 3 } } , false );
const ADS::graphblas::Matrix A = ADS::graphblas::view( g ); // no copy
GrB_Matrix C = nullptr;
GrB_Matrix_new( &C , GrB_INT64 , 4 , 4 );
GrB_mxm( C , A , nullptr , GrB_PLUS_TIMES_SEMIRING_INT64 , A , A ,
GrB_DESC_S ); // C = A .* A^2
std::int64_t t = 0;
GrB_Matrix_reduce_INT64( &t , nullptr , GrB_PLUS_MONOID_INT64 , C ,
nullptr );
GrB_Matrix_free( &C ); // t / 6 is 1 triangle
A view is a graphblas::Matrix, which frees the handle at its end and
leaves the arrays to ADS. The graph must outlive its view, and a view may be
an input of the operations of GraphBLAS but not their output (a call that
wrote it would have to copy the arrays first). An interleaved graph has no
view, and copy( g ) builds its matrix by GrB_Matrix_build() in
\(\Theta( n + a )\) time instead; conversely, toCsr() copies a matrix of
GraphBLAS into a BasicCsrMatrix by its triplets. We remark that the
header of GraphBLAS includes <complex.h>, whose macro I would rename
the template parameters of that name, and that the adapter undefines it.
C.17 NetworKit¶
NetworKit (Staudt, Sazonovs and Meyerhenke
2016) has many more algorithms of network
analysis than ADS. Some of them are dynamic, i.e., they keep a result (the
components, the distances from a source, a centrality) while the graph
changes, provided that the caller changes the graph and then passes each
change to them, by update() or by updateBatch() with one GraphEvent
per change. The header interop/networkit/NetworKit.h
(ADS_WITH_NETWORKIT, AUTO, version 11.2 or later, hints
NetworKit_INCLUDE_DIR, NetworKit_LIBRARY and tlx_INCLUDE_DIR) has two
parts. First, toNetworKit( g ) copies a graph of ADS, since the rows of
Graph::fromCSR() are of 64-bit indices and doubles. Furthermore,
NetworKitMirror is an observer of the ObservedGraph of
§14.13, which keeps a graph of NetworKit in step
with that of ADS and makes both steps for each change through the wrapper.
In the example the dynamic components of NetworKit follow the insertions
and the deletions of the edges of a ListGraph, the last two in one batch
of ADS.
// with NetworKit
#include "ADS/graph/ListGraph.h"
#include "ADS/graph/Observable.h"
#include "ADS/interop/networkit/NetworKit.h"
#include <networkit/components/DynConnectedComponents.hpp>
using G = ADS::ListGraph<>;
using M = ADS::networkit::NetworKitMirror< G >;
G g( 4 , false );
g.insertEdge( 0 , 1 );
M m( g ); // a copy of g
NetworKit::DynConnectedComponents cc( m.graph() );
cc.run(); // 3 components
m.attach( cc );
ADS::ObservedGraph< G , ADS::Static< M > > og( g , m );
og.insertEdge( 2 , 3 ); // cc.numberOfComponents() is 2
{
auto b = ADS::batch( og );
og.insertEdge( 1 , 2 );
og.deleteEdge( 0 , 1 );
} // one updateBatch(), 2 components
The events map one to one (EdgeInserted to EDGE_ADDITION, EdgeDeleted
to EDGE_REMOVAL, WeightChanged to EDGE_WEIGHT_UPDATE, and those of
the nodes to NODE_ADDITION, NODE_RESTORATION and NODE_REMOVAL). A
batch reaches each algorithm as one updateBatch(), with the net effect
per edge that ADS has already coalesced. We attach an algorithm with the
kinds of the events it takes (by default those of the edges, since most
dynamic algorithms of NetworKit reject the others), while the graph of
NetworKit receives them all. A change costs what NetworKit spends on it,
plus \(O( 1 )\), and the copy made by the constructor costs
\(\Theta( n + m )\) time.
C.18 Apache Arrow¶
Within a process, pyarrow, Polars, DuckDB, pandas and nanoarrow hand the
columns of Apache Arrow to one another by its C Data Interface, i.e., by two
structures of C, ArrowSchema (the type of a column) and ArrowArray (its
buffers), whose callback release frees what the producer keeps alive.
Since the specification freezes the two structures as an ABI,
ADS/interop/arrow/Arrow.h defines them, under the guard that the
specification prescribes, and it needs no option and no library. We export a
structure of ADS by exportArrow(), which fills them with a column whose
values are the memory of the structure, kept alive by a std::shared_ptr
until the consumer releases the array. Conversely, ArrowColumn< T > takes
a column of the consumer without copy and shows it as a
std::span< const T >. Such a span may be the input of a build of ADS
(e.g., of a WaveletMatrix or of an EliasFano, cf. chapter
22).
#include "ADS/interop/arrow/Arrow.h"
ADS::BitVector b( 1000 );
b.set( 7 );
ArrowArray a;
ArrowSchema s;
ADS::exportArrow( std::move( b ) , &a , &s , "flags" ); // no copy
a.release( &a ); // as the consumer does when done
s.release( &s );
std::vector< std::int64_t > v{ 3 , 1 , 4 };
ArrowArray c;
ArrowSchema t;
ADS::exportArrow( std::move( v ) , &c , &t );
ADS::ArrowColumn< std::int64_t > col( &c , t ); // taken back, no copy
t.release( &t );
A BitVector becomes a column of booleans with no copy, since Arrow numbers
the bit \(i\) as the bit \(i \bmod 8\) of the byte \(\lfloor i / 8 \rfloor\), which
is the layout of its words on a little-endian processor. A PackedArray of
8, 16 or 32 bits becomes a column of unsigned integers of that width, and a
contiguous sequence of numbers (a std::vector, a std::array, a
std::span) a column of their type. We copy the values only where
the layouts differ: for a PackedArray of 2 or 4 bits (decoded into
bytes), for a sequence that is not contiguous (e.g., a TieredVector), and
for the words of a BitVector or of a PackedArray on a big-endian
processor. In the other direction, toBitVector(), toPackedArray< B >()
and toVector< T >() copy a column into a structure of ADS, which then
holds the words, and they refuse a column with nulls, with children or of
another type by std::invalid_argument. Where nanoarrow is found, the test
interop_columnar.arrow-nanoarrow validates with it the columns that ADS
exports, and imports into ADS those that nanoarrow builds.
C.19 CRoaring¶
RoaringBitmap (chapter 10) writes and reads the
portable format of Roaring, by writePortable(), readPortable() and
portableSizeInBytes(). CRoaring, the implementations in Java, Go and Rust
and the systems built on them share this format, and thus a file written by
any of them is read by ADS, and the converse. Since ADS has no containers
of runs, it reads those of a file as arrays or bitmaps; the input is
checked field by field, and a truncated or corrupted one is refused with
PersistError.
On this format, ADS/interop/croaring/CRoaring.h passes a set to CRoaring
and back by toCRoaring() and fromCRoaring() (and by toRoaring() for a
roaring::Roaring), under the option ADS_WITH_CROARING, AUTO with
CMake (the component CRoaring).
// with CRoaring
#include "ADS/interop/croaring/CRoaring.h"
const std::uint32_t x[] = { 1 , 5 , 70000 };
const ADS::RoaringBitmap s( x , 3 );
const std::vector< std::byte > file = s.writePortable(); // any Roaring
roaring_bitmap_t * r = ADS::toCRoaring( s );
roaring_bitmap_add_range( r , 100 , 200 ); // in CRoaring
const ADS::RoaringBitmap t = ADS::fromCRoaring( r ); // and back
roaring_bitmap_free( r );
A conversion costs a buffer of portableSizeInBytes() bytes and two linear
passes over it, since both sides go through the format instead of the
internals of the other library. We have not measured it against a direct
copy of the containers, which would depend on those internals. We remark
that, for the sample of the specification of the format, ADS writes the
bytes of the file bitmapwithoutruns.bin of CRoaring. Also, the test
interop_columnar.roaring-croaring reads the same sample as CRoaring
writes it with runs (the file bitmapwithruns.bin), and it passes random
sets in both directions.
C.20 sdsl-lite¶
In its version 3, header-only and under the BSD license, sdsl-lite keeps
its vectors in the words of ADS. Indeed, the bit \(i\) of a bit_vector and of a
BitVector is the bit \(i \bmod 64\) of the word \(\lfloor i / 64 \rfloor\), and
the field \(i\) of an int_vector< B > and of a PackedArray< B > (chapter
22) takes the bits \(i B\) to \(( i + 1 ) B - 1\), which
never cross a word, as \(B\) divides 64. Hence ADS/interop/sdsl/Sdsl.h
converts them by a copy of the words, toSdsl() in one direction and
toBitVector() and toPackedArray< B >() in the other. It is compiled
under the option ADS_WITH_SDSL, AUTO with CMake (the component
sdsl). A structure of
either library may then be built on the data of the other, as in the
example, where a rank directory of each library is built on the same bits.
// with sdsl-lite
#include "ADS/interop/sdsl/Sdsl.h"
#include "ADS/succinct/RankSelect.h"
#include <sdsl/rank_support_v5.hpp>
ADS::BitVector b( 1000 );
b.set( 3 );
b.set( 500 );
const sdsl::bit_vector v = ADS::toSdsl( b ); // a copy of the words
const sdsl::rank_support_v5< 1 > r( &v ); // a rank of sdsl
const ADS::RankSelect q( ADS::toBitVector( v ) ); // and one of ADS
Neither library can take the words of the other without a copy, since each
one owns them: ADS aligns them to a line of the cache, and sdsl allocates
them by its manager of the memory. An int_vector of a width other
than \(B\) is read field by field. Both libraries also write a vector of
bits in the same form to the archives of cereal (cf. chapter
23), as its words in a binary archive and as
integers of 64 bits, one per bit, in a JSON one. The test
interop_columnar.sdsl-cereal thus loads in sdsl the BitVector that ADS
saves, and in ADS the bit_vector that sdsl saves, in the binary, portable
binary and JSON archives of cereal.
C.21 Python¶
We now turn to Python, where the package ads-python, in the directory
python/, gives the structures of ADS that NumPy, SciPy and NetworkX lack
through an extension module ads written on nanobind. It also registers
nx-ads, a backend of NetworkX (Hagberg et al.
2008) that runs the algorithms of ADS
behind its functions. A library of templates cannot be bound generically,
and thus the module instantiates a fixed set of them, chosen where ADS has
something that the libraries of Python have not. These are (i)
StaticGraph, with no weights and with weights of type double in both
layouts of the arcs (§14.4), with its sequential and
parallel algorithms, (ii) CsrMatrix, (iii) BitVector, RankSelect,
PackedArray of 1 to 32 bits and EliasFano (chapter
22), (iv) RoaringBitmap, (v) the Bloom, blocked
Bloom, cuckoo, prefix, binary fuse, ribbon and Grafite filters (chapter
10), (vi) the indexed heaps of chapter
9, and (vii) DynamicGraph. As for the graphs, the
algorithms are the visits, the shortest paths of
§14.8, the components, the strong components and the
topological sort, as well as the parallel visit, the components of Afforest,
the maximal independent set and the stepping algorithms of chapter
25. Also, the heaps decrease the key of an item,
which heapq cannot do, and DynamicGraph is a ListGraph behind the
ObservedGraph of §14.13, whose typed events are
read as tuples. We have left out what NumPy, SciPy and NetworkX already do
as well (e.g., the sorts, the hash tables and the dense matrices).
A graph or a matrix is built from arrays of NumPy by one copy of each, and
its rows are sorted only where they are not. Its arrays are then exposed as
read-only views of NumPy over the memory of the structure, which each view
keeps alive; in the interleaved layout, the heads and the weights are two
views with a stride of 16 bytes over the array of the pairs. We remark that
a graph cannot adopt an array of NumPy without the copy, since its arrays
are vectors that hold their memory. When a structure is opened by
restore_mapped(), i.e., by the restoreMapped() of chapter
23, the views lie instead in the file; hence a
structure that is stored once is opened by any later run in \(O( 1 )\) time,
with no copy and no parsing. Each static structure has store(),
restore(), restore_mapped(), to_bytes() and from_bytes(), and pickle
writes the same format. A RoaringBitmap is written in the portable format
of §C.19 instead, which pyroaring reads by
BitMap.deserialize() and writes by BitMap.serialize(). Each call that
takes time releases the GIL, and the parallel ones run on a ThreadPool
given to them or on a pool of the module. Furthermore, the preconditions of
ADS are checked at the level 1 of the contracts (cf.
§1.7.1), and thus a wrong argument raises
ContractViolation, or a ValueError or an IndexError of the binding,
before it can break a structure. In the example, a graph is built from its
rows, stored, opened in place and queried; then a bitmap is written in the
portable format, and the changes of a batch are read as their net effect.
import ads
import numpy as np
offsets = np.array([0, 2, 3, 4, 4], dtype=np.int32)
heads = np.array([1, 2, 3, 3], dtype=np.int32)
weights = np.array([1.0, 4.0, 2.0, 1.0])
g = ads.static_graph(offsets, heads, weights, layout="interleaved")
g.store(path) # once
h = ads.InterleavedStaticGraph.restore_mapped(path) # O(1), no copy
d, parent = ads.shortest_paths(h, 0) # [0, 1, 4, 3]
r = ads.RoaringBitmap(np.arange(0, 1 << 20, 3, dtype=np.uint32))
data = r.serialize() # read by pyroaring
dg = ads.DynamicGraph(3)
with dg.batch():
dg.add_edge(0, 1, 5.0)
dg.set_weight(0, 1, 2.0)
dg.events() # [("edge_inserted", 0, 1, 2.0)]
On the side of NetworkX, the backend follows the dispatch of NetworkX 3,
under the entry point networkx.backends. A call with backend="ads", or
with a graph already converted by nx_ads.from_networkx(), converts the
graph into a StaticGraph whose weights are those of the attribute that the
function names; it then runs the algorithm of ADS and returns the result of
NetworkX, with the names of the nodes. It implements the shortest paths from
a source (by the arcs, by Dijkstra, and by Bellman and Ford, also on
negative weights), the components, the strong and the weak ones, the
descendants and the ancestors, the test of acyclicity and the topological
sort. Its can_run() leaves to NetworkX the arguments that ADS does not
take, e.g., a weight given by a function or the shortest paths between all
the pairs. Its should_run() declines the graphs of fewer than \(10^4\) nodes
and edges, below which we expect the conversion to cost more than the
algorithm saves, although we have not yet measured this threshold. Note
that, among several shortest paths of the same length, the one of ADS may
differ from that of NetworkX, since the rows of a StaticGraph are sorted
by head, whereas NetworkX visits the neighbours in the order of their
insertion.
import networkx as nx
G = nx.grid_2d_graph(30, 30)
for k, (u, v) in enumerate(G.edges):
G.edges[u, v]["weight"] = 1 + k % 7
d = nx.single_source_dijkstra_path_length(G, (0, 0), backend="ads")
nx.number_connected_components(G, backend="ads") # 1
With CMake, the package is built under the option ADS_WITH_PYTHON, which
is AUTO (on where a Python with its headers and nanobind are found) and
off in the packages of the distributions. It is also built by pip install
python/, through scikit-build-core, into one wheel for the stable ABI of
Python 3.12 and later, with the stubs of the module written by the stubgen
of nanobind; the wheel leaves out the libraries that ADS may use beside its
headers, and it depends on NumPy only. The wheels of Linux (x86_64 and
aarch64), macOS (arm64 and x86_64) and Windows, and the sdist, are attached
to each release of ADS, and pip install of the wheel of the platform
installs the package with no compiler. Its tests of pytest, i.e., the ctest
python.pytest, compare each algorithm with NetworkX and SciPy, each bitmap
with pyroaring and each heap with heapq. They also run the tests of
NetworkX of the shortest paths, the components, the visits and the acyclic
graphs on the backend, by the machinery of NetworkX for its backends
(NETWORKX_TEST_BACKEND=ads). Only one of them is marked as an expected
failure, since it changes the graph of NetworkX while it iterates over the
topological order, which the backend computes on a copy. Both examples,
python/examples/structures.py and networkx_backend.py, are run by the
ctests python.example.*. Finally, we have not measured the times against
NetworkX and SciPy, which bench/python/compare.py takes on an idle
machine.
C.22 Where the examples run¶
Table C.1 gives the option that compiles the
examples of each library, and the names of their tests. These run on any
machine that has the libraries, and in the continuous integration, whose
job interop installs oneTBB, Boost, GMP, OpenBLAS, abLEMON, stdexec,
Taskflow and Kokkos, as well as cereal, Eigen, METIS, KaHIP, GraphBLAS,
NetworKit, CRoaring, sdsl-lite and nanoarrow, and runs the examples on all
of them by CMake and by the makefile. The jobs test install those of the
latter that the package managers of Linux, macOS and MSYS2 have, or that
are quick to build from their sources, the job of MPI runs the examples of
MPI and of Boost.MPI, and the job python builds the wheel of the package
of §C.21 and runs its tests on Linux, macOS and
Windows. Also, make check compiles the examples of a library only where
it finds the library, and it names those that it skips. The directories of
a library that is not where the compiler looks are given to it as flags in
the environment, DECLCHECK_LEMON, DECLCHECK_STDEXEC,
DECLCHECK_TASKFLOW, DECLCHECK_KOKKOS, DECLCHECK_EIGEN,
DECLCHECK_KAHIP, DECLCHECK_GRAPHBLAS, DECLCHECK_NETWORKIT,
DECLCHECK_CROARING and DECLCHECK_SDSLLITE (e.g.,
DECLCHECK_TASKFLOW="-I<dir>").
Table C.1. The libraries of the examples: the option of CMake and its
default, the component of find_package(ADS) (none where ADS::ADS
carries the library), and the tests. The makefile takes the same variable
(auto, 0 or 1) for all the libraries but Kokkos, Boost.MPI and
Python, which only CMake builds, and ADS_WITH_NANOARROW for nanoarrow,
which CMake uses where it finds it; the adapters of Eigen, METIS, KaHIP,
GraphBLAS and NetworKit are also tested by interop_graphs.*, and those of
Arrow, CRoaring and sdsl-lite by interop_columnar.*.
| Library | Option | Default | Component | Tests |
|---|---|---|---|---|
| standard library | none | none | std-* |
|
| Boost.Graph, Boost.Heap, Boost.Unordered | ADS_WITH_BOOST |
AUTO |
Boost |
bgl-*, boost-* |
| LEMON | ADS_WITH_LEMON |
AUTO |
LEMON |
lemon-* |
| GMP | ADS_WITH_GMP |
AUTO |
GMP |
gmp-numbers |
| BLAS | ADS_WITH_BLAS |
AUTO |
BLAS |
blas-dense-matrix |
| oneTBB | ADS_WITH_TBB |
OFF |
none | tbb-arena-sort |
| OpenMP | ADS_WITH_OPENMP |
OFF |
none | openmp-region-sort |
| std::execution | ADS_WITH_STDPAR |
AUTO |
StdPar |
stdpar-sort |
| stdexec | ADS_WITH_STDEXEC |
AUTO |
stdexec |
stdexec-sort |
| Taskflow | ADS_WITH_TASKFLOW |
AUTO |
Taskflow |
taskflow-sort |
| Kokkos | ADS_WITH_KOKKOS |
AUTO |
Kokkos |
kokkos-sort |
| MPI | ADS_WITH_MPI |
OFF |
none | mpi-sort |
| Boost.MPI | ADS_WITH_BOOST_MPI |
AUTO |
BoostMPI |
boost-mpi-sort |
| Eigen | ADS_WITH_EIGEN |
AUTO |
Eigen |
eigen-conjugate-gradient |
| METIS | ADS_WITH_METIS |
AUTO |
METIS |
metis-partition |
| KaHIP | ADS_WITH_KAHIP |
AUTO |
KaHIP |
kahip-partition |
| SuiteSparse:GraphBLAS | ADS_WITH_GRAPHBLAS |
AUTO |
GraphBLAS |
graphblas-triangles |
| NetworKit | ADS_WITH_NETWORKIT |
AUTO |
NetworKit |
networkit-dynamic-components |
| Arrow | none | none | arrow-columns |
|
| CRoaring | ADS_WITH_CROARING |
AUTO |
CRoaring |
croaring-bitmaps |
| sdsl-lite | ADS_WITH_SDSL |
AUTO |
sdsl |
sdsl-vectors |
| Python, NetworkX | ADS_WITH_PYTHON |
AUTO |
none | python.pytest, python.example.* |
Finally, the test of an example whose library is not compiled in passes
with no check, and it prints so. A run of
interop_examples on a machine without (say) Kokkos thus does not fail,
but it does not test that example either, which then only the continuous
integration covers.