2021-08-11 Decompose einsum into numpy operators#
Notebook Einsum decomposition what function numpy.einsum
does and how it can be decomposed into a series of basic operations,
all available in ONNX. That’s the purpose of function
Function decompose_einsum_equation.
With function export2numpy, it is possible to
convert back this ONNX graph into a series of numpy operations.
<<<
import numpy
from mlprodict.testing.einsum import decompose_einsum_equation
from mlprodict.onnx_tools.onnx_export import export2numpy
seq_clean = decompose_einsum_equation(
"bsnh,btnh->bnts", strategy='numpy', clean=True)
onx = seq_clean.to_onnx("Y", "X1", "X2", dtype=numpy.float32)
code = export2numpy(onx, name="einsum", rename=True)
print(code)
>>>
import numpy
import scipy.special as scipy_special
import scipy.spatial.distance as scipy_distance
from mlprodict.onnx_tools.exports.numpy_helper import (
argmax_use_numpy_select_last_index,
argmin_use_numpy_select_last_index,
array_feature_extrator,
make_slice)
def numpy_einsum(X1, X2):
'''
Numpy function for ``einsum``.
* producer: mlprodict
* version: 0
* description:
'''
# initializers
D = numpy.array([0, 1], dtype=numpy.int64)
E = numpy.array([4], dtype=numpy.int64)
F = numpy.array([-1], dtype=numpy.int64)
I = numpy.array([1], dtype=numpy.int64)
# nodes
K = X1
L = numpy.expand_dims(K, axis=4)
M = numpy.transpose(L, axes=(0, 2, 1, 4, 3))
N = X2
O = numpy.expand_dims(N, axis=3)
P = numpy.transpose(O, axes=(0, 2, 3, 1, 4))
Q = numpy.array(M.shape, dtype=numpy.int64)
R = numpy.array(P.shape, dtype=numpy.int64)
S = numpy.take(Q, D, axis=0)
T = numpy.take(R, D, axis=0)
U = S.prod(axis=0, keepdims=1)
V = T.prod(axis=0, keepdims=1)
W = numpy.take(Q, E, axis=0)
X = numpy.take(R, E, axis=0)
Z = numpy.concatenate([U, F, W], 0)
BA = numpy.concatenate([V, F, X], 0)
BB = M.reshape(tuple(Z))
BC = P.reshape(tuple(BA))
BD = numpy.transpose(BC, axes=(0, 2, 1))
BE = BB @ BD
BF = numpy.maximum(S, T)
BG = numpy.take(Q, [2], axis=0)
BH = numpy.take(R, [3], axis=0)
BI = numpy.concatenate([BF, BG, BH, I], 0)
BJ = BE.reshape(tuple(BI))
BK = numpy.transpose(BJ, axes=(0, 4, 1, 3, 2))
BL = numpy.squeeze(BK, axis=1)
BM = BL
Y = BM
return Y
In some cases, it is faster to permute a matrix before doing a matrix multiplication. There exists many equivalent equation by permutating letters inside the initial equation. All leads to the same results but, once decomposed, they do different transpositions. The following code is obtained by looking for the best permutation and converting the optimized ONNX graph into numpy.
<<<
import numpy
from mlprodict.onnx_tools.onnx_export import export2numpy
from mlprodict.testing.einsum import optimize_decompose_einsum_equation
seq_opt = optimize_decompose_einsum_equation(
"bsnh,btnh->bnts", numpy.float64, strategy='ml', verbose=1,
runtime="python", optimize=True)
print("best equation:", seq_opt.equation_)
code = export2numpy(seq_opt.onnx_, name="einsum_opt", rename=True)
print(code)
>>>
best equation: bhts,bnts->btnh
import numpy
import scipy.special as scipy_special
import scipy.spatial.distance as scipy_distance
from mlprodict.onnx_tools.exports.numpy_helper import (
argmax_use_numpy_select_last_index,
argmin_use_numpy_select_last_index,
array_feature_extrator,
make_slice)
def numpy_einsum_opt(X0, X1):
'''
Numpy function for ``einsum_opt``.
* producer: mlprodict
* version: 0
* description:
'''
# initializers
D = numpy.array([0, 1], dtype=numpy.int64)
E = numpy.array([4], dtype=numpy.int64)
F = numpy.array([-1], dtype=numpy.int64)
I = numpy.array([1], dtype=numpy.int64)
# nodes
K = X0
L = numpy.expand_dims(K, axis=2)
M = numpy.transpose(L, axes=(0, 3, 1, 2, 4))
N = X1
O = numpy.expand_dims(N, axis=1)
P = numpy.transpose(O, axes=(0, 3, 1, 2, 4))
Q = numpy.array(M.shape, dtype=numpy.int64)
R = numpy.array(P.shape, dtype=numpy.int64)
S = numpy.take(Q, D, axis=0)
T = numpy.take(R, D, axis=0)
U = S.prod(axis=0, keepdims=1)
V = T.prod(axis=0, keepdims=1)
W = numpy.take(Q, E, axis=0)
X = numpy.take(R, E, axis=0)
Z = numpy.concatenate([U, F, W], 0)
BA = numpy.concatenate([V, F, X], 0)
BB = M.reshape(tuple(Z))
BC = P.reshape(tuple(BA))
BD = numpy.transpose(BC, axes=(0, 2, 1))
BE = BB @ BD
BF = numpy.maximum(S, T)
BG = numpy.take(Q, [2], axis=0)
BH = numpy.take(R, [3], axis=0)
BI = numpy.concatenate([BF, BG, BH, I], 0)
BJ = BE.reshape(tuple(BI))
BK = numpy.transpose(BJ, axes=(0, 1, 3, 4, 2))
BL = numpy.squeeze(BK, axis=3)
BM = BL
Y = BM
return Y
[runpythonerror]
0%| | 0/121 [00:00<?, ?it/s]
4.5 mlbest='bsnh,btnh->bnts': 0%| | 0/121 [00:00<?, ?it/s]
4.5 mlbest='bsnh,btnh->bnts': 1%| | 1/121 [00:00<01:13, 1.63it/s]
4.5 mlbest='bsnh,btnh->bnts': 3%|▎ | 4/121 [00:00<00:16, 6.92it/s]
4.5 mlbest='bnth,bsth->btsn': 3%|▎ | 4/121 [00:00<00:16, 6.92it/s]
4.5 mlbest='bnth,bsth->btsn': 6%|▌ | 7/121 [00:00<00:09, 11.68it/s]
4.5 mlbest='bnth,bsth->btsn': 8%|▊ | 10/121 [00:00<00:07, 15.80it/s]
4.5 mlbest='bnht,bsht->bhsn': 8%|▊ | 10/121 [00:00<00:07, 15.80it/s]
4.5 mlbest='bnht,bsht->bhsn': 11%|█ | 13/121 [00:01<00:05, 19.26it/s]
4.5 mlbest='bhtn,bstn->btsh': 11%|█ | 13/121 [00:01<00:05, 19.26it/s]
4.5 mlbest='bhtn,bstn->btsh': 13%|█▎ | 16/121 [00:01<00:04, 21.85it/s]
4.5 mlbest='bhts,bnts->btnh': 13%|█▎ | 16/121 [00:01<00:04, 21.85it/s]
4.5 mlbest='bhts,bnts->btnh': 16%|█▌ | 19/121 [00:01<00:04, 23.51it/s]
4.5 mlbest='bhts,bnts->btnh': 18%|█▊ | 22/121 [00:01<00:03, 25.13it/s]
4.5 mlbest='bhts,bnts->btnh': 21%|██ | 25/121 [00:01<00:03, 26.39it/s]
4.5 mlbest='bhts,bnts->btnh': 23%|██▎ | 28/121 [00:01<00:03, 27.30it/s]
4.5 mlbest='bhts,bnts->btnh': 26%|██▌ | 31/121 [00:01<00:03, 27.90it/s]
4.5 mlbest='bhts,bnts->btnh': 28%|██▊ | 34/121 [00:01<00:03, 27.72it/s]
4.5 mlbest='bhts,bnts->btnh': 31%|███ | 37/121 [00:01<00:02, 28.15it/s]
4.5 mlbest='bhts,bnts->btnh': 33%|███▎ | 40/121 [00:01<00:02, 28.50it/s]
4.5 mlbest='bhts,bnts->btnh': 36%|███▌ | 43/121 [00:02<00:02, 28.76it/s]
4.5 mlbest='bhts,bnts->btnh': 38%|███▊ | 46/121 [00:02<00:02, 28.39it/s]
4.5 mlbest='bhts,bnts->btnh': 40%|████ | 49/121 [00:02<00:02, 28.60it/s]
4.5 mlbest='bhts,bnts->btnh': 43%|████▎ | 52/121 [00:02<00:02, 28.82it/s]
4.5 mlbest='bhts,bnts->btnh': 45%|████▌ | 55/121 [00:02<00:02, 29.13it/s]
4.5 mlbest='bhts,bnts->btnh': 48%|████▊ | 58/121 [00:02<00:02, 29.21it/s]
4.5 mlbest='bhts,bnts->btnh': 50%|█████ | 61/121 [00:02<00:02, 28.61it/s]
4.5 mlbest='bhts,bnts->btnh': 53%|█████▎ | 64/121 [00:02<00:01, 28.74it/s]
4.5 mlbest='bhts,bnts->btnh': 55%|█████▌ | 67/121 [00:02<00:01, 28.88it/s]
4.5 mlbest='bhts,bnts->btnh': 58%|█████▊ | 70/121 [00:02<00:01, 29.01it/s]
4.5 mlbest='bhts,bnts->btnh': 60%|██████ | 73/121 [00:03<00:01, 29.15it/s]
4.5 mlbest='bhts,bnts->btnh': 63%|██████▎ | 76/121 [00:03<00:01, 23.18it/s]
4.5 mlbest='bhts,bnts->btnh': 65%|██████▌ | 79/121 [00:03<00:01, 24.76it/s]
4.5 mlbest='bhts,bnts->btnh': 68%|██████▊ | 82/121 [00:03<00:01, 25.98it/s]
4.5 mlbest='bhts,bnts->btnh': 70%|███████ | 85/121 [00:03<00:01, 26.94it/s]
4.5 mlbest='bhts,bnts->btnh': 73%|███████▎ | 88/121 [00:03<00:01, 27.66it/s]
4.5 mlbest='bhts,bnts->btnh': 75%|███████▌ | 91/121 [00:03<00:01, 27.53it/s]
4.5 mlbest='bhts,bnts->btnh': 78%|███████▊ | 94/121 [00:03<00:00, 28.03it/s]
4.5 mlbest='bhts,bnts->btnh': 80%|████████ | 97/121 [00:04<00:00, 28.42it/s]
4.5 mlbest='bhts,bnts->btnh': 83%|████████▎ | 100/121 [00:04<00:00, 28.66it/s]
4.5 mlbest='bhts,bnts->btnh': 85%|████████▌ | 103/121 [00:04<00:00, 28.26it/s]
4.5 mlbest='bhts,bnts->btnh': 88%|████████▊ | 106/121 [00:04<00:00, 28.47it/s]
4.5 mlbest='bhts,bnts->btnh': 90%|█████████ | 109/121 [00:04<00:00, 28.68it/s]
4.5 mlbest='bhts,bnts->btnh': 93%|█████████▎| 112/121 [00:04<00:00, 28.85it/s]
4.5 mlbest='bhts,bnts->btnh': 95%|█████████▌| 115/121 [00:04<00:00, 29.02it/s]
4.5 mlbest='bhts,bnts->btnh': 98%|█████████▊| 118/121 [00:04<00:00, 28.49it/s]
4.5 mlbest='bhts,bnts->btnh': 100%|██████████| 121/121 [00:04<00:00, 28.68it/s]
4.5 mlbest='bhts,bnts->btnh': 100%|██████████| 121/121 [00:04<00:00, 24.95it/s]
The optimization was done for onnxruntime, that does not guarantee the result will be faster than with numpy.einsum. Let’s check…
<<<
import pprint
import numpy
from mlprodict.onnx_tools.exports.numpy_helper import (
argmin_use_numpy_select_last_index,
make_slice)
from cpyquickhelper.numbers.speed_measure import measure_time
def numpy_einsum(X1, X2):
'''
Numpy function for ``einsum``.
* producer: mlprodict
* version: 0
* description:
'''
# initializers
B = numpy.array([4], dtype=numpy.int64)
C = numpy.array([3], dtype=numpy.int64)
D = numpy.array([0, 1], dtype=numpy.int64)
E = numpy.array([4], dtype=numpy.int64)
F = numpy.array([-1], dtype=numpy.int64)
G = numpy.array([2], dtype=numpy.int64)
H = numpy.array([3], dtype=numpy.int64)
I = numpy.array([1], dtype=numpy.int64)
J = numpy.array([1], dtype=numpy.int64)
# nodes
K = X1
L = numpy.expand_dims(K, axis=tuple(B))
M = numpy.transpose(L, axes=(0, 2, 1, 4, 3))
N = X2
O = numpy.expand_dims(N, axis=tuple(C))
P = numpy.transpose(O, axes=(0, 2, 3, 1, 4))
Q = numpy.array(M.shape, dtype=numpy.int64)
R = numpy.array(P.shape, dtype=numpy.int64)
S = numpy.take(Q, D, axis=0)
T = numpy.take(R, D, axis=0)
U = S.prod(axis=0, keepdims=1)
V = T.prod(axis=0, keepdims=1)
W = numpy.take(Q, E, axis=0)
X = numpy.take(R, E, axis=0)
Z = numpy.concatenate([U, F, W], 0)
BA = numpy.concatenate([V, F, X], 0)
BB = M.reshape(tuple(Z))
BC = P.reshape(tuple(BA))
BD = numpy.transpose(BC, axes=(0, 2, 1))
BE = BB @ BD
BF = numpy.maximum(S, T)
BG = numpy.take(Q, G, axis=0)
BH = numpy.take(R, H, axis=0)
BI = numpy.concatenate([BF, BG, BH, I], 0)
BJ = BE.reshape(tuple(BI))
BK = numpy.transpose(BJ, axes=(0, 4, 1, 3, 2))
BL = numpy.squeeze(BK, axis=tuple(J))
BM = BL
Y = BM
return Y
def numpy_einsum_opt(X0, X1):
'''
Numpy function for ``einsum``.
* producer: mlprodict
* version: 0
* description:
'''
# initializers
B = numpy.array([2], dtype=numpy.int64)
C = numpy.array([1], dtype=numpy.int64)
D = numpy.array([0, 1], dtype=numpy.int64)
E = numpy.array([4], dtype=numpy.int64)
F = numpy.array([-1], dtype=numpy.int64)
G = numpy.array([2], dtype=numpy.int64)
H = numpy.array([3], dtype=numpy.int64)
I = numpy.array([1], dtype=numpy.int64)
J = numpy.array([3], dtype=numpy.int64)
# nodes
K = X0
L = numpy.expand_dims(K, axis=tuple(B))
M = numpy.transpose(L, axes=(0, 3, 1, 2, 4))
N = X1
O = numpy.expand_dims(N, axis=tuple(C))
P = numpy.transpose(O, axes=(0, 3, 1, 2, 4))
Q = numpy.array(M.shape, dtype=numpy.int64)
R = numpy.array(P.shape, dtype=numpy.int64)
S = numpy.take(Q, D, axis=0)
T = numpy.take(R, D, axis=0)
U = S.prod(axis=0, keepdims=1)
V = T.prod(axis=0, keepdims=1)
W = numpy.take(Q, E, axis=0)
X = numpy.take(R, E, axis=0)
Z = numpy.concatenate([U, F, W], 0)
BA = numpy.concatenate([V, F, X], 0)
BB = M.reshape(tuple(Z))
BC = P.reshape(tuple(BA))
BD = numpy.transpose(BC, axes=(0, 2, 1))
BE = BB @ BD
BF = numpy.maximum(S, T)
BG = numpy.take(Q, G, axis=0)
BH = numpy.take(R, H, axis=0)
BI = numpy.concatenate([BF, BG, BH, I], 0)
BJ = BE.reshape(tuple(BI))
BK = numpy.transpose(BJ, axes=(0, 1, 3, 4, 2))
BL = numpy.squeeze(BK, axis=tuple(J))
BM = BL
Y = BM
return Y
N = 2
m1 = numpy.random.randn(N, N, N, N)
m2 = numpy.random.randn(N, N, N, N)
print("Discrepencies?")
print(numpy.einsum("bsnh,btnh->bnts", m1, m2))
print(numpy_einsum(m1, m2))
print(numpy_einsum_opt(m1, m2))
N = 20
m1 = numpy.random.randn(N, N, N, N)
m2 = numpy.random.randn(N, N, N, N)
print('numpy.einsum')
res = measure_time(
lambda: numpy.einsum("bsnh,btnh->bnts", m1, m2),
repeat=10, number=20, div_by_number=True,
context={'numpy': numpy, 'm1': m1, 'm2': m2})
pprint.pprint(res)
print('numpy.einsum decomposed')
res = measure_time(
lambda: numpy_einsum(m1, m2),
repeat=10, number=20, div_by_number=True,
context={'numpy': numpy, 'm1': m1, 'm2': m2,
'numpy_einsum': numpy_einsum})
pprint.pprint(res)
print('numpy.einsum decomposed and optimized')
res = measure_time(
lambda: numpy_einsum_opt(m1, m2),
repeat=10, number=20, div_by_number=True,
context={'numpy': numpy, 'm1': m1, 'm2': m2,
'numpy_einsum_opt': numpy_einsum_opt})
pprint.pprint(res)
>>>
Discrepencies?
[[[[-0.46 0.462]
[-0.425 1.087]]
[[-0.304 0.575]
[ 5.612 3.466]]]
[[[-0.483 -0.565]
[ 0.701 0.709]]
[[-0.24 -0.616]
[-0.445 -0.554]]]]
[[[[-0.46 0.462]
[-0.425 1.087]]
[[-0.304 0.575]
[ 5.612 3.466]]]
[[[-0.483 -0.565]
[ 0.701 0.709]]
[[-0.24 -0.616]
[-0.445 -0.554]]]]
[[[[-0.46 0.462]
[-0.425 1.087]]
[[-0.304 0.575]
[ 5.612 3.466]]]
[[[-0.483 -0.565]
[ 0.701 0.709]]
[[-0.24 -0.616]
[-0.445 -0.554]]]]
numpy.einsum
{'average': 0.01419631954282522,
'context_size': 232,
'deviation': 5.4772999836583715e-05,
'max_exec': 0.014357361570000648,
'min_exec': 0.014166636485606432,
'number': 20,
'repeat': 10,
'ttime': 0.1419631954282522}
numpy.einsum decomposed
{'average': 0.01210633552633226,
'context_size': 232,
'deviation': 2.5750270798727405e-05,
'max_exec': 0.012126228213310242,
'min_exec': 0.012032157275825739,
'number': 20,
'repeat': 10,
'ttime': 0.1210633552633226}
numpy.einsum decomposed and optimized
{'average': 0.0121294676233083,
'context_size': 232,
'deviation': 5.37366503508202e-06,
'max_exec': 0.012139513622969389,
'min_exec': 0.012121503800153732,
'number': 20,
'repeat': 10,
'ttime': 0.121294676233083}
The optimization is not faster than the first decomposition but the decomposition is faster than the numpy implementation.