Optimize einsum contraction order

[AntonOresten]

Since einsum isn't a generated function, and the OMEinsum backend is mostly not type stable anyway (under-Peter/OMEinsum.jl#97), array sizes are known. This PR is meant to allow einsum contraction order optimization. I don't know exactly what sets TreeSA and the different optimizers apart, and I don't know if I'd like them to be user-facing here. Related is #26.

Closes #24

[samuelsonric]

Helpful? The image is from this page.

[AntonOresten]

Thanks! I suppose that's logarithmic?

I feel like Einsum is such a rabbit hole, and the time-to-optimize vs time-to-contract is a tricky dilemma, and I obviously want both to be good. I don't really know how optimized einsum expressions are found/used in practice. Does it get resolved at runtime on every loop or are tensors mostly of fixed size, and it can be optimized by knowing sizes before-hand? Would something like Reactant.jl be able to remove duplicate optimization work, since it compiles functions while keeping track of sizes?

Was surprised by how slow e.g. TreeSA was for a seemingly simple task:

julia> @be optimize_code(ein"ij,jk,j->", Dict('i' => 30, 'j' => 40, 'k' => 20), OMEinsum.TreeSA())
Benchmark: 15 samples with 1 evaluation
 min    6.055 ms (605052 allocs: 30.000 MiB, 8.83% gc time)
 median 6.772 ms (605052 allocs: 30.000 MiB, 12.98% gc time)
 mean   6.857 ms (605052 allocs: 30.000 MiB, 13.93% gc time)
 max    7.934 ms (605052 allocs: 30.000 MiB, 19.68% gc time)

Inclined to drop einsum in a breaking release, since it would be so difficult to get right, and my main contribution is really my zero-overhead rearrange and friends.

[codecov]

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 100.00%. Comparing base (dd3f296) to head (d6dbaaa).
Report is 3 commits behind head on main.

Additional details and impacted files

@@            Coverage Diff            @@
##              main       #30   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files           12        12           
  Lines          296       313   +17     
=========================================
+ Hits           296       313   +17     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

• ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

[GiggleLiu]

Tensor network contraction order are useful when you have 50+ tensors that beyond human capability to do it right. Usually, we have more than 1000+ tensors in many using cases. If you have small nets, GreedyMethod is good enough.

TreeSA is the slowest, simulated annealing based backend. It is the default backend due to the reliability. You do not need it when the net is small.

Also, it is deliberately made type unstable, because we have too many array shape combination in a 1000+ size tensor network, type pollution is a much more deadly issue. The only way out is to give up Julia Array, and just use vectors and strides, which takes a lot of time. Practical using cases are needed to make it happen.