Achtergrond
Mijn vraag is ingegeven door eenvoudige observaties, die enigszins afbreuk doen aan de overtuigingen / aannames vaak gehouden / gemaakt door ervaren MATLAB gebruikers:
- MATLAB is zeer goed geoptimaliseerd wat betreft de ingebouwde functies en de fundamentele taalfuncties, zoals indexering vectoren en matrices.
- Loops in MATLAB zijn traag (ondanks de JIT) en moet in het algemeen worden vermeden als het algoritme kan worden uitgedrukt in een native, ‘gevectoriseerd’ manier.
De bottom line:. Kern MATLAB functionaliteit is efficiënt en proberen om het beter te presteren met behulp van MATLAB-code is moeilijk, zo niet onmogelijk
Onderzoek naar de prestaties van vector indexeren
De voorbeeldcodes onderstaande voorbeeld als fundamenteel kan niet: ik wijs een scalaire waarde voor alle vectorelementen. Eerst, I toewijzen een lege vector x:
tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.
Het hebben van xIk wil graag al haar inzendingen ingesteld op dezelfde waarde. In de praktijk zou je het anders doen, bijvoorbeeld x = value*ones(1e8,1), maar het punt hier is om de prestaties van de vector indexering te onderzoeken. De eenvoudigste manier is om te schrijven:
tic; x(:) = 1; toc
Elapsed time is 0.094316 seconds.
zeg maar Werkwijze 1 (uit de waarde die aan x). Het lijkt zeer snel (sneller ten minste dan het toewijzen van geheugen). Omdat het enige wat ik hier doe is werken op het geheugen, kan ik de efficiëntie van deze code te schatten door het berekenen van de verkregen effectieve geheugenbandbreedte en te vergelijken met de hardware geheugenbandbreedte van mijn computer:
eff_bandwidth = numel(x) * 8 bytes per double * 2 / time
In het bovenstaande I vermenigvuldigen met 2want als SSE streaming wordt gebruikt, instelwaarden geheugen vereist dat de vector zowel gelezen van en geschreven naar het geheugen. In het bovenstaande voorbeeld:
eff_bandwidth(1) = 1e8*8*2/0.094316 = 17 Gb/s
-STREAM gebenchmarkt geheugenbandbreedte van mijn computer is ongeveer 17,9 GB / s, dus inderdaad – MATLAB levert dicht bij topprestaties in dit geval! So far, so good.
Methode 1 is geschikt als u wilt instellen alle vector elementen voor een bepaalde waarde. Maar als je wilt toegang elementen elke stepdata, moet u de :met bijvoorbeeld 1:step:end. Hieronder is een directe snelheid vergelijking met methode 1:
tic; x(1:end) = 2; toc
Elapsed time is 0.496476 seconds.
Terwijl je zou niet verwachten dat het anders uit te voeren, methode 2 is duidelijk grote problemen: factor 5 vertraging zonder reden. Mijn vermoeden is dat in dit geval MATLAB expliciet wijst de index vector (1:end). Dit is enigszins bevestigd door expliciete vectorgrootte plaats van end:
tic; x(1:1e8) = 3; toc
Elapsed time is 0.482083 seconds.
Methods 2 en 3 uit te voeren even slecht.
Een andere mogelijkheid is om expliciet een index vector iden het gebruiken om index x. Dit geeft u de meest flexibele indexering mogelijkheden. In ons geval:
tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc
Elapsed time is 1.208419 seconds.
Nu dat is echt iets – 12 keer vertraging in vergelijking met methode 1! Ik begrijp dat het zou nog erger dan methode 1 uit te voeren als gevolg van de extra geheugen wordt gebruikt voor id, maar waarom is het zo veel slechter dan methoden 2 en 3?
Laten we proberen om het te lussen te proberen -. Zo hopeloos als het klinkt
tic;
for i=1:numel(x)
x(i) = 5;
end
toc
Elapsed time is 0.788944 seconds.
Een grote verrassing – een lus verslaat een vectorizedmethode 4, maar is nog steeds langzamer dan methode 1, 2 en 3. Het blijkt dat je het in dit specifieke geval beter kunt doen:
p>
tic;
for i=1:1e8
x(i) = 6;
end
toc
Elapsed time is 0.321246 seconds.
En dat is waarschijnlijk de meest bizarre uitkomst van dit onderzoek: een door MATLAB geschreven lus presteert aanzienlijk beter dan native vectorindexering. Dat zou zeker niet zo moeten zijn. Merk op dat de JIT’ed-loop nog steeds 3 keer langzamer is dan de theoretische piek die bijna bereikt wordt met methode 1. Er is dus nog genoeg ruimte voor verbetering. Het is gewoon verrassend (een sterker woord zou geschikter zijn) dat de gebruikelijke ‘gevectoriseerde’ indexering (1:end) nog langzamer is.
Vragen
- is eenvoudig indexeren in MATLAB zeerinefficiënt (methoden 2, 3 en 4 zijn langzamer dan methode 1), of heb ik iets gemist?
- waarom is methode 4 (zoveel) langzamerdan methode 2 en 3?
- waarom versnelt het gebruik van
1e8in plaats vannumel(x)als lusbinding de code met factor 2?
Bewerken
Na het lezen van Jonas’ commentaar, is hier een andere manier om dat te doen met behulp van logische indices:
tic;
id = logical(ones(1, 1e8));
x(id) = 7;
toc
Elapsed time is 0.613363 seconds.
Veel beter dan methode 4.
Voor het gemak:
function test
tic; x = zeros(1,1e8); toc
tic; x(:) = 1; toc
tic; x(1:end) = 2; toc
tic; x(1:1e8) = 3; toc
tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc
tic;
for i=1:numel(x)
x(i) = 5;
end
toc
tic;
for i=1:1e8
x(i) = 6;
end
toc
end
Antwoord 1, autoriteit 100%
Ik kan natuurlijk alleen maar speculeren. Wanneer ik echter uw test uitvoer met de JIT-compiler ingeschakeld versus uitgeschakeld, krijg ik de volgende resultaten:
% with JIT no JIT
0.1677 0.0011 %# init
0.0974 0.0936 %# #1 I added an assigment before this line to avoid issues with deferring
0.4005 0.4028 %# #2
0.4047 0.4005 %# #3
1.1160 1.1180 %# #4
0.8221 48.3239 %# #5 This is where "don't use loops in Matlab" comes from
0.3232 48.2197 %# #6
0.5464 %# logical indexing
Verdelen laat ons zien waar er een snelheidsverhoging is:
% withoutJit./withJit
0.0067 %# w/o JIT, the memory allocation is deferred
0.9614 %# no JIT
1.0057 %# no JIT
0.9897 %# no JIT
1.0018 %# no JIT
58.7792 %# numel
149.2010 %# no numel
De schijnbare versnelling bij initialisatie gebeurt, omdat met JIT uitgeschakeld blijkt dat MATLAB de geheugentoewijzing vertraagt totdat het wordt gebruikt, dus x=nullen(…) doet eigenlijk niets. (bedankt, @angainor).
Methoden 1 tot en met 4 lijken niet te profiteren van het JIT. Ik vermoed dat #4 traag zou kunnen zijn vanwege aanvullende invoertests in subsrefom er zeker van te zijn dat de invoer de juiste vorm heeft.
Het resultaat numelkan iets te maken hebben met het feit dat het voor de compiler moeilijker is om met een onzeker aantal iteraties om te gaan, of met wat overhead vanwege het controleren of de grens van de lus in orde is (gedacht no-JIT-tests suggereren slechts ~0,1s daarvoor)
Verrassend genoeg lijkt logische indexering op R2012b op mijn computer langzamer te zijn dan #4.
Ik denk dat dit maar weer eens aantoont dat MathWorks geweldig werk heeft verricht bij het versnellen van code, en dat “geen loops gebruiken” niet altijd het beste is als je de snelste uitvoeringstijd (althans op dit moment). Desalniettemin vind ik dat vectoriseren over het algemeen een goede benadering is, aangezien (a) het JIT faalt bij complexere lussen, en (b) door te leren vectoriseren je Matlab een stuk beter begrijpt.
Conclusie: als u snelheid wilt, gebruikt u de profiler en opnieuw-profiel als u Matlab-versies wisselt.
Zoals opgemerkt door @Adriaan in de opmerkingen, is het tegenwoordig beter om TIMIT () te gebruiken om de uitvoersnelheid te meten.
Ter referentie gebruikte ik de volgende enigszins gemodificeerde testfunctie
function tt = speedTest
tt = zeros(8,1);
tic; x = zeros(1,1e8); tt(1)=toc;
x(:) = 2;
tic; x(:) = 1; tt(2)=toc;
tic; x(1:end) = 2; tt(3)=toc;
tic; x(1:1e8) = 3; tt(4)=toc;
tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
tt(5)=toc;
tic;
for i=1:numel(x)
x(i) = 5;
end
tt(6)=toc;
tic;
for i=1:1e8
x(i) = 6;
end
tt(7)=toc;
%# logical indexing
tic;
id = true(1e8,1));
x(id)=7;
tt(8)=toc;
Antwoord 2, Autoriteit 64%
Ik heb geen antwoord op alle problemen, maar ik heb wel enkele verfijnde speculaties op methoden 2, 3 en 4.
Wat betreft methoden 2 en 3. Het lijkt inderdaad dat Matlab het geheugen voor de vectordecten toewijst en vult het met waarden van 1naar 1e8. Om het te begrijpen, laten we kijken wat er aan de hand is. Matlab gebruikt standaard doubleals het gegevenstype. Het toewijzen van de indexarray neemt dezelfde tijd als toewijzing van x
tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.
Voor nu bevat de indexarray alleen nullen. Waarden toewijzen aan de xvector op een optimale manier, zoals in methode 1, neemt 0.094316seconden. Nu moet de indexvector uit het geheugen worden gelezen, zodat deze kan worden gebruikt in indexering. Dat is extra 0.094316/2seconden. Bedenk dat in x(:)=1vector xmoet zowel lezen van als geschreven naar het geheugen. Dus alleen lezen duurt de helft van de tijd. Ervan uitgaande dat dit alles is wat gedaan is in x(1:end)=value, moet de totale tijd van methoden 2 en 3
zijn
t = 0.260525+0.094316+0.094316/2 = 0.402
Het is bijna correct, maar niet helemaal. Ik kan alleen speculeren, maar het vullen van de indexvector met waarden wordt waarschijnlijk als een extra stap gedaan en neemt extra 0.094316 seconden. Vandaar dat t=0.4963, die min of meer past bij de tijd van methoden 2 en 3.
Dit zijn alleen speculaties, maar ze lijken te bevestigen dat Matlab expliciet Creëert indexvectoren bij het doen van inheemse vectorindexering. Persoonlijk vind ik dit als een prestatiebug. Matlabs JIT Compiler moet slim genoeg zijn om dit triviale construct te begrijpen en deze om te zetten naar een oproep naar een juiste interne functie. Zoals het nu is, presteert op het geheugenbandbreedte-begrensd architectuurindexering op het geheugen van de geheugen op ongeveer 20% theoretische piek.
Dus als u het doet om prestaties, moet u x(1:step:end)als een MEX-functie, zoiets als
implementeren
set_value(x, 1, step, 1e8, value);
Nu is dit duidelijk illegaal in Matlab, omdat u niet bent toegestaan om de arrays in de MEX-bestanden in te modificeren.
Bewerken Met betrekking tot methode 4 kan men proberen de prestaties van de afzonderlijke stappen als volgt te analyseren:
tic;
id = 1:1e8; % colon(1,1e8);
toc
tic
x(id) = 4;
toc
Elapsed time is 0.475243 seconds.
Elapsed time is 0.763450 seconds.
De eerste stap, het toewijzen en invullen van de waarden van de indexvector kost evenveel tijd als methode 2 en 3 alleen. Het lijkt erop dat het veel te veel is – het zou maximaal de tijd moeten kosten die nodig is om het geheugen toe te wijzen en de waarden in te stellen (0.260525s+0.094316s = 0.3548s), dus er is een extra overhead van 0.12seconden ergens, wat ik niet kan begrijpen. Het tweede deel (x(id) = 4) ziet er ook erg inefficiënt uit: het zou de nodige tijd moeten kosten om de waarden van xin te stellen en de idvector (0.094316s+0.094316/2s = 0.1415s) plus enkele foutcontroles op de idwaarden. Geprogrammeerd in C, nemen de twee stappen:
create id 0.214259
x(id) = 4 0.219768
De gebruikte code controleert of een double-index in feite een geheel getal vertegenwoordigt, en dat deze overeenkomt met de grootte van x:
tic();
id = malloc(sizeof(double)*n);
for(i=0; i<n; i++) id[i] = i;
toc("create id");
tic();
for(i=0; i<n; i++) {
long iid = (long)id[i];
if(iid>=0 && iid<n && (double)iid==id[i]){
x[iid] = 4;
} else break;
}
toc("x(id) = 4");
De tweede stap duurt langer dan de verwachte 0.1415s– dat komt door de noodzaak van foutcontroles op id-waarden. De overhead lijkt me te groot – misschien kan het beter worden geschreven. Toch is de benodigde tijd 0.4340s, niet 1.208419s. Wat MATLAB onder de motorkap doet – ik heb geen idee. Misschien is het nodig om het te doen, ik zie het gewoon niet.
Natuurlijk introduceert het gebruik van doublesals indices twee extra niveaus van overhead:
- grootte van
doubletweemaal de grootte vanuint32. Bedenk dat geheugenbandbreedte hier de beperkende factor is. - doubles moeten naar gehele getallen worden gegoten voor indexering
Methode 4 kan in MATLAB worden geschreven met behulp van integer-indices:
tic;
id = uint32(1):1e8;
toc
tic
x(id) = 8;
toc
Elapsed time is 0.327704 seconds.
Elapsed time is 0.561121 seconds.
Wat de prestatie duidelijk met 30% verbeterde en bewijst dat je gehele getallen als vectorindices moet gebruiken. De overhead is er echter nog steeds.
Zoals ik het nu zie, kunnen we niets doen om de situatie binnen het MATLAB-framework te verbeteren, en we moeten wachten tot Mathworks deze problemen oplost.
Antwoord 3, autoriteit 36%
Een korte opmerking om te laten zien hoe in 8 jaar ontwikkeling de prestatiekenmerken van MATLAB veel zijn veranderd.
Dit is op R2017a (5 jaar na de post van OP):
Elapsed time is 0.000079 seconds. % x = zeros(1,1e8);
Elapsed time is 0.101134 seconds. % x(:) = 1;
Elapsed time is 0.578200 seconds. % x(1:end) = 2;
Elapsed time is 0.569791 seconds. % x(1:1e8) = 3;
Elapsed time is 1.602526 seconds. % id = 1:1e8; x(id) = 4;
Elapsed time is 0.373966 seconds. % for i=1:numel(x), x(i) = 5; end
Elapsed time is 0.374775 seconds. % for i=1:1e8, x(i) = 6; end
Merk op hoe de lus voor 1:numel(x)sneller is dan het indexeren van x(1:end), het lijkt erop dat de array 1:endwordt nog steeds gemaakt, terwijl dat voor de lus niet het geval is. Het is nu beter in MATLAB om niette vectoriseren!
(Ik heb een toewijzing x(:)=0toegevoegd na het toewijzen van de matrix, buiten alle getimede regio’s, om daadwerkelijk het geheugen toegewezen te krijgen, aangezien alleen zerosreserveert het geheugen.)
Op MATLAB R2020b (online) (3 jaar later) zie ik deze tijden:
Elapsed time is 0.000073 seconds. % x = zeros(1,1e8);
Elapsed time is 0.084847 seconds. % x(:) = 1;
Elapsed time is 0.084643 seconds. % x(1:end) = 2;
Elapsed time is 0.085319 seconds. % x(1:1e8) = 3;
Elapsed time is 1.393964 seconds. % id = 1:1e8; x(id) = 4;
Elapsed time is 0.168394 seconds. % for i=1:numel(x), x(i) = 5; end
Elapsed time is 0.169830 seconds. % for i=1:1e8, x(i) = 6; end
x(1:end)is nu op dezelfde manier geoptimaliseerd als x(:), de vector 1:endis niet langer expliciet worden gemaakt.