arrayfun peut être beaucoup plus lent qu'une boucle explicite dans matlab. Pourquoi?

105

Considérez le test de vitesse simple suivant pour arrayfun:

T = 4000;
N = 500;
x = randn(T, N);
Func1 = @(a) (3*a^2 + 2*a - 1);

tic
Soln1 = ones(T, N);
for t = 1:T
    for n = 1:N
        Soln1(t, n) = Func1(x(t, n));
    end
end
toc

tic
Soln2 = arrayfun(Func1, x);
toc

Sur ma machine (Matlab 2011b sous Linux Mint 12), le résultat de ce test est:

Elapsed time is 1.020689 seconds.
Elapsed time is 9.248388 seconds.

Qu'est-ce que?!? arrayfun, bien que certes une solution d'apparence plus propre, est un ordre de grandeur plus lent. Qu'est-ce qui se passe ici?

De plus, j'ai fait un style de test similaire pour cellfunet j'ai trouvé qu'il était environ 3 fois plus lent qu'une boucle explicite. Encore une fois, ce résultat est le contraire de ce à quoi je m'attendais.

Ma question est: pourquoi arrayfunet cellfuntellement plus lent? Et compte tenu de cela, y a-t-il de bonnes raisons de les utiliser (autre que pour rendre le code beau)?

Remarque: je parle de la version standard d' arrayfunici, PAS de la version GPU de la boîte à outils de traitement parallèle.

EDIT: Juste pour être clair, je suis conscient que Func1ci - dessus peut être vectorisé comme l'a souligné Oli. Je l'ai choisi uniquement parce qu'il donne un simple test de vitesse aux fins de la question réelle.

EDIT: Suite à la suggestion de grungetta, j'ai refait le test avec feature accel off. Les résultats sont:

Elapsed time is 28.183422 seconds.
Elapsed time is 23.525251 seconds.

En d'autres termes, il semblerait qu'une grande partie de la différence réside dans le fait que l'accélérateur JIT accélère bien mieux la forboucle explicite qu'il ne le fait arrayfun. Cela me semble étrange, car arrayfunfournit en fait plus d'informations, c'est-à-dire que son utilisation révèle que l'ordre des appels Func1n'a pas d'importance. De plus, j'ai noté que, que l'accélérateur JIT soit activé ou désactivé, mon système n'utilise qu'un seul processeur ...

Colin T Bowers
la source
10
Heureusement, la «solution standard» reste de loin la plus rapide: tic; 3 * x. ^ 2 + 2 * x-1; toc Le temps écoulé est de 0,030662 secondes.
Oli
4
@Oli Je suppose que j'aurais dû m'attendre à ce que quelqu'un le souligne et utilise une fonction qui ne peut pas être vectorisée :-)
Colin T Bowers
3
Je serais intéressé de voir comment ce timing change lorsque l'accélérateur JIT est désactivé. Exécutez la commande 'feature accel off', puis relancez votre test.
grungetta
@grungetta Suggestion intéressante. J'ai ajouté les résultats à la question avec quelques commentaires.
Colin T Bowers

Réponses:

101

Vous pouvez avoir l'idée en exécutant d'autres versions de votre code. Envisagez d'écrire explicitement les calculs, au lieu d'utiliser une fonction dans votre boucle

tic
Soln3 = ones(T, N);
for t = 1:T
    for n = 1:N
        Soln3(t, n) = 3*x(t, n)^2 + 2*x(t, n) - 1;
    end
end
toc

Il est temps de calculer sur mon ordinateur:

Soln1  1.158446 seconds.
Soln2  10.392475 seconds.
Soln3  0.239023 seconds.
Oli    0.010672 seconds.

Maintenant, alors que la solution entièrement «vectorisée» est clairement la plus rapide, vous pouvez voir que la définition d'une fonction à appeler pour chaque entrée x est une surcharge énorme . Le simple fait d'écrire explicitement le calcul nous a permis d'accélérer le facteur 5. Je suppose que cela montre que le compilateur MATLABs JIT ne prend pas en charge les fonctions en ligne . D'après la réponse de gnovice, il est en fait préférable d'écrire une fonction normale plutôt qu'une fonction anonyme. Essayez-le.

Étape suivante - supprimer (vectoriser) la boucle interne:

tic
Soln4 = ones(T, N);
for t = 1:T
    Soln4(t, :) = 3*x(t, :).^2 + 2*x(t, :) - 1;
end
toc

Soln4  0.053926 seconds.

Un autre facteur d'accélération 5: il y a quelque chose dans ces déclarations disant que vous devriez éviter les boucles dans MATLAB ... Ou y a-t-il vraiment? Jetez un oeil à ceci alors

tic
Soln5 = ones(T, N);
for n = 1:N
    Soln5(:, n) = 3*x(:, n).^2 + 2*x(:, n) - 1;
end
toc

Soln5   0.013875 seconds.

Beaucoup plus proche de la version «entièrement» vectorisée. Matlab stocke les matrices par colonne. Vous devez toujours (si possible) structurer vos calculs pour qu'ils soient vectorisés «par colonne».

Nous pouvons revenir à Soln3 maintenant. L'ordre des boucles est «par ligne». Permet de le changer

tic
Soln6 = ones(T, N);
for n = 1:N
    for t = 1:T
        Soln6(t, n) = 3*x(t, n)^2 + 2*x(t, n) - 1;
    end
end
toc

Soln6  0.201661 seconds.

Mieux, mais toujours très mauvais. Boucle simple - bon. Double boucle - mauvais. Je suppose que MATLAB a fait un travail décent pour améliorer les performances des boucles, mais la surcharge de la boucle est toujours là. Si vous aviez un travail plus lourd à l'intérieur, vous ne le remarqueriez pas. Mais comme ce calcul est limité par la bande passante mémoire, vous voyez la surcharge de la boucle. Et vous verrez encore plus clairement les frais généraux liés à l'appel de Func1.

Alors quoi de neuf avec arrayfun? Aucune fonction inlinig là non plus, donc beaucoup de frais généraux. Mais pourquoi tant de pire qu'une double boucle imbriquée? En fait, le sujet de l'utilisation de cellfun / arrayfun a été largement discuté à plusieurs reprises (par exemple ici , ici , ici et ici ). Ces fonctions sont simplement lentes, vous ne pouvez pas les utiliser pour de tels calculs à grain fin. Vous pouvez les utiliser pour la brièveté du code et les conversions sophistiquées entre les cellules et les tableaux. Mais la fonction doit être plus lourde que ce que vous avez écrit:

tic
Soln7 = arrayfun(@(a)(3*x(:,a).^2 + 2*x(:,a) - 1), 1:N, 'UniformOutput', false);
toc

Soln7  0.016786 seconds.

Notez que Soln7 est une cellule maintenant .. parfois c'est utile. Les performances du code sont assez bonnes maintenant, et si vous avez besoin d'une cellule en sortie, vous n'avez pas besoin de convertir votre matrice après avoir utilisé la solution entièrement vectorisée.

Alors, pourquoi arrayfun est-il plus lent qu'une simple structure en boucle? Malheureusement, il nous est impossible de le dire avec certitude, car il n'y a pas de code source disponible. Vous ne pouvez que deviner que puisque arrayfun est une fonction à usage général, qui gère toutes sortes de structures de données et d'arguments différents, elle n'est pas nécessairement très rapide dans des cas simples, que vous pouvez directement exprimer sous forme de nids de boucles. D'où viennent les frais généraux, nous ne pouvons pas le savoir. Les frais généraux pourraient-ils être évités grâce à une meilleure mise en œuvre? Peut être pas. Mais malheureusement, la seule chose que nous pouvons faire est d'étudier la performance pour identifier les cas, dans lesquels cela fonctionne bien, et ceux où cela ne fonctionne pas.

Mise à jour Puisque le temps d'exécution de ce test est court, pour obtenir des résultats fiables, j'ai maintenant ajouté une boucle autour des tests:

for i=1:1000
   % compute
end

Quelques temps donnés ci-dessous:

Soln5   8.192912 seconds.
Soln7  13.419675 seconds.
Oli     8.089113 seconds.

Vous voyez que le arrayfun est toujours mauvais, mais au moins pas trois ordres de grandeur pire que la solution vectorisée. D'autre part, une seule boucle avec des calculs par colonne est aussi rapide que la version entièrement vectorisée ... Tout cela a été fait sur un seul processeur. Les résultats pour Soln5 et Soln7 ne changent pas si je passe à 2 cœurs - Dans Soln5, je devrais utiliser un parfor pour le paralléliser. Oubliez l'accélération ... Soln7 ne fonctionne pas en parallèle car arrayfun ne fonctionne pas en parallèle. Olis version vectorisée par contre:

Oli  5.508085 seconds.
angainor
la source
9
Très bonne réponse! Et les liens vers matlab central fournissent tous des lectures très intéressantes. Merci beaucoup.
Colin T Bowers
C'est une belle analyse.
H.Muster
Et une mise à jour intéressante! Cette réponse ne cesse de donner :-)
Colin T Bowers
3
juste un petit commentaire; de retour dans MATLAB 6.5, a cellfunété implémenté sous forme de fichier MEX (avec le code source C disponible à côté). C'était en fait assez simple. Bien sûr, il ne supportait que l'application de l'une des 6 fonctions codées en dur (vous ne pouviez pas passer une poignée de fonction, seulement une chaîne avec un des noms de fonction)
Amro
1
arrayfun + function handle = lent! évitez-les dans un code lourd.
Yvon
-8

C'est parce que !!!!

x = randn(T, N); 

n'est pas du gpuarraytype;

Tout ce que tu as à faire c'est

x = randn(T, N,'gpuArray');
user3932983
la source
2
Je pense que vous devez lire un peu plus attentivement la question et l'excellente réponse de @angainor. Cela n'a rien à voir avec gpuarray. C'est presque certainement la raison pour laquelle cette réponse a été rejetée.
Colin T Bowers
@Colin - Je suis d'accord qu'Angainor est plus complet, mais la réponse ne mentionne pas «gpuArray». Je pense que le «gpuArray» est une bonne contribution ici (si c'est correct). En outre, la question est devenue un peu bâclée avec "Que se passe-t-il ici?" , donc je pense que cela a ouvert la porte à des méthodes supplémentaires telles que la vectorisation des données et leur envoi vers un GPU. Je laisse passer cette réponse car elle pourrait ajouter de la valeur pour les futurs visiteurs. Mes excuses si j'ai fait le mauvais appel.
jww
1
Vous oubliez également le fait que ce gpuarrayn'est pris en charge que pour les cartes graphiques nVidia. S'ils ne disposent pas d'un tel matériel, alors vos conseils (ou leur absence) n'ont aucun sens. -1
rayryeng
D'autre part, gpuarray est le sabre laser de la programmation vectorisée matlab.
MrIO