Я возвращаюсь к этому вопросу пять лет спустя, так как это актуально и для меня.Я провел несколько измерений производительности для двух версий pure-C и двух версий inline-ассемблера для x86-64, и результаты могут быть интересными.
Протестированные варианты разделения по этажам:
- Реализация, которую я использовал в течение некоторого времени;
- Небольшой вариант представленного выше, который использует только одно деление;
- Предыдущий, но реализованный вручную в inline-монтаж;и
- A
CMOV версия, реализованная в сборке.
Ниже приведена моя программа тестирования:
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#ifndef VARIANT
#define VARIANT 3
#endif
#if VARIANT == 0
#define floordiv(a, b) (((a) < 0)?((((a) + 1) / (b)) - 1):((a) / (b)))
#elif VARIANT == 1
#define floordiv(a, b) ((((a) < 0)?((a) - ((b) - 1)):(a)) / (b))
#elif VARIANT == 2
#define floordiv(a, b) ({ \
int result; \
asm("test %%eax, %%eax; jns 1f; sub %1, %%eax;" \
"add $1, %%eax; 1: cltd; idivl %1;" \
: "=a" (result) \
: "r" (b), \
"0" (a) \
: "rdx"); \
result;})
#elif VARIANT == 3
#define floordiv(a, b) ({ \
int result; \
asm("mov %%eax, %%edx; sub %1, %%edx; add $1, %%edx;" \
"test %%eax, %%eax; cmovs %%edx, %%eax; cltd;" \
"idivl %1;" \
: "=a" (result) \
: "r" (b), \
"0" (a) \
: "rdx"); \
result;})
#endif
double ntime(void)
{
struct timeval tv;
gettimeofday(&tv, NULL);
return(tv.tv_sec + (((double)tv.tv_usec) / 1000000.0));
}
void timediv(int n, int *p, int *q, int *r)
{
int i;
for(i = 0; i < n; i++)
r[i] = floordiv(p[i], q[i]);
}
int main(int argc, char **argv)
{
int n, i, *q, *p, *r;
double st;
n = 10000000;
p = malloc(sizeof(*p) * n);
q = malloc(sizeof(*q) * n);
r = malloc(sizeof(*r) * n);
for(i = 0; i < n; i++) {
p[i] = (rand() % 1000000) - 500000;
q[i] = (rand() % 1000000) + 1;
}
st = ntime();
for(i = 0; i < 100; i++)
timediv(n, p, q, r);
printf("%g\n", ntime() - st);
return(0);
}
Я скомпилировал ее с gcc -march=native -Ofast с помощью GCC4.9.2, и результаты на моем Core i5-2400 были следующими.Результаты довольно воспроизводимы от запуска к бегу - они всегда приземляются в одном и том же порядке, по крайней мере.
- Вариант 0: 7,21 секунды
- Вариант 1: 7,26 секунды
- Вариант 2: 6,73 секунды
- Вариант 3: 4,32 секунды
Таким образом, реализация CMOV, по крайней мере, выбрасывает остальных из воды.Что удивляет меня, так это то, что вариант 2 превосходит свою версию на чистом C (вариант 1) с довольно большим отрывом.Я бы подумал, что компилятор должен иметь возможность генерировать код по крайней мере так же эффективно, как мой.
Вот несколько других платформ для сравнения:
AMD Athlon 64 X2 4200+, GCC 4.7.2:
- вариант 0: 26,33 секунды
- вариант 1: 25,38 секунды
- вариант 2: 25,19 секунды
- вариант 3: 22,39 секунды
Xeon E3-1271 v3, GCC 4.9.2:
- Вариант 0: 5,95 секунды
- Вариант 1: 5,62 секунды
- Вариант 2: 5,40 секунды
- Вариант 3: 3,44 секунды
В качестве последнего замечания я, возможно, должен предостеречь от слишком серьезного восприятия очевидного преимущества в производительности версии CMOV,потому что в реальном мире ветвление в других версиях, вероятно, не будет настолько случайным, как в этом тесте, и если предиктор ветвления может выполнить разумную работу, версии ветвления могут оказаться лучше.Однако реалии этого будут во многом зависеть от данных, которые используются на практике, и поэтому, вероятно, бессмысленно пытаться выполнить какой-либо общий тест.