VPF::[Алгоритм]сравнивать на равенство или на больше

babe

Дата 6.3.2009, 12:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 11.9.2007

Репутация: нет
Всего: нет

Добрый день,
При поиске в некотором массиве сравнение индекса для некоторой задачи можно записать:

если(индекс > 0) либо если(индекс <> 0).
Результат будет правильным и в том и в другом случае.

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

Gaudi

Дата 6.3.2009, 12:56 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 42
Регистрация: 18.3.2007

Репутация: нет
Всего: нет

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 1
Всего: 26

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Developer

Профиль
Группа: Участник
Сообщений: 380
Регистрация: 24.10.2005
Где: Владивосток

Репутация: нет
Всего: 2

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

--------------------

MaXL

alexanderwdark

Дата 6.3.2009, 15:14 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 20.2.2009

Репутация: нет
Всего: нет

Цитата(MaXL @ 6.3.2009, 14:58)

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 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 13.12.2004

Репутация: нет
Всего: 11

Кстати, Delphi 7 использует инструкцию test.

Присоединённый файл ( Кол-во скачиваний: 11 )

D7.JPG 92,15 Kb

alexanderwdark

Дата 6.3.2009, 15:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 20.2.2009

Репутация: нет
Всего: нет

Цитата(Coder @ 6.3.2009, 15:19)

Кстати, Delphi 7 использует инструкцию test.

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

Gaudi

Дата 6.3.2009, 15:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 42
Регистрация: 18.3.2007

Репутация: нет
Всего: нет

Тот же Си код, но с оптимизацией по скорости (/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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 20.2.2009

Репутация: нет
Всего: нет

Немного измел код для того, чтобы оптимизатор не ингорировал код, не имеющий эффекта (поскольку в исходном результат переменной 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

Это сообщение отредактировал(а) alexanderwdark - 6.3.2009, 16:19

Sefko

Дата 6.3.2009, 17:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 5.3.2009

Репутация: нет
Всего: 1

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

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

babe

Дата 6.3.2009, 17:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 19
Регистрация: 11.9.2007

Репутация: нет
Всего: нет

Четыре предыдущих сообщения( смотри дату) не дают возможности сделать вывод о том, что меня интересует smile

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

zim22

Дата 6.3.2009, 18:31 (ссылка)

(голосов:1)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

Цитата(babe @ 6.3.2009, 12:05

)

Вопрос в том- в каком случае сравнение произойдет быстрее

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

--------------------

C++ FAQ Lite

Sefko

Дата 6.3.2009, 19:35 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 20
Регистрация: 5.3.2009

Репутация: нет
Всего: 1

Цитата(babe @ 6.3.2009, 17:36)

Четыре предыдущих сообщения( смотри дату) не дают возможности сделать вывод о том, что меня интересует smile

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

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

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

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

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

4. Реализация исполнения скриптов осуществляется таки интерпретаторами. Например, "JavaScript-код включается в HTML-код страницы и исполняется интерпретатором, встроенным в браузер".

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

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

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

Это сообщение отредактировал(а) Sefko - 6.3.2009, 19:39

GoldFinch

Дата 6.3.2009, 22:37 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 1
Всего: 26

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

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

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

Добавлено через 14 минут и 10 секунд

Цитата(babe @ 6.3.2009, 12:05

)

каким образом сравниваются больше и меньше? как это происходит внутри языков?

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

Rififi

Дата 7.3.2009, 10:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1254
Регистрация: 9.3.2008

Репутация: 4
Всего: 36

GoldFinch,
конпелятор msvc не перестаем меня радовать

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

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

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »