1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Почему этот код быстрее, чем тот?

Тема в разделе "WASM.X64", создана пользователем Jin X, 9 ноя 2018.

  1. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    358
    Адрес:
    Кольца Сатурна
    Две одинаковые проги. Одна на C, другая на C++.
    Компилируются GCC и G++ соответственно с опцией -O2.
    Код (C):
    1. #include <stdio.h>
    2. #include <time.h>
    3.  
    4. typedef unsigned long long uint64_t;
    5.  
    6. int inner_loop(uint64_t *n, uint64_t i)
    7. {
    8.   int count = 0;
    9.   while (*n % i == 0) {
    10.     ++count;
    11.     *n /= i;
    12.   }
    13.   return count;
    14. }
    15.  
    16. int prime_count(uint64_t n)
    17. {
    18.   int count = 0;
    19.   for (uint64_t i = 2; i*i <= n; ++i) {
    20.     count += inner_loop(&n, i);
    21.   }
    22.   if (n > 1) { ++count; }
    23.   return count;
    24. }
    25.  
    26. int main()
    27. {
    28.   double elapsed = clock();
    29.   int n = prime_count(1000000000000000003);
    30.   elapsed = (clock()-elapsed) / CLOCKS_PER_SEC;
    31.   printf("Elapsed time: %.3f sec (result = %d)\n", elapsed, n);
    32.   return 0;
    33. }
    Код (C++):
    1. #include <iostream>
    2. #include <ctime>
    3.  
    4. using std::cout;
    5.  
    6. int inner_loop(uint64_t &n, uint64_t i)
    7. {
    8.   int count = 0;
    9.   while (n % i == 0) {
    10.     ++count;
    11.     n /= i;
    12.   }
    13.   return count;
    14. }
    15.  
    16. int prime_count(uint64_t n)
    17. {
    18.   int count = 0;
    19.   for (uint64_t i = 2; i*i <= n; ++i) {
    20.     count += inner_loop(n, i);
    21.   }
    22.   if (n > 1) { ++count; }
    23.   return count;
    24. }
    25.  
    26. int main()
    27. {
    28.   double elapsed = clock();
    29.   int n = prime_count(1000000000000000003);
    30.   elapsed = (clock()-elapsed) / CLOCKS_PER_SEC;
    31.   cout << "Elapsed time: " << elapsed << " sec (result = " << n << ")\n";
    32.   return 0;
    33. }
    34.  

    Запускаем. C работает 7.4 сек, C++ – 8.5 сек (плюс-минус ≈0.1 сек), т.е. разница секунда (примерно 15%). Внушительно для такого простого кода, не так ли?

    Заглянем под капот.
    Код (ASM):
    1.         call    clock
    2.         mov     r9d, 2
    3.         xor     r10d, r10d
    4.         movabs  rcx, 1000000000000000003
    5.         cvtsi2sd        xmm6, eax
    6.         .p2align 4,,10
    7. .L22:
    8.         add     r9, 1
    9.         add     ebx, r10d
    10.         mov     rax, r9
    11.         imul    rax, r9
    12.         cmp     rax, rcx
    13.         ja      .L24
    14.         xor     edx, edx
    15.         mov     rax, rcx
    16.         xor     r10d, r10d
    17.         div     r9
    18.         test    rdx, rdx
    19.         jne     .L22
    20.         .p2align 4,,10
    21. .L23:
    22.         mov     rax, rcx
    23.         xor     edx, edx
    24.         add     r10d, 1
    25.         div     r9
    26.         xor     edx, edx
    27.         mov     rcx, rax
    28.         div     r9
    29.         test    rdx, rdx
    30.         je      .L23
    31.         jmp     .L22
    32.         .p2align 4,,10
    33. .L24:
    34.         cmp     rcx, 2
    35.         sbb     ebx, -1
    36.         call    clock
    Код (ASM):
    1.         call    clock
    2.         mov     r8d, 2
    3.         xor     r9d, r9d
    4.         movabs  rcx, 1000000000000000003
    5.         cvtsi2sd        xmm7, eax
    6.         .p2align 4,,10
    7. .L20:
    8.         add     r8, 1
    9.         add     ebx, r9d
    10.         mov     rax, r8
    11.         imul    rax, r8
    12.         cmp     rax, rcx
    13.         ja      .L28
    14.         xor     edx, edx
    15.         mov     rax, rcx
    16.         xor     r9d, r9d
    17.         div     r8
    18.         test    rdx, rdx
    19.         jne     .L20
    20.         .p2align 4,,10
    21. .L22:
    22.         mov     rax, rcx
    23.         xor     edx, edx
    24.         add     r9d, 1
    25.         div     r8
    26.         xor     edx, edx
    27.         mov     rcx, rax
    28.         div     r8
    29.         test    rdx, rdx
    30.         je      .L22
    31.         jmp     .L20
    32.         .p2align 4,,10
    33. .L28:
    34.         cmp     rcx, 2
    35.         pxor    xmm6, xmm6
    36.         sbb     ebx, -1
    37.         call    clock

    Один в один, только регистры разные (ну и pxor xmm6,xmm6 в плюсах, но проблема явно не в этом).

    Откроем через HIEW, чтобы посмотреть адреса.
    C:
    C.png

    C++:
    CPP.png

    В плюсах даже код основного цикла выравнен (всё это время цикл крутится между add r8/r9,1 и test rdx,rdx+jnz)! Но он работает ДОЛЬШЕ НА СЕКУНДУ !!!

    В чём прикол? Кто мне скажет?

    p.s. В архиве все файлы, включая EXE.
     

    Вложения:

    • test.zip
      Размер файла:
      73,1 КБ
      Просмотров:
      103
  2. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.567
    Адрес:
    г. Санкт-Петербург
    Кстати, на заметку. Для простых чисел можете сразу i увеличивать на 2, т.к. не существует чётных простых чисел кроме числа 2:
    Код (Text):
    1.  
    2. for (uint64_t i = 2; i*i <= n; ++i)
    3.  
     
    Jin X нравится это.
  3. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    358
    Адрес:
    Кольца Сатурна
    А вот тут наоборот C отстаёт буквально на пару десятых долей секунды.
    Код (C):
    1. #include <stdio.h>
    2. #include <time.h>
    3.  
    4. typedef unsigned long long uint64_t;
    5.  
    6. int prime_count(uint64_t n)
    7. {
    8.   int count = 0;
    9.   for (uint64_t i = 2; i*i <= n; ++i) {
    10.     while (n % i == 0) {
    11.       ++count;
    12.       n /= i;
    13.     }
    14.   }
    15.   if (n > 1) { ++count; }
    16.   return count;
    17. }
    18.  
    19. int main()
    20. {
    21.   double elapsed = clock();
    22.   int n = prime_count(1000000000000000003);
    23.   elapsed = (clock()-elapsed) / CLOCKS_PER_SEC;
    24.   printf("Elapsed time: %.3f sec (result = %d)\n", elapsed, n);
    25.   return 0;
    26. }
    Код (C++):
    1. #include <iostream>
    2. #include <ctime>
    3.  
    4. using std::cout;
    5.  
    6. int prime_count(uint64_t n)
    7. {
    8.   int count = 0;
    9.   for (uint64_t i = 2; i*i <= n; ++i) {
    10.     while (n % i == 0) {
    11.       ++count;
    12.       n /= i;
    13.     }
    14.   }
    15.   if (n > 1) { ++count; }
    16.   return count;
    17. }
    18.  
    19. int main()
    20. {
    21.   double elapsed = clock();
    22.   int n = prime_count(1000000000000000003);
    23.   elapsed = (clock()-elapsed) / CLOCKS_PER_SEC;
    24.   cout << "Elapsed time: " << elapsed << " sec (result = " << n << ")\n";
    25.   return 0;
    26. }
    Хотя по сути всё то же самое!

    p.s. Всё это, разумеется, запускалось многократно, так что это не погрешности.
    --- Сообщение объединено, 9 ноя 2018 ---
    Точно, спасибо! Банально, но ведь не задумывался об этом раньше :)
     

    Вложения:

    • test2.zip
      Размер файла:
      14,9 КБ
      Просмотров:
      99
  4. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.567
    Адрес:
    г. Санкт-Петербург
    Полную команду компиляции, плиз, в студию, для обоих кейсов. Прогоню локально у себя, посмотрю.
     
  5. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    358
    Адрес:
    Кольца Сатурна
    И сразу прикол!
    Поменял на
    Код (C++):
    1.   count += inner_loop(n, 2);
    2.   for (uint64_t i = 3; i*i <= n; i += 2) {
    3.     count += inner_loop(n, i);
    4.   }
    И плюсы стали обгонять.
    --- Сообщение объединено, 9 ноя 2018 ---
    Всё просто:
    gcc -s -O2 testC.c -o testC.exe
    g++ -s -O2 testCPP.cpp -o testCPP.exe

    и
    gсс -S -O2 -masm=intel testC.c -o testC.s
    g++ -S -O2 -masm=intel testCPP.cpp -o testCPP.s

    --- Сообщение объединено, 9 ноя 2018 ---
    Очепятка была, исправил...
    --- Сообщение объединено, 9 ноя 2018 ---
    Везде одинаково.
    Для test2 так же.
     
  6. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.567
    Адрес:
    г. Санкт-Петербург
    Разницы никакой, на уровне стат. погрешности:
    Компиляция:
    Код (Text):
    1.  
    2. #!/bin/bash
    3.  
    4. gcc -m64 -s -O2 testC.c -o testC.exe
    5. g++ -m64 -s -O2 testCPP.cpp -o testCPP.exe
    6.  
    7. g++ -m64 -S -O2 testC.c -o testC.s
    8. gcc -m64 -S -O2 testCPP.cpp -o testCPP.s
    9.  
    У вас никакого CPU frequency scaling, случаем, не включено? Попробуйте для начала его отключить и ещё раз тесты попробовать прогнать.
     
  7. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    358
    Адрес:
    Кольца Сатурна
    SadKo, ну как? В Электропитании → Управление питанием процессора → Минимальное состояние процессора стоит 5%. Но я код перезапускал многократно, всё время одинаковый результат. Не может же проц в одной программе всё время scale'иться, а в другой – нет.
    Ещё вы же в Linux'е собираете, а я в винде. Я думаю, это влияет, там как минимум адреса разные. Если есть винда, Wine (etc), попробуйте запустить мои EXE-шники.
     
  8. Ronin_

    Ronin_ Active Member

    Публикаций:
    1
    Регистрация:
    24 дек 2016
    Сообщения:
    242
    Jin X, тоже разницa ~1 sec, если компилировать cl от ms то разница ~0,065, но прирост по времени ~10 sec у каждого из подопытных.
     
  9. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    358
    Адрес:
    Кольца Сатурна
    Ronin_, то есть дольше на 10 сек становится?
    Тут какой-то прикол с выравниванием, видимо.
    Если добавить в начало main'а строку:
    Код (C):
    1.   volatile int x = 5;
    то код на C начинает выполняться на секунду дольше, как C++.
    --- Сообщение объединено, 9 ноя 2018 ---
    Только хочется найти объяснение этому...
     
  10. Ronin_

    Ronin_ Active Member

    Публикаций:
    1
    Регистрация:
    24 дек 2016
    Сообщения:
    242
    Jin X, и вызовов на плюсах в майн 11 против Си где их всего 7.

    c
    Код (Text):
    1. call fcn.004017d0
    2. call sub.msvcrt.dll_clock_950 ; clock_t clock(void)
    3. call fcn.004027d0
    4. call fcn.004026d0
    5. call fcn.004027d0
    6. call sub.msvcrt.dll_clock_950 ; clock_t clock(void)
    7. call sub.msvcrt.dll_printf_910 ; int printf(const char *format)
    cpp:

    Код (Text):
    1.  
    2. call fcn.00401820
    3. call sub.msvcrt.dll_clock_794 ; clock_t clock(void)
    4. call sub.libgcc_s_dw2_1.dll___umoddi3_6f0
    5. call sub.libgcc_s_dw2_1.dll___udivdi3_6f8
    6. call sub.libgcc_s_dw2_1.dll___umoddi3_6f0
    7. call sub.msvcrt.dll_clock_794 ; clock_t clock(void)
    8. call sub.libstdc___6.dll__ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ost
    9. call sub.libstdc___6.dll__ZNSo9_M_insertIdEERSoT_788
    10. call sub.libstdc___6.dll__ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ost
    11. call sub.libstdc___6.dll__ZNSolsEi_780
    12. call sub.libstdc___6.dll__ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc_7
    13.  
     
  11. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    358
    Адрес:
    Кольца Сатурна
    Ronin_, а вы ставите оптимизацию на -O2 и компилите гнусавым (судя по msvcrt это не шланг)?
    У меня вообще без вызовов всё сплошной простынёй идёт, только call __main и call clock (2 шт) и таи, и там.
    Да даже если и есть, то фиг с ними! Основной же код между двумя вызовами clock'а – он же замеряется! А там всё одинаково...
     
  12. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.567
    Адрес:
    г. Санкт-Петербург
    А аверов у вас никаких не стоит? Может, имеет смысл отключить на время тестирования?
     
  13. Ronin_

    Ronin_ Active Member

    Публикаций:
    1
    Регистрация:
    24 дек 2016
    Сообщения:
    242
    Jin X, gcc v8.1.

    Код (Text):
    1. gcc -Wall -O2 -s -o test testC.c
     
  14. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    358
    Адрес:
    Кольца Сатурна
    Прикол в том, что я авер отключил и забыл включить, так что без него всё тестилось...

    Ronin_, интересно, почему результат разный? :)
    Ааа, может, под x86? Я под x64 делал...
     
  15. Thetrik

    Thetrik UA6527P

    Публикаций:
    0
    Регистрация:
    25 июл 2011
    Сообщения:
    550
    Из 1 поста оба EXE отрабатывают одинаково.
    [​IMG]
     
    Последнее редактирование: 9 ноя 2018
  16. Ronin_

    Ronin_ Active Member

    Публикаций:
    1
    Регистрация:
    24 дек 2016
    Сообщения:
    242
    gcc:
    [​IMG]

    cl показал новые результаты:
    [​IMG]
    Да.
     

    Вложения:

  17. Jin X

    Jin X Active Member

    Публикаций:
    0
    Регистрация:
    15 янв 2009
    Сообщения:
    358
    Адрес:
    Кольца Сатурна
    Thetrik, не грузится картинка.
    А что за проц? Несколько раз запускал?
    --- Сообщение объединено, 9 ноя 2018 ---
    А если x64 ?
     
  18. Ronin_

    Ronin_ Active Member

    Публикаций:
    1
    Регистрация:
    24 дек 2016
    Сообщения:
    242
    [​IMG]
     

    Вложения:

  19. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    5.265
    профилируйте и узрите, где тормоза.. откеля они :)