Эффективность роли от size_t до double

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

У меня возникают проблемы с производительностью, которые я не совсем понимаю. Контекст - это захват кадра камеры, где изображение 128x128 uint16_t считывается и обрабатывается с частотой 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 950 @3.07GHz код в 10 раз быстрее. На моем Macbook8,1, который имеет Intel Core i7 Sandy Bridge 2,7 ГГц (2620M), код только в 2 раза быстрее.

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

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

Update:

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

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

Update2:

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

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 a double и 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 секунду). Время cpu для обеих двух строк, потому что я не совсем уверен, правильно ли профайлер разделяет две строки кода.

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

или

casting performance

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

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

Ответы

Ответ 1

По оригинальным вопросам:

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

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

  • "Удивительно, что int быстрее, чем uint_fast32_t"? Что за sizeof (size_t) и sizeof (int) на вашей платформе? Можно предположить, что оба вероятно, 64 бит, и поэтому приведение к 32 бит не только может дать вам ошибок расчета, но также включает в себя различное исполнение штраф.

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

Ответ 2

В x86 преобразование 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, или если вы изменили контроль точности, остерегайтесь того, что преобразование игнорирует контроль точности, но дополнение уважает его.)

An uint32_t сначала распространяется на int64_t.

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