Оптимизация подсчёта количества строк в файле

AMD64: 9,8 млн. тактов. PM: 9.7 млн.

 

Лидер снова с вами. Можете не вставать.
Опупеть, IceStudent меня удалил, шалунишка.
Зря вы Miller Rabinа не восприняли всерьез. Он тему толкает в правильном направлении.
Следующий алгоритм в 2 раза быстрее перечисленных выше.
Я не стал оптимизировать команды сами прооптимизируете.

Код (Text):

1. xor ebx,ebx
2. xor edx,edx
3. MOVdqa xmm1,dqword [цифры0a]
4. MOVdqa xmm2,dqword [цифрыff]
5. pxor xmm3,xmm3
6. pxor xmm4,xmm4
7. pxor xmm6,xmm6
8. pxor xmm7,xmm7
9. mov edi,УказательНаТекстовыйФайл
10. mov ecx,[dwSize]
11. shr ecx,4
12. add ecx,1
13. Цикл :MOVdqa xmm0,dqword [edi]
14. pcmpeqb xmm0, xmm1
15. psubb xmm4, xmm0
16. add edi,16
17. MOVdqa xmm5,xmm4
18. pcmpeqb xmm5, xmm2
19. pmovmskb eax,xmm5
20. cmp eax,0
21. loopz Цикл
22. jecxz Итог
23. pxor  xmm4,xmm5
24. psubb xmm6, xmm5
25. MOVdqa xmm5,xmm6
26. pcmpeqb xmm5, xmm2
27. pmovmskb eax,xmm5
28. cmp eax,0
29. jne Переполнение2
30. jmp Цикл
31. Переполнение2:
32. pxor  xmm6,xmm5
33. psubb xmm7, xmm5
34. jmp Цикл
35.  
36. Итог:MOVdqa dqword [цифры0a],xmm4
37. mov cl,16
38. СуммированиеЕдениц:movzx eax,byte[(цифры0a-1)+ecx]
39. add ebx,eax
40. sub ecx,1
41. jne СуммированиеЕдениц
42. MOVdqa dqword [цифры0a],xmm6
43. mov cl,16
44. mov esi,$ff
45. Суммирование1хМножителей:movzx eax,byte[(цифры0a-1)+ecx]
46. mul esi
47. add ebx,eax
48. sub ecx,1
49. jne Суммирование1хМножителей
50. MOVdqa dqword [цифры0a],xmm7
51. mov cl,16
52. mov esi,$fe01
53. Суммирование2хМножителей:movzx eax,byte[(цифры0a-1)+ecx]
54. mul esi
55. add ebx,eax
56. sub ecx,1
57. jne Суммирование2хМножителей
58. __________________________________________________________
59. цифры0a:  times 16 db $a
60. цифрыff:  times 16 db $ff
61. УказательНаТекстовыйФайл file 'numbers.dic'
62. dwSize dd $-УказательНаТекстовыйФайл

 

гы. lzebars не удаляйте пожалуйста студента он хорощий =))))

 

lzebars
Приведи результаты теста.

 

>> здесь ограничивающим фактором является скорость чтения данных из ОЗУ, т.к. файл в ~8Мб ни в какой кэш не влезает

здравая мысль... а еще посчитать время чтения файла с диска... :Р

>> Лидер снова с вами. Можете не вставать.

да да... вставать рано... пока нет ни одного решения поставленной задачи

 

Посчитать все можно, но в предлагаемом варианте теста время чтения с диска не учитывается, а вот ограниченная скорость чтения 8Mб данных из ОЗУ нивелирует разницу в методах. Поэтому если уж соревноваться в суперскоростях, то на объемах в несколько сот Кб, чтобы данные после первого прохода сидели в кэше. Наверняка великий Izebars свои 2 раза получает на малом объеме буфера или в своем богатом воображении, а на 8Мб хоть в лепешку расшибись, а меньше 8 млн.тиков не получишь )

 

Здарова, черти, я ваш чертопас.

doctor_Ice

Ладно, так и быть. Он пока ещё форуму не надоел.

IceStudent
согласен ли ты с выводом leo что меньше 8000000 тиков не получишь?

Чтобы ты опять написал "Абсолютно" или "Восхитительно". Всем и так ясно, что у меня круче и никакой чебурек не сможет мне противостоять.

 

Горбатого могила исправит :-\

 

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

Код (Text):

1. ;==================================================================
2. format      PE GUI 4.0
3. entry       start
4. ;==================================================================
5. include 'win32a.inc'
6. ;==================================================================
7.                         ; В А Ш И   Д А Н Н Ы Е
8.  
9. цифры0a:  times 16 db $a
10. цифрыff:  times 16 db $ff
11. УказательНаТекстовыйФайл file 'numbers.dic'
12. dwSize dd $-УказательНаТекстовыйФайл
13. ;++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
14.  
15. buf rb 1024
16. ptr equ
17. offset equ
18.  
19. ;++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
20. iter        =       10           ; кол-во проходов testing:
21. ;==================================================================
22. section     '.test' code readable writeable executable
23. ;++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
24. tics        dq      0
25. overhead    dd      0
26. counter     dd      0
27. resultlist  rq      iter
28. templist    rb      iter*10+2
29. message     rb      iter*26+1+64
30. caption     rb      64
31. lpfmtave    db      13,10,'average:',13,10
32. lpfmtm      db      '%.8X%.8X%.8X',13,10,0
33. lpfmtc      db      '%u bytes , %u passes',0
34.  
35. ;==================================================================
36. align       1024
37. ;==================================================================
38. start:
39. ; ==================================
40. ;   Initialization  
41. ; ==================================
42.  
43. ;--------------------------------------------------------------------------------
44.     invoke  GetCurrentProcess
45.     invoke  SetPriorityClass,eax,REALTIME_PRIORITY_CLASS
46. ;==================================================================
47.     mov ebp,5
48. @@:
49.     xor eax,eax
50.     cpuid
51.     rdtsc
52.     mov dword [tics],eax
53.     mov dword [tics+4],edx
54.     xor eax,eax
55.     cpuid
56.     xor eax,eax
57.     cpuid
58.     rdtsc
59.     sub eax,dword [tics]
60.     mov [overhead],eax
61.     dec ebp
62.     jnz @B
63. ;==================================================================
64. ;                                          цикл проходов (итераций)
65. ;==================================================================
66. align       16
67. testloop:   xor     eax,eax
68.         cpuid
69.         rdtsc
70.         mov     dword [tics],eax
71.         mov     dword [tics+4],edx
72.         xor     eax,eax
73.         cpuid
74. ;==================================================================
75. testing:          ; Т Е С Т И Р У Е М Ы Е   И Н С Т Р У К Ц И И
76. ;++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
77. xor ebx,ebx
78. xor edx,edx
79. MOVdqa xmm1,dqword [цифры0a]
80. MOVdqa xmm2,dqword [цифрыff]
81. pxor xmm3,xmm3
82. pxor xmm4,xmm4
83. pxor xmm6,xmm6
84. pxor xmm7,xmm7
85. mov edi,УказательНаТекстовыйФайл
86. mov ecx,[dwSize]
87. shr ecx,4
88. add ecx,1
89. Цикл :MOVdqa xmm0,dqword [edi]
90. pcmpeqb xmm0, xmm1
91. psubb xmm4, xmm0
92. add edi,16
93. MOVdqa xmm5,xmm4
94. pcmpeqb xmm5, xmm2
95. pmovmskb eax,xmm5
96. cmp eax,0
97. loopz Цикл
98. jecxz Итог
99. pxor  xmm4,xmm5
100. psubb xmm6, xmm5
101. MOVdqa xmm5,xmm6
102. pcmpeqb xmm5, xmm2
103. pmovmskb eax,xmm5
104. cmp eax,0
105. jne Переполнение2
106. jmp Цикл
107. Переполнение2:
108. pxor  xmm6,xmm5
109. psubb xmm7, xmm5
110. jmp Цикл
111.  
112. Итог:MOVdqa dqword [цифры0a],xmm4
113. mov cl,16
114. СуммированиеЕдениц:movzx eax,byte[(цифры0a-1)+ecx]
115. add ebx,eax
116. sub ecx,1
117. jne СуммированиеЕдениц
118. MOVdqa dqword [цифры0a],xmm6
119. mov cl,16
120. mov esi,$ff
121. Суммирование1хМножителей:movzx eax,byte[(цифры0a-1)+ecx]
122. mul esi
123. add ebx,eax
124. sub ecx,1
125. jne Суммирование1хМножителей
126. MOVdqa dqword [цифры0a],xmm7
127. mov cl,16
128. mov esi,$fe01
129. Суммирование2хМножителей:movzx eax,byte[(цифры0a-1)+ecx]
130. mul esi
131. add ebx,eax
132. sub ecx,1
133. jne Суммирование2хМножителей
134. ;++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
135. testsize    =       $-testing     ; К О Н Е Ц   И Н С Т Р У К Ц И Й
136. ;==================================================================
137.         xor     eax,eax
138.         cpuid
139.         rdtsc
140.         mov     ebp,[counter]
141.         mov     dword [resultlist+ebp],eax
142.         mov     dword [resultlist+ebp+4],edx
143.         xor     eax,eax
144.         cpuid
145.         mov     eax,dword [tics]
146.         mov     edx,dword [tics+4]
147.         add     eax,[overhead]
148.         adc     edx,0
149.         sub     dword [resultlist+ebp],eax
150.         sbb     dword [resultlist+ebp+4],edx
151.         add     ebp,8
152.         mov     [counter],ebp
153.         cmp     ebp,iter * 8
154.         jb      testloop
155. ;==================================================================
156. ;                                                 вывод результатов
157. ;==================================================================
158.         invoke  GetCurrentProcess
159.         invoke  SetPriorityClass,eax,NORMAL_PRIORITY_CLASS
160. ;==================================================================
161.         finit
162.         mov     esi,resultlist
163.         mov     ebp,templist
164.         mov     edi,message
165. align 4
166. @@:     fild    qword [esi]
167.         fabs
168.         fbstp   [ebp]
169.         cinvoke  wsprintf,edi,lpfmtm,[ebp+8],[ebp+4],[ebp]
170.         add     esi,8
171.         add     ebp,10
172.         add     edi,eax
173.         sub     [counter],8
174.         jnz     @B
175. ; average
176.         mov     esi,resultlist
177.         mov     ebp,templist
178.         mov     [counter],iter
179.         fldz
180.         fild    dword[counter]
181.         fldz
182. align 4
183. @@:
184.         fild    qword[esi]
185.         fabs
186.         faddp
187.         add     esi,8
188.         sub     [counter],1
189.         jnz     @B
190.  
191.         fdiv    st0,st1
192.         frndint
193.         fbstp   [ebp]
194.         fstp    qword[ebp+8]
195.         fstp    qword[ebp+8]
196.         cinvoke wsprintf,edi,lpfmtave,[ebp+8],[ebp+4],[ebp]
197.        
198.         cinvoke  wsprintf,caption,lpfmtc,testsize,iter
199.         invoke  MessageBox,0,message,caption,MB_ICONINFORMATION
200.         finit
201.  
202. ; ==================================
203. ;   Finalization  
204. ; ==================================
205.     ;invoke VirtualFree,[pMem],0,MEM_RELEASE
206.     ;invoke CloseHandle,[hFile]
207.  
208.  
209. ;--------------------------------------------------------------------------------
210.     invoke  ExitProcess,0
211. ;==================================================================
212. section '.idata' import data readable writeable
213.   library kernel32,'KERNEL32.DLL',\
214.       user32,'USER32.DLL'
215.  
216.   include 'apia\kernel32.inc'
217.   include 'apia\user32.inc'
218. ;==================================================================

EBX = Количество строк

 

Leo я понимаю тебя что основным ограничивающим фактором является скорость чтения из памяти.
Только вот узким местом в наших программах пока является отнюдь не скорость памяти, а логика процесора
До момента когда я упрусь в ограничение по скорости считывания из памяти я пока не дорос
MMX я использую не из-за того что там, типа, регистры большие. Просто я хочу попробовать применить арифметику с насыщением на данной задаче. Основной же проблемой моего алогритма был контроль переполнений вордов в регистре подсчета строк. Мне очень понравилось как решил эту проблему ты, предлагая обрабатывать данные поблочно. тем самым можно вынести контроль переполнения из главного цикла в дополнительный. Вот код, который использует эту идею для MMX

Код (Text):

1. proc CountLine Buffer, Length
2.     local CountLine: DWORD, Result: QWORD
3.     mov esi, 8
4.     xor ecx, ecx
5.     mov [CountLine], ecx
6.     mov ecx, 0E00h
7.     movd mm7, ecx
8.     pshufw mm7, mm7, 0
9.     pxor mm6, mm6
10.     pxor mm3, mm3
11.     mov eax, [Buffer]
12.     mov ecx, [Length]
13.     jmp .lbBlock
14.  
15. align 16
16.  
17. .lbCheck:
18.     movq mm0, [eax+edx]         ;mm0 - Строка файла
19.     psubusw mm0, mm7                ;mm1 - Временный регистр
20.     add edx, esi
21.     pcmpeqw mm0, mm6                ;mm2 - Временный регистр
22.     psubw mm1, mm0                  ;mm3 - Количество строк
23.     js .lbCheck                         ;mm4 - неиспользуется
24.  
25. .lbBlock:                                   ;mm5 - неиспользуется    
26.     movq mm2, mm1                    ;mm6 - 0                
27.     punpckhwd mm1,mm6               ;mm7 - 0E000E000E000E00h
28.     paddd mm3,mm1
29.     punpcklwd mm2,mm6
30.     paddd mm3,mm2
31.     pxor mm1, mm1
32.     mov edx, 262144
33.     cmp ecx, edx
34.     cmovc edx, ecx
35.     sub ecx, edx
36.     add eax, edx
37.     neg edx
38.     jne .lbCheck
39.  
40.     movq [Result], mm3
41.     mov eax, DWORD [Result]
42.     add eax, DWORD [Result+4]
43. ret
44. endp

 

130 Bytes 10 Passes
...
Average 7560554

 

Я прекрасно понимаю, что данный алгоритм не совершенен.
Так как все символы меньшие чем 0Dh попадают под конец строки.
и хоть на файле Numbers.txt это дает правильный результат, на файлах, которые активно используют управляющие символы, результат будет неверным. Уникодные файлы также не будут корректно обрабатываться.
И я пытаюсь найти такую логическую последовательность, которая будет выполняться также быстро и давать максимально корректный результат, изучая особенности команд и выши алгоритмы.
Но даже данный код показывает, что расти есть куда.

 

Хорошо, что ты прекрасно понимаешь, что ты сам себя дисквалифицировал.
Мой алгоритм с любыми текстовым файлом работает корректно.
210 Bytes 10 Passes
...
Average 7595046
Но мне все равно кажется, что из всех выше, только ты сможешь ещё, как-то тягаться со мной. Так что с удовольствием ждем твоего правильного кода.

 

Miller Rabin

Чушь несусветная ) Для начала перечитай пост #11. Затем загляни в IA-32 Optimization или в instruction_tables.pdf А.Фога и убедись, что все твои MMX-инструкции имеют имеют латентность = 2 тика (кроме movq) и throughput = 1 тик. Число мопов во внутреннем цикле = 6, значит грузятся они за 2 такта и скорость фетчем и ретайрментом не ограничивается. Дальше movq, add, jcc MMX-ам не мешают, т.к. идут в другие порты и значит работают в параллель. Остается цепочка из 3-х MMX по два такта - уже не больше 6 тактов, а реально доставка мопов идет быстрее, поэтому соседние циклы должны перекрываться и в итоге скорость должна быть на уровне 3-4 тактов на qword = 8 байт, т.е. лучше 0.5 такта в пересчете на байт данных. А у тебя с многоликим ??eBars'ом ( получается ~7.6млн на 7.9Мб, т.е. вдвое хуже.
Поэтому перестаньте заниматься ерундой и мерять скорость ОЗУ и чипсета - просто задай Length например 100*1000 (сразу видны такты на байт) или 80*1000 (такты на qword) и получишь реальную скорость "логики процесора". У меня на P4 твой код дает ~0.48 такта на байт, т.е. менее 4-х тактов на qword - в полном соответствии с "теорией"

 

IceStudent

Оперативно

 

Короче насчет ерунды.
Я замерил то количество которое мой процессор тратит на то, чтобы просто считать файл по размеру равный numbers.txt из оперативной памяти.
Получилось 5.2 млн тиков это предел. Быстрее уже не выйдет.
Но тем не менее это не твои 8мл тиков.

Код (Text):

1.    mov esi, 16
2.    mov ecx, 00FF00FFh
3.    movd xmm7, ecx
4.    shufps xmm7, xmm7, 0
5.     mov ecx, 00F600F6h
6.     movd xmm6, ecx
7.     shufps xmm6, xmm6, 0
8.     mov ecx, 01030103h
9.     movd xmm5, ecx
10.     shufps xmm5, xmm5, 0
11.         pxor xmm4, xmm4
12.     pxor xmm3, xmm3
13.     pxor xmm1, xmm1
14.     mov eax, [Buffer]
15.     mov ecx, [MemSize]
16.     add eax, 15
17.     and eax, -16
18.     add ecx, 15
19.     and ecx, -16
20.     jmp .lbBlock
21.  
22. align 16
23.  
24. .lbCheck:
25.     movdqa xmm0, [eax+edx]
26.     pand xmm0, xmm7
27.     paddw xmm0, xmm6
28.     psubusb xmm0, xmm5
29.     pcmpeqw xmm0, xmm4
30.     add edx, esi
31.     psubw xmm1, xmm0
32.     js .lbCheck        
33.  
34. .lbBlock:                  
35.     movdqa xmm2, xmm1
36.     punpckhwd xmm1,xmm4
37.     paddd xmm3,xmm1
38.     punpcklwd xmm2,xmm4
39.     paddd xmm3,xmm2
40.     pxor xmm1, xmm1
41.     mov edx, 262144
42.     cmp ecx, edx
43.     cmovc edx, ecx
44.     sub ecx, edx
45.     add eax, edx
46.     neg edx
47.     jne .lbCheck
48.  
49.     movdqa DQWORD [.Result], xmm3
50.     mov eax, DWORD [.Result]
51.     add eax, DWORD [.Result+4]
52.     add eax, DWORD [.Result+8]
53.     add eax, DWORD [.Result+12]

Данный код работает корректно. С любыми файлами.

193 Bytes 10 Passes
Average 6557932

Вот так.

оформляем код тегом [ code ]

 

Мой предыдущий алгоритм который ищет все символы меньшие OD, только портированный на SSE
выполняется за 5,4 млн тиков что и соответствует моему пределу.

Код (Text):

1.  
2.     mov esi, 16
3.     mov ecx, 0E000E00h
4.     movd xmm7, ecx
5.     pshufd xmm7, xmm7, 0
6.     pxor xmm6, xmm6
7.     pxor xmm3, xmm3
8.     mov eax, [Buffer]
9.     mov ecx, [MemSize]
10.     add eax, 15
11.     and eax, -16
12.     add ecx, 15
13.     and ecx, -16
14.     jmp .lbBlock
15.  
16. align 16
17.  
18. .lbCheck:
19.     movdqa xmm0, [eax+edx]
20.     psubusw xmm0, xmm7
21.     add edx, esi
22.     pcmpeqw xmm0, xmm6
23.     ]psubw xmm1, xmm0
24.     js .lbCheck        
25.  
26. .lbBlock:                  
27.     movdqa xmm2, xmm1  
28.     punpckhwd xmm1,xmm6
29.     paddd xmm3,xmm1
30.     punpcklwd xmm2,xmm6
31.     paddd xmm3,xmm2
32.     pxor xmm1, xmm1
33.     mov edx, 262144
34.     cmp ecx, edx
35.     cmovc edx, ecx
36.     sub ecx, edx
37.     add eax, edx
38.     neg edx
39.     jne .lbCheck
40.  
41.     movdqa DQWORD [Result], xmm3
42.     mov eax, DWORD [Result]
43.     add eax, DWORD [Result+4]
44.     add eax, DWORD [Result+8]
45.     add eax, DWORD [Result+12]

141 Bytes 10 Passes
average 5653237

Жаль только, что в данном алгоритме под конец строки попадает все, что меньше 0D
Но я уверен что решение выполняющее данную задачу более корректно и за то же время есть.
Вобщем LEO иди ка ты сам почитай что-нибудь. Твои теоретические выкладки не соответствуют практическим результатам

Я привел вам два кода. Первый для IzeBars, который корректно решает поставленную задачу за более короткое время. И правильно работает со всеми файлами.
А второй для Leo, который действительно демонстрирует предел скорости ОЗУ на больших файлах

Я всегда ставил под сомнение свой профессионализм.
А теперь я ставлю под сомнение ваш

 

Miller Rabin =? **eBars

 

Та вроде нет.

 

Miller Rabin

Насчет манер пожалуй промолчу и просто попробую вталдычить еще раз
Возможно твой проффесионализм придет в недоумение или возмущение, но у меня все три твоих последних варианта дают примерно одно и тоже ~9-9.5 млн (тот "который корректно решает поставленную задачу за более короткое время" получается чуть хуже и через раз выдает ~10 млн). Причина ясна как божий день - проц P4 3.2ГГц, память DDR400 = PC3200, т.е. теретически из нее скорость больше 3.2Гб/с или 3.2/3.2 = 1 байт за такт ЦПУ не выжмешь и поэтому время загрузки 7.9 Mб numbers.dic никак не может быть меньше 8 млн тактов, а реально процентов на 10-15 хуже из-за накладных расходов на инициализацию чтения пакетов (+ прочие штучки, связанные с переполнением очередей ожидающих мопов). То, что тебе удалось "установить рекорд" в ~5.5 млн, говорит лишь о том, что у тебя ОЗУ почти вдвое быстрее - значит у тебя тачка круче, а значит ты и сам крутой профессионал и можешь "ставить под сомнение" тех, у кого результы этого дурного теста колом стоят на отметке 8-10 млн или даже на 30 млн. Но ведь мы крутые, нам даже все посты топика некогда почитать, чтобы не натыкаться на уже пройденные грабли

Об этом можно будет говорить, если ты наконец бросишь амбиции и соизволишь перед тестом вызвать mov [Length или MemSize],100*1000 и для своего предыдущего MMX-алгоритма получишь результаты, сильно отличающиеся от 48 тыс. (на P4). А также как профессионал объяснишь по каким таким причинам у тебя при увеличении размера в 79 раз (со 100Кб до 7.9Мб) время выполнения увеливается в ~157 раз (с 48 тыс. до 7.5 млн)