Pourquoi einsum de numpy est-il plus rapide que les fonctions intégrées de numpy?

Question

Permet de commencer avec trois tableaux de dtype=np.double. Les Timings sont exécutées sur un PROCESSEUR intel à l'aide de numpy 1.7.1 compilé avec icc et lié à intel mkl. Un cpu AMD avec numpy 1.6.1 compilé avec gcc sans mkl a également été utilisé pour vérifier les horaires. Veuillez noter les horaires d'échelle près linéairement avec la taille du système et ne sont pas dues à la faible surcharge engagés dans les fonctions de numpy if des déclarations de ces différences apparaîtront dans microsecondes pas millisecondes:

arr_1D=np.arange(500,dtype=np.double)
large_arr_1D=np.arange(100000,dtype=np.double)
arr_2D=np.arange(500**2,dtype=np.double).reshape(500,500)
arr_3D=np.arange(500**3,dtype=np.double).reshape(500,500,500)

La première permet de regarder le np.sum fonction de:

np.all(np.sum(arr_3D)==np.einsum('ijk->',arr_3D))
True

%timeit np.sum(arr_3D)
10 loops, best of 3: 142 ms per loop

%timeit np.einsum('ijk->', arr_3D)
10 loops, best of 3: 70.2 ms per loop

Pouvoirs:

np.allclose(arr_3D*arr_3D*arr_3D,np.einsum('ijk,ijk,ijk->ijk',arr_3D,arr_3D,arr_3D))
True

%timeit arr_3D*arr_3D*arr_3D
1 loops, best of 3: 1.32 s per loop

%timeit np.einsum('ijk,ijk,ijk->ijk', arr_3D, arr_3D, arr_3D)
1 loops, best of 3: 694 ms per loop

Produit extérieur:

np.all(np.outer(arr_1D,arr_1D)==np.einsum('i,k->ik',arr_1D,arr_1D))
True

%timeit np.outer(arr_1D, arr_1D)
1000 loops, best of 3: 411 us per loop

%timeit np.einsum('i,k->ik', arr_1D, arr_1D)
1000 loops, best of 3: 245 us per loop

Tous les ci-dessus sont deux fois plus rapide avec l' np.einsum. Ceux-ci devraient être des pommes à des pommes de comparaisons comme tout ce qui est spécifiquement de l' dtype=np.double. J'attendrais la vitesse dans une opération comme celle-ci:

np.allclose(np.sum(arr_2D*arr_3D),np.einsum('ij,oij->',arr_2D,arr_3D))
True

%timeit np.sum(arr_2D*arr_3D)
1 loops, best of 3: 813 ms per loop

%timeit np.einsum('ij,oij->', arr_2D, arr_3D)
10 loops, best of 3: 85.1 ms per loop

Einsum semble être au moins deux fois plus rapide pour np.inner, np.outer, np.kron, et np.sum , indépendamment de l' axes sélection. La principale exception étant l' np.dot comme elle les appelle DGEMM à partir d'une bibliothèque BLAS. Alors, pourquoi est - np.einsum plus rapide que les autres fonctions de numpy qui sont équivalents?

Le DGEMM cas pour l'exhaustivité:

np.allclose(np.dot(arr_2D,arr_2D),np.einsum('ij,jk',arr_2D,arr_2D))
True

%timeit np.einsum('ij,jk',arr_2D,arr_2D)
10 loops, best of 3: 56.1 ms per loop

%timeit np.dot(arr_2D,arr_2D)
100 loops, best of 3: 5.17 ms per loop

---

Le leader de la théorie de @sebergs commentaire qu' np.einsum pouvez faire usage de SSE2, mais numpy est ufuncs ne sera pas jusqu'à ce que numpy 1.8 (voir le journal des modifications). Je crois que c'est la bonne réponse, mais n'ont pas été en mesure de le confirmer. Certains ont limité la preuve peut être trouvée par la modification de la dtype de tableau d'entrée, et en observant la différence de vitesse et le fait que pas tout le monde observe les mêmes tendances dans les horaires.

Answer 1

Tout d'abord, il y a eu beaucoup de passé de discussion à ce sujet sur le numpy liste. Par exemple, voir: http://numpy-discussion.10968.n7.nabble.com/poor-performance-of-sum-with-sub-machine-word-integer-types-td41.html http://numpy-discussion.10968.n7.nabble.com/odd-performance-of-sum-td3332.html

Certains se résume au fait qu' einsum est nouveau, et est sans doute essayer d'être meilleurs sur le cache de l'alignement et de la mémoire d'autres problèmes d'accès, tandis que bon nombre d'anciennes fonctions de numpy se concentrer sur un portable facilement mise en œuvre sur une fortement optimisé. Je suis juste en spéculant, là, si.

---

Cependant, certains de ce que vous faites n'est pas tout à fait une "des pommes avec des pommes" de comparaison.

En plus de ce que @Jamie déjà dit, sum utilise le plus approprié accumulateur pour les tableaux

Par exemple, sum est plus prudent de vérifier le type de l'entrée et un accumulateur. Par exemple, considérez les points suivants:

In [1]: x = 255 * np.ones(100, dtype=np.uint8)

In [2]: x
Out[2]:
array([255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
       255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
       255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
       255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
       255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
       255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
       255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
       255, 255, 255, 255, 255, 255, 255, 255, 255], dtype=uint8)

Notez que l' sum est correct:

In [3]: x.sum()
Out[3]: 25500

Alors qu' einsum donnera le mauvais résultat:

In [4]: np.einsum('i->', x)
Out[4]: 156

Mais si nous utilisons moins limiter dtype, nous allons continuer à obtenir le résultat que vous attendez:

In [5]: y = 255 * np.ones(100)

In [6]: np.einsum('i->', y)
Out[6]: 25500.0

Answer 2

Maintenant que numpy 1.8 est sorti, où, selon les docs tous ufuncs doit utiliser SSE2, je voulais vérifier que Seberg, du commentaire à propos de SSE2 était valide.

Pour effectuer le test un nouveau python 2.7 installation a été créé - numpy 1.7 et 1.8 ont été compilés avec icc à l'aide des options standard sur un AMD opteron de base sous Ubuntu.

C'est un essai à la fois avant et après la 1.8 mise à niveau:

import numpy as np
import timeit

arr_1D=np.arange(5000,dtype=np.double)
arr_2D=np.arange(500**2,dtype=np.double).reshape(500,500)
arr_3D=np.arange(500**3,dtype=np.double).reshape(500,500,500)

print 'Summation test:'
print timeit.timeit('np.sum(arr_3D)',
                      'import numpy as np; from __main__ import arr_1D, arr_2D, arr_3D',
                      number=5)/5
print timeit.timeit('np.einsum("ijk->", arr_3D)',
                      'import numpy as np; from __main__ import arr_1D, arr_2D, arr_3D',
                      number=5)/5
print '----------------------\n'


print 'Power test:'
print timeit.timeit('arr_3D*arr_3D*arr_3D',
                      'import numpy as np; from __main__ import arr_1D, arr_2D, arr_3D',
                      number=5)/5
print timeit.timeit('np.einsum("ijk,ijk,ijk->ijk", arr_3D, arr_3D, arr_3D)',
                      'import numpy as np; from __main__ import arr_1D, arr_2D, arr_3D',
                      number=5)/5
print '----------------------\n'


print 'Outer test:'
print timeit.timeit('np.outer(arr_1D, arr_1D)',
                      'import numpy as np; from __main__ import arr_1D, arr_2D, arr_3D',
                      number=5)/5
print timeit.timeit('np.einsum("i,k->ik", arr_1D, arr_1D)',
                      'import numpy as np; from __main__ import arr_1D, arr_2D, arr_3D',
                      number=5)/5
print '----------------------\n'


print 'Einsum test:'
print timeit.timeit('np.sum(arr_2D*arr_3D)',
                      'import numpy as np; from __main__ import arr_1D, arr_2D, arr_3D',
                      number=5)/5
print timeit.timeit('np.einsum("ij,oij->", arr_2D, arr_3D)',
                      'import numpy as np; from __main__ import arr_1D, arr_2D, arr_3D',
                      number=5)/5
print '----------------------\n'

Numpy 1.7.1:

Summation test:
0.172988510132
0.0934836149216
----------------------

Power test:
1.93524689674
0.839519000053
----------------------

Outer test:
0.130380821228
0.121401786804
----------------------

Einsum test:
0.979052495956
0.126066613197

Numpy 1.8:

Summation test:
0.116551589966
0.0920487880707
----------------------

Power test:
1.23683619499
0.815982818604
----------------------

Outer test:
0.131808176041
0.127472200394
----------------------

Einsum test:
0.781750011444
0.129271841049

Je pense que c'est assez concluante que l'ESS joue un grand rôle dans les différences de calendrier, il convient de noter que la répétition de ces tests, les timings très en seulement ~0.003 s. La différence devrait être couverte dans les autres réponses à cette question.

Answer 3

Je pense que ces timings expliquer ce qu'il se passe:

a = np.arange(1000, dtype=np.double)
%timeit np.einsum('i->', a)
100000 loops, best of 3: 3.32 us per loop
%timeit np.sum(a)
100000 loops, best of 3: 6.84 us per loop

a = np.arange(10000, dtype=np.double)
%timeit np.einsum('i->', a)
100000 loops, best of 3: 12.6 us per loop
%timeit np.sum(a)
100000 loops, best of 3: 16.5 us per loop

a = np.arange(100000, dtype=np.double)
%timeit np.einsum('i->', a)
10000 loops, best of 3: 103 us per loop
%timeit np.sum(a)
10000 loops, best of 3: 109 us per loop

Donc en gros, vous avez à peu près constante 3us surcharge lors de l'appel d' np.sum sur np.einsum, donc ils se sont contentés de courir aussi vite, mais on prend un peu plus de temps à démarrer. Pourquoi pourrait-il être? Mon argent est sur les points suivants:

a = np.arange(1000, dtype=object)
%timeit np.einsum('i->', a)
Traceback (most recent call last):
...
TypeError: invalid data type for einsum
%timeit np.sum(a)
10000 loops, best of 3: 20.3 us per loop

Pas sûr de ce qui se passe exactement, mais il semble qu' np.einsum est de sauter quelques vérifications pour extraire le type de fonctions spécifiques pour faire les multiplications et d'additions, et va directement avec * et + pour la norme C types seulement.

---

Les multiples cas ne sont pas différents:

n = 10; a = np.arange(n**3, dtype=np.double).reshape(n, n, n)
%timeit np.einsum('ijk->', a)
100000 loops, best of 3: 3.79 us per loop
%timeit np.sum(a)
100000 loops, best of 3: 7.33 us per loop

n = 100; a = np.arange(n**3, dtype=np.double).reshape(n, n, n)
%timeit np.einsum('ijk->', a)
1000 loops, best of 3: 1.2 ms per loop
%timeit np.sum(a)
1000 loops, best of 3: 1.23 ms per loop

Donc, essentiellement constant, les frais généraux, pas d'aller plus vite une fois qu'ils obtiennent.