Fermion sign check slows down small block contraction

[mtfishman]

This line https://github.com/ITensor/ITensors.jl/blob/ae3b49d9b5d530e144ec10bd8aeafec288cca5bc/src/NDTensors/blocksparse/blocksparsetensor.jl#L1082-L1084 takes up a nontrivial (say 50%) of time for block sparse contractions with small blocks (dimension 1).

Here is a minimal code to try:

using ITensors
using BenchmarkTools
using SparseArrays

d = 500
i = Index([QN() => d])
A = ITensor(i', dag(i))
A[1, 2] = 1
x = randomITensor(i)

Asp = splitblocks(A)
xsp = splitblocks(x)
Ax = @btime $Asp * $xsp

A_ = sparse(Array(A, i', i))
x_ = Array(x, i)
Ax_ = @btime $A_ * $x_

You should see the fermion sign check showing up as a significant portion of the profile.

[emstoudenmire]

Thanks for posting this - just assigned myself

[mtfishman]

An interesting related question is if there is any way for us to reach the efficiency of SparseArrays. Even if we remove the timing of the fermion sign check we are pretty far off. I think it may just be inherent to using a dictionary-of-keys instead of a more specialized CSC format that Julia uses.

[emstoudenmire]

This is an interesting point we should really think about. The block sparse system may need either a little or perhaps quite a serious redesign in order to accomodate SU(2) symmetric blocks. But on the other hand, maybe that feature calls for a sort of 'decoupling' of the physics aspects from the computing and data structure aspects, and then we connect the two with a function mapping one to the other. Decoupling them may in fact let us use whatever works the best for each 'side' of things (i.e. whatever is most natural on the math/physics side on the one hand, then whatever gives the highest performance on the low-level computing side on the other).