Вопрос по c, casting, performance – Приведение производительности от size_t к двойному

28

TL; DR: Почему умножение / приведение данных вsize_t медленно и почему это зависит от платформы?

У меня проблемы с производительностью, которые я до конца не понимаю. Контекст представляет собой устройство захвата кадров камеры, где изображение uint16_t размером 128x128 считывается и обрабатывается с частотой несколько 100 Гц.

При постобработке я генерирую гистограммуframe->histo который имеетuint32_t и имеетthismaxval = 2 ^ 16 элементов, в основном я подсчитываю все значения интенсивности. Используя эту гистограмму, я вычисляю сумму и квадратную сумму:

double sum=0, sumsquared=0;
size_t thismaxval = 1 << 16;

for(size_t i = 0; i < thismaxval; i++) {
    sum += (double)i * frame->histo[i];
    sumsquared += (double)(i * i) * frame->histo[i];
}

Профилируя код с профилем, я получил следующее (образцы, процент, код):

 58228 32.1263 :  sum += (double)i * frame->histo[i];
116760 64.4204 :  sumsquared += (double)(i * i) * frame->histo[i];

или первая строка занимает 32% процессорного времени, вторая строка 64%.

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

uint_fast64_t isum=0, isumsquared=0;

for(uint_fast32_t i = 0; i < thismaxval; i++) {
    isum += i * frame->histo[i];
    isumsquared += (i * i) * frame->histo[i];
}

работает ~ в 10 раз быстрее. Тем не менее, это снижение производительности также зависит от платформы. На рабочей станции Core i7 CPU 950 @ 3,07 ГГц код работает в 10 раз быстрее. На моем Macbook8,1, который имеет Intel Core i7 Sandy Bridge 2,7 ГГц (2620M), код всего в 2 раза быстрее.

Теперь мне интересно:

Почему оригинальный код такой медленный и легко ускоряется? Почему это сильно зависит от платформы?

Обновить

Я скомпилировал приведенный выше код с помощью

g++ -O3  -Wall cast_test.cc -o cast_test

Update2:

Я запускал оптимизированные коды через профилировщик Инструменты на Mac, какАкул) и нашел две вещи:

1) Сам цикл в некоторых случаях занимает значительное время.thismaxval имеет типsize_t.

for(size_t i = 0; i < thismaxval; i++) занимает 17% моего общего времени выполненияfor(uint_fast32_t i = 0; i < thismaxval; i++) берет 3,5%for(int i = 0; i < thismaxval; i++) не отображается в профилировщике, я предполагаю, что это меньше, чем 0,1%

2) Типы данных и данные о кастингах таковы:

sumsquared += (double)(i * i) * histo[i]; 15% (сsize_t i)sumsquared += (double)(i * i) * histo[i]; 36% (сuint_fast32_t i)isumsquared += (i * i) * histo[i]; 13% (сuint_fast32_t i, uint_fast64_t isumsquared)isumsquared += (i * i) * histo[i]; 11% (сint i, uint_fast64_t isumsquared)

Удивительно,int быстрее чемuint_fast32_t?

Update4:

Я провел еще несколько тестов с разными типами данных и разными компиляторами на одной машине. Результаты приведены ниже

Для testd 0 - 2 соответствующий код

    for(loop_t i = 0; i < thismaxval; i++)
        sumsquared += (double)(i * i) * histo[i];

сsumsquared двойной иloop_t size_t, uint_fast32_t а такжеint для тестов 0, 1 и 2.

Для тестов 3--5 код

    for(loop_t i = 0; i < thismaxval; i++)
        isumsquared += (i * i) * histo[i];

сisumsquared типаuint_fast64_t а такжеloop_t опять такиsize_t, uint_fast32_t а такжеint для тестов 3, 4 и 5.

Я использовал следующие компиляторы: gcc 4.2.1, gcc 4.4.7, gcc 4.6.3 и gcc 4.7.0. Временные параметры указаны в процентах от общего времени процессора, поэтому они показывают относительную производительность, а не абсолютную (хотя время выполнения было довольно постоянным в 21 с). Время процессора для обеих двух строк, потому что я не совсем уверен, правильно ли разделитель разделил две строки кода.

gcc:    4.2.1  4.4.7  4.6.3  4.7.0
----------------------------------
test 0: 21.85  25.15  22.05  21.85
test 1: 21.9   25.05  22     22
test 2: 26.35  25.1   21.95  19.2
test 3: 7.15   8.35   18.55  19.95
test 4: 11.1   8.45   7.35   7.1
test 5: 7.1    7.8    6.9    7.05

или

Исходя из этого, кажется, что приведение стоит дорого, независимо от того, какой тип целого числа я использую.

Также кажется, что gcc 4.6 и 4.7 не могут должным образом оптимизировать цикл 3 (size_t и uint_fast64_t).

Ты имеешь ввидуuint_fast32_t isum? Я мог бы попытаться, хотя я думаю, что это могло бы переполниться, поэтому я использовал uint_fast64_t. Tim
Можете ли вы опубликовать разборки? harold
Я допустил небольшую ошибку в предыдущем комментарии, больше не могу ее редактировать. Не обращайте внимания на это :). Если вы печатаетеsizeof(uint_fast32_t), я думаю, что вы увидите 8 байтов. Это означает, что он имеет тот же размер, что и машинная инструкция, и, возможно, он быстрее обрабатывается. Yuri
Well, для 1 .: Причина почему-то диктует, что приведение целых чисел к числам с плавающей точкой и выполнение операций с плавающей запятой должно выполняться медленнее, чем выполнение операций с непосредственным использованием int (хотя int-to-float не должно быть таким же злым, как float-to-int), даже более так с не таким оптимальным стеком x87. Вы компилируете его с поддержкой SSE? Christian Rau
не могли бы вы попробовать это сuint_fast32_t? Неожиданное предположение состоит в том, что он быстрее из-за того, что второй тип данных имеет ту же длину бит, что и машинные инструкции (64-битная). Догадываясь, что у вас есть как минимум 64-битная машина. Я ожидаю, что fast32 также медленнее.редактироват не могли бы вы также проверить размер обоихuint_fast32_t а такжеuint_fast64_t? Я предполагаю, что 32 на самом деле 64-битные. Yuri

Ваш Ответ

2   ответа
4

Код медленный, потому что включает в себя преобразование целочисленных в плавающие типы данных. Вот почему он легко ускоряется, когда вы используете также целочисленный тип данных для переменных суммы, потому что он больше не требует преобразования с плавающей запятой. Разница является результатом нескольких факторов. Например, это зависит от того, насколько эффективно платформа может выполнять преобразование с плавающей запятой. Кроме того, это преобразование может также испортить внутреннюю оптимизацию процессора в программном потоке и механизме прогнозирования, кэшах, ... а также внутренние возможности параллелизации процессоров могут оказать огромное влияние на такие вычисления.

Для дополнительных вопросов:

"Удивительно, но int быстрее, чем uint_fast32_t"? Каковы sizeof (size_t) и sizeof (int) на вашей платформе? Одно из предположений, которое я могу сделать, заключается в том, что оба, вероятно, являются 64-битными и, следовательно, приведение к 32-битному не только может дать вам ошибки в расчетах, но также включает штраф за приведение к разным размера

В общем, старайтесь избегать видимых и скрытых приведений настолько хорошо, насколько это возможно, если они действительно не нужны. Например, попытайтесь выяснить, какой реальный тип данных скрыт за "size_t" в вашей среде (gcc), и используйте его для переменной цикла. В вашем примере тип квадрата uint не может быть типом данных с плавающей точкой, поэтому нет смысла использовать здесь double. Придерживайтесь целочисленных типов для достижения максимальной производительности.

Благодарность. Я знал, что броски не идеальны, но я не знал, что это так дорого. Что касается вашего второго пункта: машина 64-битная, ноuint_fast32_t должно бытькак миниму 32-битная, если я правильно понимаю, так что, если 64-битная не должна использовать это вместо этого? Я не понимаю, почему это объясняет, чтоint быстрее чемuint_fast32_t. Также я не понимаю, почемуforроизводительность @ -loop сильно отличается для разных целочисленных типов. Tim
Ну, так какuint_fast32_t должен быть самым быстрым целочисленным типом, по крайней мере, с 32 битами, реализация должна быть достаточно умной, чтобы использовать 64-битный тип, если это быстрее в 64-битной системе. Но в остальном хороший ответ, конечно. Christian Rau
Я провел еще несколько тестов, и суть в том, что кастинг просто дорогой. Я был удивлен, что это было так дорого, хотя. Tim
Другое различие между uint_fast32_t и int заключается в подписанности, я не могу придумать какой-либо внутренней причины, почему это должно иметь значение, но мы говорим о том, как усердно разработчик компилятора и разработчик чипа задумывались о том, чтобы заставить конкретные редкие последовательности идти быстро. jthill
одна вещь, которую вы можете сделать, это поддерживать счетчики параллельных циклов,double di = 0; for ( int i=0 ; i < thismaxval ; ++i,++di ). jthill
1

uint64_t с плавающей точкой медленнее, потому что есть только инструкции для преобразованияint64_t, int32_t а такжеint16_t. int16_t и в 32-битном режимеint64_t можно конвертировать только с помощью инструкций x87, но не SSE.

При конвертацииuint64_t в плавающую точку, GCC 4.2.1 сначала преобразует значение, как если бы оно былоint64_t а затем добавляет 2 64 если это было отрицательно, чтобы компенсировать. (При использовании x87 в Windows и * BSD, или если вы изменили контроль точности, имейте в виду, что преобразование игнорирует контроль точности, но дополнение учитывает его.)

Анuint32_t сначала расширяется доint64_t.

При преобразовании 64-разрядных целых чисел в 32-разрядном режиме на процессорах с определенными 64-разрядными возможностями проблема пересылки из хранилища в загрузку может привести к зависанию. 64-разрядное целое число записывается как два 32-разрядных значения и считывается как одно 64-разрядное значение. Это может быть очень плохо, если преобразование является частью длинной цепочки зависимостей (не в этом случае).

Похожие вопросы