Про быструю сортировку, SORT DOS и ассемблер

Тема в разделе "WASM.RESEARCH", создана пользователем Эдуард, 23 фев 2017.

  1. Эдуард

    Эдуард New Member

    Публикаций:
    0
    Регистрация:
    22 фев 2017
    Сообщения:
    5
    Про быструю сортировку

    ОГРОМНАЯ благодарность Mikl___ за не имеющие аналогов статьи и комментарии, размещённые в разные времена на различных ресурсах. В частности,
    здесь - уникальная подборка решений от Mikl___ по сортировке массива двойных слов на ассемблере.

    Я воспользовался сортировкой Хоара, немного сократив код с целью создания ассемблерной вставки:
    Код (ASM):
    1.     pop eax
    2.     pop ebx
    3.     pop ecx
    4.     add  esp,0x8
    5.     push ecx
    6.     push ebx
    7.     push eax
    8. start:    mov  ebx,DWORD PTR [esp+0x4]
    9.     mov  ebp,DWORD PTR [esp+0x8]
    10.     mov eax, ebx
    11.     cmp eax, ebp
    12.     jae  short x1
    13.     mov edx, ebp
    14.     sub  edx,eax
    15.     shr  edx,0x3
    16.     mov  edi,DWORD PTR [eax+edx*4]
    17.     cmp eax, ebp
    18.     ja   short b0
    19. b1:    mov eax, ebx
    20.     cmp  DWORD PTR [eax],edi
    21.     jge  short b3
    22.     add  ebx,0x4
    23.     jmp  short b1
    24. b4:    sub  ebp,0x4
    25. b3:    mov eax, ebp
    26.     cmp  DWORD PTR [eax],edi
    27.     jg   short b4
    28.     mov ecx, ebx
    29.     cmp ecx, eax
    30.     ja   short b5
    31.     sub  ebp,0x4
    32.     add  ebx,0x4
    33.     mov  edx,DWORD PTR [eax]
    34.     xchg  DWORD PTR [ecx],edx
    35.     mov  DWORD PTR [eax],edx
    36. b5:    mov eax, ebx
    37.     cmp eax, ebp
    38.     jbe  short b1
    39. b0:    mov edi, eax
    40.     sub  eax,0x4
    41.     push eax
    42.     push  DWORD PTR [esp+0x8]
    43.     call start
    44.     push  DWORD PTR [esp+0x8]
    45.     push edi
    46.     call start
    47. x1:    ret  0x8
    Эффективность (процессор x86 Family 6 Model 23 Stepping 10 GenuineIntel ~2500 МГц):

    • 50.000 Long - среднее время 8,72 мс (диапазон 0..31 мс)
    • 1.000.000 Long - среднее время 202,70 мс (диапазон 187..235 мс)
    Решение задачи по сортировке массива двойных слов проверено. Перейдём к сортировке строк.


    Про SORT DOS

    Требуется быстрая сортировка массива строк различной длины. Опять же Mikl___ предлагает отличное, скоростное решение:
    через вызов командной строки и системную команду SORT:
    Код (DOS):
    1. sort test.txt > test.srt
    или на masm:
    Код (ASM):
    1. ; masm dos com #
    2. .286
    3. .model tiny
    4. .code
    5. org 100h
    6. start:  mov bx,100h ;выделим блок памяти в 256 параграфов
    7.     mov ah,4Ah      
    8.     int 21h
    9.     mov bx,offset parametrs ;указываем на блок параметров
    10.     mov [bx+4],cs
    11.     mov dx,offset filename
    12.     mov ax,4B00h;загрузить и выполнить программу из командной строки
    13.     int 21h
    14.     retn        ;выход в DOS
    15. command_line db N,'/c sort abc.txt > abc.srt',0Dh
    16. N = $-command_line-1;длина командной строки
    17. ;командная строка типа pascal, начинается с байта длины строки, заканчивается
    18. ;ASCII-кодом клавиши Enter (0Dh). При передаче команды CMD.EXE нужно указать /С перед
    19. ;строкой (требование вызова вторичного командного процессора). Программу cmd.exe
    20. ;из папки windows\system32\ проще разместить в том же каталоге, что и программа
    21. filename db 'cmd.exe',0
    22. parametrs dw 0,command_line,5 dup(0);блок параметров
    23. end start
    Сортировка текста в файле работает отлично: файл размером 1,33 Мб (более 26'000 строк различной длины, но не более 64 байт) - сортируется менее чем за 2 секунды, включая сохранение отсортированных текстовых данных во вновь создаваемом файле. Условие: разделитель строк - CRLF, или 0A0Dh. Об этом даже прописано в исходнике файла SORT.exe:
    Код (ASM):
    1. TITLE   SORT FILTER FOR MS-DOS
    2. ;
    3. ; Sort  /R /+n
    4. ; /R -> reverse sort
    5. ; /+n -> sort on column n
    6. ;
    7. ; Written by:   Chris Peters
    8. ;
    9. ; Modification History:
    10. ;           3-18-83 MZ  Fix CR-LF at end of buffer
    11. ;                       Fix small file sorting
    12. ;                       Fix CR-LF line termination bug
    13. ;                       Comment the Damn source
    14. ;

    А как быть, если текст - не в файле, а в памяти? К примеру, это байтовый массив - результат расшифровки потока Stream методом Deflate [RFC 1951].

    Вопрос: можно ли подставить в аргументы функции sort не имена in/out файлов, а указатели на адреса памяти?


    Ассемблер


    В очередной раз прошу прощения за возможные ошибки в терминологии и своих рассуждениях.
    _____________________________________________________

    Команда
    Код (DOS):
    1. sort test.txt > test.srt
    вызывает исполняемый файл SORT.exe, расположенный в C:\Windows\system32.

    Может поправить исходный код файла SORT.ASM, датированного, правда, 18 марта 1983 года, зато с подробнейшими комментариями от компании Microsoft по каждой строке кода (см. прикреплённый файл)? В надежде, что в современных его версиях исходный код не претерпел сильных изменений, разве что регистры стали 32/64 битные.

    Кроме этого решения есть ещё предложение от магистра богословия Аллена Бичика с быстрой, но платной сортировкой строкового массива ($49 + $39 за комментарии).

    Прошу уважаемых форумчан поделиться идеями и опытом в быстрой сортировке строковых массивов.
     

    Вложения:

    • SORT (ASM).TXT
      Размер файла:
      16,7 КБ
      Просмотров:
      799
    Последнее редактирование: 23 фев 2017
  2. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    Несколько раз пришлось это перечитать.. что бы убедиться что я правильно прочитал :lol:

    > 50.000 Long - среднее время 8,72 мс (диапазон 0..31 мс)

    Это ничего не значит. Тайминг относительный. Так что это не профайл, а какое то значение, которое несчем связать.
     
  3. Эдуард

    Эдуард New Member

    Публикаций:
    0
    Регистрация:
    22 фев 2017
    Сообщения:
    5
    в развитие темы богословия: https://habrahabr.ru/post/201534/ :angel:
     
  4. shufps

    shufps New Member

    Публикаций:
    0
    Регистрация:
    13 дек 2016
    Сообщения:
    10
    Интересная тема, на самом деле можно быстрее.
    xchg - медленная инструкция, она еще и шину блокирует.
    рекурсия - источник бранч миссингов, лучше заменить на стек
    маленькие блоки сортировать лучше на месте вставками.
    PS могу выложить свою реализацию, но там полностью AT&T синтаксис.
     
    Эдуард нравится это.
  5. Эдуард

    Эдуард New Member

    Публикаций:
    0
    Регистрация:
    22 фев 2017
    Сообщения:
    5
    shufps, спасибо! Это хорошие предложения и они дали результат!
    заменил на XOR:
    Код (ASM):
    1.     xor  DWORD PTR [ecx],edx
    2.     xor  edx, DWORD PTR [ecx]
    3.     xor  DWORD PTR [ecx],edx
    4.  
    поправил, по сути вызовы call заменены на jmp. Подскажите, как могут проявить себя бранч миссинги? Зависание цикла? Неверный результат сортировки? AppCrash? Где-то читал, что есть вероятность их наступления порядка 5%, реально не сталкивался.
    Сообщаю результативность внесённых изменений по пунктам 1. и 2., предложенным shufps, : время работы алгоритма сократилось на 17,8%! В том числе:
    • 9,5% дало избавление от рекурсии (сохранение в стеке по сути уже было реализовано, экономия, я так понимаю, на сохранении 4 байт адреса возврата и одного из аргументов, который передавался в новый вызов без изменений)
    • 9,2% дало избавление от xchg
    Про маленькие блоки пока не думал, я так понимаю, Вы говорите уже про сортировку строкового массива?
    shufps, буду признателен, если поделитесь своей реализацией. AT&T синтаксис в большей степени похож на Intel, за исключением известных моментов, будем надеяться, разберёмся.
     
    Последнее редактирование: 27 фев 2017
    Mikl___ нравится это.
  6. shufps

    shufps New Member

    Публикаций:
    0
    Регистрация:
    13 дек 2016
    Сообщения:
    10
    Вот держи, с замерами и числом элементов :)
    Код (Text):
    1. .file "quicksort"
    2. .equ CUTOFF,16
    3. .equ UNROLL,CUTOFF - 1
    4. .equ ELEMENTS_COUNT,1000000
    5. .equ ELEMENT_SIZE,4
    6. .equ ARRAY_SIZES_IN_BYTES,ELEMENTS_COUNT*ELEMENT_SIZE
    7. .equ BOUNDS_SIZE, ELEMENTS_COUNT / 2 * 8
    8. .equ DIAPAZON,30000
    9. .equ MIN_DIAPAZON,-15000
    10.  
    11. PRINT_ARRAY = 0
    12. .bss
    13.     .lcomm my_array,ARRAY_SIZES_IN_BYTES
    14. .data
    15.     stack_begin:  .int 0
    16.     stack_top:    .int 0
    17.     my_frequency: .int 0,0
    18.     time_elapsed: .int 0,0
    19. .text
    20.     .global start
    21.         start:
    22.             push %ebp
    23.             mov %esp,%ebp
    24.     #;Инициализация значений для функций
    25.             mov $my_array,%ebx
    26.             mov $ARRAY_SIZES_IN_BYTES,%ecx
    27.             lea (%ebx,%ecx),%edx
    28.     #;Сохраняем адрес конца массива
    29.             push %edx
    30.     #;Заполняем массив случайными числами
    31.             push %edx
    32.             push %ebx
    33.             call fill_rand
    34.     #;Печать старых данных, если надо
    35.         .if PRINT_ARRAY
    36.             push (%esp)
    37.             push %ebx
    38.             call print_all
    39.         .endif
    40.     #;Инициализация таймера
    41.             call timer_init
    42.     #;Вызов быстрой сортировки
    43.             push (%esp)
    44.             push %ebx
    45.             call quick_sort
    46.     #;Получение прошедшего времени с момента вызова
    47.             call calc_time_and_print
    48.     #;Печать новых данных, если надо
    49.         .if PRINT_ARRAY
    50.             push (%esp)
    51.             push $my_array
    52.             call print_all
    53.         .endif
    54.             leave
    55.             ret
    56. #;No params
    57. calc_time_and_print:
    58.     push %ebp
    59.     mov %esp,%ebp
    60.     push time_elapsed+4
    61.     push time_elapsed
    62.     push $time_elapsed
    63.     call _QueryPerformanceCounter@4
    64.     mov time_elapsed,%eax
    65.     mov time_elapsed+4,%edx
    66.     sub (%esp),%eax
    67.     sbb 0x4(%esp),%edx
    68.     mov %eax,(%esp)
    69.     mov %edx,0x4(%esp)
    70.     fildq my_frequency
    71.     fildq (%esp)
    72.     fdivp
    73.     fstpl (%esp)
    74.     push $format_2
    75.     call _printf
    76.     leave
    77.     ret
    78. #;No params
    79. timer_init:
    80.     push %ebp
    81.     mov %esp,%ebp
    82.     push $my_frequency
    83.     call _QueryPerformanceFrequency@4
    84.     push $time_elapsed
    85.     call _QueryPerformanceCounter@4
    86.     leave
    87.     ret
    88. #;0x8(%ebp) - начальный адрес, 0xC(%ebp) - конечный адрес
    89. fill_rand:
    90.     push %ebp
    91.     mov %esp,%ebp
    92.     mov 0x8(%ebp),%ebx
    93.     mov 0xC(%ebp),%edi
    94.     sub %ebx,%edi
    95.     shr $2,%edi
    96.     xor %esi,%esi
    97.     push $0
    98.     call _time
    99.     push %eax
    100.     call _srand
    101.     my_fill_loop:
    102.         call _rand
    103.         xor %edx,%edx
    104.         mov $DIAPAZON,%ecx
    105.         div %ecx
    106.         add $MIN_DIAPAZON,%edx
    107.         mov %edx,(%ebx,%esi,4)
    108.         inc %esi
    109.         cmp %esi,%edi
    110.         jnz my_fill_loop
    111.     leave
    112.     ret $8
    113. #;0x8(%ebp) - начальный адрес, 0xC(%ebp) - конечный адрес
    114. print_all:
    115.     push %ebp
    116.     mov %esp,%ebp
    117.     mov 0x8(%ebp),%ebx
    118.     mov 0xC(%ebp),%edi
    119.     sub %ebx,%edi
    120.     shr $2,%edi
    121.     xor %esi,%esi
    122.     my_print_loop:
    123.         push (%ebx,%esi,4)
    124.         push $format_0
    125.         call _printf
    126.         add $8,%esp
    127.         inc %esi
    128.         cmp %esi,%edi
    129.         jnz my_print_loop
    130.     push $format_1
    131.     call _printf
    132.     add $4,%esp
    133.     leave
    134.     ret $8
    135. #;0x8(%esp) - начальный адрес ; 0xC(%esp) - конечный адрес
    136. .p2align 4,,
    137. quick_sort:
    138.     push %ebp
    139.     mov %esp,%ebp
    140. #;---------------Инициализация, создание точки опоры, занесение в стек начальных значений  
    141.     #;-----Записываем в регистр адрес начала и будующую точку опоры, проверяем если адреса равны - сортировка не нужна
    142.     mov 0x8(%esp),%esi
    143.     mov 0xC(%esp),%edi
    144.     sub $0x4,%edi
    145.     cmp %esi,%edi
    146.     jng end_sort
    147.     sub %esi,%edi
    148.     shr $2,%edi
    149.     #;Заносим первые две границы в стек
    150.     push %edi
    151.     push %esi
    152. #;---------------Цикл--------------------------
    153. .p2align 4,,
    154.     qs_loop:
    155.         cmp %ebp,%esp
    156.         jnl end_sort
    157.         pop %esi
    158.         pop %edi
    159.         mov %esi,0x8(%ebp)
    160.         mov %edi,0xC(%ebp)
    161.         mov %edi,%ebx
    162.         shr $1,%ebx
    163.         mov (%esi,%ebx,4),%edx
    164.         xor %ecx,%ecx
    165.         xor %eax,%eax
    166.         xor %ebx,%ebx
    167.     .p2align 4,,
    168.         left_branch:
    169.     .rep 8
    170.         .rep 16
    171.             cmp (%esi,%ecx,4),%edx
    172.             lea 0x1(%ecx),%ecx
    173.             jle 1f
    174.         .endr
    175.             jmp left_branch
    176.     .p2align 4,,
    177.         1:
    178.         .rep 16      
    179.             cmp (%esi,%edi,4),%edx
    180.             lea -0x1(%edi),%edi
    181.             jge 1f
    182.         .endr
    183.             jmp 1b
    184.     .p2align 4,,
    185.         1:
    186.             cmp %ecx,%edi
    187.             js split_bounds
    188.             mov -0x4(%esi,%ecx,4),%eax
    189.             mov 0x4(%esi,%edi,4),%ebx
    190.             mov %eax,0x4(%esi,%edi,4)
    191.             mov %ebx,-0x4(%esi,%ecx,4)
    192.     .endr
    193.             jmp left_branch
    194.     .p2align 4,,
    195.         split_bounds:
    196.             inc %edi
    197.             dec %ecx
    198.             test %edi,%edi
    199.             jz right_bound
    200.             xor %dh,%dh
    201.             jmp set_ret_address
    202.     .p2align 4,,
    203.         right_bound:
    204.             lea (%esi,%ecx,4),%esi
    205.             mov 0xC(%ebp),%edi
    206.             sub %ecx,%edi
    207.             jz qs_loop
    208.             mov $0x1,%dh
    209.             jmp set_ret_address
    210. .p2align 4,,
    211. end_sort:
    212.     pop %ebp
    213.     ret $8
    214.  
    215. .p2align 4,,
    216. insert_init:
    217.     push %ebp
    218.     push %ecx
    219.     push %edx
    220.     mov %esi,%ebx
    221.     mov %edi,%ebp
    222.     xor %eax,%eax
    223.     std
    224. .p2align 4,,
    225. insert_sort:
    226.     inc %eax
    227.     cmp %eax,%ebp
    228.     jl end_insert_sort
    229.     mov %eax,%ecx
    230.     lea (%ebx,%ecx,4),%edi
    231.     lea -0x4(%edi),%esi
    232.     mov (%edi),%edx
    233. .rep UNROLL
    234.     cmp (%esi),%edx
    235.     jge restore
    236.     movsd
    237.     dec %ecx
    238.     jz restore
    239. .endr
    240.  
    241. .p2align 4,,
    242. restore:
    243.     mov %edx,(%edi)
    244.     jmp insert_sort
    245. .p2align 4,,
    246. end_insert_sort:
    247.     cld
    248.     mov %ebx,%esi
    249.     pop %edx
    250.     pop %ecx
    251.     pop %ebp
    252.     test %dh,%dh
    253.     jnz qs_loop
    254.     jmp right_bound
    255.    
    256. .p2align 4,,
    257. stack_push:
    258.     push %edi
    259.     push %esi
    260.     test %dh,%dh
    261.     jnz qs_loop
    262.     jmp right_bound
    263.    
    264. .p2align 4,,
    265. set_ret_address:
    266.     cmp $CUTOFF,%edi
    267.     setl %dl
    268.     jl insert_init
    269.     jmp stack_push
    270.    
    271. format_0: .asciz "%d "
    272. format_1: .asciz "\n\n"
    273. format_2: .asciz "Time elapsed: %f\n"  
    Все верно - рекурсию заменяем на итерации цикла, на каждой итерации проверяем, есть ли еще половинки (разница между esp и ebp), адреса половинок пушатся в стек в том случае, если они достаточно велики, если маленькие (я например беру размер линии кэша) то сортируем на месте вставками. В среднем 1-млн dword-ов сортируются от 45-60 мс на моей машине. Ну, если вкратце в процессорах имеется апаратное устройство - предсказатель переходов, он достаточно хорошо предсказывает переходы, при некоторых условиях, в общем у него специальные алгоритмы предсказания, которые используют аппаратные буфферы (BTB и буффер стека), при большой глубине рекурсии - очень велики возникновения миссов (лучше почитать статьи у Agner Fog у него это все подробно описывается, Мики уже тут переводы выкладывал). Смысл в том, что, если предсказатель ошибется - то произойдет сброс конвейера равный его глубине (от 12 и выше стадий на современных процессорах), всю работу (выборка,декодирование,исполнение,отставка инструкций) придется выполнять заново - уже по правильной ветке.
     
    Mikl___ и rococo795 нравится это.
  7. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    shufps

    Не разбирался в вашем примере, но судя по коментам вы память заполняете - тогда она должна быть заранее закреплена в рабочем наборе, иначе тест такой будет не корректен, так как тайминг подкачки большой. Аллокация памяти не приводит к её физическому выделению.
    И зачем счётчики через апи запрашивать, это же rdtsc :mda:

    Предсказание ветвлений етц это весьма отрешённый механизм, не забывайте что вы не в реалтайме это тестите. После того, как прерывание возникнет, а они возникают очень часто, эта фича будет смысла не иметь, поэтому это врядле как то скажется на профайле.
     
    shufps нравится это.
  8. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.076
    за сортировку строк не скажу, а вот с числами игрался https://sourceforge.net/projects/fsort--no-if/ но разобраться в ней будет нелегко: стругал я её для линя х64 + некоторые косяки с выделением памяти имеются :)
     
  9. Эдуард

    Эдуард New Member

    Публикаций:
    0
    Регистрация:
    22 фев 2017
    Сообщения:
    5
    shufps, спасибо за пример! Читается легко. Интересная реализация небольших вставок - может пригодиться при сортировке строкового массива.

    Вопросы по коду, для понимания:
    можно упростить до lea (%esi,%edi,2),%edx ?
    пропали буквы у меток, предполагаю, что первая - 1b, вторая - 1f
    а может, вместо цикла, сразу вычислить количество элементов массива между адресами, хранящимися в %esi и %edx? например,
    Код (ASM):
    1. mov %edx, %ecx
    2. sub %esi, %ecx
    3. shr $2, ecx
    Пока Indy_, не успел поругаться, что мы сравниваем таймы, скажу - превосходный результат! На моей порядка 92 мс.

    UbIvItS, исходник не скачался, но замеры (которые по ссылке) - чрезвычайно медленные, в разы. Присмотритесь к алгоритму shufps.
     
    Последнее редактирование: 28 фев 2017
  10. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.076
    они не могут быть медленней, пч написаны под х64 + использованы векторные регистры, а у обычных х86 кодов кол-во обращений к озу слишком велико из-за малого набора доступных регистров. замеры же я делал на сравнительно больших массивах против стандартной qsort. сначала не хотел париться и всё на сях прописать, но, посмотрев Асм аутпут компиля, стало понятно, что сяхи не есмь хороший вариант. ещё один момент -- это алго пивота, тут имеются определённые шероховатости == быстрый приводит к слишком большим отклонениям от реал. центра.

    ЗЫ.. делал я и под х86 тоже с векторными регами.. найду -- скину.
     

    Вложения:

  11. shufps

    shufps New Member

    Публикаций:
    0
    Регистрация:
    13 дек 2016
    Сообщения:
    10
    Это высчитывание pivot точки, то есть в ebx содержится уполовиненый индекс - затем берется значение из построенного эффективного адреса. Упрощение - даст неверный эффективный адрес.
    Тут все нормально.Это временные метки в GAS, они существуют пока не встретится та же метка, которая ее переопределит. 1b и 1f - это указание собственно метки + f/b(forward/back, куда прыгать назад или вперед).
    Можно все намного упростить, например не использовать базово-индексную адресацию (они кстати больше МОП-ов генерируют), а просто использовать адреса и смещения их же и "зашивать" в стек. Думаю немного оптимизировать, тут еще и разворот несовсем технически правильно сделан. Что еще можно попробовать:
    В некоторых статьях говорилось, что опорная точка должна браться рандомно в пределах границ текущего сортируемого блока, в принципе это логично, если мы попадаем на максимальное/минмимальное значение, то это целый ряд неэффективных сравнений одной из половин.
    Собственно по совету UbIvItS можно использовать векторные инструкции и регистры, но это придется полностью переделывать алгоритм, но они гарантировано дадут очень мощный профит.
    Туда же, использовать инструкции типа movntdq - запись в обход кэша.
    Попробовать использовать многопоточность, без мьютексов.
     
    Эдуард нравится это.
  12. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.076
    про мощный тут не столь однозначная ситуация -- со всеми извратами я получил прирост в районе 7% против стандартной qsort, а извращался я сильно вплоть до полиморфа :)))
     
  13. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.076
    все извраты более-менее профитны на сравнительно больших массивах, а ниже определённой отметки весь профит кушает оверхед той иль иной методы. по идее, тут стоит писать несколько различных алгосов с прицелом, к примеру, на размер массива.
     
  14. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    shufps

    > Туда же, использовать инструкции типа movntdq - запись в обход кэша.

    Видимо что бы тесты по профайлу выполнять, нужно всё в целом понимать. Отдельная NPX-итерация производительна(MMX etc). Но, ось опять же не реалтайм. Если эти блоки поток не юзает, то не выполняется их перезагрузка. А это одна из самых тяжёлых по таймингу операций. Причём если хоть один раз выполнено обращение к NPX-блоку, то перезагрузка NPX-фрейма будет выполняться многократно в течении кванта времени потока("delayed-npx"). Соответственно задержка из за перезагрузок фрейма будет много больше, чем профайл от самих элементарных операций. И за время, когда поток миллионы раз свопнется и соотвественно будут перезагрузки контекста математики он в десятки или сотни раз времени потеряет больше, чем без юзания данных блоков.

    Это всё теневая работа оси, без учёта которой результат тестов - просто рандом.
     
    shufps нравится это.
  15. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.076
    Indy_, ох, да тут от всего зависит == от оси, от проца, от текущей загрузки проца другими задачами. Однако, сравнивая алгосы друг против друга, ты можешь получать средние значения по тестам и они будут вполне объективны.
     
  16. shufps

    shufps New Member

    Публикаций:
    0
    Регистрация:
    13 дек 2016
    Сообщения:
    10
    Эх... даже гугл не знает, что это такое. Казалось бы итак сложно, но винда еще больше усложняет. Пока мой код дойдет до кэша инструкций пройдет хз сколько времени, он же еще будет конкурировать с другими данными/кодесами. С ностальгией вспоминаю Win95, как же там все быстро работало для своего времени железа.
     
  17. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    shufps

    Что не знает гугл ?
    Numeric Processor eXtension" это контекст математики, а как и любой контекст перезагружается. Весь набор этих экзотических" инструкций обьединён в один блок математики, который перезагружается через fxsave. Вы потестите профайл данной инструкции. И не забывайте есчо про рабочий набор и шедулер. Ну а потом можно прикинуть вообще смысл снятия профайла в мультизадачной оси.
    ps: ну и нужно помнить, что если что то не вызывается напрямую, это не значит что оно не вызывается..
     
  18. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.076
    а с другой стороны, какая разница -- если параллельно пашут процессы, кои тормозят твой код == выруби их. с оптимизацией выни, конечно, сложней, чем с линем.
     
  19. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS

    Да, можно повысить приоритет/аффинитет или какие то есчо теневые" свойства и предыдущие тесты по профайлу окажутся бессмысленными.. сколько миллисекунд говорите :preved:
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.076
    в лине легче: весь левач можно выкинуть, а в случае необходимости -- можно пересобрать крит. либы. в выне же приходится укладывать свои решения в данный набор шаблонов. Поэтому про бессмысленность профайла согласен лишь относительно выни.