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

Про быструю сортировку

ОГРОМНАЯ благодарность 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 за комментарии).

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

 

Несколько раз пришлось это перечитать.. что бы убедиться что я правильно прочитал :lol:

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

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

 

в развитие темы богословия: https://habrahabr.ru/post/201534/

 

Интересная тема, на самом деле можно быстрее.
xchg - медленная инструкция, она еще и шину блокирует.
рекурсия - источник бранч миссингов, лучше заменить на стек
маленькие блоки сортировать лучше на месте вставками.
PS могу выложить свою реализацию, но там полностью AT&T синтаксис.

 

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, за исключением известных моментов, будем надеяться, разберёмся.

 

Вот держи, с замерами и числом элементов

Код (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 и выше стадий на современных процессорах), всю работу (выборка,декодирование,исполнение,отставка инструкций) придется выполнять заново - уже по правильной ветке.

 

shufps

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

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

 

за сортировку строк не скажу, а вот с числами игрался https://sourceforge.net/projects/fsort--no-if/ но разобраться в ней будет нелегко: стругал я её для линя х64 + некоторые косяки с выделением памяти имеются

 

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.

 

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

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

 

Это высчитывание pivot точки, то есть в ebx содержится уполовиненый индекс - затем берется значение из построенного эффективного адреса. Упрощение - даст неверный эффективный адрес.

Тут все нормально.Это временные метки в GAS, они существуют пока не встретится та же метка, которая ее переопределит. 1b и 1f - это указание собственно метки + f/b(forward/back, куда прыгать назад или вперед).

Можно все намного упростить, например не использовать базово-индексную адресацию (они кстати больше МОП-ов генерируют), а просто использовать адреса и смещения их же и "зашивать" в стек. Думаю немного оптимизировать, тут еще и разворот несовсем технически правильно сделан. Что еще можно попробовать:
В некоторых статьях говорилось, что опорная точка должна браться рандомно в пределах границ текущего сортируемого блока, в принципе это логично, если мы попадаем на максимальное/минмимальное значение, то это целый ряд неэффективных сравнений одной из половин.
Собственно по совету UbIvItS можно использовать векторные инструкции и регистры, но это придется полностью переделывать алгоритм, но они гарантировано дадут очень мощный профит.
Туда же, использовать инструкции типа movntdq - запись в обход кэша.
Попробовать использовать многопоточность, без мьютексов.

 

про мощный тут не столь однозначная ситуация -- со всеми извратами я получил прирост в районе 7% против стандартной qsort, а извращался я сильно вплоть до полиморфа ))

 

все извраты более-менее профитны на сравнительно больших массивах, а ниже определённой отметки весь профит кушает оверхед той иль иной методы. по идее, тут стоит писать несколько различных алгосов с прицелом, к примеру, на размер массива.

 

shufps

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

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

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

 

Indy_, ох, да тут от всего зависит == от оси, от проца, от текущей загрузки проца другими задачами. Однако, сравнивая алгосы друг против друга, ты можешь получать средние значения по тестам и они будут вполне объективны.

 

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

 

shufps

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

 

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

 

UbIvItS

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

 

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