0.9.0 release card: acceleration#
Release card
Acceleration
0.9.0
0.9.0 changes how fast Andrey runs, not what it returns. This card answers two questions. How much faster is each method than in 0.8.0, on the same data with the same output? And how does GES on the 0.9.0 build compare with pcalg’s? These results apply to the measured workloads. Speed depends on the data, settings, and hardware.
Summary#
Faster than 0.8.0, with the same output. At the best of the sizes we measured, with one worker: BOSS 8.19x, exact search 5.29x, GRaSP 3.89x, GFCI 3.18x, FCI 3.15x, LPCMCI 2.87x, PNL 2.28x, MultiGroupDirectLiNGAM 1.97x, DirectLiNGAM 1.96x, PC 1.89x, GES and XGES 1.71x, CD-NOD 1.62x, and LongitudinalLiNGAM 1.34x. With four workers, CD-NOD runs 4.62x faster than 0.8.0 and PC 2.60x. Every fit of both builds returned the same output.
No measurable change. The other methods run as fast as in 0.8.0: their speedups lie within the run-to-run spread, 0.85x to 1.24x.
GES against pcalg. Andrey’s GES runs 1.68x to 5.43x faster than pcalg 2.7-12’s, with the same or fewer errors at every size.
How we compare#
The same work. Andrey 0.9.0 (release/0.9.0 at b94e647) and Andrey 0.8.0 (andrey-core 0.8.0 from PyPI, with the same dependency versions) are two contestants in the benchmark harness. Both fit the same datasets with the same parameters and limits: a 1,800 s wall cap and a 20,000 MB memory cap per fit. No fit reached either.
The same machine, at the same time. Both builds of a row run in one job on one node, an AMD EPYC 7713, in a 4-CPU slot of a shared node. Each dataset is fit by one build and then the other, the order swapped on alternate rounds, each fit in its own process. A one-worker fit runs on one thread; a four-worker fit on 4 cores.
The same output. A speedup counts only when both builds return the same output. We check this by a hash of the full output of every fit. Before the timing, the identity check compared the two builds’ full outputs on its own datasets: 1,216 of 1,216 rows identical (27 methods, five column orders, one and four workers).
The speedup. A dataset’s time is its median over 2 or 3 rounds, after 0 or 1 untimed warm-up fit; a size’s time is the median over its 3 or 5 datasets; the speedup is 0.8.0’s time divided by 0.9.0’s. Times and ratios have three significant figures.
Data. Each method runs on the data its release card used: linear-Gaussian Erdos-Renyi graphs with mean degree 2 for most searches, and the family’s own data for the latent-variable, pairwise, multi-domain, and time-series methods. For the time-series methods, Variables counts the series and Rows the time steps.
Faster than 0.8.0#
Each table answers one question: for the same datasets and the same output, how much less time does 0.9.0 take than 0.8.0?
Constraint-based methods#
Method |
Variables |
Rows |
0.8.0 (s) |
0.9.0 (s) |
Faster |
|---|---|---|---|---|---|
PC |
800 |
8,000 |
11.1 |
5.88 |
1.89x |
PC |
1,000 |
10,000 |
52.5 |
30.7 |
1.71x |
FCI |
400 |
4,000 |
6.24 |
1.98 |
3.15x |
FCI |
800 |
8,000 |
111 |
36.9 |
3.00x |
GFCI |
200 |
2,000 |
2.90 |
1.29 |
2.24x |
GFCI |
400 |
4,000 |
18.3 |
5.76 |
3.18x |
CD-NOD |
70 |
20,000 |
28.0 |
17.3 |
1.62x |
CD-NOD |
100 |
2,000 |
468 |
331 |
1.41x |
Constraint-based methods with four workers#
0.9.0 runs the larger skeleton passes in worker processes; 0.8.0 has none in the skeleton search, and uses its workers only in GFCI’s GES phase. Both builds get the same four workers.
Method |
Variables |
Rows |
0.8.0 (s) |
0.9.0 (s) |
Faster |
|---|---|---|---|---|---|
PC |
800 |
8,000 |
10.8 |
5.66 |
1.90x |
PC |
1,000 |
10,000 |
54.9 |
21.1 |
2.60x |
FCI |
400 |
4,000 |
5.85 |
1.79 |
3.27x |
FCI |
800 |
8,000 |
111 |
37.9 |
2.93x |
GFCI |
200 |
2,000 |
2.87 |
1.30 |
2.21x |
GFCI |
400 |
4,000 |
18.4 |
5.75 |
3.21x |
CD-NOD |
70 |
20,000 |
32.3 |
11.5 |
2.82x |
CD-NOD |
100 |
2,000 |
483 |
104 |
4.62x |
Score-based methods#
Method |
Variables |
Rows |
0.8.0 (s) |
0.9.0 (s) |
Faster |
|---|---|---|---|---|---|
Exact search |
14 |
140 |
3.03 |
0.573 |
5.29x |
Exact search |
15 |
150 |
6.26 |
1.19 |
5.24x |
Exact search |
16 |
160 |
16.0 |
3.15 |
5.08x |
GES |
200 |
2,000 |
1.09 |
0.809 |
1.35x |
GES |
300 |
3,000 |
2.77 |
1.83 |
1.51x |
GES |
400 |
4,000 |
5.73 |
3.36 |
1.71x |
XGES |
200 |
2,000 |
1.81 |
1.57 |
1.15x |
XGES, mean degree 4 |
200 |
2,000 |
11.1 |
9.89 |
1.13x |
XGES |
500 |
5,000 |
9.69 |
5.69 |
1.71x |
Permutation-based methods#
Method |
Variables |
Rows |
0.8.0 (s) |
0.9.0 (s) |
Faster |
|---|---|---|---|---|---|
BOSS |
200 |
2,000 |
5.58 |
1.87 |
2.98x |
BOSS |
400 |
4,000 |
45.4 |
5.54 |
8.19x |
GRaSP |
200 |
2,000 |
19.1 |
4.92 |
3.89x |
LiNGAM, pairwise, and temporal methods#
Method |
Variables |
Rows |
0.8.0 (s) |
0.9.0 (s) |
Faster |
|---|---|---|---|---|---|
DirectLiNGAM |
50 |
500 |
2.99 |
1.62 |
1.84x |
DirectLiNGAM |
100 |
1,000 |
37.5 |
19.1 |
1.96x |
MultiGroupDirectLiNGAM |
20 |
1,000 |
1.38 |
0.783 |
1.77x |
MultiGroupDirectLiNGAM |
30 |
1,000 |
3.69 |
1.97 |
1.88x |
MultiGroupDirectLiNGAM |
40 |
1,000 |
8.02 |
4.07 |
1.97x |
PNL |
2 |
5,000 |
5.07 |
2.23 |
2.28x |
PNL |
2 |
10,000 |
21.8 |
9.71 |
2.25x |
PNL |
2 |
20,000 |
72.3 |
32.2 |
2.25x |
LongitudinalLiNGAM |
20 |
200 |
3.25 |
2.43 |
1.34x |
LongitudinalLiNGAM |
20 |
500 |
8.33 |
6.70 |
1.24x |
LongitudinalLiNGAM |
30 |
300 |
7.55 |
6.05 |
1.25x |
LPCMCI |
30 |
1,000 |
2.91 |
1.36 |
2.15x |
LPCMCI |
40 |
1,000 |
8.13 |
2.83 |
2.87x |
No measurable change#
ICA-LiNGAM, GIES, VARMA-LiNGAM, and ANM changed in 0.9.0 (ICA-LiNGAM’s order search, GES’s update inside GIES, the LiNGAM entropy, ANM’s memory) but run no faster at these sizes. Hill climbing, tabu search, CALM, PCMCI, PCMCI+, Granger, GIN, RCD, and BottomUpParceLiNGAM have no speed work in 0.9.0. Their differences from 0.8.0 lie within the run-to-run spread: at 800 variables, hill climbing’s datasets ranged from 0.60x to 1.56x. Their published comparisons stand.
Method |
Variables |
Rows |
0.8.0 (s) |
0.9.0 (s) |
Faster |
|---|---|---|---|---|---|
ICA-LiNGAM |
100 |
1,000 |
3.23 |
3.03 |
1.06x |
ICA-LiNGAM |
200 |
2,000 |
21.2 |
20.6 |
1.03x |
GIES |
200 |
2,000 |
1.16 |
1.21 |
0.963x |
GIES |
300 |
3,000 |
3.84 |
3.70 |
1.04x |
VARMA-LiNGAM |
3 |
1,000 |
3.34 |
2.70 |
1.24x |
VARMA-LiNGAM |
5 |
1,000 |
18.7 |
18.9 |
0.990x |
VARMA-LiNGAM |
10 |
1,000 |
75.3 |
73.5 |
1.02x |
ANM |
2 |
1,000 |
3.23 |
3.22 |
1.01x |
ANM |
2 |
2,000 |
18.7 |
18.1 |
1.03x |
Hill climbing |
800 |
8,000 |
1.55 |
1.82 |
0.854x |
Hill climbing |
1,600 |
16,000 |
5.08 |
5.06 |
1.00x |
Hill climbing |
3,200 |
32,000 |
36.4 |
39.1 |
0.931x |
Tabu search |
800 |
8,000 |
1.96 |
1.94 |
1.01x |
Tabu search |
1,600 |
16,000 |
12.0 |
11.4 |
1.06x |
Tabu search |
3,200 |
32,000 |
69.7 |
69.3 |
1.01x |
CALM |
10 |
100 |
25.8 |
24.5 |
1.05x |
CALM |
50 |
500 |
37.6 |
39.2 |
0.958x |
PCMCI |
160 |
1,000 |
4.69 |
4.58 |
1.02x |
PCMCI |
240 |
1,000 |
19.1 |
18.4 |
1.04x |
PCMCI |
320 |
2,000 |
52.8 |
52.6 |
1.00x |
PCMCI+ |
120 |
3,000 |
3.94 |
3.94 |
1.00x |
PCMCI+ |
160 |
3,000 |
32.3 |
32.2 |
1.00x |
Granger |
80 |
1,000 |
3.07 |
3.00 |
1.02x |
Granger |
160 |
1,000 |
19.3 |
20.9 |
0.921x |
Granger |
240 |
1,000 |
110 |
105 |
1.04x |
GIN |
12 |
1,000 |
2.39 |
2.38 |
1.00x |
GIN |
16 |
1,000 |
5.81 |
5.58 |
1.04x |
GIN |
20 |
1,000 |
11.4 |
11.7 |
0.972x |
RCD |
20 |
2,000 |
11.6 |
11.6 |
0.999x |
RCD |
30 |
2,000 |
20.1 |
19.4 |
1.04x |
BottomUpParceLiNGAM |
10 |
2,000 |
8.00 |
8.05 |
0.994x |
BottomUpParceLiNGAM |
20 |
2,000 |
32.8 |
35.3 |
0.927x |
GES against pcalg#
This table answers one question: on the 0.9.0 build, how fast is Andrey’s GES against pcalg’s, at the same level of accuracy? pcalg runs its GES in C++, called from R. Both run on the same datasets (linear-Gaussian Erdos-Renyi graphs, mean degree 2, standardized, 5 per size) on one core of the same node, with 3 timed repeats after one warm-up fit each. Errors are the median SHD against the true CPDAG; the empty graph makes as many errors as there are true edges.
Variables |
Rows |
Andrey (s) |
pcalg (s) |
Faster |
Andrey errors |
pcalg errors |
|---|---|---|---|---|---|---|
20 |
200 |
0.0286 |
0.0479 |
1.68x |
12 |
12 |
50 |
500 |
0.0975 |
0.163 |
1.68x |
47 |
47 |
100 |
1,000 |
0.239 |
0.536 |
2.25x |
79 |
82 |
200 |
2,000 |
0.963 |
3.63 |
3.77x |
200 |
204 |
400 |
4,000 |
4.04 |
22.0 |
5.43x |
470 |
471 |
The comparisons with Tetrad 7.6.10 (PC, GES, BOSS, GRaSP, and FCI) are measured, and appear in a later card once each row’s difference in errors is explained.
Builds and versions#
Comparison |
Andrey build |
Measured package versions |
|---|---|---|
Faster than 0.8.0 |
release/0.9.0 at b94e647 |
Andrey 0.8.0 (andrey-core from PyPI) |
GES against pcalg |
release/0.9.0 at b94e647 |
pcalg 2.7-12 (R 4.6.1, rpy2 3.6.9) |
Other changes in 0.9.0#
With more than one worker,
pc,fci,gfci, andcdnodrun the larger passes of their skeleton search in worker processes, with the same graphs and p-values as with one.andrey calibrate --method skeletonmeasures when a skeleton pass is large enough to repay the workers on your machine;ANDREY_SKELETON_PARALLEL_MIN_WORKsets it.pnlruns its independence tests on a CUDA GPU, in float64, fromANDREY_PNL_GPU_THRESHOLD.
The changelog lists every change.
Limits#
Same output. On the identity datasets, 0.9.0 returns exactly 0.8.0’s outputs, the LiNGAM methods included. DirectLiNGAM, MultiGroupDirectLiNGAM, and the temporal LiNGAM methods compute their internal scores differently in the last bits, which could change a causal order only at an exact tie between two candidates. With one worker, PNL’s linear algebra uses every core, so its result can differ in the last digits from that with several workers; the identity check pins one thread and cannot show it.
Hardware. Speedups are specific to the measured CPU, an AMD EPYC 7713, the core budget, and the settings. Worker processes repay their start-up cost only on large passes.
Not faster everywhere. The methods under No measurable change run as fast as in 0.8.0, within the run-to-run spread.
Reproduce#
You can find environment setup, campaign drivers, and scores in the benchmark harness
guide. To rerun a row, install Andrey 0.8.0 (andrey-core 0.8.0) in its own environment as
the guide’s “Older Andrey builds” describes, and run the row’s driver with both builds:
anm_pairs.py, benchmark.py, boss_grasp_cpu.py, calm_cpu.py, cdnod_cpu.py,
confounded_cpu.py, exact_cpu.py, fci_latent.py, ges_cpu.py, gfci_latent.py, gies_cpu.py,
gin_cpu.py, granger_var.py, lingam_cpu.py, lingam_ts.py, multi_group_cpu.py,
pcmci_cpu.py, pnl_pairs.py, tabu_cpu.py, and xges_cpu.py. The summary names each
row’s driver, solutions, and seeds. Times will differ with the hardware; outputs should match
exactly.