Половое деление - это когда результат всегда уменьшается (в сторону -∞), а не в сторону 0:
Можно ли эффективно реализовать напольное или евклидово целочисленное деление в C/C++?
(очевидное решение — проверить знак делимого)
Половое деление - это когда результат всегда уменьшается (в сторону -∞), а не в сторону 0:
Можно ли эффективно реализовать напольное или евклидово целочисленное деление в C/C++?
(очевидное решение — проверить знак делимого)
Я возвращаюсь к этому вопросу пять лет спустя, так как это актуально и для меня. Я провел некоторые измерения производительности на двух версиях на чистом C и двух версиях на встроенной сборке для x86-64, и результаты могут быть интересными.
Испытываемые варианты напольного деления:
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
, используя GCC 4.9.2, и результаты на моем Core i5-2400 были следующими. Результаты довольно воспроизводимы от запуска к запуску — они всегда приземляются в одном и том же порядке, по крайней мере.
Так что реализация CMOV
, по крайней мере, превосходит все остальные. Что меня удивляет, так это то, что вариант 2 превосходит свою версию на чистом C (вариант 1) с довольно большим отрывом. Я бы подумал, что компилятор должен иметь возможность генерировать код, по крайней мере, столь же эффективный, как мой.
Вот некоторые другие платформы для сравнения:
AMD Athlon 64 X2 4200+, GCC 4.7.2:
Xeon E3-1271 v3, GCC 4.9.2:
В качестве последнего замечания я, возможно, должен предостеречь от слишком серьезного отношения к явному преимуществу в производительности версии CMOV
, потому что в реальном мире ветвь в других версиях, вероятно, не будет такой полностью случайной, как в этом тесте, и если ветвь предиктор может делать разумную работу, версии с ветвлениями могут оказаться лучше. Однако реалии этого будут в значительной степени зависеть от данных, которые используются на практике, и поэтому, вероятно, бессмысленно пытаться провести какой-либо общий эталонный тест.
/
обычно приводит к тому, что компилятор генерирует дополнительный код для создания неравномерности, близкой к нулю, что затем заставляет программиста писать дополнительный дополнительный код. Я думаю, что лучший подход — преобразовать в беззнаковый, добавить одно смещение, выполнить деление, а затем вычесть другое смещение, но это кажется немного неприглядным.
- person supercat; 02.11.2017
Я написал тестовую программу для проверки идей, представленных здесь:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#define N 10000000
#define M 100
int dividends[N], divisors[N], results[N];
__forceinline int floordiv_signcheck(int a, int b)
{
return (a<0 ? a-(b-1) : a) / b;
}
__forceinline int floordiv_signcheck2(int a, int b)
{
return (a - (a<0 ? b-1 : 0)) / b;
}
__forceinline int floordiv_signmultiply(int a, int b)
{
return (a + (a>>(sizeof(a)*8-1))*(b-1)) / b;
}
__forceinline int floordiv_floatingpoint(int a, int b)
{
// I imagine that the call to floor can be replaced to a cast
// if you can get FPU rounding control to work (I couldn't).
return floor((double)a / b);
}
void main()
{
for (int i=0; i<N; i++)
{
dividends[i] = rand();
do
divisors[i] = rand();
while (divisors[i]==0);
}
LARGE_INTEGER t0, t1;
QueryPerformanceCounter(&t0);
for (int j=0; j<M; j++)
for (int i=0; i<N; i++)
results[i] = floordiv_signcheck(dividends[i], divisors[i]);
QueryPerformanceCounter(&t1);
printf("signcheck : %9llu\n", t1.QuadPart-t0.QuadPart);
QueryPerformanceCounter(&t0);
for (int j=0; j<M; j++)
for (int i=0; i<N; i++)
results[i] = floordiv_signcheck2(dividends[i], divisors[i]);
QueryPerformanceCounter(&t1);
printf("signcheck2 : %9llu\n", t1.QuadPart-t0.QuadPart);
QueryPerformanceCounter(&t0);
for (int j=0; j<M; j++)
for (int i=0; i<N; i++)
results[i] = floordiv_signmultiply(dividends[i], divisors[i]);
QueryPerformanceCounter(&t1);
printf("signmultiply : %9llu\n", t1.QuadPart-t0.QuadPart);
QueryPerformanceCounter(&t0);
for (int j=0; j<M; j++)
for (int i=0; i<N; i++)
results[i] = floordiv_floatingpoint(dividends[i], divisors[i]);
QueryPerformanceCounter(&t1);
printf("floatingpoint: %9llu\n", t1.QuadPart-t0.QuadPart);
}
Результаты:
signcheck : 61458768
signcheck2 : 61284370
signmultiply : 61625076
floatingpoint: 287315364
Итак, по моим результатам проверка знака самая быстрая:
(a - (a<0 ? b-1 : 0)) / b
printf
для предыдущего ответа. printf
довольно медленный, не знаю, достаточно ли он медленный, чтобы повлиять на ваши результаты или нет.
- person Mark Ransom; 06.11.2010
double
вместо float
, так как там тоже могут происходить конверсии.
- person Mark Ransom; 06.11.2010
double
заставило работать с плавающей запятой немного быстрее, но ненамного. В остальном результат не сильно изменился.
- person Vladimir Panteleev; 06.11.2010
rand()
указано, чтобы возвращать только положительные целые числа.
- person Dolda2000; 21.04.2016
return (a - (a>>(sizeof(a)*8-1))&(b-1)) / b;
. Однако обратите внимание, что ВСЕ варианты signcheck/signmultiply страдают недостатком памяти, если a
близко к INT_MIN
. Если вы точно не знаете, что a - b + 1
никогда не опускается ниже INT_MIN
, я настоятельно не рекомендую их использовать.
- person Kai Petzke; 08.10.2020
Было бы более эффективно придумать что-то бесплатное для ветвления, чтобы исправить результат на основе знака, поскольку ветки дороги.
См. стр. 20 и далее главы 2 в Hacker's Delight о том, как получить доступ к знаку.
Можно ли эффективно реализовать напольное или евклидово целочисленное деление в C/C++?
да.
(очевидное решение — проверить знак делимого)
Я полностью согласен, и мне было бы трудно поверить, что существует альтернатива, которая значительно быстрее.
Просто примечание: инструкция x86 sar
выполняет деление по полу, когда речь идет о степенях двойки.
Поскольку IEEE-754 указывает округление в сторону -inf как один из обязательных режимов округления, я полагаю, что ответ на ваш вопрос - да. Но, возможно, вы можете объяснить, хотите ли вы знать, как можно было бы реализовать процедуру, если бы вы писали компилятор, или узнать, как использовать конкретный компилятор для выполнения операции?