Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Алгоритм]сравнивать на равенство или на больше


Автор: babe 6.3.2009, 12:05
Добрый день,
При поиске в некотором массиве сравнение индекса для некоторой задачи  можно записать:
 
если(индекс > 0) либо если(индекс <> 0). 
Результат будет правильным и в том и в другом случае.

Вопрос в том- в каком случае сравнение произойдет быстрее и будет ли это быстрее, то есть есть ли принципиальная разница что лучше использовать- видимо обоснованием будет каким образом происходит сравнение на больше? Можно ли где-нибудь прочитать каким образом сравниваются больше и меньше? как это происходит внутри языков?
Заранее большое спасибо! 

Автор: Gaudi 6.3.2009, 12:56
Код

int main()
{
    int a;
    int b = 0;
    a = rand();
    if (a != 0)
        b++;
}


asm код, полученной в IDA 5.2
Код

_main proc near

var_D8=    byte ptr -0D8h
var_14=    dword ptr -14h
var_8= dword ptr -8

push    ebp
mov    ebp, esp
sub    esp, 0D8h
push    ebx
push    esi
push    edi
lea    edi, [ebp+var_D8]
mov    ecx, 36h
mov    eax, 0CCCCCCCCh
rep stosd
mov    [ebp+var_14], 0
call    j__rand
mov    [ebp+var_8], eax
cmp    [ebp+var_8], 0
jz    short loc_4113DC
mov    eax, [ebp+var_14]
add    eax, 1
mov    [ebp+var_14], eax

loc_4113DC:
xor    eax, eax
pop    edi
pop    esi
pop    ebx
add    esp, 0D8h
cmp    ebp, esp
call    j___RTC_CheckEsp
mov    esp, ebp
pop    ebp
retn
_main endp


если
Код

int main()
{
    int a;
    int b = 0;
    a = rand();
    if (a > 0)
        b++;
}


то
Код

_main proc near

var_D8=    byte ptr -0D8h
var_14=    dword ptr -14h
var_8= dword ptr -8

push    ebp
mov    ebp, esp
sub    esp, 0D8h
push    ebx
push    esi
push    edi
lea    edi, [ebp+var_D8]
mov    ecx, 36h
mov    eax, 0CCCCCCCCh
rep stosd
mov    [ebp+var_14], 0
call    j__rand
mov    [ebp+var_8], eax
cmp    [ebp+var_8], 0
jle    short loc_4113DC
mov    eax, [ebp+var_14]
add    eax, 1
mov    [ebp+var_14], eax

loc_4113DC:
xor    eax, eax
pop    edi
pop    esi
pop    ebx
add    esp, 0D8h
cmp    ebp, esp
call    j___RTC_CheckEsp
mov    esp, ebp
pop    ebp
retn
_main endp


jle(of 8e) и jz(of 84) выполнятся одинаково ?_быстро_?

ps: компилировал в  vc2008 express с опциями по-умолчанию

Автор: GoldFinch 6.3.2009, 13:03
Код

mov    [ebp+var_8], eax
cmp    [ebp+var_8], 0
jz    short loc_4113DC

конпелятор msvc не перестаем меня радовать
обычно для проверки на равенство нулю юзают test eax,eax\jz xxx а для сравнения с нулем cmp xxx,0\jxx zzz
test eax,eax короче и может гдето быстрее
впрочем с таким компилятором об оптимизации такого рода можно не думать, и так и так *плохо* компилит

Автор: MaXL 6.3.2009, 14:58
GoldFinch, а разве MSVC++ не лучший в мире компилер по оптимизации ? чот я слышал такой расклад:
 1) MSVC++.
 2) Intel.
 3) g++
Gaudi, попробуйти ещё интеловским скомпилить. И вообще вы в каком режиме компилили, с оптимизацией ?

Автор: alexanderwdark 6.3.2009, 15:14
Цитата(MaXL @ 6.3.2009,  14:58)
GoldFinch, а разве MSVC++ не лучший в мире компилер по оптимизации ? чот я слышал такой расклад:
 1) MSVC++.
 2) Intel.
 3) g++
Gaudi, попробуйти ещё интеловским скомпилить. И вообще вы в каком режиме компилили, с оптимизацией ?

ICC 11, конечно, гораздо разумнее компилирует, чем MSVC.


Код

_main    PROC NEAR 
.B1.1:                          ; Preds .B1.0
        push      ebp                                           ;5.1
        mov       ebp, esp                                      ;5.1
        sub       esp, 3                                        ;5.1
        and       esp, -8                                       ;5.1
        add       esp, 4                                        ;5.1
        sub       esp, 12                                       ;5.1
        mov       DWORD PTR [-12+ebp], 0          ;7.11
        call      _rand                                            ;8.9
                                ; LOE eax
.B1.7:                          ; Preds .B1.1
        mov       DWORD PTR [-4+ebp], eax                       ;8.9
                                ; LOE
.B1.2:                          ; Preds .B1.7
        mov       eax, DWORD PTR [-4+ebp]                       ;8.5
        mov       DWORD PTR [-8+ebp], eax                       ;8.5
        mov       eax, DWORD PTR [-8+ebp]                       ;9.9
        test      eax, eax                                      ;9.13
        jle       .B1.4         ; Prob 50%                      ;9.13
                                ; LOE
.B1.3:                          ; Preds .B1.2
        inc       DWORD PTR [-12+ebp]                           ;10.9
                                ; LOE
.B1.4:                          ; Preds .B1.3 .B1.2
        xor       eax, eax                                      ;11.1
        leave                                                   ;11.1
        ret                                                     ;11.1
        ALIGN     2
                                ; LOE
; mark_end;


Автор: Coder 6.3.2009, 15:19
Кстати, Delphi 7 использует инструкцию test.


Автор: alexanderwdark 6.3.2009, 15:30
Цитата(Coder @ 6.3.2009,  15:19)
Кстати, Delphi 7 использует инструкцию test.

В последних версиях компилятор в делфи очень даже разумный. Не раз видел отличный высокоуровневый код, например компрессоров на чистом делфи, дающий более высокую производительность, чем оптимизированный сишный.

Автор: Gaudi 6.3.2009, 15:33
Тот же Си код, но с оптимизацией по скорости (/O2)
Код

_main proc near
call    _rand
xor    eax, eax
retn
_main endp

Ни байта лишнего кода!

Тогда вот для этого
Код

#include <stdio.h>
int main()
{
    int a;
    int b = 0;
    a = rand();
    if (a != 0)
        printf("%d", ++b);
}


msvc с теми же опциями дает
Код

_main proc near
call    _rand
test    eax, eax
jz    short loc_401019
push    1
push    offset aD    ; "%d"
call    ds:__imp__printf
add    esp, 8

loc_401019:
xor    eax, eax
retn
_main endp


Intell c++ compiler'a под рукой нету

Автор: alexanderwdark 6.3.2009, 15:34
Немного измел код для того, чтобы оптимизатор не ингорировал код, не имеющий эффекта (поскольку в исходном результат переменной b не используется нигде после присванивания)

Код

int main()
{
    int a;
    int b = 0;
    
    a = rand();
    if (a > 0)
        b++;

return b;
}




MSVC 9 (maximize speed mode)

Код

PUBLIC    _main
EXTRN    _rand:PROC
; Function compile flags: /Ogtpy
; File c:\temp\test\test\test.cpp
;    COMDAT _main
_TEXT    SEGMENT
_main    PROC                        ; COMDAT

; 6    : {

    push    esi

; 7    :     int a;
; 8    :     int b = 0;

    xor    esi, esi

; 9    :    
; 10   :     a = rand();

    call    _rand

; 11   :     if (a > 0)

    test    eax, eax

; 12   :         b++;

    lea    eax, DWORD PTR [esi+1]
    jg    SHORT $LN1@main

; 13   : 
; 14   : return b;

    mov    eax, esi
$LN1@main:
    pop    esi

; 15   : }

    ret    0
_main    ENDP
_TEXT    ENDS
END




Intel CPP11 Maximize Speed + Hi-level

Код

       ALIGN     16
    PUBLIC _main
_main    PROC NEAR 
.B1.1:                          ; Preds .B1.0

;;; {

        push      ebp                                           ;6.1
        mov       ebp, esp                                      ;6.1
        and       esp, -128                                     ;6.1
        sub       esp, 128                                      ;6.1
        push      3                                             ;6.1
        call      ___intel_new_proc_init                        ;6.1
                                ; LOE ebx esi edi
.B1.5:                          ; Preds .B1.1
        pop       ecx                                           ;6.1
        stmxcsr   DWORD PTR [esp]                               ;6.1
        or        DWORD PTR [esp], 32768                        ;6.1
        ldmxcsr   DWORD PTR [esp]                               ;6.1

;;;     int a;
;;;     int b = 0;
;;;    
;;;     a = rand();

        call      _rand                                         ;10.9
                                ; LOE eax ebx esi edi
.B1.2:                          ; Preds .B1.5
        mov       edx, 1                                        ;
        xor       ecx, ecx                                      ;
        cmp       eax, 0                                        ;
        cmovg     ecx, edx                                      ;

;;;     if (a > 0)
;;;         b++;
;;; 
;;; return b;

        mov       eax, ecx                                      ;14.8
        mov       esp, ebp                                      ;14.8
        pop       ebp                                           ;14.8
        ret                                                     ;14.8
        ALIGN     16
                                ; LOE
; mark_end;
_main ENDP





C Builder 2007:


Код

_main    proc    near
?live1@0:
@1:
    push      ebx
    xor       ebx,ebx
?live1@32: ; EBX = b
    call      _rand
?live1@48: ; EBX = b, EAX = a
    test      eax,eax
    jle       short @2
?live1@64: ; EBX = b
    inc       ebx
@2:
    mov       eax,ebx
?live1@96: ; 
@4:
@3:
    pop       ebx
    ret 
_main    endp
_TEXT    ends
    public    _main
 extrn _rand:near




FreePascal 2.2.2 с оптимизацией


Код

_main:
; Temps allocated between esp+0 and esp+0
; [test.pas]
; [8] BEGIN
        call    FPC_INITIALIZEUNITS
; [13] a := random(32768);
        mov    eax,32768
        call    SYSTEM_RANDOM$LONGINT$$LONGINT
        mov    dword ptr [dword ptr TC_P$TEST_A],eax
; [14] if a > 0 then
        test    eax,eax
        jna    @@j8
; [15] b:=b+1;
        inc    dword ptr [dword ptr TC_P$TEST_B]
@@j8:
; [17] halt(b);
        mov    al,byte ptr [dword ptr TC_P$TEST_B]
        call    SYSTEM_HALT$BYTE
; [20] END.
        call    FPC_DO_EXIT
        ret



и без

Код

# [8] BEGIN
    pushl    %ebp
    movl    %esp,%ebp
    call    FPC_INITIALIZEUNITS
# [13] a := random(32768);
    movl    $32768,%eax
    call    SYSTEM_RANDOM$LONGINT$$LONGINT
    movl    %eax,TC_P$TEST_A
# [14] if a > 0 then
    movl    TC_P$TEST_A,%eax
    cmpl    $0,%eax
    ja    .Lj7
    jmp    .Lj8
.Lj7:
# [15] b:=b+1;
    movl    TC_P$TEST_B,%eax
    incl    %eax
    movl    %eax,TC_P$TEST_B
.Lj8:
# [17] halt(b);
    movb    TC_P$TEST_B,%al
    call    SYSTEM_HALT$BYTE
# [20] END.
    call    FPC_DO_EXIT
    leave
    ret




Автор: Sefko 6.3.2009, 17:05
Забавно все это читать новичку. 
Интересно не столько то, что такой вопрос появился а разделе "Алгоритмы", сколько стиль ответов, по всему видно, знающих людей.

Смотрим профиль вопрошающей, на предмет выяснения языка программирования, который интересен ей.
Что видим? Четыре предыдущих сообщения babe относились к JavaScript.
.

Автор: babe 6.3.2009, 17:36
Четыре предыдущих сообщения( смотри дату) не дают возможности сделать вывод о том, что меня интересуетsmile
меня интересует КАК обрабатывается сравнение на больше - то есть можно ли где то почитать вразумительно реализацию этого внутри компилятора- любого. Кажется в разделе оговаривается не привязываться к конкретному языку, но если уж так это принципиально- решение задачи видится на  php.
Но конечно количество ответов и их содержимое меня впечатлило!)))
Идея практическая понятна- большое спасибо- но хотелось бы слегка теории- так сказать изнутри.
Если не затруднит.
Большое спасибо всем, кто откликнулся и потратил свое время!!!

Автор: zim22 6.3.2009, 18:31
Цитата(babe @  6.3.2009,  12:05 Найти цитируемый пост)
Вопрос в том- в каком случае сравнение произойдет быстрее

напишите два варианта кода. один с <, второй с <>. замерьте время выполнения. что выполняется быстрее - то и происходит быстрее.

Автор: Sefko 6.3.2009, 19:35
Цитата(babe @ 6.3.2009,  17:36)
Четыре предыдущих сообщения( смотри дату) не дают возможности сделать вывод о том, что меня интересуетsmile
меня интересует КАК обрабатывается сравнение на больше - то есть можно ли где то почитать вразумительно реализацию этого внутри компилятора- любого.

Тут вот какое дело.

1. Вообще-то именно в такой постановке (реализация внутри любого компилятора) вопрос не имеет смысла.

2. Для большинства компиляторов - во всяком случае, для компиляторов с языка C++ - вопрос вряд ли актуален с практической точки зрения. Не удастся как-то ускорить выполнение на таких мелочах. Так что тут имеет смысл разве что теоретический интерес к качеству транслятора.

3. Кроме компиляторов бывают еще интерпретаторы. Вот для них этот вопрос, пожалуй, более актуальный. Тут бывают всякие чудеса.

4. Реализация исполнения скриптов осуществляется таки интерпретаторами. Например, http://ru.wikipedia.org/wiki/JavaScript

5. Написать скрипт, который будет достаточно бодро исполняться на НЕИЗВЕСТНО каком компьютере НЕИЗВЕСТНО каким интерпретатором - задача не очень простая. А именно такая задача и стоит, если делается какое-то сетевое приложение. И вряд ли (ну, мне так кажется) решению этой задачи могут помочь ассемблерные коды, изготовленные разными трансляторами с языка C++. Подлянка состоит в том, что даже такие разумные советы, как данный здесь на ветке - измерить физическое время, - как-то трудно осуществимы. Не из-за этих ли обстоятельств и появилась "теоретическая" постановка вопроса?

6. И, тем не менее, все обсуждение сконцентрировалось вокруг анализа ассемблерных кодов.

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

Автор: GoldFinch 6.3.2009, 22:37
zim22, замер времени выполнения такой кратковременной операции - весьма нетривиальная задача

если компилятор оптимизирует код, то результирующий код будет зависеть от контекста в котором происходит сравнение

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

Добавлено через 14 минут и 10 секунд
Цитата(babe @  6.3.2009,  12:05 Найти цитируемый пост)
каким образом сравниваются больше и меньше? как это происходит внутри языков?

любой компилятор\интерпретатор компилирует высокоуровневый код языка в некоторый низкоуровневый код
сравнение двух чисел производится их вычитанием друг из друга, больше\меньше\равно соответствует положительному\отрицательному\нулевому результату этого вычитания
проверка числа на ноль может быть вынесена в отдельную инструкцию, требующую 1 операнд и не выполняющую никаких арифметических\логических действий

Автор: Rififi 7.3.2009, 10:07
GoldFinch, 
конпелятор msvc не перестаем меня радовать

Возрадуйся ещё больше, когда откроется тебе Знамение, что такое конструкции

mov    [ebp+var_8], eax
cmp    [ebp+var_8], 0

конпелятор использует только в дебаге.

Автор: GoldFinch 7.3.2009, 10:24
Rififi, в релизе при работе с вещественными числами он и не такое использует

Автор: babe 7.3.2009, 10:39
Вот и ответ!smile
Цитата

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


GoldFinch, спасибо

Цитата

проверка числа на ноль может быть вынесена в отдельную инструкцию, требующую 1 операнд и не выполняющую никаких арифметических\логических действий
 - каким образом?smile

Автор: zim22 7.3.2009, 11:30
babe, GoldFinch уже ответил каким образом:

Цитата(GoldFinch @  6.3.2009,  13:03 Найти цитируемый пост)
обычно для проверки на равенство нулю юзают test eax,eax\jz xxx а для сравнения с нулем cmp xxx,0\jxx zzztest eax,eax короче и может гдето быстрее


Автор: GoldFinch 7.3.2009, 11:36
babe, все зависит от платформы 
Если платформа аппаратная - конкретное семейство процессоров (например х86) то инструкции аппаратные и проверка на 0 выполняется аппаратно, например операцией ИЛИ для всех разрядов числа.
Если платформа программная - виртуальная машина которая обрабатывает байт-код (java, .NET) то ее инструкции выполняются виртуальной машиной, путем выполнения кода на конкретной аппаратной платформе.
Вобщем если платформа поддерживает отдельную инструкцию проверки на 0, то она какнибудь ее реализует smile При этом если инструкции имеют разную длину и разное время выполнения, то отдельная инструкция проверки на 0 будет короче инструкции сравнения (т.к. только 1 операнд), и возможно быстрее. В любом случае оптимизацией такого рода должен заниматься компилятор а не программист.

Автор: babe 7.3.2009, 12:01
угу, все понятно- что ж тут непонятного.
Спасибо!smile
Конечно инструкция с одним операндом выполнится быстрее, чем с двумя.
Меня просто смутило "не выполняет никаких логических действий".

Автор: alexanderwdark 10.3.2009, 15:35
Говоря о оптимизации, сложно вести речь о интерпретаторах и о компиляторах, не генерирующих машинный код. Быстродействующие решения принципиально не разрабатываются для виртуальных машин, реалтайм интерпретаторов да и dotnet. Что касается последней - по причине значительной общипанности последней и переходу к ограниченному безопасному программированию.  Область оптимизаци  - ASM, C/C++ без классов,  Delphi/FPC/GPC без классов.  Здесь возможен наиболее оптимальный код, в частности, наиболее эффективная реализация компрессоров, криптосистем и прочих критичных по времени алгоритмов.

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

Подумайте лучше о алгоритмической оптимизации.  Чаще всего в подобных случаях помогает выбор более разумного алгоритма. К примеру, замена алгоритмов сортировки, простейшее хэширование при поиске и прочее..

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)