Фон
Мой вопрос мотивирован простыми наблюдениями, что несколько подрывает убеждения/предположения, часто проводимые/сделанные опытными пользователями MATLAB:
- MATLAB очень хорошо оптимизирован, когда речь идет о встроенных функциях и основных функциях языка, таких как индексирующие векторы и матрицы.
- Петли в MATLAB медленны (несмотря на JIT) и, как правило, следует избегать, если алгоритм может быть выражен в нативной, "векторизованной" манере.
В нижней строке: функциональность ядра MATLAB эффективна и пытается превзойти ее, используя код MATLAB, трудно, если не невозможно.
Исследование эффективности векторной индексации
Примеры кодов, показанных ниже, являются такими же фундаментальными, как и:: Я назначаю скалярное значение всем векторам. Во-первых, я выделяю пустой вектор x
:
tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.
Имея x
, я хотел бы установить все его записи в одно и то же значение. На практике вы сделали бы это по-другому, например, x = value*ones(1e8,1)
, но здесь нужно исследовать эффективность векторной индексации. Самый простой способ - написать:
tic; x(:) = 1; toc
Elapsed time is 0.094316 seconds.
Позвольте вызвать метод 1 (от значения, присвоенного x
). Это кажется очень быстрым (быстрее по крайней мере, чем распределение памяти). Поскольку единственное, что я здесь делаю, - это работать с памятью, я могу оценить эффективность этого кода, вычислив полученную эффективную пропускную способность памяти и сравнив ее с пропускной способностью аппаратного обеспечения моего компьютера:
eff_bandwidth = numel(x) * 8 bytes per double * 2 / time
В приведенном выше примере я умножаюсь на 2
, потому что, если SSE-потоковая передача не используется, для установки значений в памяти требуется, чтобы вектор считывался и записывался в память. В приведенном выше примере:
eff_bandwidth(1) = 1e8*8*2/0.094316 = 17 Gb/s
STREAM-эталонная пропускная способность памяти моего компьютера составляет около 17,9 Гбит/с, так что действительно - MATLAB обеспечивает почти максимальную производительность в этом случае! Пока что так хорошо.
Метод 1 подходит, если вы хотите установить для всех векторных элементов какое-то значение. Но если вы хотите получить доступ к элементам в каждой записи step
, вам нужно подставить :
, например, 1:step:end
. Ниже приведено прямое сравнение скорости с методом 1:
tic; x(1:end) = 2; toc
Elapsed time is 0.496476 seconds.
Пока вы не ожидали, что он будет выполнять какие-либо другие действия, метод 2 явно представляет собой большую проблему: замедление фактора 5 без причины. Мое подозрение в том, что в этом случае MATLAB явно выделяет индексный вектор (1:end
). Это несколько подтверждается использованием явного размера вектора вместо end
:
tic; x(1:1e8) = 3; toc
Elapsed time is 0.482083 seconds.
Методы 2 и 3 выполняют одинаково плохо.
Другая возможность - явно создать индексный индекс id
и использовать его для индексации x
. Это дает вам самые гибкие возможности индексирования. В нашем случае:
tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc
Elapsed time is 1.208419 seconds.
Теперь это действительно что-то - 12-кратное замедление по сравнению с методом 1! Я понимаю, что он должен работать хуже, чем метод 1 из-за дополнительной памяти, используемой для id
, но почему это намного хуже, чем методы 2 и 3?
Попробуйте дать петлям попробовать - как можно более безнадежным.
tic;
for i=1:numel(x)
x(i) = 5;
end
toc
Elapsed time is 0.788944 seconds.
Большой сюрприз - цикл бьет метод vectorized
4, но все еще медленнее, чем методы 1, 2 и 3. Оказывается, что в этом конкретном случае вы можете сделать это лучше:
tic;
for i=1:1e8
x(i) = 6;
end
toc
Elapsed time is 0.321246 seconds.
И это, пожалуй, самый причудливый результат этого исследования - написанный MATLAB цикл значительно превосходит индексирование собственного вектора. Это, конечно, не так. Заметим, что цикл JIT'ed все еще в 3 раза медленнее теоретического пика, почти полученного методом 1. Таким образом, все еще есть много возможностей для улучшения. Это просто удивительно (более сильное слово было бы более подходящим), что обычное "векторизованное" индексирование (1:end
) еще медленнее.
Вопросы
- простая индексация в MATLAB очень неэффективна (методы 2, 3 и 4 медленнее, чем метод 1), или я что-то пропустил?
- почему метод 4 (столько) медленнее, чем методы 2 и 3?
- Почему использование
1e8
вместоnumel(x)
в качестве привязки цикла ускоряет код в 2 раз?
Edit После прочтения комментария Jonas, вот еще один способ сделать это с использованием логических индексов:
tic;
id = logical(ones(1, 1e8));
x(id) = 7;
toc
Elapsed time is 0.613363 seconds.
Гораздо лучше, чем метод 4.
Для удобства:
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