Эффективное внедрение полных/эвклидовых целых делений

Ответ 1

Я пересматриваю этот вопрос пять лет спустя, поскольку это имеет значение и для меня. Я сделал некоторые измерения производительности на двух версиях pure-C и двух встроенных версиях для x86-64, и результаты могут быть интересными.

Проверенными вариантами разделения пола являются:

• Реализация, которую я использовал в течение некоторого времени;
• Небольшой вариант, представленный выше, который использует только одно подразделение;
• Предыдущий, но реализованный вручную в inline-assembly; и
• 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 с помощью GCC 4.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 секунды

Ответ 2

Я написал тестовую программу для сравнения представленных здесь идей:

#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

Ответ 3

Возможно, было бы более эффективно придумать что-то ветки, чтобы исправить результат на основе знака, поскольку ветки дороги.

См. стр. 20ff Глава 2 в Хакерское наслаждение о том, как получить доступ к знаку.

Ответ 4

Можно ли эффективно реализовать разбиение на пол или эвклидово целое число в C/С++?

Да.

(очевидное решение - проверить знак дивиденда)

Я полностью согласен, и мне будет трудно поверить, что существует альтернатива, которая значительно быстрее.

Ответ 5

Просто примечание: команда x86 sar выполняет разделение пополам, когда дело доходит до полномочий двух.

Ответ 6

Поскольку IEEE-754 указывает round на -inf как на один из требуемых режимов округления, я полагаю, что ответ на ваш вопрос - да. Но, возможно, вы можете объяснить, хотите ли вы знать, как реализовать эту процедуру, если вы пишете компилятор, или знать, как использовать конкретный компилятор для выполнения операции?