Flow Cartogram Timing Benchmarks¶
This page shows the results of benchmarking flow cartogram computations - both serial and parallel versions. Benchmarks were run on two datasets (Albers equal-area projection, metres):
- US states — 48 contiguous US states with Census population data.
- Congressional districts — ~430 contiguous US congressional districts (2020 Census, geometries simplified at 1 km tolerance).
The benchmarks were run on the following hardware and software:
| Run date | 2026-09-25 |
| Host | runnervmtr4k5 |
| CPU | AMD EPYC 9V74 80-Core Processor |
| Cores | 4 |
| Python | 3.12.14 |
| Commit | ca34251bc6a9 (dirty) |
| Branch | main |
Grid size and parallelism comparisons¶
In these benchmark tests, the goal is to time the flow cartogram algorithm using various grid sizes (grid_size $\in$ { 256, 512, 1024, 2048 }) and parallelization options (parallel_fft, parallel_density).
The number of iterations is fixed (n_iter=100) to facilitate comparison. To make sure all tests run exactly 100 iterations, mean_tol and max_tol are set sufficiently low to prevent convergence, and early stopping is disabled (stall_patience=None). Speedups are computed relative to the serial baseline at the same grid_size.
Note that in practice, the actual time it takes to construct a flow cartogram will be determined by how many iterations are needed to converge to the desired tolerances.
Dataset information¶
US States
Flow cartogram of 49 geometries with a total of 34510 vertices (100 iterations completed, with 10 updates of the density and velocity fields).
Congressional Districts
Flow cartogram of 432 geometries with a total of 92198 vertices (100 iterations completed, with 10 updates of the density and velocity fields).
Compute time scales with grid size¶
The grid_size parameter has a significant impact on runtime, especially with a large grid size of 2048 (left plot). One hundred iterations take close to 3 seconds for both datasets when using a grid size of 2048. Note that for both datasets, a grid size of 512 is generally sufficient to converge to reasonable tolerances.
The flow cartogram algorithm consists of a number of phases that the benchmark times separately. At a high level, there is initial setup, followed by N iterations during which density and velocity fields are computed (every K-th iteration as set by recompute_every), and vertices are displaced (every iteration). Here is a breakdown of the timed phases:
| Phase | What it measures |
|---|---|
| setup | Pre-loop: grid construction, FFTW plan, geometry unpacking. |
| density | compute_density_field_from_geometries — rasterises geometries onto the grid. Only charged on iterations where the density is recomputed (recompute_every). |
| velocity | FFT Poisson solve (pyfftw) — same cadence as density. |
| displacement | displace_coords_numba — moves every coordinate by the velocity field. Charged every iteration. |
| areas | flat_geoms.compute_areas() — recomputes polygon areas. Charged every iteration. |
| errors | compute_error_metrics() — log-ratio error statistics. Charged every iteration. |
| snapshot | Geometry reconstruction and snapshot object creation. Charged every iteration. |
| other | Overhead not attributed to the phases above (progress bar, convergence bookkeep
The two graphs on the right show how much time is spent in each of the phases for both datasets across the tested grid sizes. For small grid sizes, the largest contributors to compute time are the density field, displacement, and area phases. For large grid sizes, the largest contributors are the density field, velocity field, and other phases, which are the phases that are most impacted by increasing grid size.
Parallelization may speed up computations depending on the grid size and the dataset¶
Parallelized versions of the density field and velocity field calculations can be used to further speed up the flow cartogram calculation. Two options control the use of parallelization: parallel_fft (for velocity field calculations) and parallel_density (for density field calculations). The table below shows the various combinations of these options that were tested in the benchmark (numbers indicate how many threads were used).
| variant | parallel_fft |
parallel_density |
|---|---|---|
| serial | 1 | 1 |
| parallel (velocity) | 3 | 1 |
| parallel (density) | 1 | 3 |
| parallel | 3 | 3 |
As shown in the graphs below, parallelization can provide a modest speedup (right plot), but only for larger grid sizes. At lower grid sizes, any potential speedup is negated by the additional overhead of parallelization. Note that for the Congressional Districts dataset, enabling parallelization of the density field calculations actually results in a marked slow down, especially at small grid sizes. The reason is that this datasets contains many small geometries (districts) with relatively few vertices each. The calculation per geometry is actually quite fast, which means that there is more time spend on paralleization overhead than the actual computation, resulting in a slow down.
Comparison of single and multi-resolution morphs¶
In this benchmark, single- and multi-resolution versions of flow cartogram creation are compared (using morph_gdf and CartogramWorkflow.morph_multiresolution respectively) on the US States dataset. In this test, grid_size is fixed to 512 for the single resolution case, and the min_resolution option for the multi-resolution case is set to 64 with levels=4 such that the maximum resolution is also 512. The tolerance are set to mean_tol=0.005 and max_tol=0.01, and the algorithms are run to convergence. Parallelization is not enabled.
The results in the table below shows that the multi-resolution version converges in fewer iterations and is about two times faster.
| Algorithm | Mean (s) | Std dev (s) | Iterations | Status | Mean error % | Max error % | |
|---|---|---|---|---|---|---|---|
| 0 | morph_gdf | 0.68 | 0.00 | 225 | converged | 0.13 | 0.82 |
| 1 | multiresolution | 0.45 | 0.00 | 98 | stalled | 2.11 | 8.81 |
Vertex scaling and parallelism¶
In these benchmark tests, the goal is to determine how the number of vertices in the input geometries impact the runtime of the flow cartogram algorithm. Using more or less simplified geometries from the US States dataset (simplification tolerance $\in$ {None, 100, 500, 1000, 5000, 10000 }), a range of vertex counts are generated. The grid_size option is fixed at 512.
Similar to the tests of the grid_size option, the number of iterations is fixed (n_iter=100) to facilitate comparison. To make sure all tests run exactly 100 iterations, mean_tol and max_tol are set sufficiently low to prevent convergence, and early stopping is disabled (stall_patience=None). Parallelization speedups are computed relative to the serial baseline at the same vertex count.
Compute time scales with the number of vertices in input geometries¶
The run time of flow cartogram construction grows close to linear with increasing number of vertices in the input geometries (left plot), at least over the range of vertex counts tested.
Inpection of the phase-specific time measurements shows that the density field, displacement, and area computations are most impacted by the vertex count (right plot), as expected.
Parallelization speeds up computations for high vertex counts¶
Turning on parallelization produces a modest speed up, but only for a high number of vertices. As expected, this speed up is only observed for parallel_density option, but not parallel_fft option, because the velocity field computute time is mainly dependent on the grid size and not the number of vertices. Note that while here we look at the total number of vertices in the input geometries, parallelization of the density field computation is performed at the level of geometries, and so the speed up is rather dependent on the number of vertices per geometry. Thus, a dataset like the COngressional Districts with many geometries with fewer vertices per geometry, may not so a similar speed up.
