Une méthode plus rapide pour initialiser des tableaux via une multiplication de masortingce vide? (Matlab)

Je suis tombé sur la façon étrange (à mon avis) que Matlab traite des masortingces vides . Par exemple, si deux masortingces vides sont multipliées, le résultat est le suivant:

zeros(3,0)*zeros(0,3) ans = 0 0 0 0 0 0 0 0 0 

Maintenant, cela m’a déjà pris par surprise, cependant, une recherche rapide m’a amené au lien ci-dessus, et j’ai eu une explication de la logique quelque peu tordue de la raison pour laquelle cela se produit.

Cependant , rien ne m’a préparé à l’observation suivante. Je me suis demandé à quel point ce type de multiplication par rapport à la fonction zeros(n) est-il efficace, par exemple pour l’initialisation? J’ai utilisé le timeit de répondre à ceci:

 f=@() zeros(1000) timeit(f) ans = 0.0033 

contre:

 g=@() zeros(1000,0)*zeros(0,1000) timeit(g) ans = 9.2048e-06 

Les deux ont le même résultat que la masortingce 1000×1000 de zéros de la classe double , mais la multiplication de la masortingce vide on est ~ 350 fois plus rapide! (un résultat similaire se produit en utilisant tic et toc et une boucle)

Comment se peut-il? sont timeit ou tic,toc bluff ou ai-je trouvé un moyen plus rapide d’initialiser les masortingces? (cela a été fait avec matlab 2012a, sur une machine win7-64, intel-i5 650 3.2Ghz …)

MODIFIER:

Après avoir lu vos commentaires, j’ai étudié plus attentivement cette particularité et testé sur deux ordinateurs différents (même matlab ver 2012a) un code qui examine le temps d’exécution par rapport à la taille de la masortingce n. C’est ce que je reçois:

entrer la description de l'image ici

Le code pour générer ce temps utilisé comme précédemment, mais une boucle avec tic et toc sera identique. Ainsi, pour les petites tailles, les zeros(n) sont comparables. Cependant, autour de n=400 il y a un saut de performance pour la multiplication de masortingce vide. Le code que j’ai utilisé pour générer ce tracé était le suivant:

 n=unique(round(logspace(0,4,200))); for k=1:length(n) f=@() zeros(n(k)); t1(k)=timeit(f); g=@() zeros(n(k),0)*zeros(0,n(k)); t2(k)=timeit(g); end loglog(n,t1,'b',n,t2,'r'); legend('zeros(n)','zeros(n,0)*zeros(0,n)',2); xlabel('masortingx size (n)'); ylabel('time [sec]'); 

Est-ce que certains d’entre vous en font aussi l’expérience?

EDIT # 2:

Incidemment, la multiplication de la masortingce vide n’est pas nécessaire pour obtenir cet effet. On peut simplement faire:

 z(n,n)=0; 

où n> une taille de masortingce de seuil vue dans le graphique précédent, et obtenir le profil d’efficacité exact comme avec la multiplication de masortingce vide (en utilisant à nouveau timeit).

entrer la description de l'image ici

Voici un exemple où il améliore l’efficacité d’un code:

 n = 1e4; clear z1 tic z1 = zeros( n ); for cc = 1 : n z1(:,cc)=cc; end toc % Elapsed time is 0.445780 seconds. %% clear z0 tic z0 = zeros(n,0)*zeros(0,n); for cc = 1 : n z0(:,cc)=cc; end toc % Elapsed time is 0.297953 seconds. 

Cependant, en utilisant z(n,n)=0; au lieu de cela donne des résultats similaires au cas des zeros(n) .

C’est étrange, je vois que je suis plus rapide tout en étant plus lent que ce que vous voyez. Mais les deux sont identiques pour moi. Peut-être une version différente de MATLAB?

 >> g = @() zeros(1000, 0) * zeros(0, 1000); >> f = @() zeros(1000) f = @()zeros(1000) >> timeit(f) ans = 8.5019e-04 >> timeit(f) ans = 8.4627e-04 >> timeit(g) ans = 8.4627e-04 

EDIT pouvez-vous append + 1 pour la fin de f et g, et voir quelles sont les heures que vous obtenez.

EDIT 6 janvier 2013 7h42 HNE

J’utilise une machine à distance, alors désolé pour les graphiques de faible qualité (qui devaient les générer en aveugle).

Machine config:

i7 920. 2.653 GHz. Linux 12 Go de RAM. 8 Mo de cache.

Graphique généré sur i7 920

Il semble même que la machine à laquelle j’accède montre ce comportement, sauf à une taille plus grande (quelque part entre 1979 et 2073). Il n’y a aucune raison pour que je puisse penser que la multiplication de la masortingce vide soit plus rapide dans les grandes tailles.

Je vais enquêter un peu plus avant de revenir.

EDIT 11 janvier 2013

Après le post de @EitanT, je voulais faire un peu plus de creusage. J’ai écrit du code C pour voir comment matlab peut créer une masortingce de zéros. Voici le code c ++ que j’ai utilisé.

 int main(int argc, char **argv) { for (int i = 1975; i <= 2100; i+=25) { timer::start(); double *foo = (double *)malloc(i * i * sizeof(double)); for (int k = 0; k < i * i; k++) foo[k] = 0; double mftime = timer::stop(); free(foo); timer::start(); double *bar = (double *)malloc(i * i * sizeof(double)); memset(bar, 0, i * i * sizeof(double)); double mmtime = timer::stop(); free(bar); timer::start(); double *baz = (double *)calloc(i * i, sizeof(double)); double catime = timer::stop(); free(baz); printf("%d, %lf, %lf, %lf\n", i, mftime, mmtime, catime); } } 

Voici les résultats.

 $ ./test 1975, 0.013812, 0.013578, 0.003321 2000, 0.014144, 0.013879, 0.003408 2025, 0.014396, 0.014219, 0.003490 2050, 0.014732, 0.013784, 0.000043 2075, 0.015022, 0.014122, 0.000045 2100, 0.014606, 0.014480, 0.000045 

Comme vous pouvez le voir, calloc (4ème colonne) semble être la méthode la plus rapide. Il est également de plus en plus rapide entre 2025 et 2050 (je suppose que ce serait vers 2048?).

Maintenant, je suis retourné à Matlab pour vérifier la même chose. Voici les résultats.

 >> test 1975, 0.003296, 0.003297 2000, 0.003377, 0.003385 2025, 0.003465, 0.003464 2050, 0.015987, 0.000019 2075, 0.016373, 0.000019 2100, 0.016762, 0.000020 

Il semble que les deux f () et g () utilisent un calloc à des tailles plus petites (<2048?). Mais pour des tailles plus grandes, f () (zéros (m, n)) commence à utiliser malloc + memset , tandis que g () (zéros (m, 0) * zéros (0, n)) continue à utiliser le calloc .

La divergence s'explique donc par ce qui suit

  • les zéros (..) commencent à utiliser un schéma différent (plus lent?) pour les grandes tailles.
  • calloc se comporte également de manière inattendue, entraînant une amélioration des performances.

C'est le comportement sous Linux. Est-ce que quelqu'un peut faire la même expérience sur une autre machine (et peut-être un autre système d'exploitation) et voir si l'expérience est valable?

Les résultats peuvent être un peu trompeurs. Lorsque vous multipliez deux masortingces vides, la masortingce résultante n’est pas immédiatement “allouée” et “initialisée”, elle est plutôt rescope jusqu’à ce que vous l’utilisiez pour la première fois (un peu comme une évaluation paresseuse).

Il en va de même lors de l’ indexation hors limites pour développer une variable qui, dans le cas des tableaux numériques, remplit les entrées manquantes avec des zéros (je parlerai ensuite de la casse non numérique). Bien sûr, la croissance de la masortingce de cette façon ne remplace pas les éléments existants.

Donc, même si cela peut sembler plus rapide, vous ne faites que retarder le temps d’atsortingbution jusqu’à ce que vous utilisiez la masortingce pour la première fois. À la fin, vous aurez les mêmes horaires que si vous aviez effectué l’allocation depuis le début.

Exemple pour montrer ce comportement, comparé à quelques autres alternatives :

 N = 1000; clear z tic, z = zeros(N,N); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = zeros(N,0)*zeros(0,N); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z(N,N) = 0; toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = full(spalloc(N,N,0)); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z(1:N,1:N) = 0; toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z val = 0; tic, z = val(ones(N)); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = repmat(0, [NN]); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) 

Le résultat montre que si vous additionnez le temps écoulé pour les deux instructions dans chaque cas, vous obtenez des durées totales similaires:

 // zeros(N,N) Elapsed time is 0.004525 seconds. Elapsed time is 0.000792 seconds. // zeros(N,0)*zeros(0,N) Elapsed time is 0.000052 seconds. Elapsed time is 0.004365 seconds. // z(N,N) = 0 Elapsed time is 0.000053 seconds. Elapsed time is 0.004119 seconds. 

Les autres horaires étaient:

 // full(spalloc(N,N,0)) Elapsed time is 0.001463 seconds. Elapsed time is 0.003751 seconds. // z(1:N,1:N) = 0 Elapsed time is 0.006820 seconds. Elapsed time is 0.000647 seconds. // val(ones(N)) Elapsed time is 0.034880 seconds. Elapsed time is 0.000911 seconds. // repmat(0, [NN]) Elapsed time is 0.001320 seconds. Elapsed time is 0.003749 seconds. 

Ces mesures sont trop petites en millisecondes et peuvent ne pas être très précises. Vous pouvez donc exécuter ces commandes en boucle quelques milliers de fois et prendre la moyenne. De plus, l’exécution de fonctions M sauvegardées est parfois plus rapide que l’exécution de scripts ou de l’invite de commandes, car certaines optimisations ne se produisent que de cette manière …

Dans les deux cas, l’allocation est généralement effectuée une fois, alors qui se soucie de savoir s’il faut 30 ms supplémentaires 🙂


Un comportement similaire peut être vu avec des tableaux de cellules ou des tableaux de structures. Prenons l’exemple suivant:

 N = 1000; tic, a = cell(N,N); toc tic, b = repmat({[]}, [N,N]); toc tic, c{N,N} = []; toc 

qui donne:

 Elapsed time is 0.001245 seconds. Elapsed time is 0.040698 seconds. Elapsed time is 0.004846 seconds. 

Notez que même s’ils sont tous égaux, ils occupent une quantité de mémoire différente:

 >> assert(isequal(a,b,c)) >> whos abc Name Size Bytes Class Atsortingbutes a 1000x1000 8000000 cell b 1000x1000 112000000 cell c 1000x1000 8000104 cell 

En fait, la situation est un peu plus compliquée car MATLAB partage probablement la même masortingce vide pour toutes les cellules, plutôt que de créer plusieurs copies.

Le tableau de cellules a est en fait un tableau de cellules non initialisées (un tableau de pointeurs NULL), tandis que b est un tableau de cellules où chaque cellule est un tableau vide [] interne et en raison du partage des données, seule la première cellule b{1} pointe sur [] alors que tous les autres font référence à la première cellule). Le tableau final c est similaire à a (cellules non initialisées), mais le dernier contient une masortingce numérique vide [] .


J’ai libmx.dll la liste des fonctions C exscopes depuis libmx.dll (en utilisant l’outil Dependency Walker ) et j’ai trouvé quelques choses intéressantes.

  • Il existe des fonctions non documentées pour la création de tableaux non initialisés: mxCreateUninitDoubleMasortingx , mxCreateUninitNumericArray et mxCreateUninitNumericMasortingx . En fait, il existe une soumission sur File Exchange qui utilise ces fonctions pour fournir une alternative plus rapide à la fonction des zeros .

  • il existe une fonction non documentée appelée mxFastZeros . Googler en ligne, je peux voir que vous avez aussi croisé cette question sur MATLAB Answers, avec d’excellentes réponses là-bas. James Tursa (même auteur d’UNINIT d’avant) a donné un exemple sur l’utilisation de cette fonction non documentée.

  • libmx.dll est lié à la bibliothèque partagée tbbmalloc.dll . Ceci est l’allocateur de mémoire évolutif Intel TBB . Cette bibliothèque fournit des fonctions d’allocation de mémoire équivalentes ( malloc , calloc , free ) optimisées pour des applications parallèles. Rappelez-vous que de nombreuses fonctions MATLAB sont automatiquement multithreadées , donc je ne serais pas surpris si les zeros(..) sont multithreadés et utilisent l’allocateur de mémoire d’Intel une fois que la taille de la masortingce est assez grande (voici le récent commentaire de Loren Shure ) .

En ce qui concerne le dernier point concernant l’allocateur de mémoire, vous pouvez écrire un test similaire en C / C ++ similaire à celui de @PavanYalamanchili , et comparer les différents allocateurs disponibles. Quelque chose comme ça . Rappelez-vous que les fichiers MEX ont une charge de gestion de la mémoire légèrement supérieure, puisque MATLAB libère automatiquement toute mémoire allouée dans les fichiers MEX à l’aide des fonctions mxCalloc , mxMalloc ou mxRealloc . Pour ce que cela vaut, il était possible de changer le gestionnaire de mémoire interne dans les anciennes versions.


MODIFIER:

Voici un benchmark plus complet pour comparer les alternatives discutées. Cela montre spécifiquement qu’une fois que vous insistez sur l’utilisation de la masortingce entière, les trois méthodes sont sur un pied d’égalité et la différence est négligeable.

 function compare_zeros_init() iter = 100; for N = 512.*(1:8) % ZEROS(N,N) t = zeros(iter,3); for i=1:iter clear z tic, z = zeros(N,N); t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf('N = %4d, ZEROS = %.9f\n', N, mean(sum(t,2))) % z(N,N)=0 t = zeros(iter,3); for i=1:iter clear z tic, z(N,N) = 0; t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf('N = %4d, GROW = %.9f\n', N, mean(sum(t,2))) % ZEROS(N,0)*ZEROS(0,N) t = zeros(iter,3); for i=1:iter clear z tic, z = zeros(N,0)*zeros(0,N); t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf('N = %4d, MULT = %.9f\n\n', N, mean(sum(t,2))) end end 

Vous trouverez ci-dessous les durées moyennes sur 100 itérations en termes d’augmentation de la taille de la masortingce. J’ai effectué les tests dans R2013a.

 >> compare_zeros_init N = 512, ZEROS = 0.001560168 N = 512, GROW = 0.001479991 N = 512, MULT = 0.001457031 N = 1024, ZEROS = 0.005744873 N = 1024, GROW = 0.005352638 N = 1024, MULT = 0.005359236 N = 1536, ZEROS = 0.011950846 N = 1536, GROW = 0.009051589 N = 1536, MULT = 0.008418878 N = 2048, ZEROS = 0.012154002 N = 2048, GROW = 0.010996315 N = 2048, MULT = 0.011002169 N = 2560, ZEROS = 0.017940950 N = 2560, GROW = 0.017641046 N = 2560, MULT = 0.017640323 N = 3072, ZEROS = 0.025657999 N = 3072, GROW = 0.025836506 N = 3072, MULT = 0.051533432 N = 3584, ZEROS = 0.074739924 N = 3584, GROW = 0.070486857 N = 3584, MULT = 0.072822335 N = 4096, ZEROS = 0.098791732 N = 4096, GROW = 0.095849788 N = 4096, MULT = 0.102148452 

Après avoir fait quelques recherches, j’ai trouvé cet article dans “Undocumented Matlab” , dans lequel M. Yair Altman était déjà arrivé à la conclusion que la méthode de préallocation des masortingces à l’ aide de zeros(M, N) n’est pas la méthode la plus efficace.

Il a chronométré x = zeros(M,N) contre clear x, x(M,N) = 0 et a trouvé que ce dernier était ~ 500 fois plus rapide. Selon son explication, la deuxième méthode crée simplement une masortingce M-by-N, dont les éléments sont automatiquement initialisés à 0. La première méthode crée cependant x (avec x comportant des éléments zéro automatiques) et affecte ensuite un zéro à chaque élément dans x encore, et c’est une opération redondante qui prend plus de temps.

Dans le cas d’une multiplication de masortingce vide, telle que celle que vous avez montrée dans votre question, MATLAB s’attend à ce que le produit soit une masortingce M × N et alloue donc une masortingce M × N. Par conséquent, la masortingce de sortie est automatiquement initialisée à zéro. Les masortingces d’origine étant vides, aucun autre calcul n’est effectué et, par conséquent, les éléments de la masortingce de sortie restnt inchangés et égaux à zéro.

Question intéressante, il existe apparemment plusieurs façons de «battre» la fonction de zeros intégrée. Ma seule supposition est que cela pourrait être plus efficace en zeros(LargeNumer) mémoire (après tout, les zeros(LargeNumer) feront que Matlab atteindra plus rapidement la limite de la mémoire que la plupart des codes), ou plus robuste. .

Voici une autre méthode d’allocation rapide utilisant une masortingce fragmentée, j’ai ajouté la fonction de zéros réguliers comme référence:

 tic; x=zeros(1000,1000); toc Elapsed time is 0.002863 seconds. tic; clear x; x(1000,1000)=0; toc Elapsed time is 0.000282 seconds. tic; x=full(spalloc(1000,1000,0)); toc Elapsed time is 0.000273 seconds. tic; x=spalloc(1000,1000,1000000); toc %Is this the same for practical purposes? Elapsed time is 0.000281 seconds. 

Cette réponse est falsifiée. Conservé juste pour l’enregistrement. Il semble que matlab décide d’utiliser des masortingces éparses quand il reçoit une commande comme z(n,n)=0; quand n est assez grand L’implémentation interne peut prendre la forme d’une condition telle que: (si newsize> THRESHOLD + oldsize alors utiliser sparse …) où THRESHOLD est votre “taille de seuil”.

Cependant, c’est en dépit de Mathworks affirmant: “Matlab ne crée jamais de masortingces clairsemées automatiquement” ( lien )

Je n’ai pas Matlab pour le tester. Néanmoins, l’utilisation de masortingces éparses (en interne) est une explication plus courte (le razor d’Occam) et est donc meilleure jusqu’à ce que falsifié.