Latest Results
feat: New ConvexChecker algorithm for Circuit-like graphs (#240)
This PR adds a new convex checker `LineConvexChecker`. All existing
benchmarks `check_convexity_full`, `check_convexity_sparse` and
`initialize_convexity` have been implemented for the new checker. I have
also added a new `check_convexity_fixed_size` benchmark, which models
more closely the kind of workloads that `tket2` uses these checkers for.
The comparison between the two checkers is interesting
- 👍 on the `fixed_size` convexity check, the new checker is **~4x
faster**, across all graph sizes. The one-time memory allocation would
get amortised even further if more convexity checks were made in
sequence (only making 3 in the benchmarks)
- 👍 on the `sparse` convexity check, the new checker is between **36%
and 60% faster**
- on the `full` convexity check, the new checker is slightly faster on
the smallest instance, but goes up to being 8x slower on the largest
instance. This is expected, as it is optimised for small subgraph
convexity checking.
- 👎 Initialisation of the new checker is ~4x slower - again, this is by
design. I've made a node of this in the docs and would still recommend
the `TopoConvexChecker` as a "sane default" for this reason.
The benchmarks that CodSpeed marks as "dropped" have in fact been
renamed with the suffix `_TopoConvexChecker<PortGraph>`. No modification
has been made to `TopoConvexChecker` (but the code was moved to its own
file, hence the noisy diff). You can see though that the renamed
benchmarks perform identically to the old ones.
For reviewing the file `src/algorithms/convex.rs`, it might be simpler
to just read the new version rather than reading the diff. All code that
has been deleted from that file is now in
`src/algorithms/convex/topo_convex_checker.rs`. Active Branches
#2370%
#1810%
© 2025 CodSpeed Technology