Ответ 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 бит).
Этот удивительный результат должен научить нас нескольким урокам:
- Оптимизация - сложное искусство, смиренное и откладывание.
- правильность часто нарушается оптимизациями.
- Выбор лучшего алгоритма превосходит оптимизацию на длинный снимок.
- всегда проверяйте код, не доверяйте своим инстинктам.