Почему поэлементное возведение в степень MATLAB ускоряется для 512 элементов?

Question

Степенная функция MATLAB для вычисления поэлементной экспоненты для постоянной базы, и массив экспонент становится заметно быстрее, когда размер массива становится 512. Я ожидал увидеть увеличение времени вычисления с размером ввода, однако, есть заметное падение, когда в массиве показателей 512 элементов. Вот пример кода

x_list = 510:514;
for i = 1:numel(x_list)
    x = x_list(i);
    tic
    for j = 1:10000
        y = power(2,1:x); 
    end
    toc
end

Вывод кода

Elapsed time is 0.397649 seconds.
Elapsed time is 0.403687 seconds.
Elapsed time is 0.318293 seconds.
Elapsed time is 0.238875 seconds.
Elapsed time is 0.175525 seconds.

Что здесь происходит?

Answer 1

Я вижу тот же эффект, используя случайные числа для показателя степени, как я вижу, используя целые числа в диапазоне 1:n:

x = 500:540;
t = zeros(size(x));
for ii = 1:numel(x)
    %m = 1:x(ii);
    m = 500*rand(1,x(ii));
    t(ii) = timeit(@()power(2,m));
end
plot(x,t)

Когда вы заставляете MATLAB использовать один поток с maxNumCompThreads(1) и снова запускаете код, приведенный выше, я вижу этот график вместо этого (обратите внимание на ось y, пики - это просто шум):

Мне кажется, что MATLAB использует одно ядро ​​для вычисления показателя 511 значений и запускает все ядра, если матрица больше.Использование многопоточности накладно, но для небольших массивов это не стоит.Точная точка, в которой накладные расходы компенсируются за счет экономии времени, зависит от многих факторов, и поэтому жесткое кодирование фиксированного порогового значения для перехода к многопоточному вычислению приводит к скачку времени выполнения в системах с характеристиками, отличными от характеристик системы, гдепорог был определен.

Обратите внимание, что @ norok2 не видит такой же скачок, потому что в их системе MATLAB был ограничен одним потоком .

Answer 2

Вот несколько подтверждений того, что Cris обнаружил , используя 4-ядерный компьютер с Windows, работающий под управлением MATLAB R2018a.Сначала я проверил следующий код, чтобы показать, что конкретное значение показателя не является виновником прыжка:

t = zeros(4, 1000);
for p = 1:size(t, 1)
  for n = 1:size(t, 2)
    t(p, n) = timeit(@() power(2, (2.^(p-1)).*ones(1, n)));
  end
end

И вот результаты:

Для случаев вырожденного ребра, когда показатель степени равен 1 (возвращают одно и то же значение) или 2 (возвращают само значение, умноженное на значение), вычисление выполняется быстрее, как и ожидалось.Однако скачок с размером массива 512 или выше указывает, что издержки добавлены к этим краевым случаям по сравнению с сокращением времени вычисления для показателей 4 и 8, когда размер массива превышает 512. Большие значения показателя степенипросто воспроизведите верхние кривые.

Затем я провел еще два теста: один с размером массива от 1 до 511, а второй с размером массива от 512 до 1024. Вот как выглядела загрузка процессора:

Процессор 3 показывает большой скачок нагрузки во время первого теста, в то время как все 4 процессора показывают скачки нагрузки во время второго теста.Это подтверждает, что многопоточность используется для массивов размером 512 или выше.Это также объясняет более медленные вычисления для крайних случаев больших размеров, поскольку накладные расходы от многопоточности перевешивают ускорение, обеспечиваемое разделением более простых вычислений.

Answer 3

Это связано с размером числа, для которого вычисляется мощность, а не с размером контейнера.

Если вы используете случайные числа, для изменения размера контейнера, не наблюдается скачка времени:

x = 450:1550;
y = zeros(numel(x), 1);
X = rand(1, 10000);
for i = 1:length(x)
    f = @() 2 .^ X(1:x(i));
    y(i) = timeit(f);
end

figure()
plot(x, y)

Поэтому проблема должна быть в вычислениях для очень больших чисел. Сначала я подумал, что это может быть связано с переполнением, но переполнение происходит в 2 ^ 1024 == inf в соответствии с стандартами IEEE , которым следует MATLAB, и я подумал, что для inf это было бы намного быстрее, чем вычисление числа для реального.

Это поддерживается следующим тестом, в котором размер массива поддерживается постоянным:

x = 450:1550;
y = zeros(numel(x), 1);
X = rand(1, 10000);
for i = 1:length(x)
    f = @() 2 .^ (ones(1, 500) * x(i));
    y(i) = timeit(f);
end

figure()
plot(x, y)

Почему именно это может иметь отношение к вашей настройке, когда 2 ^ 512 вместо 2 ^ 1024, я не очень понимаю.

(Обратите внимание, что я использовал 2 .^ ... вместо power(2, ...), но результаты те же.)

---

Кроме того, выполнение кода @ CrisLuengo в моей системе на самом деле не воспроизводит скачок.

x = 500:540;
t = zeros(size(x));
for ii = 1:numel(x)
    %m = 1:x(ii);
    m = 500*rand(1,x(ii));
    t(ii) = timeit(@()power(2,m));
end
plot(x,t)

все имеющиеся на данный момент свидетельства указывают на то, что всплеск связан с задержкой / прогревом JIT.