The examples and the benchmark

The programs in examples are, for the most part, the search problems of chapter 3 of Russell and Norvig [13], each one with its Domain in a header of include/PBeFS/astar (e.g., NQueens.h or Romania.h), which the benchmark shares. 8Puzzle solves the instance of figure 3.28 of the book, or an instance at a given distance from the goal, with the number of misplaced tiles (h1), the Manhattan distance (h2) or the sequence score of Nilsson [8], which is not admissible; with -t it repeats the comparison of h1 and h2 of figure 3.29 (nodes generated and effective branching factor). 15Puzzle solves an instance of Korf, sequentially or with HDA* (-t <threads>); RouteFinding finds a road between two cities of the map of Romania of the book; FindPath finds a path on a weighted grid, random or read from a Moving AI map, and draws it. VacuumWorld is the vacuum world of section 3.2.1 on a row of n cells, and NQueens places n queens with the incremental formulation of the same section, checking the placement apart from the search. The last three come from the exercises of the book: MissionariesCannibals carries m missionaries and c cannibals over a river with a boat of b seats (exercise 3.9), WaterJugs measures a quantity of water with jugs (exercise 3.6(d)), and TravelingSalesman solves the traveling salesperson problem with the minimum spanning tree heuristic (exercise 3.30), checking the tour against the dynamic program of Held and Karp [14]. Each run with a known answer (e.g., the 26 moves of figure 3.28, the 418 km from Arad to Bucharest and the 11 crossings of the missionaries) is also a test of ctest, labelled example. In tools, AStarBench runs any search, runtime and distribution of the library on the 100 instances of Korf (data/15-puzzle/korf100.txt), on the 8-puzzle, on the grids (with unit or weighted cells) and on the other problems of the examples, sized by --size (e.g., the number of queens or of cities), and it prints a line of CSV per run with the cost, the counters and the time; BranchAndBoundBench does the same for every scheme of the branch-and-bound, on random 0-1 knapsacks (include/PBeFS/bnb/Knapsack.h) and on the traveling salesperson problem (the tree of the partial tours, bounded by the minimum spanning tree), and AStarBenchMPI and BranchAndBoundBenchMPI are their MPI counterparts, to be started with mpirun. If the environment variable PBEFS_PIN is set, the i-th worker is pinned to the i-th CPU of the affinity mask of the process (as given, e.g., by numactl --physcpubind or taskset). On machines with several sockets this is usually needed for the timings to be repeatable. Finally, tools/bench/structures.sh runs sequential A*, and HDA* and SPA* on 1 to 16 threads, of four builds, one per set of data structures, on instances of growing size (the 15-puzzle in bands of the instances of Korf, and random grids of growing side), and tools/bench/structures.py makes the tables of the comparison, with the noise of two runs of the same build. In both campaigns (campaign.sh and structures.sh) each run is a process of its own, pinned with its workers to given cores of one NUMA node and with its memory on that node, and the runs that the tables compare are made twice, in two processes, so that the gap between the two (the A/A noise, which tables.py and structures.py report with each table) says how far two timings can differ by the machine alone; a campaign holds a lock on each of its cores, so that a second one started on the same cores waits for it, and tools/bench/launch.sh starts it detached, saving its PID. On x86, AStarBench is compiled with the branches kept off the 32-byte boundaries, by -Wa,-mbranches-within-32B-boundaries where the assembler takes it, against the erratum JCC of Skylake, which slows a loop by its alignment alone, and since the data structures compared with those of PBeFS are compiled into the same program they get it alike. The timings are meant to be taken on a machine at rest; a virtual machine whose memory is given and taken back while it runs (such as a VM of Hyper-V with dynamic memory, which may stay at about 2.4 GB for hours and swap on any large instance) gives timings that are not comparable with each other, and is not to be used for them.