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.