Войти
ПрограммированиеФорумОбщее

Подсчет количества ненулевых элементов массива из рубрики "Странное дело".

Страницы: 1 2 Следующая »
#0
(Правка: 21:54) 20:51, 3 янв 2022

  Как-то на досуге экспериментировал с циклами с ветвлениями и обнаружил нечто странное в поведении оных. Начну с псевдокода(точнее код на Free pascal) для подсчета количества ненулевых элементов в массиве с неотрицательными числами:

function ArrNzItCnt(constref arr_:TLongWordArr): longword;
var
  i: integer;
begin
  Result:=0;
  for i:=0 to Length(arr)-1 do
    if arr[i]<>0 then
      Inc(Result);
end;

Ну, тут как бы все очевидно с производительностью скажете вы. Давайте теперь посмотрим, что будет, если скармливать функции разные по разреженности массивы.
  В дальнейшем буду проводить эксперименты над массивом с 10000000 элементами:

arr_test: array of longword;

Эксперимент №1 - заполним весь массив arr нулями:

SetLength(arr_test,10000000);
for i:=0 to 10000000-1 do
  arr_test[i]:=0;
ArrNzItCnt(arr_test);

Время выполнения 15 мс.

Едем дальше!
Эксперимент №2 - заполним весь массив arr единицами:

SetLength(arr_test,10000000);
for i:=0 to 10000000-1 do
  arr_test[i]:=1;
ArrNzItCnt(arr_test);

Время выполнения 30 мс.

Эксперимент №3 - заполним весь массив arr нулями и единицами рандомно:

SetLength(arr_test,10000000);
for i:=0 to 10000000-1 do
  arr_test[i]:=Random(2);
ArrNzItCnt(arr_test);

Время выполнения 71 мс. Вот тут уже начинается что-то интересное). Но и это еще не все).

Эксперимент №4 - заполним весь массив arr нулями по нечетным номерам и единицами по четным:

SetLength(arr_test,10000000);
for i:=0 to 5000000-1 do
  arr_test[2*i+0]:=1;
for i:=0 to 5000000-1 do
  arr_test[2*i+1]:=0;
ArrNzItCnt(arr_test);

Время выполнения 83-106 мс.

Теперь поступим наоборот.
Эксперимент №5 - заполним весь массив arr нулями по четным номерам и единицами по нечетным:

SetLength(arr_test,10000000);
for i:=0 to 5000000-1 do
  arr_test[2*i+0]:=0;
for i:=0 to 5000000-1 do
  arr_test[2*i+1]:=1;
ArrNzItCnt(arr_test);

Время выполнения 93-111 мс.

Теперь запишем наш цикл в функции ArrNzItCnt(arr) без ветвлений:

function ArrNzItCnt(constref arr:TLongWordArr): longword;
var
  n,m: longword;
  i  : integer;
begin
  Result:=0;
  n     :=1+Trunc(ln(Double(MAXDWORD))/ln(2)); 
  m     :=1<<n-1;
  for i:=0 to Length(arr)-1 do
    Inc(Result,(arr[i]+m)>>n);
end; {$endregion}

Тут, время выполнения на исходном массиве при любом количестве в нем нулей и единиц постоянно от эксперимента к эксперименту, как и ожидается, и составило 30 мс., то есть в два раза хуже, чем "идеальный"(Эксперимент №1) случай с ветвлениями и почти в 3.7 раз лучше, чем "худший"(Эксперимент №5) случай с ветвлениями. Напрашиваются некоторые вопросы по данному поводу. Почему для цикла с ветвлениями такой разброс и увеличение времени исполнения не "нерегулярных" массивах? Это связано как-то с кеш-промахами или предсказателем ветвлений? И насколько "разреженным" должен быть массив чтобы применение цикла без ветвлений было предпочтительней, чем с ветвлениями? Также, если кому не сложно, можете проверить на других языках, какая будет разница времени исполнения(потому как возможно сам компилятор FPC что-то чудит с оптимизациями).
P.S. Мне эта тема важна прежде всего тем, что у меня в движке есть обьекты "сплайны", спрайты которых сжимаются на лету и для такого сжатия нужно быстро делать сабж.

#1
21:05, 3 янв 2022

ArtProg
> без ветвлений
> if arr[i]<>0 then
чё?

#2
(Правка: 21:20) 21:08, 3 янв 2022

  А что смутило-то? Все верно. Сначала цикл с ифами, потом без.
P.S. А хотя да, Вы правы, заменю на "с ветвлениями", так как странности происходят именно с ними).

#3
(Правка: 22:20) 22:20, 3 янв 2022

ArtProg
> или предсказателем ветвлений?
Похоже. Ну сам факт берётся переход или нет (а иначе у "все 0" и "все 1" была бы одинаковая скорость).
Чуть странно, что даже регулярный пример с чередованием тормозит. Вроде многие предсказатели умеют такое.

Кеш-промахи-то тут причём? Порядок доступа к памяти тут вроде как не зависит от входных данных.

Пробовал

for i:=0 to Length(arr)-1 do
      Inc(Result,Ord(arr[i]<>0));

?

#4
22:30, 3 янв 2022

> Ord(arr[i]<>0)
Вроде компилируется без ветвлений:
https://godbolt.org/z/r84Edse8j

#5
(Правка: 22:50) 22:38, 3 янв 2022

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

#6
22:48, 3 янв 2022

FordPerfect
>Чуть странно, что даже регулярный пример с чередованием тормозит. Вроде многие предсказатели умеют такое.
  Может быть в современных процессорах так и есть. У меня тестировалось ведь на системе 11-12-летней давности).

#7
23:39, 3 янв 2022

ArtProg
> и тогда возникает логичный вопрос: насколько массив должен быть плотным
Так такое имеет смысл замерять.

Там ещё возникают зависимости по, собственно, инкрементируемому значению, которых в версии без ветвлений с 0 нет.
Это можно попробовать решить разворотом цикла и несколькими счётчиками.

int count(const int *arr,int n)
{
    int c0=0,c1=0,c2=0,c3=0,c=0,n4=n>>2;
    for(int i=0;i<n4;++i)
    {
        int id=i<<2;
        c0+=(arr[id+0]!=0);
        c1+=(arr[id+1]!=0);
        c2+=(arr[id+2]!=0);
        c3+=(arr[id+3]!=0);
    }
    for(int i=n4<<2;i<n;++i)
    {
        c+=(arr[i]!=0);
    }
    return c+c0+c1+c2+c3+c4;
}
#8
0:08, 4 янв 2022

В C++ какие-то неинтересные результаты:
https://rextester.com/KMA87580

#9
0:44, 4 янв 2022

> В C++ какие-то неинтересные результаты:
Логично:
https://godbolt.org/z/cah4MqG5j
Компилятор сам заменил branch на суммирование с флагом (точнее вычитание с займом).

#10
6:16, 4 янв 2022

я с трудом верю, что branch predictor не смог в чередующиеся значения

#11
(Правка: 7:09) 7:09, 4 янв 2022

У меня еще со времён Pentium Pro осталось чёткое ощущение, что когда размеры циклов крайне небольшие, то предсказать производительность крайне трудно.
Общие лекалы конечно есть, но вот подобные девиации как в сабже всегда надо ожидать.
Можно столкнуться например с тем, что добавив операцию в цикл мы повысим производительность на треть.
Как? Почему?
А просто в конвеер лучше улеглось и всё. Причём как и почему - это снаружи трудно догадаться и с каждым новым поколением процессоров меняется на 200%.
В какой то момент я словил то, что на пентиуме чем меньше цикл был по инструкциям, тем медленнее он исполнялся (заметно), а на AMD более нового поколения все те же циклы выполнялись практически за одинаковое время.
Поэтому надо осторожно к этим вопросам подходить.

#12
7:11, 4 янв 2022

Suslik
> я с трудом верю, что branch predictor не смог в чередующиеся значения
Судя по https://en.wikipedia.org/wiki/Branch_predictor , начиная с Pentium II - должен вроде данный паттерн распознавать.

#13
(Правка: 8:07) 8:04, 4 янв 2022

недавно смотрел интервью с джимом келлером (кто не в курсе, его без ограничения общности можно считать отцом x64 вообще и большинства их реализаций в частности). так он там задвигал какой-то лютый матан про едва ли не general ai нейросети, которые занимают половину кристалла CPU и которые занимаются исключительно branch prediction'ом. короче, по его словам, branch prediction — это, несомненно, самая сложная и самая критически важная часть любого современного cpu. и, разумеется, самая мутная для любого программиста, который типично понятия не имеет, что именно она делает и как.

но вообще джим келлер давно известен тем, что его троллинг не уступает его гениальности, поэтому тут трудно сказать.

#14
(Правка: 9:01) 8:52, 4 янв 2022

попробовал на IDEONE (там линуксы какие-то крутятся)
результаты тестов разнятся в 4м и 5м... прироста по времени нет. Вполне себе сопоставимы с 1м и 2м тестами

+ код, если IDE one помрёт
Normal Test 1: 6ms
Normal Test 2: 8ms
Normal Test 3: 43ms
Normal Test 4: 7ms
Normal Test 5: 8ms
Math Test 1: 11ms
Math Test 2: 12ms
Math Test 3: 11ms
Math Test 4: 11ms
Math Test 5: 11ms
Boolcast Test 1: 8ms
Boolcast Test 2: 9ms
Boolcast Test 3: 8ms
Boolcast Test 4: 8ms
Boolcast Test 5: 8ms
Страницы: 1 2 Следующая »
ПрограммированиеФорумОбщее