Pourquoi numpy.any est-il si lent sur les grands tableaux?

Question

Je suis à la recherche de la façon la plus efficace pour déterminer si un grand tableau contient au moins une valeur différente de zéro. Au premier coup d'œil np.any semble être la outil idéal pour le travail, mais il semble lent de façon inattendue sur de grands tableaux.

Considérer ce cas extrême:

first = np.zeros(1E3,dtype=np.bool)
last = np.zeros(1E3,dtype=np.bool)

first[0] = True
last[-1] = True

# test 1
%timeit np.any(first)
>>> 100000 loops, best of 3: 6.36 us per loop

# test 2
%timeit np.any(last)
>>> 100000 loops, best of 3: 6.95 us per loop

Au moins np.any semble être de faire quelque chose de vaguement sensible ici - si l' valeur différente de zéro est le premier dans le tableau, il ne devrait pas être nécessaire de considérer tout les autres avant de revenir True, donc je m'attends test 1 pour être légèrement plus rapide que le test 2.

Cependant, ce qui se passe lorsque nous faisons des tableaux beaucoup plus grande?

first = np.zeros(1E9,dtype=np.bool)
last = np.zeros(1E9,dtype=np.bool)

first[0] = True
last[-1] = True

# test 3
%timeit np.any(first)
>>> 10 loops, best of 3: 21.6 ms per loop

# test 4
%timeit np.any(last)
>>> 1 loops, best of 3: 739 ms per loop

Comme prévu, test 4 est beaucoup plus lent que le test 3. Toutefois, dans le test 3 np.any devrait toujours avoir seulement pour vérifier la valeur d'un élément unique dans first , pour savoir qu'il contient au moins une valeur différente de zéro. Pourquoi, ensuite, c'est de tester 3 donc beaucoup plus lent que le test 1?

Edit 1:

Je suis à l'aide d'une version de développement de Numpy (1.8.0.dev-e11cd9b), mais j'obtiens exactement le même chrono résultats à l'aide de Numpy 1.7.1. Je suis en cours d'exécution 64 bits de Linux, Python 2.7.4. Mon système est à la base de la marche au ralenti (je suis à court d'une IPython session, un navigateur et un éditeur de texte), et je ne suis certainement pas frapper le swap. J'ai aussi reproduit le résultat sur une autre machine sous Numpy 1.7.1.

Edit 2:

Utilisation de Numpy 1.6.2-je obtenir des moments de ~1.85 nous pour les deux tests 1 et 3, ainsi que jorgeca dit, il semble y avoir eu une certaine régression de la performance entre Numpy 1.6.2 et 1.7.1 1.7.0 à cet égard.

Edit 3:

Suivant J. F. Sebastian et jorgeca de plomb, j'ai fait un peu plus d'analyse comparative à l'aide de np.all sur un tableau de zéros, ce qui devrait être équivalent à l'appel de np.any sur un tableau dont le premier élément est un.

Script de Test:

import timeit
import numpy as np
print 'Numpy v%s' %np.version.full_version
stmt = "np.all(x)"
for ii in xrange(10):
    setup = "import numpy as np; x = np.zeros(%d,dtype=np.bool)" %(10**ii)
    timer = timeit.Timer(stmt,setup)
    n,r = 1,3
    t = np.min(timer.repeat(r,n))
    while t < 0.2:
        n *= 10
        t = np.min(timer.repeat(r,n))
    t /= n
    if t < 1E-3:
        timestr = "%1.3f us" %(t*1E6)
    elif t < 1:
        timestr = "%1.3f ms" %(t*1E3)
    else:
        timestr = "%1.3f s" %t
    print "Array size: 1E%i, %i loops, best of %i: %s/loop" %(ii,n,r,timestr)

Résultats:

Numpy v1.6.2
Array size: 1E0, 1000000 loops, best of 3: 1.738 us/loop
Array size: 1E1, 1000000 loops, best of 3: 1.845 us/loop
Array size: 1E2, 1000000 loops, best of 3: 1.862 us/loop
Array size: 1E3, 1000000 loops, best of 3: 1.858 us/loop
Array size: 1E4, 1000000 loops, best of 3: 1.864 us/loop
Array size: 1E5, 1000000 loops, best of 3: 1.882 us/loop
Array size: 1E6, 1000000 loops, best of 3: 1.866 us/loop
Array size: 1E7, 1000000 loops, best of 3: 1.853 us/loop
Array size: 1E8, 1000000 loops, best of 3: 1.860 us/loop
Array size: 1E9, 1000000 loops, best of 3: 1.854 us/loop

Numpy v1.7.0
Array size: 1E0, 100000 loops, best of 3: 5.881 us/loop
Array size: 1E1, 100000 loops, best of 3: 5.831 us/loop
Array size: 1E2, 100000 loops, best of 3: 5.924 us/loop
Array size: 1E3, 100000 loops, best of 3: 5.864 us/loop
Array size: 1E4, 100000 loops, best of 3: 5.997 us/loop
Array size: 1E5, 100000 loops, best of 3: 6.979 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.196 us/loop
Array size: 1E7, 10000 loops, best of 3: 116.162 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.112 ms/loop
Array size: 1E9, 100 loops, best of 3: 11.061 ms/loop

Numpy v1.7.1
Array size: 1E0, 100000 loops, best of 3: 6.216 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.257 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.318 us/loop
Array size: 1E3, 100000 loops, best of 3: 6.247 us/loop
Array size: 1E4, 100000 loops, best of 3: 6.492 us/loop
Array size: 1E5, 100000 loops, best of 3: 7.406 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.426 us/loop
Array size: 1E7, 10000 loops, best of 3: 115.946 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.102 ms/loop
Array size: 1E9, 100 loops, best of 3: 10.987 ms/loop

Numpy v1.8.0.dev-e11cd9b
Array size: 1E0, 100000 loops, best of 3: 6.357 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.399 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.425 us/loop
Array size: 1E3, 100000 loops, best of 3: 6.397 us/loop
Array size: 1E4, 100000 loops, best of 3: 6.596 us/loop
Array size: 1E5, 100000 loops, best of 3: 7.569 us/loop
Array size: 1E6, 100000 loops, best of 3: 17.445 us/loop
Array size: 1E7, 10000 loops, best of 3: 115.109 us/loop
Array size: 1E8, 1000 loops, best of 3: 1.094 ms/loop
Array size: 1E9, 100 loops, best of 3: 10.840 ms/loop

Edit 4:

Suivant seberg, le commentaire que j'ai essayé le même test avec un np.float32 tableau au lieu de np.bool. Dans ce cas, Numpy 1.6.2 montre également une période de ralentissement de la matrice de l'augmentation de la taille:

Numpy v1.6.2
Array size: 1E0, 100000 loops, best of 3: 3.503 us/loop
Array size: 1E1, 100000 loops, best of 3: 3.597 us/loop
Array size: 1E2, 100000 loops, best of 3: 3.742 us/loop
Array size: 1E3, 100000 loops, best of 3: 4.745 us/loop
Array size: 1E4, 100000 loops, best of 3: 14.533 us/loop
Array size: 1E5, 10000 loops, best of 3: 112.463 us/loop
Array size: 1E6, 1000 loops, best of 3: 1.101 ms/loop
Array size: 1E7, 100 loops, best of 3: 11.724 ms/loop
Array size: 1E8, 10 loops, best of 3: 116.924 ms/loop
Array size: 1E9, 1 loops, best of 3: 1.168 s/loop

Numpy v1.7.1
Array size: 1E0, 100000 loops, best of 3: 6.548 us/loop
Array size: 1E1, 100000 loops, best of 3: 6.546 us/loop
Array size: 1E2, 100000 loops, best of 3: 6.804 us/loop
Array size: 1E3, 100000 loops, best of 3: 7.784 us/loop
Array size: 1E4, 100000 loops, best of 3: 17.946 us/loop
Array size: 1E5, 10000 loops, best of 3: 117.235 us/loop
Array size: 1E6, 1000 loops, best of 3: 1.096 ms/loop
Array size: 1E7, 100 loops, best of 3: 12.328 ms/loop
Array size: 1E8, 10 loops, best of 3: 118.431 ms/loop
Array size: 1E9, 1 loops, best of 3: 1.172 s/loop

Pourquoi devrait-il se produire? Comme avec le booléen cas, np.all devrait toujours avoir seulement pour vérifier le premier élément avant de revenir, tant de fois doit toujours être constante w.r.t. taille de la matrice.

Answer 1

Comme l'a deviné dans les commentaires, je peux confirmer que le traitement de la matrice qui est fait dans les morceaux. Tout d'abord, je vais vous montrer où en sont les choses dans le code et ensuite, je vais vous montrer comment vous pouvez changer la taille de bloc et de l'effet que cela a sur votre référence.

Où trouver le traitement de réduction de la Numpy fichiers source

np.tous les(x) est le même que x.tous les(). tous les() vraiment les appels np.de base.umath.logical_and.réduire(x).

Si vous voulez plonger dans la numpy source, je vais essayer de vous guider à travers la recherche d'un tampon/taille de segment est utilisé. Le dossier avec tous les code que nous allons regarder est numpy/base/src/umath/.

PyUFunc_Reduce() dans ufunc_object.c est la fonction C qui gère le réduire. Dans PyUFunc_Reduce(), le bloc ou le tampon, la taille est trouvé par la recherche de la valeur pour réduire dans certaines régions du globe dictionnaire via le PyUFunc_GetPyValues() fonction (ufunc_object.c). Sur ma machine et de la compilation de la branche de développement, la taille de bloc est de 8192. PyUFunc_ReduceWrapper() dans la réduction.c est appelé pour mettre en place l'itérateur (avec une foulée égale à la taille de bloc) et il appelle le passé en fonction de boucle qui est reduce_loop() dans ufunc_object.c.

reduce_loop() fondamentalement juste utilise l'itérateur et appelle une autre innerloop() fonction pour chaque morceau. Le innerloop fonction se trouve dans les boucles.c.src. Pour un booléen tableau et notre affaire de tous/logical_and, le innerloop fonction est BOOL_logical_and. Vous pouvez trouver le droit de la fonction par la recherche BOOLÉENNE BOUCLES et puis c'est la deuxième fonction en dessous (c'est dur à trouver en raison du modèle de programmation de type utilisé ici). Là, vous trouverez que le court-circuit est, en fait, faire de même pour chaque morceau.

Comment modifier la taille de la mémoire tampon utilisée dans ufunctions (et donc en toute/tous)

Vous pouvez obtenir le morceau/taille de la mémoire tampon avec np.getbuffersize(). Pour moi, qui renvoie 8192 sans manuellement le paramètre qui correspond à ce que j'ai trouvé par l'impression de la taille de la mémoire tampon dans le code. Vous pouvez utiliser np.setbuffersize() pour changer la taille de bloc.

Les résultats à l'aide d'une plus grande taille de la mémoire tampon

J'ai changé votre test code de la manière suivante:

import timeit
import numpy as np
print 'Numpy v%s' %np.version.full_version
stmt = "np.all(x)"
for ii in xrange(9):
    setup = "import numpy as np; x = np.zeros(%d,dtype=np.bool); np.setbufsize(%d)" %(10**ii, max(8192, min(10**ii, 10**7)))
    timer = timeit.Timer(stmt,setup)
    n,r = 1,3
    t = np.min(timer.repeat(r,n))
    while t < 0.2:
        n *= 10
        t = np.min(timer.repeat(r,n))
    t /= n
    if t < 1E-3:
        timestr = "%1.3f us" %(t*1E6)
    elif t < 1:
        timestr = "%1.3f ms" %(t*1E3)
    else:
        timestr = "%1.3f s" %t
    print "Array size: 1E%i, %i loops, best of %i: %s/loop" %(ii,n,r,timestr)

Numpy n'aime pas la taille de la mémoire tampon trop petit ou trop grand donc j'ai fait en sorte que cela n'a pas plus petit que 8192 ou plus grand que 1E7 parce que Numpy n'est pas comme une taille de mémoire tampon de 1E8. Sinon, j'ai été réglage de la taille de la mémoire tampon de la taille du tableau en cours de traitement. Je ne suis allé jusqu'à 1E8 parce que ma machine a seulement 4 go de mémoire en ce moment. Voici les résultats:

Numpy v1.8.0.dev-2a5c2c8
Array size: 1E0, 100000 loops, best of 3: 5.351 us/loop
Array size: 1E1, 100000 loops, best of 3: 5.390 us/loop
Array size: 1E2, 100000 loops, best of 3: 5.366 us/loop
Array size: 1E3, 100000 loops, best of 3: 5.360 us/loop
Array size: 1E4, 100000 loops, best of 3: 5.433 us/loop
Array size: 1E5, 100000 loops, best of 3: 5.400 us/loop
Array size: 1E6, 100000 loops, best of 3: 5.397 us/loop
Array size: 1E7, 100000 loops, best of 3: 5.381 us/loop
Array size: 1E8, 100000 loops, best of 3: 6.126 us/loop

Il y a une petite remontée dans le dernier calendrier parce qu'il y a plusieurs morceaux en cours de traitement, en raison de limitations sur la taille de la taille de la mémoire tampon peut être.