Целое число против двойной арифметической производительности? - PullRequest
Новая
       8

Целое число против двойной арифметической производительности?

11 голосов
/ 09 сентября 2010

Я пишу класс C # для выполнения делимой двумерной свертки, используя целые числа, чтобы получить лучшую производительность, чем двойной аналог.Проблема в том, что я не получаю реального прироста производительности.

Это код фильтра X (он действителен как для int, так и для двойных случаев): 

foreach (pixel)
{
      int value = 0;
      for (int k = 0; k < filterOffsetsX.Length; k++)
      {
          value += InputImage[index + filterOffsetsX[k]] * filterValuesX[k];  //index is relative to current pixel position
      }
      tempImage[index] = value;
 }

В целых числахcase "value", "InputImage" и "tempImage" относятся к типам "int", "Image <byte>" и "Image <int>".
В двойном регистре "value", "InputImage" и "tempImage"имеют типы" double "," Image <double> "и" Image <double> ".
(filterValues ​​в каждом случае имеет значение int [])
(класс Image <T> является частью externdll. Он должен быть похож на класс .NET Drawing Image ..).

Моя цель - добиться быстрой производительности благодаря int + = (byte * int) против double + = (double * int)

Следующие значения означают 200 повторений.
Размер фильтра 9 = 0,031 (двойной) 0,027 (целых)
Размер фильтра 13 = 0,042 (двойной) 0,038 (целых)
Размер фильтра 25 =0.078 (double) 0.070 (int)

Прирост производительности минимален.Может ли это быть вызвано остановкой конвейера и неоптимальным кодом?

EDIT: упрощен код, удаляющий неважные переменные.

EDIT2: я не думаю, что у меня есть проблема, связанная с отсутствием кэша, потому что "индекс" перебирает смежные ячейки памяти (строка за строкой).Кроме того, «filterOffstetsX» содержит только небольшие смещения, относящиеся к пикселям в той же строке и на максимальном расстоянии от размера фильтра / 2. Проблема может присутствовать во втором сепарабельном фильтре (Y-фильтр), но времена не столь различны.

Ответы [ 7 ]

15 голосов
/ 09 сентября 2010

Кажется, вы говорите, что выполняете этот внутренний цикл 5000 раз даже в самом длинном случае. Последний проверенный мной FPU (по общему признанию, давным-давно) потребовал всего около 5 циклов для выполнения умножения, чем целочисленная единица. Таким образом, используя целые числа, вы экономите около 25 000 тактов процессора. При этом предполагается, что в кеше нет ни одного промаха или чего-либо еще, что могло бы заставить процессор сидеть и ждать в любом из событий.

Предполагая, что современный процессор Intel Core работает с тактовой частотой около 2,5 ГГц, можно ожидать, что вы сэкономите около 10 микросекунд времени выполнения, используя целочисленные единицы. Какая ничтожная. Я зарабатываю в режиме реального времени на жизнь, и мы бы не потратили столько времени на процессорную нагрузку, даже если бы где-то пропустили крайний срок.

digEmAll делает очень хорошие замечания в комментариях. Если компилятор и оптимизатор выполняют свою работу, все это конвейерно. Это означает, что на самом деле весь внутренний цикл будет работать на 5 циклов дольше, чем целочисленный модуль, а не на каждой операции в нем. Если бы это было так, ваша ожидаемая экономия времени была бы настолько мала, что было бы сложно измерить их.

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

  1. Распараллелить ваш алгоритм и запустить его на каждом процессоре, доступном на вашем процессоре.
  2. Не запускайте его на CLR (используйте нативный C ++, Ada, Fortran или что-то в этом роде).
  3. Перепишите его для запуска на GPU. Графические процессоры по сути являются процессорами массивов и предназначены для массовой параллельной математики для массивов значений с плавающей запятой.
15 голосов
/ 11 декабря 2010

Используя Visual C ++, потому что таким образом я могу быть уверен, что я синхронизирую арифметические операции и ничего больше.

Результаты (каждая операция выполняется 600 миллионов раз): 

i16 add: 834575
i32 add: 840381
i64 add: 1691091
f32 add: 987181
f64 add: 979725
i16 mult: 850516
i32 mult: 858988
i64 mult: 6526342
f32 mult: 1085199
f64 mult: 1072950
i16 divide: 3505916
i32 divide: 3123804
i64 divide: 10714697
f32 divide: 8309924
f64 divide: 8266111

freq = 1562587

ЦП - это Intel Core i7 с турбонаддувом до 2,53 ГГц.

Код эталона: 

#include <stdio.h>
#include <windows.h>

template<void (*unit)(void)>
void profile( const char* label )
{
    static __int64 cumtime;
    LARGE_INTEGER before, after;
    ::QueryPerformanceCounter(&before);
    (*unit)();
    ::QueryPerformanceCounter(&after);
    after.QuadPart -= before.QuadPart;
    printf("%s: %I64i\n", label, cumtime += after.QuadPart);
}

const unsigned repcount = 10000000;

template<typename T>
void add(volatile T& var, T val) { var += val; }

template<typename T>
void mult(volatile T& var, T val) { var *= val; }

template<typename T>
void divide(volatile T& var, T val) { var /= val; }

template<typename T, void (*fn)(volatile T& var, T val)>
void integer_op( void )
{
    unsigned reps = repcount;
    do {
        volatile T var = 2000;
        fn(var,5);
        fn(var,6);
        fn(var,7);
        fn(var,8);
        fn(var,9);
        fn(var,10);
    } while (--reps);
}

template<typename T, void (*fn)(volatile T& var, T val)>
void fp_op( void )
{
    unsigned reps = repcount;
    do {
        volatile T var = (T)2.0;
        fn(var,(T)1.01);
        fn(var,(T)1.02);
        fn(var,(T)1.03);
        fn(var,(T)2.01);
        fn(var,(T)2.02);
        fn(var,(T)2.03);
    } while (--reps);
}

int main( void )
{
    LARGE_INTEGER freq;
    unsigned reps = 10;
    do {
        profile<&integer_op<__int16,add<__int16>>>("i16 add");
        profile<&integer_op<__int32,add<__int32>>>("i32 add");
        profile<&integer_op<__int64,add<__int64>>>("i64 add");
        profile<&fp_op<float,add<float>>>("f32 add");
        profile<&fp_op<double,add<double>>>("f64 add");

        profile<&integer_op<__int16,mult<__int16>>>("i16 mult");
        profile<&integer_op<__int32,mult<__int32>>>("i32 mult");
        profile<&integer_op<__int64,mult<__int64>>>("i64 mult");
        profile<&fp_op<float,mult<float>>>("f32 mult");
        profile<&fp_op<double,mult<double>>>("f64 mult");

        profile<&integer_op<__int16,divide<__int16>>>("i16 divide");
        profile<&integer_op<__int32,divide<__int32>>>("i32 divide");
        profile<&integer_op<__int64,divide<__int64>>>("i64 divide");
        profile<&fp_op<float,divide<float>>>("f32 divide");
        profile<&fp_op<double,divide<double>>>("f64 divide");

        ::QueryPerformanceFrequency(&freq);

        putchar('\n');
    } while (--reps);

    printf("freq = %I64i\n", freq);
}

Я выполнил оптимизированную сборку по умолчанию, используя 32-разрядную версию Visual C ++ 2010.

Каждый вызов profile, add, mult и divide (внутри циклов) был встроен. Вызовы функций по-прежнему генерируются на profile, но, поскольку для каждого вызова выполняется 60 миллионов операций, я думаю, что издержки вызова функции не важны.

Даже с добавленным volatile оптимизирующим компилятором Visual C ++ является SMART . Первоначально я использовал маленькие целые числа в качестве правого операнда, а компилятор с радостью использовал инструкции lea и add для целочисленного умножения. Вы можете получить больший импульс от вызова высоко оптимизированного кода C ++, чем принято считать, просто потому, что оптимизатор C ++ работает намного лучше, чем любой JIT.

Изначально у меня была инициализация var вне цикла, и из-за постоянных переполнений код умножения с плавающей точкой выполнялся ужасно медленно. FPU обрабатывает NaN медленно, что нужно учитывать при написании высокопроизводительных подпрограмм обработки чисел.

Зависимости также настроены таким образом, чтобы предотвратить конвейерную обработку. Если вы хотите увидеть результаты конвейерной обработки, скажите это в комментарии, и я пересмотрю тестовый стенд, чтобы он работал с несколькими переменными вместо одной.

Разборка i32 умножается: 

;   COMDAT ??$integer_op@H$1??$mult@H@@YAXACHH@Z@@YAXXZ
_TEXT   SEGMENT
_var$66971 = -4                     ; size = 4
??$integer_op@H$1??$mult@H@@YAXACHH@Z@@YAXXZ PROC   ; integer_op<int,&mult<int> >, COMDAT

; 29   : {

  00000 55       push    ebp
  00001 8b ec        mov     ebp, esp
  00003 51       push    ecx

; 30   :    unsigned reps = repcount;

  00004 b8 80 96 98 00   mov     eax, 10000000      ; 00989680H
  00009 b9 d0 07 00 00   mov     ecx, 2000      ; 000007d0H
  0000e 8b ff        npad    2
$LL3@integer_op@5:

; 31   :    do {
; 32   :        volatile T var = 2000;

  00010 89 4d fc     mov     DWORD PTR _var$66971[ebp], ecx

; 33   :        fn(var,751);

  00013 8b 55 fc     mov     edx, DWORD PTR _var$66971[ebp]
  00016 69 d2 ef 02 00
    00       imul    edx, 751       ; 000002efH
  0001c 89 55 fc     mov     DWORD PTR _var$66971[ebp], edx

; 34   :        fn(var,6923);

  0001f 8b 55 fc     mov     edx, DWORD PTR _var$66971[ebp]
  00022 69 d2 0b 1b 00
    00       imul    edx, 6923      ; 00001b0bH
  00028 89 55 fc     mov     DWORD PTR _var$66971[ebp], edx

; 35   :        fn(var,7124);

  0002b 8b 55 fc     mov     edx, DWORD PTR _var$66971[ebp]
  0002e 69 d2 d4 1b 00
    00       imul    edx, 7124      ; 00001bd4H
  00034 89 55 fc     mov     DWORD PTR _var$66971[ebp], edx

; 36   :        fn(var,81);

  00037 8b 55 fc     mov     edx, DWORD PTR _var$66971[ebp]
  0003a 6b d2 51     imul    edx, 81            ; 00000051H
  0003d 89 55 fc     mov     DWORD PTR _var$66971[ebp], edx

; 37   :        fn(var,9143);

  00040 8b 55 fc     mov     edx, DWORD PTR _var$66971[ebp]
  00043 69 d2 b7 23 00
    00       imul    edx, 9143      ; 000023b7H
  00049 89 55 fc     mov     DWORD PTR _var$66971[ebp], edx

; 38   :        fn(var,101244215);

  0004c 8b 55 fc     mov     edx, DWORD PTR _var$66971[ebp]
  0004f 69 d2 37 dd 08
    06       imul    edx, 101244215     ; 0608dd37H

; 39   :    } while (--reps);

  00055 48       dec     eax
  00056 89 55 fc     mov     DWORD PTR _var$66971[ebp], edx
  00059 75 b5        jne     SHORT $LL3@integer_op@5

; 40   : }

  0005b 8b e5        mov     esp, ebp
  0005d 5d       pop     ebp
  0005e c3       ret     0
??$integer_op@H$1??$mult@H@@YAXACHH@Z@@YAXXZ ENDP   ; integer_op<int,&mult<int> >
; Function compile flags: /Ogtp
_TEXT   ENDS

И f64 умножить: 

;   COMDAT ??$fp_op@N$1??$mult@N@@YAXACNN@Z@@YAXXZ
_TEXT   SEGMENT
_var$67014 = -8                     ; size = 8
??$fp_op@N$1??$mult@N@@YAXACNN@Z@@YAXXZ PROC        ; fp_op<double,&mult<double> >, COMDAT

; 44   : {

  00000 55       push    ebp
  00001 8b ec        mov     ebp, esp
  00003 83 e4 f8     and     esp, -8            ; fffffff8H

; 45   :    unsigned reps = repcount;

  00006 dd 05 00 00 00
    00       fld     QWORD PTR __real@4000000000000000
  0000c 83 ec 08     sub     esp, 8
  0000f dd 05 00 00 00
    00       fld     QWORD PTR __real@3ff028f5c28f5c29
  00015 b8 80 96 98 00   mov     eax, 10000000      ; 00989680H
  0001a dd 05 00 00 00
    00       fld     QWORD PTR __real@3ff051eb851eb852
  00020 dd 05 00 00 00
    00       fld     QWORD PTR __real@3ff07ae147ae147b
  00026 dd 05 00 00 00
    00       fld     QWORD PTR __real@4000147ae147ae14
  0002c dd 05 00 00 00
    00       fld     QWORD PTR __real@400028f5c28f5c29
  00032 dd 05 00 00 00
    00       fld     QWORD PTR __real@40003d70a3d70a3d
  00038 eb 02        jmp     SHORT $LN3@fp_op@3
$LN22@fp_op@3:

; 46   :    do {
; 47   :        volatile T var = (T)2.0;
; 48   :        fn(var,(T)1.01);
; 49   :        fn(var,(T)1.02);
; 50   :        fn(var,(T)1.03);
; 51   :        fn(var,(T)2.01);
; 52   :        fn(var,(T)2.02);
; 53   :        fn(var,(T)2.03);
; 54   :    } while (--reps);

  0003a d9 ce        fxch    ST(6)
$LN3@fp_op@3:
  0003c 48       dec     eax
  0003d d9 ce        fxch    ST(6)
  0003f dd 14 24     fst     QWORD PTR _var$67014[esp+8]
  00042 dd 04 24     fld     QWORD PTR _var$67014[esp+8]
  00045 d8 ce        fmul    ST(0), ST(6)
  00047 dd 1c 24     fstp    QWORD PTR _var$67014[esp+8]
  0004a dd 04 24     fld     QWORD PTR _var$67014[esp+8]
  0004d d8 cd        fmul    ST(0), ST(5)
  0004f dd 1c 24     fstp    QWORD PTR _var$67014[esp+8]
  00052 dd 04 24     fld     QWORD PTR _var$67014[esp+8]
  00055 d8 cc        fmul    ST(0), ST(4)
  00057 dd 1c 24     fstp    QWORD PTR _var$67014[esp+8]
  0005a dd 04 24     fld     QWORD PTR _var$67014[esp+8]
  0005d d8 cb        fmul    ST(0), ST(3)
  0005f dd 1c 24     fstp    QWORD PTR _var$67014[esp+8]
  00062 dd 04 24     fld     QWORD PTR _var$67014[esp+8]
  00065 d8 ca        fmul    ST(0), ST(2)
  00067 dd 1c 24     fstp    QWORD PTR _var$67014[esp+8]
  0006a dd 04 24     fld     QWORD PTR _var$67014[esp+8]
  0006d d8 cf        fmul    ST(0), ST(7)
  0006f dd 1c 24     fstp    QWORD PTR _var$67014[esp+8]
  00072 75 c6        jne     SHORT $LN22@fp_op@3
  00074 dd d8        fstp    ST(0)
  00076 dd dc        fstp    ST(4)
  00078 dd da        fstp    ST(2)
  0007a dd d8        fstp    ST(0)
  0007c dd d8        fstp    ST(0)
  0007e dd d8        fstp    ST(0)
  00080 dd d8        fstp    ST(0)

; 55   : }

  00082 8b e5        mov     esp, ebp
  00084 5d       pop     ebp
  00085 c3       ret     0
??$fp_op@N$1??$mult@N@@YAXACNN@Z@@YAXXZ ENDP        ; fp_op<double,&mult<double> >
; Function compile flags: /Ogtp
_TEXT   ENDS
4 голосов
/ 09 сентября 2010

Ваш алгоритм, кажется, обращается к большим областям памяти в очень непоследовательном порядке.Это, вероятно, генерирует тонны кеша.Узким местом является, вероятно, доступ к памяти, а не арифметика.Использование ints должно сделать это немного быстрее, потому что int 32-битные, а double 64-битные, что означает, что кеш будет использоваться немного более эффективно.Если почти каждая итерация цикла включает в себя промах кеша, вам, в принципе, не повезет, если вы не сможете внести некоторые изменения алгоритмической структуры или структуры данных, чтобы улучшить местность ссылок.БПФ для свертки?Это поставит вас в совершенно другой класс биг-О.

2 голосов
/ 09 сентября 2010

по крайней мере, нечестно сравнивать int (DWORD, 4 байта) и double (QWORD, 8 байтов) в 32-битной системе. Сравните int с float или long с double, чтобы получить достоверные результаты. double увеличена точность, вы должны заплатить за нее.

PS : для меня это пахнет микро (+ преждевременной) оптимизацией, и этот запах не очень хороший.

Редактировать : Хорошо, хорошо. Неправильно сравнивать long с double, но сравнивать int и double на 32 CPU нельзя, даже если они имеют обе встроенные инструкции. Это не волшебство, x86 - жирный CISC, но двойное не обрабатывается внутри как один шаг.

1 голос
/ 09 сентября 2010

На моей машине я обнаружил, что умножение с плавающей запятой примерно равно скорости целочисленного умножения.

Я использую эту функцию синхронизации: 

static void Time<T>(int count, string desc, Func<T> action){
    action();

    Stopwatch sw = Stopwatch.StartNew();
    for(int i = 0; i < count; i++)
        action();

    double seconds = sw.Elapsed.TotalSeconds;

    Console.WriteLine("{0} took {1} seconds", desc, seconds);
}

Допустим, вы 'перерабатывая массив 200 x 200 с фильтром 25 длины, 200 раз, тогда ваш внутренний цикл выполняется 200 * 200 * 25 * 200 = 200 000 000 раз.Каждый раз вы выполняете одно умножение, одно сложение и 3 индексов массива.Поэтому я использую этот код профилирования 

const int count = 200000000;

int[]  a = {1};
double d = 5;
int    i = 5;

Time(count, "array index", ()=>a[0]);
Time(count, "double mult", ()=>d * 6);
Time(count, "double add ", ()=>d + 6);
Time(count, "int    mult", ()=>i * 6);
Time(count, "int    add ", ()=>i + 6);

На моей машине (думаю, что она медленнее вашей), я получаю следующие результаты: 

array index took 1.4076632 seconds
double mult took 1.2203911 seconds
double add  took 1.2342998 seconds
int    mult took 1.2170384 seconds
int    add  took 1.0945793 seconds

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

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

Кстати, разница в производительности для деления гораздо более значительна.Следуя приведенному выше шаблону, я получаю: 

double div  took 3.8597251 seconds
int    div  took 1.7824505 seconds

Еще одно примечание:

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

0 голосов
/ 09 сентября 2010

Вы пробовали смотреть на разобранный код? В языках высокого уровня я доверяю компилятору в оптимизации моего кода. Например, for(i=0;i<imageSize;i++) может быть быстрее, чем foreach. Кроме того, арифметические операции могут быть оптимизированы компилятором в любом случае .... когда вам нужно что-то оптимизировать, вы либо оптимизируете весь «черный ящик» и, возможно, заново изобретаете алгоритм, используемый в этом цикле, либо сначала смотрите на расформированный код и посмотреть, что с ним не так

0 голосов
/ 09 сентября 2010

Если время, которое вы измерили, является точным, то время выполнения вашего алгоритма фильтрации, кажется, увеличивается с кубом размера фильтра.Что это за фильтр?Может быть, вы можете уменьшить количество необходимых умножений.(например, если вы используете ядро ​​с разделяемым фильтром?)

В противном случае, если вам нужна грубая производительность, вы можете рассмотреть возможность использования библиотеки, такой как Intel Performance Primitives - она ​​содержит высоко оптимизированные функции для таких вещей, которые используютПроцессор SIMD инструкции.Обычно они работают намного быстрее, чем рукописный код на C # или C ++.

...