search

homotopy-io / homotopy-rs

A Rust/WASM implementation of homotopy.io
https://homotopy.io
BSD 3-Clause "New" or "Revised" License
84 stars 7 forks source link

Recursive collapse #980

Open NickHu opened 1 year ago

NickHu commented 1 year ago

Collapse seems to have a recursive structure, so it can be reimplemented from the current approach (fully explode, then collapse a graph of 0-diagrams and 0-rewrites). The hope is that this new approach would be faster too.

NickHu commented 1 year ago

I have a working draft of this, currently it passes 47/53 test cases for contraction.

NickHu commented 1 year ago

Here is some performance data of running the benchmark for label identifications high dimensions/8

w/ shared label identifications allocations (eebc0a8e7ebdc986120acec375182b5ad03d42c7) w/o shared label identifications allocations
old collapse https://share.firefox.dev/3GSqazn (6.7s) https://share.firefox.dev/3WmidYC (9.4s)
new collapse https://share.firefox.dev/3XySflG (497ms) https://share.firefox.dev/3ZNTpvU (1.2s)

Thankfully, it confirms that eebc0a8e7ebdc986120acec375182b5ad03d42c7 is a performance improvement.

jamievicary commented 1 year ago

Fantastic to see this performance improvement being realized.

NickHu commented 1 year ago

I made a small mistake in eebc0a8e7ebdc986120acec375182b5ad03d42c7, so that it never actually memoized anything (but it did avoid reallocations). Fixed in 15f2cd1fcf3d5e05a6592be45ca93bb73413d6a5. I noticed a lot of potential for speedup in memoizing Rewrite::cone_over_generator too, which is done here: 5bda4a97bd1de7917ffa6b590df2be7a0522eb1a. Also made a slight change to label identification sharing here: ea0dd8de9006858c44ecba5b1b88c49b230c0622. All of these changes have been backported to the existing (old) collapse implementation, and should make noticeable performance improvements, but it also importantly means that the tests which we're using to measure the speed of collapse are not dominated by other factors.

This gives us a new baseline also (again for label identifications high dimensions/8):

old collapse https://share.firefox.dev/3w9txwO (2.4s)
new collapse https://share.firefox.dev/3w9u41M (**54ms**)

That's a ~98% speedup for the new collapse algorithm in this case, now that repeated allocations/recursive calls unrelated to collapse aren't dominating the running time. The speedup should be non-linear: I can now run label identifications high dimensions/9 on my machine with the new collapse in roughly 200ms (previously it wouldn't finish in a reasonable amount of time, definitely not under 20 minutes).

jamievicary commented 1 year ago

Really excellent!!