В Си, почему "подписанный int" быстрее, чем "unsigned int"?

Question

В Си, почему "подписанный int" быстрее, чем "unsigned int"?

В С, почему signed int быстрее, чем unsigned int? Правда, я знаю, что на этом сайте неоднократно задавались вопросы и ответы (ссылки ниже). Тем не менее, большинство людей сказали, что нет никакой разницы. Я написал код и случайно обнаружил существенную разницу в производительности.

Почему "беззнаковая" версия моего кода будет медленнее, чем "подписанная" версия (даже при тестировании того же номера)? (У меня процессор Intel x86-64).

Похожие ссылки

Команда компиляции: gcc -Wall -Wextra -pedantic -O3 -Wl,-O3 -g0 -ggdb0 -s -fwhole-program -funroll-loops -pthread -pipe -ffunction-sections -fdata-sections -std=c11 -o ./test ./test.c && strip --strip-all --strip-unneeded --remove-section=.note --remove-section=.comment ./test

`signed int` версия

ПРИМЕЧАНИЕ. Нет разницы, если я signed int на все номера.

int isprime(int num) {
    // Test if a signed int is prime
    int i;
    if (num % 2 == 0 || num % 3 == 0)
        return 0;
    else if (num % 5 == 0 || num % 7 == 0)
        return 0;
    else {
        for (i = 11; i < num; i += 2) {
            if (num % i == 0) {
                if (i != num)
                    return 0;
                else
                    return 1;
            }
        }
    }
    return 1;
}

`unsigned int` версия

int isunsignedprime(unsigned int num) {
    // Test if an unsigned int is prime
    unsigned int i;
    if (num % (unsigned int)2 == (unsigned int)0 || num % (unsigned int)3 == (unsigned int)0)
        return 0;
    else if (num % (unsigned int)5 == (unsigned int)0 || num % (unsigned int)7 == (unsigned int)0)
        return 0;
    else {
        for (i = (unsigned int)11; i < num; i += (unsigned int)2) {
            if (num % i == (unsigned int)0) {
                if (i != num)
                    return 0;
                else
                    return 1;
            }
        }
    }
    return 1;
}

Проверьте это в файле с кодом ниже:

int main(void) {
    printf("%d\n", isprime(294967291));
    printf("%d\n", isprime(294367293));
    printf("%d\n", isprime(294967293));
    printf("%d\n", isprime(294967241)); // slow
    printf("%d\n", isprime(294967251));
    printf("%d\n", isprime(294965291));
    printf("%d\n", isprime(294966291));
    printf("%d\n", isprime(294963293));
    printf("%d\n", isprime(294927293));
    printf("%d\n", isprime(294961293));
    printf("%d\n", isprime(294917293));
    printf("%d\n", isprime(294167293));
    printf("%d\n", isprime(294267293));
    printf("%d\n", isprime(294367293)); // slow
    printf("%d\n", isprime(294467293));
    return 0;
}

Результаты (time ./test):

Signed - real 0m0.949s
Unsigned - real 0m1.174s

42

c performance optimization unsigned signed

Источник

user2354783 08 дек '15 в 20:09

5 ответов

Другие вопросы по тегам c performance optimization unsigned signed

user4593267 31 авг '17 в 22:03 2017-08-31 22:03 · Answer 1 · 2017-08-31 22:03

Ваш вопрос действительно интригует, так как неподписанная версия постоянно генерирует код, который на 10-20% медленнее. Тем не менее, в коде есть несколько проблем:

Обе функции возвращают 0 за 2, 3, 5 а также 7, что неверно.
Тест if (i != num) return 0; else return 1; абсолютно бесполезен, так как тело цикла выполняется только для i < num, Такой тест был бы полезен для небольших простых тестов, но специальный корпус для них не очень полезен.
броски в неподписанной версии являются избыточными.
код бенчмаркинга, который производит текстовый вывод на терминал, ненадежен, вы должны использовать clock() функция для измерения времени работы процессора без каких-либо промежуточных операций ввода-вывода.
Алгоритм первичного тестирования совершенно неэффективен во время цикла num / 2 раз вместо sqrt(num),

Давайте упростим код и проведем несколько точных тестов:

#include <stdio.h>
#include <time.h>

int isprime_slow(int num) {
    if (num % 2 == 0)
        return num == 2;
    for (int i = 3; i < num; i += 2) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

int unsigned_isprime_slow(unsigned int num) {
    if (num % 2 == 0)
        return num == 2;
    for (unsigned int i = 3; i < num; i += 2) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

int isprime_fast(int num) {
    if (num % 2 == 0)
        return num == 2;
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

int unsigned_isprime_fast(unsigned int num) {
    if (num % 2 == 0)
        return num == 2;
    for (unsigned int i = 3; i * i <= num; i += 2) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

int main(void) {
    int a[] = {
        294967291, 0, 294367293, 0, 294967293, 0, 294967241, 1, 294967251, 0,
        294965291, 0, 294966291, 0, 294963293, 0, 294927293, 1, 294961293, 0,
        294917293, 0, 294167293, 0, 294267293, 0, 294367293, 0, 294467293, 0,
    };
    struct testcase { int (*fun)(); const char *name; int t; } test[] = {
        { isprime_slow, "isprime_slow", 0 },
        { unsigned_isprime_slow, "unsigned_isprime_slow", 0 },
        { isprime_fast, "isprime_fast", 0 },
        { unsigned_isprime_fast, "unsigned_isprime_fast", 0 },
    };

    for (int n = 0; n < 4; n++) {
        clock_t t = clock();
        for (int i = 0; i < 30; i += 2) {
            if (test[n].fun(a[i]) != a[i + 1]) {
                printf("%s(%d) != %d\n", test[n].name, a[i], a[i + 1]);
            }
        }
        test[n].t = clock() - t;
    }
    for (int n = 0; n < 4; n++) {
        printf("%21s: %4d.%03dms\n", test[n].name, test[n].t / 1000), test[n].t % 1000);
    }
    return 0;
}

Код, скомпилированный с clang -O2 на OS/X выдает такой вывод:

         isprime_slow:  788.004ms
unsigned_isprime_slow:  965.381ms
         isprime_fast:    0.065ms
unsigned_isprime_fast:    0.089ms

Эти временные интервалы соответствуют наблюдаемому поведению OP в другой системе, но показывают существенное улучшение, вызванное более эффективным итерационным тестом: в 10000 раз быстрее!

Относительно вопроса Почему функция медленнее с unsigned? давайте посмотрим на сгенерированный код ( gcc 7.2 -O2):

isprime_slow(int):
        ...
.L5:
        movl    %edi, %eax
        cltd
        idivl   %ecx
        testl   %edx, %edx
        je      .L1
.L4:
        addl    $2, %ecx
        cmpl    %esi, %ecx
        jne     .L5
.L6:
        movl    $1, %edx
.L1:
        movl    %edx, %eax
        ret

unsigned_isprime_slow(unsigned int):
        ...
.L19:
        xorl    %edx, %edx
        movl    %edi, %eax
        divl    %ecx
        testl   %edx, %edx
        je      .L22
.L18:
        addl    $2, %ecx
        cmpl    %esi, %ecx
        jne     .L19
.L20:
        movl    $1, %eax
        ret
       ...
.L22:
        xorl    %eax, %eax
        ret

Внутренние циклы очень похожи, одинаковое количество инструкций, одинаковые инструкции. Вот, однако, некоторые возможные объяснения:

cltd расширяет знак eax зарегистрироваться в edx регистр, который может быть причиной задержки инструкции, потому что eax модифицируется непосредственно предшествующей инструкцией movl %edi, %eax, Однако это сделало бы подписанную версию медленнее, чем неподписанная, но не быстрее.
начальные инструкции циклов могут быть выровнены для неподписанной версии, но это маловероятно, поскольку изменение порядка в исходном коде не влияет на время.
Хотя содержимое регистра идентично для подписанных и неподписанных кодов деления, возможно, что idivl инструкция занимает меньше циклов, чем divl инструкция. Действительно, подписанное деление работает с меньшей точностью, чем беззнаковое деление, но разница кажется довольно большой для этого небольшого изменения.
Я подозреваю, что больше усилий было приложено к кремниевой реализации idivl потому что подписанные деления встречаются чаще, чем беззнаковые (по годам статистики кодирования в Intel).
Как прокомментировал rcgldr, просматривая таблицы команд для процесса Intel, для Ivy Bridge 32-разрядный DIV занимает 10 микроопераций, 19–27 циклов, IDIV 9 микроопераций, 19–26 циклов. Время тестов соответствует этим временным параметрам. Дополнительная микрооперация может происходить из-за более длинных операндов в DIV (64/32 бит), в отличие от IDIV (63/31 бит).

Этот удивительный результат должен преподать нам несколько уроков:

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

user2080733 31 авг '17 в 13:01 2017-08-31 13:01 · Answer 2 · 2017-08-31 13:01

Поскольку целочисленное переполнение со знаком не определено, компилятор может сделать много предположений и оптимизаций в коде, включающем целые числа со знаком. Целочисленное переполнение без знака определено для переноса, поэтому компилятор не сможет оптимизировать так много. Также смотрите http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html и http://www.airs.com/blog/archives/120.

user719263 08 дек '15 в 20:57 2015-12-08 20:57 · Answer 3 · 2015-12-08 20:57

Из инструкции к AMD/Intel мы имеем (для K7):

Instruction Ops Latency Throughput
DIV r32/m32 32  24      23
IDIV r32    81  41      41
IDIV m32    89  41      41

Для i7 задержка и пропускная способность одинаковы для IDIVL а также DIVLНебольшая разница существует для мопов.

Это может объяснить разницу, поскольку коды сборки -O3 отличаются только подписью (DIVL против IDIVL) на моей машине.

user2410359 31 авг '17 в 13:32 2017-08-31 13:32 · Answer 4 · 2017-08-31 13:32

Альтернативный тест кандидата в вики, который может показывать / не показывать значительную разницу во времени.

#include <stdio.h>
#include <time.h>

#define J 10
#define I 5

int main(void) {
  clock_t c1,c2,c3;
  for (int j=0; j<J; j++) {
    c1 = clock();
    for (int i=0; i<I; i++) {
      isprime(294967241);
      isprime(294367293);
    }
    c2 = clock();
    for (int i=0; i<I; i++) {
      isunsignedprime(294967241);
      isunsignedprime(294367293);
    }
    c3 = clock();
    printf("%d %d %d\n", (int)(c2-c1), (int)(c3-c2), (int)((c3-c2) - (c2-c1)));
    fflush(stdout);
  }
  return 0;
}

Образец вывода

2761 2746 -15
2777 2777 0
2761 2745 -16
2793 2808 15
2792 2730 -62
2746 2730 -16
2746 2730 -16
2776 2793 17
2823 2808 -15
2793 2823 30

user865220 18 сен '22 в 15:53 2022-09-18 15:53 · Answer 5 · 2022-09-18 15:53

На самом деле во многих случаях unsigned быстрее, чем подписанный для примера.

При делении на степень 2

          unsigned int x=37;
    cout<<x/4;

При проверке, является ли число четным

          unsigned int x=37;
    cout<<(x%2==0)?"even":"odd";

-1

Источник

user865220 18 сен '22 в 15:53

В Си, почему "подписанный int" быстрее, чем "unsigned int"?

signed int версия

unsigned int версия

5 ответов

`signed int` версия

`unsigned int` версия