search

mggg / GerryChain

Use MCMC to analyze districting plans and gerrymanders
https://mggg.github.io/GerryChain/
Other
132 stars 74 forks source link

Rustworkx acceleration #381

Open InnovativeInventor opened 2 years ago

InnovativeInventor commented 2 years ago

This is a draft PR (based off perf-tuning that rewrites the balance edge picking algorithm in Rust using retworkx, yielding a ~16x speedup in chain run times).

PA chain run times (congressional) are now at 50 it/s on my computer with commit e9eddbef5b82522e4d1d3c12e68d35958fb1cae9 (as opposed to ~3 it/s). This also leaves a few more low-hanging fruit optimizations on the table which could yield more speedups in the future.

Some of the new retworkx code has been upstreamed, other bits are in the process of being upstreamed. This PR works with my feat-balanced-cut-edges branch here: https://github.com/InnovativeInventor/retworkx/tree/feat-balanced-cut-edges.

InnovativeInventor commented 2 years ago

The speedup should be > 16x now, for some computers at least.