possible optimization for sheep

[pazz]

the dimension is fixed, so we could consider fixing the capacity of the vectors representing sheep:

https://www.reddit.com/r/learnrust/comments/12eczea/how_much_faster_are_arrays_that_vecs_and_is_my/?rdt=48521

if you know in advance (at runtime) the number of elements you need, you can use Vec::with_capacity to reserve enough space up front - for large arrays, this essentially makes the malloc cost disappear, as the cost of the actual operation dominates the cost of malloc

[Numero7]

@pazz I believe the effect will be negligible.

I did put some efforts last week in running hard examples with a performance analysis tool called "flamegraph",
which led me to add a few heuristics, starting with parallelization of the semigroup computation,
and lazy computation of the answer --solver-output yes-no avoiding full computation of the entire semigroup.

Current status:

cargo build --release
cargo flamegraph --root -- -s topological -i dot  -f examples/fig6-butterfly.dot

produces the stats

To make things clearer, I can turn off the parallelization and get

The bottle neck is clearly the closure by product and iteration of the semigroup,
fn close_by_product_and_iteration(&mut self, maximal_finite_coordinate: coef) {
which is implemented in a very naive way at the time,
there are plenty of algorithmic optimizations to be found there,
by using some more structure / insight.
By exploring the most maximal elements first (large coefs and a lot of non-zero entries)
and avoiding all those matrices full of zeros.
Also the matrices are full of zeros, a more compact representation could be a game changer.

You want to discuss that by zoom?

[pazz]

Nice! Yes, I also suspect the effect will be negligible. I just wanted to bring it up in case it is easy and impactful after reading about it online.

I am quite busy this week and want to read more about performance testing and rust in general before it makes sense to discuss this. But perhaps late next week makes sense.

[Numero7]

@pazz ok please come back to me when needed