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

модераторы замутите пожалста какуюнибудь систему медалей. и дайте izebars'у самую главную =)

 

Black_mirror
А как он возвращает число?

 

Через EAX.

 

izebars
Не вдаваясь в низкопробные пререкания, просто вывешиваю файл, которым тестил твой код когда писал #30
Можешь найти в нём строку === Собственно алгоритм поиска === и убедиться, что подсчёт строк там по твоему алгоритму
Открой им свой любой .txt и сравни количество строк возвращаемое твоим кодом с тем что показывает любой текстовый редактор Особенно попробуй посчитать строки в самом *.asm файле (на большом литературном тексте ошибка меньше, но всё равно достаточно заметная)

doctor_Ice
Не тянет izebars на медальку - апломбу много, Дзену мало.

 

Ну.. Можно, конечно, вырезать из картошки.

Он дисквалифицирован

Black_mirror
Неа. Бряк на ret

<вырезано>

 

IceStudent

- это маскировка, бряк нужно на ret 8 ставить.

 

Y_Mur
Циц
IceStudent
А ты продолжай, продолжай, вырезай

Код (Text):

1. mov esi,УказательНаТекстовыйФайл
2.  mov ecx,[dwSize]
3.   shr ecx,3           ;*
4.   xor edx,edx
5.   xor ebx,ebx
6. Цикл1:mov eax,[esi]  ;**
7.   sub eax,0a000a00h
8.   sub eax,04000000h
9.   adc edx,ebx
10.   sub ah,04h
11.   adc edx,ebx
12.   mov eax,[esi+4]
13.   add esi,8
14.   sub eax,0a000a00h
15.   sub eax,04000000h
16.   adc edx,ebx
17.   sub ah,04h
18.   adc edx,ebx
19.   sub ecx, 1
20.   jnz Цикл1

чё не понятно чтоли что тогда я сделал для обычного текста без всяких шестнадцатеричных вставок типа 09h которая не имеет символа. cresta кстати также это игнорировал
Но хорошо что заметили. Поэтому этот побыстрее будет и у уж точно по точнее.

 

Black_mirror
А.. Не разобрался. Из-за данных OllyDbg неправильно дизасмил и я бряк не туда ставил. Получалось после обнуления еах в wintest.

Код (Text):

1. [b]Black_mirror[/b]
2. ---------------------------
3. 211 bytes , 10 passes
4. ---------------------------
5. 000000000000000008887048
6. 000000000000000009008464
7. 000000000000000008354613
8. 000000000000000008918087
9. 000000000000000009003194
10. 000000000000000008325055
11. 000000000000000008349563
12. 000000000000000008985926
13. 000000000000000008235351
14. 000000000000000008967765
15.  
16. average:
17. 000000000000000008703507
18.  
19. [b]izebars[/b]
20. average:
21. 000000000000000009228272

Добавил в wintest подсчёт среднего значения.

 

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

 

IceStudent
Ты чета тавось. значит у меня полностью тестировал, а у Black_mirror только цикл.
Я не просто так поставил звездочки в предыдущем коде:

Код (Text):

1. mov esi,УказательНаТекстовыйФайл
2.  mov ecx,[dwSize]
3.   shr ecx,4
4.   xor edx,edx
5.   xor ebx,ebx
6. Цикл:mov eax,[esi]
7.   sub eax,0a000a00h
8.   sub eax,04000000h
9.   adc edx,ebx
10.   sub ah,04h
11.   adc edx,ebx
12.   mov eax,[esi+4]
13.   sub eax,0a000a00h
14.   sub eax,04000000h
15.   adc edx,ebx
16.   sub ah,04h
17.   adc edx,ebx
18.   mov eax,[esi+8]
19.   sub eax,0a000a00h
20.   sub eax,04000000h
21.   adc edx,ebx
22.   sub ah,04h
23.   adc edx,ebx
24.   mov eax,[esi+12]
25.   add esi,16
26.   sub eax,0a000a00h
27.   sub eax,04000000h
28.   adc edx,ebx
29.   sub ah,04h
30.   adc edx,ebx
31.   sub ecx, 1
32.   jnz Цикл

 

izebars
В аттаче общепринятый тест, добавь в него свой код и замерь. Потом добавь любой другой вариант и сравни результаты.

 

Black_mirror
Тестил твой код на файле Numbers.rar
в котором 1 000 000 строк но почему-то он выдает только 930959 строк
Странно что этого никто не увидел может я как-то не так его применил?
Судя по
mov edx,[esp+4]
mov ecx,[esp+8]
он должен быть отдельной процедурой [esp] - адрес возврата, остальное параметры
процедура сама должна быть без параметров чтобы в начале Fasm не добавил push ebp
Ну я так и сделал

proc CountLn
твой код в том виде, который ты опубликовал без видоизменений
endp

а вызывал
push [FileBuffer]
push [FileLength]
call CountLn

Но результат он возвращает неправильный.
Где косяк?

 

Слыхали, ну и кто теперь из нас дисквалифицирован.
IceStudent
Кстати по твоему атачу мой самый последний код у меня 8 выдает.

 

Miller Rabin
Не надо оформлять его в процедуру, он и так как процедура. Просто call делай.

izebars
8 попугаев? Или слонов? Время выполнения кода - величина относительная. Приводи в сравнении с другими вариантами, иначе у всех будет разное число.

 

IceStudent
На:

Black_mirror
---------------------------
211 bytes , 10 passes
---------------------------
000000000000000008887048
000000000000000009008464
000000000000000008354613
000000000000000008918087
000000000000000009003194
000000000000000008325055
000000000000000008349563
000000000000000008985926
000000000000000008235351
000000000000000008967765

average:
000000000000000008703507

izebars
average:
000000000000000000000008

Короче у меня быстрее

 

Абсолютно.

 

Самый быстрый код из приведенных выше:

Код (Text):

1. mov esi,УказательНаТекстовыйФайл
2.  mov ecx,[dwSize]
3.   shr ecx,4
4.   xor edx,edx
5.   xor ebx,ebx
6. ;Цикл:mov eax,[esi]
7.   sub eax,0a000a00h
8.   cmp eax,04000000h
9.   adc edx,ebx
10.   cmp ah,04h
11.   adc edx,ebx
12.   mov eax,[esi+4]
13.   sub eax,0a000a00h
14.   cmp eax,04000000h
15.   adc edx,ebx
16.   cmp ah,04h
17.   adc edx,ebx
18.   mov eax,[esi+8]
19.   sub eax,0a000a00h
20.   cmp eax,04000000h
21.   adc edx,ebx
22.   cmp ah,04h
23.   adc edx,ebx
24.   mov eax,[esi+12]
25.   add esi,16
26.   sub eax,0a000a00h
27.   cmp eax,04000000h
28.   adc edx,ebx
29.   cmp ah,04h
30.   adc edx,ebx
31.   sub ecx, 1
32.   jnz Цикл

Чаще всего в файлах txt встречаются строки свыше 10 символов, поэтому гораздо эффективней использовать именно это:

Код (Text):

1. xor edx,edx
2. MOVDQA xmm1,dqword [цифры0a]
3. MOVDQA xmm2,dqword [цифры7f]
4. MOVDQA xmm3,dqword [цифры04]
5. MOVDQA xmm4,dqword [цифры00FF]
6. MOVDQA xmm5,dqword [цифрыFF00]
7. mov edi,УказательНаТекстовыйФайл
8. mov ecx,[dwSize]
9. shr ecx,5
10. ;add ecx,1
11. Цикл :MOVDQA xmm0,dqword [edi]
12. MOVDQU xmm7,dqword [edi+17]
13. pand xmm0,xmm4
14. pand xmm7,xmm5
15. por  xmm0,xmm7
16. psubb xmm0,xmm1
17. pand xmm0,xmm2
18. psubb xmm0,xmm3
19. pmovmskb eax,xmm0
20. add edi,32
21. bsf ebx,eax
22. btr eax,ebx
23. jnc m1
24. adc edx,0
25. bsf ebx,eax
26. btr eax,ebx
27. jnc m1
28. adc edx,0
29. bsf ebx,eax
30. btr eax,ebx
31. jnc m1
32. adc edx,0
33. bsf ebx,eax
34. btr eax,ebx
35. jnc m1
36. adc edx,0
37. bsf ebx,eax
38. btr eax,ebx
39. jnc m1
40. adc edx,0
41. bsf ebx,eax
42. btr eax,ebx
43. jnc m1
44. adc edx,0
45. bsf ebx,eax
46. btr eax,ebx
47. jnc m1
48. adc edx,0
49. bsf ebx,eax
50. btr eax,ebx
51. jnc m1
52. adc edx,0
53. bsf ebx,eax
54. btr eax,ebx
55. jnc m1
56. adc edx,0
57. bsf ebx,eax
58. btr eax,ebx
59. jnc m1
60. adc edx,0
61. bsf ebx,eax
62. btr eax,ebx
63. jnc m1
64. adc edx,0
65. bsf ebx,eax
66. btr eax,ebx
67. jnc m1
68. adc edx,0
69. bsf ebx,eax
70. btr eax,ebx
71. jnc m1
72. adc edx,0
73. bsf ebx,eax
74. btr eax,ebx
75. jnc m1
76. adc edx,0
77. bsf ebx,eax
78. btr eax,ebx
79. jnc m1
80. adc edx,0
81. cmp ah,10
82. jz m1
83. add edx,1
84. m1:sub ecx,1
85. jnz Цикл
86. ;=========================
87. align 16
88. цифры0a:  times 16 db $a
89. цифры7f:  times 16 db $7f
90. цифры04:  times 16 db 4
91. цифры00FF:times 8  dw $ff00
92. цифрыFF00:times 8  dw $00ff
93.      УказательНаТекстовыйФайл file 'Любой.txt'

 

izebars
Всё, свободен. За нарушения.

 

Решил выложить свое решение подсчета строк в файле

Код (Text):

1. proc CountLn Buffer, Length
2.     local CountLine: DWORD, Result1: QWORD, Result2: QWORD
3.     mov esi, 8
4.     xor ecx, ecx
5.     mov [CountLine], ecx
6.     pxor mm2, mm2
7.     mov edx, 0E00h
8.     movd mm7, edx
9.     mov eax, [Buffer]
10.     pshufw mm7, mm7, 0
11.     mov ecx, [Length]
12.     pxor mm3,mm3
13.     add ecx, eax
14.     pxor mm5,mm5
15.     mov edx, ecx
16.     pcmpeqw mm5,mm5
17.     pxor mm6, mm6
18.     and ecx,-8
19.     align 16
20.  
21. .lbCheck:
22.     movq mm0, [eax]
23.     psubusw mm0, mm7                 ;mm0 - Строка из файла
24.     pcmpeqw mm0, mm6                ;mm1 - Временный регистр
25.     psubw mm2, mm0                      ;mm2 - Количество строк в файле
26.     pshufw mm4, mm2, 0xE4                ;mm3 - Количество переполнений в mm2
27.     pcmpeqw mm4, mm5                     ;mm4 - Временный регистр
28.     add eax, esi                        ;mm5 - FFFFFFFFFFFFFFFFh
29.     psubw mm3, mm4                       ;mm6 - 0
30.     cmp eax, ecx                           ;mm7 - 0E000E000E000E00h
31.     psubw mm2, mm4
32.     jne .lbCheck
33.    
34.     mov edi, 0Ah
35.         cmp eax, edx
36.         je .lbSkip
37. .lbFix:
38.     movzx ecx, BYTE [eax]
39.     cmp ecx, edi
40.     jne .lbInc
41.     inc [CountLine]
42.  
43. .lbInc:
44.     inc eax
45.     cmp eax, edx
46.     jne .lbFix
47.  
48. .lbSkip:
49.     mov ecx, 3
50.     movq [Result1], mm3
51.     movq [Result2], mm2
52.     lea edi, [Result1]
53.     lea esi, [Result2]
54.     xor ebx, ebx
55.     or ebx, 0000FFFFh
56. .lbLoop:
57.     movzx eax, WORD [edi+ecx*2]
58.     mul ebx
59.     add [CountLine], eax
60.     movzx eax, WORD [esi+ecx*2]
61.     add [CountLine], eax
62.     dec ecx
63.     jns .lbLoop
64.     mov eax, [CountLine]
65. ret
66. endp

Тесты проводил на P4 3Ггц 800 FSB 1024кб Cash

Получил следующее

186Bytes 10 Passes
...
average 11816398

Против кода, который опубликовал IzeBars, когда предлагал смыть наши мозги в унитаз

68 Bytes 10 Passes
....
average 20803687

на коде от Black Mirror не тестировал потому что не смог добиться от него правильного результата, к сожалению

А вот результат по коду Leo который с параллельным подсчетом четырех сумм

146 Bytes 10 passes
...
Average 21439838

Результат второго кода IzeBars, который "самый быстрый из всех приведенных выше"

106 Bytes 10 Passes
...
Average 16897862

Результат кода который IzeBars рекомендует использовать для строк свыше 10 символов
295Bytes 10 passes
...
Average 44330435

 

Miller Rabin
Вот на шару простой вариант без adc, который на P4 дает те же 11 млн.тиков, но вдвое короче твоего

Код (Text):

1.   mov edi,[lpBuf]
2.   mov ebx,[BufSize]
3.   add ebx,3
4.   and ebx,-4
5.   xor esi,esi
6.   jmp .nextblock
7. align 16
8. @@:
9.   mov edx,[edi+ecx]
10.   and eax,$FF00FF00
11.   add edx,$00F200F2
12.   add eax,$00040004
13.   and edx,$00FF00FF
14.   add eax,edx
15.   add ecx,4
16.   jl @B
17.  
18.   movzx edx,ah
19.   shr eax,24
20.   add esi,edx
21.   add esi,eax
22. .nextblock:
23.   mov ecx,ebx
24.   mov eax,255*4
25.   cmp ecx,eax
26.   cmovg ecx,eax
27.   xor eax,eax
28.   sub ebx,ecx
29.   add edi,ecx
30.   neg ecx
31.   jnz @B
32.   mov eax,esi

Может MMX\XMM и суперразвороты потенциально и быстрее, но как я уже говорил, здесь ограничивающим фактором является скорость чтения данных из ОЗУ, т.к. файл в ~8Мб ни в какой кэш не влезает, а поэтому при такой постановке задачи и извращаться незачем )
PS: Кстати этот вариантик и на атлоне должен неплохо работать (но, конечно не лучше суперварианта izebars c cmp )