The data structures
The data structures of the searches are those of ADS. OPEN is either a
4-ary heap (ADS::DaryHeap), for any cost type, or a two-level bucket
queue (ADS::BucketQueue, on f first, then on g) for integer costs, which
[4] reports to be somewhat faster than a heap on the sliding-tile
puzzles; neither one supports decrease-key, and an entry made stale by a
cheaper path is skipped when it surfaces. CLOSED (NodeTable.h) is an
open-addressing hash table (ADS::PointerTable) that stores the hash of a
state next to its node, so that most probes do not compare the states, and
spreads the slots by Fibonacci hashing; the nodes are allocated from an
arena (ADS::Arena), and both the table and the arena are requested from
the operating system as transparent huge pages, where available. In the
sequential search the slots of the successors are also prefetched before
being probed, since on large instances most probes are cache misses (the
parallel searches do the same with the batches they receive). The queues
inside the other searches come from ADS as well: the free list of SafePBNF
and the OPEN of PA*SE are B+-trees (ADS::BTreeMap), which give both the
least key and the scan in order that their tests of interference need, and
the queue of the B&B is a pair of indexed heaps on the same nodes
(ADS::IndexedHeapPair), one by the key of the selection and one by the
bound, which the test of termination needs. Each search returns a
Solution holding the status (solved, unsolvable or stopped at the node
limit), the cost, the path and the counters of the search; for the
parallel ones, these include the load balance and the communication
overhead of [2].
The structures of A* can be replaced, at compile time, by those of the
standard library (std::deque, std::unordered_map and
std::priority_queue) or of Boost (boost::object_pool,
boost::unordered_flat_map and boost::heap::d_ary_heap), with the same
interface (Structures.h); the searches do not change, and neither does
the order of their expansions, but for the ties of f and g in OPEN, which
the sets break differently. Neither the standard library nor Boost has a
bucket queue, and hence with them both OPEN lists are a heap. With the
structures of ADS the domains on a graph take their adjacency from ADS too:
the grids from ADS::GridGraph, which computes the moves from a cell and
their costs from a vector of the costs of the cells (a move paying the cell
it leaves, as in the domain), and the explicit graphs from
ADS::ArrayGraph, built from the arcs before the first expansion. The
other two sets compute the moves of a grid from its map, as neither the
standard library nor Boost has a graph of a grid with blocked cells and
diagonal moves (and a graph in compressed rows of a map of 20000 by 20000
cells would take tens of GB), and keep the arcs of an explicit graph in a
list per node or in the compressed_sparse_row_graph of Boost. The
standard library and Boost are there to measure the searches against them
(tools/bench/structures.sh), and the B&B does not depend on the set.