Добавление частей матриц медленнее, чем целых

Question

У меня есть простой код, где у меня есть большая двумерная матрица, которую я хочу сжать, чтобы она составляла половину размера в каждом измерении. A - желаемая выходная (500 х 500) матрица, и она занимает 0,004 секунды. Однако B занимает меньше времени, и это матрица (1000 x 1000). Насколько я понимаю, для создания временных матриц для вычисления A требуется больше времени, чем для фактического вычисления A; поэтому решение заключается в использовании циклов for, так что 4 больших (500 x 500) матрицы на самом деле создавать не нужно. Однако, когда это было сделано в скрипте (C), в отдельной функции (C2) или в скомпилированном MEX-файле (C3), время вычислений еще больше. (Еще более загадочным является то, что компиляция кода медленнее, чем циклы JIT for в Matlab). Кто-нибудь имеет представление о том, что происходит? TIA

    clc
clear all
N = 1e3;
X = rand(N);
i=1:2:N-1;
j=1:2:N-1;
tic
A = (X(j,i) + X(j,i+1) + X(j+1,i) + X(j+1,i+1))/4;
toc
%% Elapsed time is 0.003942 seconds.
tic
B = (X + X + X + X)/4;
toc
%% Elapsed time is 0.001632 seconds.
tic
I=1:2:N-1;
J=1:2:N-1;
C = zeros(N/2);
for i=1:length(I)
    for j=1:length(J)
        C(j,i) = (X(J(j),I(i))+X(J(j)+1,I(i))+X(J(j),I(i)+1)+X(J(j)+1,I(i)+1))/4;
    end
end
toc
%% Elapsed time is 0.012286 seconds.
tic
C2 = MyRestrict(X);
toc
%% Elapsed time is 0.010636 seconds.
tic
C3 = MyRestrict_mex(X);
toc
%% Elapsed time is 0.068403 seconds.

Answer 1

Я полагаю, что вы не рассматривали ни обработку параллелизма, ни работу многопоточности. Как использовать параллельную обработку в Matlab https://es.mathworks.com/discovery/matlab-multicore.html Есть много вещей, которые вам нужно понять об этих двух концепциях, но в основном: Использование struture for заставляет Matlab работать в указанном порядке c, пока итерация не закончена, следующая не может начаться. Между тем, если вы используете код для A или B, это намного эффективнее, поскольку вы не заставляете matlab следовать исключительному порядку, и вы можете воспользоваться преимуществами многопотоковых операций intrinsi c внутри Matlab (одновременно можно выполнять несколько задач). Пример:

C(j,i) = (X(J(j),I(i))+X(J(j)+1,I(i))+X(J(j),I(i)+1)+X(J(j)+1,I(i)+1))/4;

C (1,1) не зависит от других C (j, i), поэтому нет необходимости ждать, пока эта итерация завершится до sh думая о результате C (1,2). Так что многопоточность здесь полезна, каждый поток может выполнять каждую математическую операцию, как они уже делают в A и B.

Answer 2

Я вижу гораздо меньшую разницу, чем вы. B - это совершенно другой результат, чем A или C, поэтому я проигнорирую эту часть. C2 и C3 Я ничего не могу сказать, потому что для них нет кода, я не знаю, что они делают.

С N=1e3 я получаю 2,0 мс для A и 3,3 мс для C. Массив настолько мал, что создание четырех промежуточных копий не является большой проблемой. Накладные расходы на l oop, хотя и небольшие, заметны (MATLAB 15 лет go видел бы, что l oop был бы в 100 раз медленнее!). Отметим также, что, как Марта Г. предложила , суммирование для A распараллелено, MATLAB может использовать инструкции SIMD и / или несколько ядер для выполнения этих дополнений. Это ускорение частично компенсирует стоимость создания копий данных.

При N=1e4 я получаю 0,62 с для A и 0,37 с для C. Здесь массив настолько велик, что накладные расходы на создание копий начинают действительно показываться. Для еще больших массивов разница во времени будет намного больше. Обратите внимание, что время вычисления C близко к 100 раз больше, чем в первом случае, и что массив X в 100 раз больше, чем в первом случае. Поэтому пришло время вычислить A, которое не подходило для размера массива.

Итак, когда вы решаете, как реализовать что-то, попробуйте разные варианты и всегда рассчитывайте их с realisti c размеры массивов.

---

Примечание для синхронизации:

Всегда запускайте синхронизацию, используя функции и timeit. Вызов l oop или функции, для выполнения которой требуются миллисекунды, не может быть правильно рассчитан с помощью tic / toc. Только то, что для запуска занимает около секунды или более, может быть рассчитано так, как вы это сделали. Но поместите код в функцию, чтобы можно было применить JIT. Скрипты JIT'ы в самых последних версиях MATLAB, но не в более ранних версиях, и поэтому tic / toc всегда должны появляться внутри функции.

Так может выглядеть код синхронизации :

X = rand(1e4);
A = methodA(X);
C = methodC(X);
assert(all(all(abs(A-C)<1e-14)))

timeit(@()methodA(X))
timeit(@()methodC(X))

function A = methodA(X)
N = size(X,1);
i=1:2:N-1;
j=1:2:N-1;
A = (X(j,i) + X(j,i+1) + X(j+1,i) + X(j+1,i+1)) / 4;
end

function C = methodC(X)
N = size(X,1);
C = zeros(N/2);
for i=1:N/2
   si = i*2-1;
   for j=1:N/2
      sj = j*2-1;
      C(j,i) = (X(sj,si) + X(sj+1,si) + X(sj,si+1) + X(sj+1,si+1)) / 4;
   end
end
end