операторы int! = и == при сравнении с нулем

Я обнаружил, что! = И == - не самые быстрые способы проверки нуля или ненулевого значения.

bool nonZero1 = integer != 0;
xor eax, eax
test ecx, ecx
setne al

bool nonZero2 = integer < 0 || integer > 0;
test ecx, ecx
setne al

bool zero1 = integer == 0;
xor eax, eax
test ecx, ecx
sete al

bool zero2 = !(integer < 0 || integer > 0);
test ecx, ecx
sete al

Компилятор: VC ++ 11 Флаги оптимизации: / O2 / GL / LTCG

Это результат сборки для x86-32. Вторые версии обоих сравнений были примерно на 12% быстрее как на x86-32, так и на x86-64. Однако на x86-64 инструкции были идентичны (первые версии выглядели точно так же, как и вторые версии), но вторые версии были все же быстрее.

  1. Почему компилятор не генерирует более быструю версию на x86-32?
  2. Почему вторые версии все еще быстрее на x86-64, когда вывод сборки идентичен?

РЕДАКТИРОВАТЬ: я добавил код тестирования. НОЛЬ: 1544 мс, 1358 мс NON_ZERO: 1544 мс, 1358 мс http://pastebin.com/m7ZSUrcP или http://anonymouse.org/cgi-bin/anon-www.cgi/http://pastebin.com/m7ZSUrcP

Примечание: вероятно, неудобно находить эти функции при компиляции в одном исходном файле, потому что main.asm имеет довольно большой размер. У меня были zero1, zero2, nonZero1, nonZero2 в отдельном исходном файле.

РЕДАКТИРОВАТЬ 2. Может ли кто-нибудь, у кого установлены VC ++ 11 и VC ++ 2010, запустить тестовый код и опубликовать тайминги? Это действительно может быть ошибка в VC ++ 11.


person NFRCR    schedule 31.05.2012    source источник
comment
Не могли бы вы предоставить полную программу, которую используете для оценки производительности?   -  person James McNellis    schedule 31.05.2012
comment
Так как же гарантировать, что остаток eax равен нулю, если он просто пропускает xor?   -  person harold    schedule 31.05.2012
comment
Откуда берутся xor инструкции? Они не выглядят релевантными для теста, поэтому они должны быть частью окружающего кода.   -  person Mark Ransom    schedule 31.05.2012
comment
Что будет, если изменить порядок? Компилятор достаточно умен, чтобы знать, что у него есть xor: ed eax перед первым тестом и что это остается действительным для следующего ...   -  person Andreas Magnusson    schedule 31.05.2012
comment
NFRCR, вы действительно тестировали это как линейный код? Я предположил, что вы просто склеили их вместе, чтобы уменьшить размер сообщения.   -  person harold    schedule 31.05.2012
comment
Я добавил код тестирования.   -  person NFRCR    schedule 31.05.2012
comment
У меня были zero1, zero2, nonZero1, nonZero2 в отдельном модуле компиляции .... самая важная оптимизация на сегодняшний день - это встраивание, и вы предотвратили это? Никого не волнует производительность крошечной функции, которая сравнивает число с нулем. Их волнует, как они должны записать это сравнение внутри более крупной функции (вызовите встроенную функцию, используйте !=, используйте > || <). Или, по крайней мере, введите виртуальный вызов, что является единственной реальной ситуацией, когда это может происходить как отдельная функция.   -  person Ben Voigt    schedule 31.05.2012
comment
Кроме того, очень распространено встраивание кросс-TU, и компилятор отлично справляется с этим для простых функций.   -  person Puppy    schedule 31.05.2012
comment
@ Бен Фойгт. Взгляните на ссылку pastebin. Теперь все в одном исходном файле. И работает так же.   -  person NFRCR    schedule 31.05.2012
comment
@ Бен Войт. И сначала он тоже был встроенным. Я фактически отключил встраивание и наблюдал, как тайминги выросли в 3 раза. Так что встраивание точно сработало. Почему отдельный исходный файл предотвращает встраивание? У меня был / LTCG.   -  person NFRCR    schedule 31.05.2012
comment
@NFRCR: приветствуется отображение всех флагов оптимизации;)   -  person Ben Voigt    schedule 31.05.2012
comment
@NFRCR: Мой чертов провайдер заблокировал банкомат pastebin по неизвестной причине. Не могли бы вы опубликовать код или сообщить мне, что vc11 делает с опубликованными мною источниками? У меня нет компилятора vc11, удобного для сравнения: /   -  person dirkgently    schedule 31.05.2012
comment
@dirkgently Попробуйте: http://anonymouse.org/cgi-bin/anon-www.cgi/http://pastebin.com/m7ZSUrcP   -  person NFRCR    schedule 31.05.2012
comment
Хорошо, я рассмотрел это с помощью Visual C ++ 2012 RC. Я скомпилировал ваш код с помощью / O2 и / GL и получил один и тот же дамп сборки x86 для каждой функции. Benchmark1 постоянно на 20% быстрее, чем Benchmark2 на моем Core i5 540M (~ 1433 такта против ~ 1800 тактов). Я получаю почти одинаковые результаты для x86 и x64. Итак, мне интересно, лучше ли сгенерированный код для одних процессоров и хуже для других? (Я не гуру производительности, поэтому не знаю, но решил, что хотя бы взгляну и доложу о своих выводах.)   -  person James McNellis    schedule 01.06.2012


Ответы (2)


РЕДАКТИРОВАТЬ: увидел список сборки OP для моего кода. Я сомневаюсь, что сейчас это даже общая ошибка VS2011. Это может быть просто частный случай ошибки кода OP. Я запускал код OP как есть с clang 3.2, gcc 4.6.2 и VS2010, и во всех случаях максимальные различия составляли ~ 1%.

Просто скомпилировал исходники с подходящими модификациями моего ne.c файла и флагов /O2 и /GL. Вот источник

int ne1(int n) {
 return n != 0;
 }

 int ne2(int n) {
 return n < 0 || n > 0;
 }

 int ne3(int n) {
 return !(n == 0);
 }

int main() { int p = ne1(rand()), q = ne2(rand()), r = ne3(rand());}

и соответствующая сборка:

    ; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.30319.01 

    TITLE   D:\llvm_workspace\tests\ne.c
    .686P
    .XMM
    include listing.inc
    .model  flat

INCLUDELIB OLDNAMES

EXTRN   @__security_check_cookie@4:PROC
EXTRN   _rand:PROC
PUBLIC  _ne3
; Function compile flags: /Ogtpy
;   COMDAT _ne3
_TEXT   SEGMENT
_n$ = 8                         ; size = 4
_ne3    PROC                        ; COMDAT
; File d:\llvm_workspace\tests\ne.c
; Line 11
    xor eax, eax
    cmp DWORD PTR _n$[esp-4], eax
    setne   al
; Line 12
    ret 0
_ne3    ENDP
_TEXT   ENDS
PUBLIC  _ne2
; Function compile flags: /Ogtpy
;   COMDAT _ne2
_TEXT   SEGMENT
_n$ = 8                         ; size = 4
_ne2    PROC                        ; COMDAT
; Line 7
    xor eax, eax
    cmp eax, DWORD PTR _n$[esp-4]
    sbb eax, eax
    neg eax
; Line 8
    ret 0
_ne2    ENDP
_TEXT   ENDS
PUBLIC  _ne1
; Function compile flags: /Ogtpy
;   COMDAT _ne1
_TEXT   SEGMENT
_n$ = 8                         ; size = 4
_ne1    PROC                        ; COMDAT
; Line 3
    xor eax, eax
    cmp DWORD PTR _n$[esp-4], eax
    setne   al
; Line 4
    ret 0
_ne1    ENDP
_TEXT   ENDS
PUBLIC  _main
; Function compile flags: /Ogtpy
;   COMDAT _main
_TEXT   SEGMENT
_main   PROC                        ; COMDAT
; Line 14
    call    _rand
    call    _rand
    call    _rand
    xor eax, eax
    ret 0
_main   ENDP
_TEXT   ENDS
END

ne2(), в котором использовались операторы <, > и ||, явно дороже. ne1() и ne3(), в которых используются операторы == и != соответственно, являются более краткими и эквивалентными.

Visual Studio 2011 находится в стадии бета. Я бы счел это ошибкой. Мои тесты с двумя другими компиляторами, а именно gcc 4.6.2 и clang 3.2, с переключателем оптимизации O2 дали точно такую ​​же сборку для всех трех тестов (которые у меня были) на моем Коробка Windows 7. Вот краткое изложение:

$ cat ne.c

#include <stdbool.h>
bool ne1(int n) {
    return n != 0;
}

bool ne2(int n) {
    return n < 0 || n > 0;
}

bool ne3(int n) {
    return !(n != 0);
}

int main() {}

дает с помощью gcc:

_ne1:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    testl   %eax, %eax
    setne   %al
    ret
    .cfi_endproc
LFE0:
    .p2align 2,,3
    .globl  _ne2
    .def    _ne2;   .scl    2;  .type   32; .endef
_ne2:
LFB1:
    .cfi_startproc
    movl    4(%esp), %edx
    testl   %edx, %edx
    setne   %al
    ret
    .cfi_endproc
LFE1:
    .p2align 2,,3
    .globl  _ne3
    .def    _ne3;   .scl    2;  .type   32; .endef
_ne3:
LFB2:
    .cfi_startproc
    movl    4(%esp), %ecx
    testl   %ecx, %ecx
    sete    %al
    ret
    .cfi_endproc
LFE2:
    .def    ___main;    .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 2,,3
    .globl  _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
LFB3:
    .cfi_startproc
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset 5, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register 5
    andl    $-16, %esp
    call    ___main
    xorl    %eax, %eax
    leave
    .cfi_restore 5
    .cfi_def_cfa 4, 4
    ret
    .cfi_endproc
LFE3:

и с лязгом:

    .def     _ne1;
    .scl    2;
    .type   32;
    .endef
    .text
    .globl  _ne1
    .align  16, 0x90
_ne1:
    cmpl    $0, 4(%esp)
    setne   %al
    movzbl  %al, %eax
    ret

    .def     _ne2;
    .scl    2;
    .type   32;
    .endef
    .globl  _ne2
    .align  16, 0x90
_ne2:
    cmpl    $0, 4(%esp)
    setne   %al
    movzbl  %al, %eax
    ret

    .def     _ne3;
    .scl    2;
    .type   32;
    .endef
    .globl  _ne3
    .align  16, 0x90
_ne3:
    cmpl    $0, 4(%esp)
    sete    %al
    movzbl  %al, %eax
    ret

    .def     _main;
    .scl    2;
    .type   32;
    .endef
    .globl  _main
    .align  16, 0x90
_main:
    pushl   %ebp
    movl    %esp, %ebp
    calll   ___main
    xorl    %eax, %eax
    popl    %ebp
    ret

Я предлагаю зарегистрировать это как ошибку с помощью Microsoft Connect.

Примечание: я скомпилировал их как исходный код C, так как не думаю, что использование соответствующего компилятора C ++ внесет здесь какие-либо существенные изменения.

person dirkgently    schedule 31.05.2012
comment
Хороший тест, но вы поместили сравнения внутри функций. OP не предоставил никакого контекста и подойдет для компиляции вашей версии. - person phkahler; 31.05.2012
comment
Компиляция коротких фрагментов как независимых функций не интересна. Оптимизация, которая происходит после того, как они встраиваются в сайт звонка, более важна. - person Ben Voigt; 31.05.2012
comment
@BenVoigt: Я думаю, что мои тесты с VS2010 (выпущенным компилятором) решают эту проблему. Кроме того, мой (обновленный) источник (который я использовал для VS2010) должен ответить на все ваши вопросы относительно независимых функций. - person dirkgently; 31.05.2012
comment
Ваш новый тест испорчен, компилятор выполнил постоянное распространение, так как он всегда определял n = 10. А потом, вдобавок ко всему, он полностью исключил вызовы функций, так как результат не использовался и побочных эффектов не было. - person Ben Voigt; 31.05.2012
comment
не должно ли ne3 быть !(n == 0)? (У вас есть !(n != 0)) - person Matt; 31.05.2012
comment
@BenVoigt: Обновлено. Этого должно хватить. Я придерживаюсь своей точки зрения, что это ошибка, чем правило. - person dirkgently; 31.05.2012
comment
@BenVoigt: Также воздержитесь от слов вроде Компиляция коротких фрагментов как независимых функций неинтересна. ИМХО, это фактическое правило размещения сообщений на досках / работы с проблемами. Кроме того, именно так вы тестируете компиляторы. - person dirkgently; 31.05.2012
comment
@dirkgently: Когда дело доходит до вопросов оптимизатора, контекст решает все. - person Ben Voigt; 31.05.2012
comment
@dirkgently Вывод сборки: http://anonymouse.org/cgi-bin/anon-www.cgi/http://pastebin.com/DVH8ex2P Если я использую константу вместо rand (), эти инструкции оптимизируются до чего-то другого. Однако это не имеет значения, так как я также использовал std :: generate () с rand () в моем тестовом коде, и он использовал те же точные инструкции. Так что я должен думать об этом? Оптимизация, которая становится ошибкой? - person NFRCR; 31.05.2012
comment
@NFRCR: Я только что запустил ваш код с VS2010 cl на x86. С обоими макросами NON_ZERO и ZERO (отдельно, конечно!). Разница составляет ~ 1%. И я говорю «разница», потому что цифры меняются в любую сторону. Причина, по которой я использовал C, заключалась в том, что я не хотел пробираться сквозь искаженные имена и ужас iostreams в сборке. Также обратите внимание, что конкретный битовый шаблон может генерировать странные результаты (что является еще одной причиной использования rand(), хотя rand() не свободен от своих недостатков). - person dirkgently; 31.05.2012
comment
@dirkgently Если у вас есть больше времени, вы можете переместить zero1, zero2, nonZero1, nonZero2 в отдельный модуль компиляции (возможно, Test.h + Test.cpp). Тогда было бы проще найти общий вывод для этих функций в Test.asm. - person NFRCR; 31.05.2012
comment
@NFRCR: Я думаю, что код отягощен многими другими вещами. Вы пробовали код, который я опубликовал? Я мог бы перемещать ваш код, но я не вижу в этом смысла. С логической точки зрения, когда компилятору больше не над чем работать, я вижу, что прямые проверки на равенство более эффективны, чем две потенциальные проверки упорядочения (и необязательная OR). Я предлагаю обратиться напрямую к команде VS. - person dirkgently; 31.05.2012
comment
@dirkgently Да, я пробовал ваш код. Результаты - несколько комментариев. - person NFRCR; 31.05.2012
comment
ЭТО НЕ ОШИБКА! Как это может быть ошибкой, если скомпилированный код ведет себя должным образом? Это показывает, что оптимизатор можно улучшить, но можно улучшить каждый оптимизатор. (Между прочим, это теорема.) - person TonyK; 31.05.2012
comment
@TonyK: Это именно то, что я называю ошибкой. Очевидная (одна инструкция по сравнению с тремя - как написано программистом) тоже одна. Также попробуйте это с несколькими компиляторами. Затем вы начинаете думать, ошибка это или нет. - person dirkgently; 31.05.2012
comment
@NFRCR: Я полагаю, сборка? Это вроде как решает вопрос для меня. Это даже не ошибка. Он ведет себя именно так, как должен. Возможно, вы столкнулись с особым сценарием. Но потом, как я постоянно говорю, поговорите с командой VS. Они отличные, быстрые, и я уверен, что вы получите от них гораздо более надежный ответ. - person dirkgently; 31.05.2012
comment
Об ошибках Visual C ++ можно сообщать в Microsoft Connect. - person James McNellis; 01.06.2012
comment
Кроме того, стоит протестировать это с помощью Visual C ++ 2012 RC. это было выпущено только сегодня. - person James McNellis; 01.06.2012
comment
К вашему сведению: я протестировал код OP с помощью clang и gcc, и снова различия составили ~ 1% (или ниже). - person dirkgently; 01.06.2012
comment
dirkgently: Значит, программа, которую можно улучшить, - это именно то, что вы называете ошибкой? Мы не говорим на одном языке! - person TonyK; 01.06.2012
comment
@TonyK: IIUC, в предыдущем комментарии вы говорили об оптимизаторе. Это то, что я имел в виду в своем предыдущем комментарии. - person dirkgently; 01.06.2012
comment
смиренно: Да. У оптимизатора возникает ошибка, если он изменяет поведение оптимизируемой программы. Здесь дело обстоит не так. Все оптимизаторы нуждаются в улучшении; как я уже сказал, это теорема. Математики. - person TonyK; 01.06.2012
comment
@TonyK: Также было бы ошибкой ухудшить производительность одной инструкции по сравнению с производительностью трех. - person dirkgently; 01.06.2012
comment
dirkgently: Ты просто не слушаешь меня, не так ли? Ну что ж. - person TonyK; 01.06.2012
comment
Я не уверен, что это действительно ошибка. См. Мой комментарий в ответ на исходный вопрос о противоречивых контрольных данных. - person James McNellis; 01.06.2012
comment
@JamesMcNellis: Я обновил свой ответ некоторое время назад, как только взглянул на сборку, опубликованную OP, и мои тесты с кодом OP с использованием трех разных компиляторов. Проверьте правку вверху. Я тоже не думаю, что одна версия лучше другой. - person dirkgently; 01.06.2012

Это отличный вопрос, но я думаю, что вы стали жертвой анализа зависимостей компилятора.

Компилятору нужно очистить старшие биты eax только один раз, и они остаются очищенными для второй версии. За второй версии пришлось бы заплатить xor eax, eax, за исключением того, что анализ компилятора показал, что первая версия оставила это неясным.

Вторая версия может «обмануть», используя работу, проделанную компилятором в первой версии.

Как вы измеряете время? Это «(первая версия, за которой следует вторая версия) в цикле», или «(первая версия в цикле), за которой следует (вторая версия в цикле)»?

Не выполняйте оба теста в одной и той же программе (вместо этого перекомпилируйте для каждой версии) или, если вы это сделаете, протестируйте как «сначала версию A», так и «сначала версию B» и посмотрите, не повлияет ли то, что наступит раньше.


Иллюстрация обмана:

timer1.start();
double x1 = 2 * sqrt(n + 37 * y + exp(z));
timer1.stop();
timer2.start();
double x2 = 31 * sqrt(n + 37 * y + exp(z));
timer2.stop();

Если timer2 duration меньше timer1 duration, мы не делаем вывод, что умножение на 31 быстрее, чем умножение на 2. Вместо этого мы понимаем, что компилятор выполнил общий анализ подвыражения, и код стал:

timer1.start();
double common = sqrt(n + 37 * y + exp(z));
double x1 = 2 * common;
timer1.stop();
timer2.start();
double x2 = 31 * common;
timer2.stop();

И единственное, что доказано, это то, что умножение на 31 быстрее, чем вычисление common. Что неудивительно - умножение происходит намного быстрее, чем sqrt и exp.

person Ben Voigt    schedule 31.05.2012
comment
Добавлен тестовый код. Я запускал тесты 1 и 2 отдельно, результаты одинаковые. Единственная разница в том, что запускается первый тест, затем он нагревается и работает немного медленнее. - person NFRCR; 31.05.2012
comment
Это несколько не связано, но разве компилятор не оптимизирует умножение на 31 до (common << 5) - common? - person Matt; 31.05.2012
comment
@Matt: Не для умножения с плавающей запятой, это не так;) Для целочисленного умножения, да, я думаю, что большинство компиляторов знают этот трюк, но в зависимости от архитектуры он может быть или не быть быстрее. IMUL на два почти наверняка преобразуется в сдвиг влево. - person Ben Voigt; 31.05.2012