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

Ответ 1

Ваш вопрос действительно интригует, так как неподписанная версия последовательно создает код, который на 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, бит DIV 32 принимает 10 микроопераций, от 19 до 27 циклов, IDIV 9 микроопераций, от 19 до 26 циклов. Контрольные времена согласуются с этими таймингами. Дополнительный микрооператор может быть вызван более длинными операндами в DIV (64/32 бит) в отличие от IDIV (63/31 бит).

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

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

Ответ 2

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

Ответ 3

Из Инструкция по 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, для μops существует небольшая разница.

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

Ответ 4

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

#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