Pytanie Efektywne przydzielanie macierzy w MATLAB


Jedną z pierwszych rzeczy, które dowiadują się o efektywnym programowaniu w MATLABie, jest unikanie dynamicznej zmiany rozmiaru macierzy. Standardowy przykład jest następujący.

N = 1000;

% Method 0: Bad
clear a
for i=1:N
    a(i) = cos(i);
end

% Method 1: Better
clear a; a = zeros(N,1);
for i=1:N
    a(i) = cos(i)
end

Wariant "Zły" wymaga tutaj O (N^ 2) czas uruchomienia, ponieważ musi przydzielić nową tablicę i skopiować stare wartości w każdej iteracji pętli.

Moja własna preferowana praktyka podczas debugowania polega na przydzieleniu tablicy NaN, trudniej jest pomylić z poprawną wartością niż 0.

% Method 2: Easier to Debug
clear a; a = NaN(N,1);
for i=1:N
    a(i) = cos(i)
end

Jednak można by naiwnie myśleć, że po debugowaniu naszego kodu marnujemy czas, przypisując tablicę, a następnie wypełniając ją 0 lub NaN. Jak wspomniano tutajmożesz utworzyć niezainicjowaną tablicę w następujący sposób

% Method 3 : Even Better?
clear a; a(N,1) = 0;
for i=1:N
    a(i) = cos(i);
end

Jednak w moich własnych testach (MATLAB R2013a) nie zauważam żadnej znaczącej różnicy między metodami 1 i 3, podczas gdy metoda 2 zajmuje więcej czasu. Sugeruje to, że MATLAB uniknął jawnego inicjowania tablicy do zera, kiedy a = zeros(N,1) jest nazywany.

Dlatego jestem ciekawy

  • Jaki jest optymalny sposób na wstępne przydzielenie macierzy (niezainicjowanej) w programie MATLAB? (Co najważniejsze, duże tablice)
  • Czy to też ma miejsce w Octave?

11
2017-08-16 14:55


pochodzenie


To jest interesujące. Pomyślałem, że może MATLAB nie inicjował zer, dopóki modyfikacja matrycy nie została wykonana (podobnie jak w matlab kopiuje matryce), ale tic; a = NaN(1e4); a(1) = 1; toc jest rzeczywiście wolniejszy niż tic; a = zeros(1e4); a(1) = 1; toc na mojej maszynie. Tak jak w heads-upie, naprawdę widziałem tylko alokację zeros więc jestem prawie pewien, że nie ma możliwości wstępnego przydziału bez inicjalizacji, chyba że wykonasz procedurę mex, ale może inni tutaj się dowiedzą. - Justin
Szybko staje się to Matlab FAQ i aspekty tego zagadnienia zostały już omówione tutaj na SO. W innych miejscach, na przykład na nieocenionym nieoficjalnym blogu Matlab - undocumentedmatlab.com/blog/allocation-performance-take-2/...  Porównywalność różnych metod wydaje się zmieniać wraz z rozwojem Matlaba. - High Performance Mark
@Shai dotyczy to wydajności metod alokacji wstępnej, a nie potrzeby wcześniejszej alokacji. Przestań zamykać takie pytania, proszę. - EJG89
@ EJG89 Uważam, że pytania są wystarczająco bliskie, aby uzasadnić "zamknięcie jako dup". Rozumiem, że nie zgadzasz się ze mną i to jest w porządku. W przypadku takich nieporozumień istnieje możliwość głosowania na ponowne otwarcie. Zapraszamy do głosowania na ponowne otwarcie. - Shai
Wystarczająco blisko? W jaki sposób różne sposoby alokacji pamięci i jej wydajność stanowią duplikat potrzeby wstępnego przydzielania pamięci. Dyskusja jest na bardziej zaawansowanym poziomie, a ja po prostu nie rozumiem, dlaczego tak szybko można zamknąć pytania. Prawdopodobnie nie mam przedstawiciela, który zagłosowałby za ponownym otwarciem, więc po prostu grasz na własną rękę. Po prostu nie chcesz, aby ludzie dyskutowali o głębszych warstwach / wewnętrznym działaniu MatLab. Drugi temat nie dotknął nawet JIT, myślę, że jest to podstawą tego pytania. - EJG89


Odpowiedzi:


Test

Korzystając z MatLab 2013b I i Intel Xeon 3.6 GHz + 16 GB pamięci RAM, uruchomiłem poniższy kod do profilu. Wyróżniłem 3 metody i tylko rozważałem tablice 1D, tj. Wektory. Metody 1 i 2 testowano przy użyciu wektorów kolumnowych i wektorów wierszowych, tj. (N, 1) i (1, n).

Metoda 1 (M1R, M1C)

a = zeros(1,n);

Metoda 2 M2R, M2C

a = NaN(1,n);

Metoda 3 (M3)

a(n) = 0;

Wyniki

Wyniki czasowe i liczba elementów zostały naniesione na duŜą skalę logarytmiczną w taktowaniu figury 1D.

timings1d

Jak pokazano, trzecia metoda ma przypisanie prawie niezależne od wielkości wektora, podczas gdy inne stałe zwiększenie sugeruje domyślną definicję wektora.

Dyskusja

MatLab wykonuje wiele optymalizacji kodu przy użyciu JIT (Just in time), tj. Optymalizacji kodu podczas pracy. Tak więc ważnym pytaniem jest stwierdzenie, czy część kodu działającego szybciej jest spowodowana programowaniem (zawsze takim samym bez względu na to, czy jest zoptymalizowana), czy z powodu optymalizacji. Aby przetestować tę optymalizację można wyłączyć za pomocą funkcji ("accel", "off"). Wyniki ponownego uruchomienia kodu są dość interesujące:

timings1Dnoacceleration

Pokazano, że teraz metoda 1 jest optymalna, zarówno dla wektorów wierszowych, jak i kolumnowych. A metoda 3 zachowuje się jak inne metody w pierwszym teście.

Wniosek

Optymalizacja wstępnej alokacji pamięci jest bezużyteczna i strata czasu, ponieważ i tak Matlab zoptymalizuje się dla ciebie.

Pamiętaj, że pamięć powinna być wstępnie przydzielona, ​​ale sposób, w jaki to robisz, nie ma znaczenia. Wydajność wstępnej alokacji pamięci zależy w dużej mierze od tego, czy kompilator JIT z MatLab zdecyduje się zoptymalizować kod, czy też nie. Jest to w pełni zależne od wszystkich innych treści pliku .m, ponieważ kompilator rozważa porcje kodów w danym momencie, a następnie próbuje zoptymalizować (ma nawet pamięć, dzięki czemu kilkakrotne uruchomienie pliku może spowodować nawet mniejszą wydajność- czas). Również wstępna alokacja pamięci jest najczęściej bardzo krótkim procesem, biorąc pod uwagę wydajność w porównaniu do późniejszych obliczeń

Moim zdaniem pamięć powinna być wstępnie przydzielona przez użycie metody 1 lub 2 w celu zachowania czytelnego kodu i użycia funkcji sugerowanej przez MatLab, ponieważ są one najbardziej prawdopodobne, że zostaną ulepszone w przyszłości.

Używany kod

clear all
clc
feature('accel','on')

number1D=30;

nn1D=2.^(1:number1D);

timings1D=zeros(5,number1D);

for ii=1:length(nn1D);
    n=nn1D(ii);
    % 1D
    tic
    a = zeros(1,n);
    a(randi(n,1))=1;
    timings1D(1,ii)=toc;
    fprintf('1D row vector method1 took: %f\n',timings1D(1,ii))
    clear a

    tic
    b = zeros(n,1);
    b(randi(n,1))=1;
    timings1D(2,ii)=toc;
    fprintf('1D column vector method1 took: %f\n',timings1D(2,ii))
    clear b

    tic
    c = NaN(1,n);
    c(randi(n,1))=1;
    timings1D(3,ii)=toc;
    fprintf('1D row vector method2 took: %f\n',timings1D(3,ii))
    clear c

    tic
    d = NaN(n,1);
    d(randi(n,1))=1;
    timings1D(4,ii)=toc;
    fprintf('1D row vector method2 took: %f\n',timings1D(4,ii))
    clear d

    tic
    e(n) = 0;
    e(randi(n,1))=1;
    timings1D(5,ii)=toc;
    fprintf('1D row vector method3 took: %f\n',timings1D(5,ii))
    clear e
end
logtimings1D = log10(timings1D);
lognn1D=log10(nn1D);
figure(1)
clf()
hold on
plot(lognn1D,logtimings1D(1,:),'-k','LineWidth',2)
plot(lognn1D,logtimings1D(2,:),'--k','LineWidth',2)
plot(lognn1D,logtimings1D(3,:),'-.k','LineWidth',2)
plot(lognn1D,logtimings1D(4,:),'-','Color',[0.6 0.6 0.6],'LineWidth',2)
plot(lognn1D,logtimings1D(5,:),'--','Color',[0.6 0.6 0.6],'LineWidth',2)
xlabel('Number of elements (log10[-])')
ylabel('Timing of each method (log10[s])')
legend('M1R','M1C','M2R','M2C','M3','Location','NW')
title({'Various methods of pre-allocation in 1D','nr. of elements vs timing'})
hold off

Uwaga

Linie zawierające c(randi(n,1))=1; nie rób nic poza przypisaniem wartości 1 do elementu losowego we wstępnie przydzielonej tablicy, tak aby tablica była używana do zakwestionowania nieco kompilatora JIT. Linie te nie mają znaczącego wpływu na pomiar przydziału wstępnego, tj. Nie są mierzalne i nie wpływają na test.


8
2017-07-31 08:06



Niezły test, ale a(randi(n,1))=1; inicjuje tylko jeden element losowy wektora? Brzmi całkiem arbitralnie. Wolałbym zainicjować każdy element z czymś podobnym 2*i+1 aby zapobiec niektórym możliwym optymalizacjom. - Mathias
Linia ta ma przypisać 1 do elementu losowego, aby optymalizacja JIT nie wykryła, że ​​nic nie jest wykonywane z tablicami. Nie inicjalizuje niczego, ale tylko przypisuje jeden do wstępnie przydzielonej tablicy zer lub nans. - EJG89
Dodałem notatkę wyjaśniającą cel tych linii. - EJG89
Co jeśli matlab wewnętrznie generuje rzadką macierz dla M3 i alokuje pełne, jeśli zapisano wystarczającą liczbę wartości? Ustawienie jednej wartości losowej nie wyklucza tego. - Mathias
MatLab nie generuje rzadkiej macierzy, ponieważ również mapowałem pamięć i widzę, że jest ona wstępnie przydzielona (to jest zarezerwowana) i zwiększa pamięć. Losowa wartość jest bardziej jak flaga: używam tej tablicy, nie opuszczaj jej całkowicie. - EJG89


Co powiesz na to, aby Matlab zajął się przydzieleniem ci?

clear a;
for i=N:-1:1
    a(i) = cos(i);
end

Następnie Matlab może przydzielić i wypełnić tablicę tym, co uważa za optymalne (prawdopodobnie zero). Nie masz przewagi debugowania NaNs, chociaż.


1
2017-07-30 12:22



Czy to zaplanowałeś? Zakładam, że to jest to samo co metoda (3) - Patrick Sanan
Nie przerywałem tego, ale spodziewam się tego (w większości przypadków). Jedyną możliwą korzyścią jest to, że masz gwarancję otrzymania zmiennej właściwej klasy - przypisania a(n) = 0 nie może i może wymagać ponownego przydziału. - Dylan Richard Muir