Зловещие циклы

[warlock66613]

Я ещё вижу такую разницу: в одном случае pos_x только инкреметируется, а в другом - ещё и вычислятся с помощью умножения на счётчик цикла (что вообще-то тоже можно заменить прибавлением константы). Я не уверен, имеет ли это значение (и даже если да, то какой вариант лучше), тем более это всё во внешнем цикле, а не во внутреннем, но разница такая есть.

[Andrey_Kireew]

photon в сообщении #1450696 писал(а):

Я так понимаю, вас бОльше все-таки должно интересовать не почему быстрее или медленнее, а как сделать быстрее

нет, больше меня интересует именно почему одно быстрее другого, причём в разы, и при одинаковых условиях
Я бы согласился с тем, что проблема с памятью, и с тем, что он берёт данные из двух массивов. Но ведь во втором случае так же используется 2 массива, просто в первом варианте данные берутся из двух массивов и результат складывается в переменной, а во втором, данные хоть и берутся только из одного массива, но записываются не в одну переменную, а в разные элементы другого массива. Так, что в обоих случаях, обращение идёт к двум разнесённым в памяти массивам.
Есть ещё один аргумент против "тормозов" памяти, о котором я писал в самом начале - сначала массив заполнятся по строкам, т.е. обращение к нему шло не подряд, а через Nstr элементов. Я сделал нумерацию по столбцам, обращение стало подряд. В таких случаях обычно наблюдается многократное ускорение, во всех - но не в этом. Ускорение конечно произошло, но не более чем на 10%. Всё это вызывает у меня просто недоумение. В этом цикле и тормозить то нечему, и тем не менее это факт.

Ну, а то что в этом месте - это точно. Может, конечно, не 90% времени тратится в этом цикле, а 85% или даже 80 - сути проблемы это совсем не меняет. И уточнение этих цифр до десятых долей % мне ничем не поможет.

-- 03.04.2020, 03:39 --

warlock66613 в сообщении #1450709 писал(а):

в одном случае pos_x только инкреметируется, а в другом - ещё и вычислятся с помощью умножения на счётчик цикла

да, это так, но как Вы сами верно заметили, разница от этого не особенно большая, а с учётом того, что эта операция выполняется во внешнем цикле - скорее всего, она вообще не оказывает сколь либо заметного влияния. А тут различия в 4 раза ...

[Munin]

Про кэш-память вы чего-нибудь слышали?

[Dmitriy40]

Andrey_Kireew
Кроме "замедления в 4 раза" неплохо бы ещё указывать и абсолютные цифры замедления, потому что если это продолжение предыдущей вашей темы, то там всё время внутреннего цикла укладывается в одну-две мкс (все 2048 итераций) и все данные лежат в L1d — и оба этих условия важны для понимания происходящего! 2000 итераций не так много, тут могут, подчёркиваю, могут, не обязательно 100%, проявляться и неточности измерения времени, и эффекты от разного кода на выходе компилятора (в 1.5-2 раза по скорости легко, особенно для хорошо оптимизированного), и расположение в памяти (точнее когда оно попадёт в кэш), и количество умножений (я совершенно не уверен что умножение на переменную цикла [не]будет заменено компилятором на суммирование с константой), и вообще в первом коде компилятор может выкинуть внутренний цикл целиком так как val потом не используется ...

Причину замедления я не вижу. Самое разумное было высказано сразу же, проблемы с clock().

photon в сообщении #1450673 писал(а):

Ускорения можно добиться, перейдя к целочисленной арифметике. Во-первых, само по себе умножение-сложение даблов медленнее,

Вот этот совет уже несколько лет как не универсальный, в разных случаях может быть очень по разному: например умножение int64 не векторизируется, а умножение double очень даже, причём даже с вычитанием (FMA в его процессоре присутствует, дело лишь за компилятором). Скалярное же произведение double вообще вдвое быстрее int64 (два вычислительных блока вместо одного) при почти одинаковой латентности (3-4 такта).
Andrey_Kireew, это кстати пример необходимости пользоваться относительно свежими компиляторами, чтобы они поддерживали возможности процессора.

Вообще же, для такого слишком простого кода, каждый огрех компилятора от идеала (грубо каждая лишняя команда процессора) выливается в десятки процентов замедления, а при приближении к предельной скорости замедление может составлять и 50%-100%-150% очень даже легко (в прошлой теме мне пришлось конкретно извращаться в одном из вариантов кода чтобы не допустить разрастания кода из 8 команд ещё на одну команду, замедляющей скорость в полтора раза!).

[Andrey_Kireew]

Dmitriy40 в сообщении #1450720 писал(а):

если это продолжение предыдущей вашей темы

Нет, это совсем не то, с тем всё уже нормально. Но повторюсь, разница во времени обнаруживается путем непосредственного наблюдения за работой программ. Разница эта очевидна, и при многократном запуске примерно одинаковая. Измеряется она в секундах (разумеется - это совокупное время всех вызовов этого злополучного цикла). Опять же, повторяюсь, clock() использовался только для поиска узкого места. Уж на этот цикл я никак подумать не мог, а дело оказалось именно в нём. Расставляю clock() по коду, и смотрю сколько времени зависает какой кусок. На этот цикл приходится примерно 90% всего времени. Тоже самое сделал в другой программе, т.к. там есть похожий цикл. И выходит, что время выполнения различается у них в 4 раза. И самое главное, от запуска к запуску она не меняется.

К стати, в предыдущем сообщении я случайно ввёл читателей в заблуждение. При изменении порядка заполнения матрицы скорость выполнения цикла действительно изменяется незначительно. Но оно не уменьшается, а увеличивается! Я это осознал только недавно, раньше даже и не думал что так может быть. Оказывается, так работает быстрее:

Используется синтаксис C++

T+=clock()-t0;

for (j=0; j<Lstr; j++)
{
     t0=clock();
        val=0; pos_x=X+j;  
        for (int ii=0; ii<nVar; ii++)
        {val+=(*(b+ii)**pos_x); pos_x+=Lstr;}
      T+=clock()-t0;

...........
}
 

-- 03.04.2020, 06:30 --

warlock66613 в сообщении #1450709 писал(а):

одном случае pos_x только инкреметируется, а в другом - ещё и вычислятся с помощью умножения на счётчик цикла (что вообще-то тоже можно заменить прибавлением константы)

к стати, в свете последних событий решил последовать этому совету - но это абсолютно ни на что не повлияло

[photon]

Andrey_Kireew в сообщении #1450726 писал(а):

Но оно не уменьшается, а увеличивается!

Если ваша матрица X маленькая, то разницы быть не должно, если большая, то этот результат странный и говорит лишь о том, что эффект вызван не этим циклом, а тем, что вне его.

[Andrey_Kireew]

Странный не то слово - должно быть как бы всё наоборот.
Изучая код, выяснил ещё один нюанс. В первом варианте (который в 4 раза быстрее) pos_x и pos_v - это указателя на один и тот же массив, но на разные его участки, кто его знает - может они все оказываются в кэш одновременно. Во втором варианте b и X это разные массивы, могут находиться друг от друга далеко. Может дело и в этом. Но откуда берётся ускорение, при чтении X через Lstr а не подряд, неясно.

Массив X средний - матрица несколько тыс. на несколько сотен, видимо несколько мегабайт, соответственно, сдвиг Lstr несколько тысяч. Массив b маленький, всего несколько сотен элементов.

[aitap]

Andrey_Kireew в сообщении #1450592 писал(а):

я пытался использовать gprof, но у меня ничего не получилось, out файл так и не появился,

Если Вы на Windows, попробуйте Very Sleepy. Если на Linux, используйте perf и/или KCachegrind. На обе платформы также есть Intel VTune, доступный вместе с компиляторами и математической библиотекой бесплатно для научных целей.

[Dmitriy40]

Насчёт обхода по столбцам вместо обхода по строкам.
Тут ситуация странная, при маленьких матрицах (влезающих в L1) разницы быть не должно. Если матрица больше размера L1, но влезает в L2, то будет ли разница зависит от скорости самих вычислений, что из них будет тормозить, вычисления или пересылка между L2 и L1. Аналогично и с размером между L2 и L3, но тут надо уже учитывать и наличие 4(8)-х ядер. Ну а если размер матрицы больше (примерно двойного-тройного) размера L3, то скорость будет ограничиваться скоростью памяти. Это в общем.
При прохождении по столбцам (с большим шагом по памяти) в кэш читается вся строка кэша, 64 байта, для каждого массива. В худшем случае это даёт 8-ми кратное замедление по трафику (используется лишь 8 байт из прочитанных 64). Трафик записи, а это снова 8 байт из 64-х, если запись тоже пойдёт по столбцам, считается отдельно и в удвоенном размере если выходной массив не был прочитан как аргумент для вычислений (чтобы записать байт (или 8 байтов) сначала читается строка кэша, в неё пишется байт (или double), потом она сбрасывается в память). Но, если поток записи короткий (55 записей), то он осядет в буфере записи и тормозить вычисления не будет, т.е. для коротких внутренних циклов запись данных тормозить не будет, если конечно она укладывается в суммарное время внешнего цикла с другими вычислениями.
Если по трафику между кэшами всё проходит (тормозит не оно), то латентность кэшей выше L1 можно уже не учитывать, процессор аппаратно заранее продвинет десятки следующих требуемых данных в L1 (предвыборка), во всяком случае для равномерных выборок (с постоянным шагом, любым).

В итоге, проход по столбцам (с большим шагом по памяти) не может быть быстрее прохода по строкам (с единичным шагом по памяти). Но может быть медленнее, от 8 раз, до десятков раз (если доступ к памяти будет более случайным, латентность резко снизит скорость).

[Andrey_Kireew]

Dmitriy40 в сообщении #1450892 писал(а):

В итоге, проход по столбцам (с большим шагом по памяти) не может быть быстрее прохода по строкам (с единичным шагом по памяти)

Я это и сам понимаю, но тем не менее, наблюдается именно это. Нужно ещё всё хорошенько перепроверить ...

[photon]

Чтобы перепроверить, я вам снова рекомендую записать код читаемо.
Даю пример, который должен помочь, - фактически, читаемая реализация внутреннего цикла в одну строку.

Используется синтаксис C++

#include <numeric>
#include <vector>

///...

std::vector<double> X = {0.0, 1.0, 2.0, 5.0, 10.0};
std::vector<double> b = {1.0, 2.0, 3.0};
size_t shift = 1;

///...


double const val = std::inner_product(b.begin(), b.end(), X.begin() + shift, 0.0);
 

[Dmitriy40]

photon в сообщении #1450958 писал(а):

Даю пример, который должен помочь, - фактически, читаемая реализация внутреннего цикла в одну строку.

А я даже добавлю, что такой цикл компилятору проще векторизовать/распараллелить.

(Оффтоп)

Хотя чисто идеологически мне такой стиль не нравится, предпочитаю разделять объявление/инициализацию переменных и вычисления. Когда это не вступает в противоречие с производительностью.

[Mihaylo]

Andrey_Kireew в сообщении #1450471 писал(а):

в чём тут может быть дело?

Попробуйте убрать у счетчика циклов ii определение типа int. Как вы это делаете для j.

-- 02.05.2020, 10:18 --

В ассемблере отличие лишь в пяти строчках. Там, где написан комментарий "старый код", эта строчка присутствует лишь в варианте 1 (медленный код с поэлементным инкрементом). Комментарий "новый код" - эти строчки присутствуют в варианте 2 (быстрый код с чересстрочным инкрементом).

Используется синтаксис ASM

func():
push rbp
mov rbp, rsp
sub rsp, 48
mov DWORD PTR [rbp-28], 1000
mov DWORD PTR [rbp-32], 1000
mov eax, DWORD PTR [rbp-32]
cdqe
sal rax, 3
mov rdi, rax
call malloc
mov QWORD PTR [rbp-40], rax
mov eax, DWORD PTR [rbp-32]
cdqe
sal rax, 3
mov rdi, rax
call malloc
mov QWORD PTR [rbp-48], rax
mov DWORD PTR [rbp-20], 0
.L5:
mov eax, DWORD PTR [rbp-20]
cmp eax, DWORD PTR [rbp-28]
jge .L6
pxor xmm0, xmm0
movsd QWORD PTR [rbp-8], xmm0
mov eax, DWORD PTR [rbp-20]
imul eax, DWORD PTR [rbp-32] //старый код
cdqe
lea rdx, [0+rax*8]
mov rax, QWORD PTR [rbp-40]
add rax, rdx
mov QWORD PTR [rbp-16], rax
mov DWORD PTR [rbp-24], 0
.L4:
mov eax, DWORD PTR [rbp-24]
cmp eax, DWORD PTR [rbp-32]
jge .L3
mov eax, DWORD PTR [rbp-24]
cdqe
lea rdx, [0+rax*8]
mov rax, QWORD PTR [rbp-48]
add rax, rdx
movsd xmm1, QWORD PTR [rax]
mov rax, QWORD PTR [rbp-16]
movsd xmm0, QWORD PTR [rax]
mulsd xmm0, xmm1
movsd xmm1, QWORD PTR [rbp-8]
addsd xmm0, xmm1
movsd QWORD PTR [rbp-8], xmm0
mov eax, DWORD PTR [rbp-28] //новый код
cdqe           //новый код
sal rax, 3         //новый код
add QWORD PTR [rbp-16], rax //новый код
add QWORD PTR [rbp-16], 8 //старый код
add DWORD PTR [rbp-24], 1
jmp .L4
.L3:
add DWORD PTR [rbp-20], 1
jmp .L5
.L6:
nop
leave
ret

[photon]

Mihaylo в сообщении #1459489 писал(а):

В ассемблере отличие лишь в пяти строчках.

Было бы хорошо при этом указывать для какого компилятора и с какими ключами компиляции.

[Mihaylo]

Компилятор x86-64 gcc 9.3, опции по умолчанию вроде бы.