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

Приветствую.

Давно интересен был сабж в плане красивого решения, а теперь понадобилась реализация.

Входные данные: текстовой файл, строки разделены символами 0D0A.
Выходные - количество строк в файле.

Для тестирования сгенерил файл в миллион строк (размером 7,5 мб).

Мерял просто - RDTSC. Файл просто прочитывал в память целиком; решение для больших файлов в другой теме. Мерял по 8-10 раз каждый тест.

Так вот. Первое решение "в лоб":

Код (Text):

1. ; ebx:esi - кол-во строк в файле.
2. ; edi - указатель на память с прочитанным файлом.
3.     mov     al,0Dh  ; разделитель строки
4.     mov     ecx,[dwSize] ; размер файла
5. align 16
6. @@:
7.     add     esi,1
8.     adc     ebx,0
9.    
10.     repne scasb
11.     je      @B

Дало в среднем 83 500 000 тиков.

Чуть улучшил, убрал rep и scas:

Код (Text):

1.     mov     al,0Dh
2.     mov     ecx,[dwSize]
3.     sub     edi,1
4.     add     ecx,1
5. align 16
6. .l1:
7.     add     edi,1
8.     sub     ecx,1
9.     jz      @F   ; файл закончился
10.    
11.     cmp     [edi],al
12.     jne     .l1
13.  
14.     add     esi,1
15.     adc     ebx,0
16.     jmp     .l1

В среднем дало 60 768 108 тиков. Уже лучше. Попробовал "распараллелить":

Код (Text):

1.     mov     al,0Dh
2.     mov     ecx,[dwSize]
3.     and     ecx,$FFFFFFFE
4.  
5.     jmp     .l1
6. align 16
7. .l1:
8.     cmp     [edi],al
9.     je      .l2
10.     cmp     [edi+1],al
11.     je      .l3
12.  
13.     add     edi,2  
14.     sub     ecx,2
15.     jnz     .l1
16.  
17.     jmp     @F
18.  
19. align 16
20. .l2:
21.     add     esi,1
22.     adc     ebx,0
23.     add     edi,1
24.     jmp     .l1
25.  
26. align 16
27. .l3:
28.     add     esi,1
29.     adc     ebx,0
30.     add     edi,2
31.     jmp     .l1
32.  
33. @@: ; выход

Получилось. В среднем стало давать 23 091 034 тиков. Но дальнейшая разбивка проверки на 4 байта подряд уменьшила производительность и стала давать 44 341 990. Остановился на варианте №3. Это мерял на PM 1,6 GHz, модель 13.

На AMD64 3000+ (2,5 GHz) получаются следующие результаты: ~43 000 000, 20 000 000, 30 000 000, 32 000 000. То есть, получается, что отказ от rep и scas к лучшему, но "распараллеливание" хорошего не даёт.

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

 

Не пробовал метод, используемый в сишной strlen (похожий метод используется в масмовой StrLen)?
Там заряжено на ноль в конце строки, но можно пересчитать константу на 0D или 0A. Первые 0 - 3 байта сканирование побайтное, а затем, как только адрес очередного байта будет кратен 4 - подвордное сканирование

 

cresta
Пока не разобрался в алгоритме strlen. А memchr слишком избыточен на вид, хотя его не тестил.

Алгоритм strlen следующий:

Код (Text):

1. if( ((c1 + i) ^ (i ^ c2)) & c3 ) { искомый байт присутствует в дворде }
2. где
3.   i = входной дворд
4.  c1 = 7EFEFEFF ( 0111 1110 1111 1110 1111 1110 1111 1111 )
5.  c2 = FFFFFFFF ( 1111 1111 1111 1111 1111 1111 1111 1111 )
6.  c3 = 81010100 ( 1000 0001 0000 0001 0000 0001 0000 0000 )

То есть, c3 = ~c1. Но как подобрать значение, чтобы после приведённых операций результат был бы не равен 0 при наличии 0D в дворде?

Хотя можно обойти это: i ^= 0D0D0D0D.

По алгоритму strlen с корректировкой через xor даёт 20 000 000 на атлоне. Наверное, стоит попытаться улучшить её через подбор константы и оптимизации проверки размера буфера.

 

Код (Text):

1. counter proc uses ebx esi edi lpFile:DWORD
2.    
3.     xor     eax,eax                         ;counter
4.     mov     esi,lpFile
5. _start:
6.     mov     edi,esi
7.     lea     edx,[esi+3]
8. _bt:
9.     test    esi,3
10.     je      _dw
11.     cmp     byte ptr[esi],0Dh
12.     je      _next
13.     inc     esi
14.     jmp     _bt
15.    
16. _dw:
17.     mov     ebx,[esi]
18.     add     esi,4
19.     lea     ecx,[ebx-0E0E0E0Eh]
20.     not     ebx
21.     and     ecx,ebx
22.     and     ecx,80808080h
23.     jz      _dw
24.     test    ecx,00008080h
25.     jnz     _next
26.     shr     ecx,16
27.     add     esi,2
28. _next:
29.     shl     cl,1
30.     sbb     esi,edx
31.     inc     eax
32.     lea     esi,[edi+esi+1]     ;или +2, если разделитель 0D0A
33.     cmp     byte ptr[esi+1],0
34.     jne     _start
35.    
36.     ret
37.  
38. counter endp

попробуй это. Тут ещё можно оптимизировать, только голова после месяца в php уже не работает

Если строки совсем короткие, то выравнивание на три (в начале процедуры) может пойти во вред.

P.S.
Пока рисовал, ты уже strlen переделал, но все равно попробуй.

 

IceStudent
Можно загружать в один MMX регистр по 8 символов(или в XMM по 16), и формировать маску FF (PCMPEQB) для символов равных 0D, а в другой регистр загружать символы со сдригом на 1 байт и формировать FF для символов равных 0A. Далее делаем AND и вычитаем это из регистра с 8 байтовыми суммами. Сдвигаемся на 8 символов. После 255*2 (пока не возникло переполнения) итераций необходимо перенести накопленное в сумматор большей разрядности. Если скорость ограничивается не памятью, то по идее должен быть прирост.

 

Если закрыть глаза на partial register stall на младших P6, то можно сделать так

Код (Text):

1.   mov ecx,[dwSize]
2.   xor eax,eax
3.   xor edx,edx
4. @@:
5.   mov al,[edi]
6.   mov dl,[edi+1]
7.   add edi,2
8.   sub al,0Eh
9.   sub dl,0Eh
10.   add eax,1  ;!!! stall на PPro-PIII и PM модель 9
11.   add edx,1
12.   sub ecx,2
13.   jg @B
14.   and eax,-256 ;0FFFFFF00h
15.   add eax,edx
16.   shr eax,8

На P4, AMD и P6 модели 13 и выше должно работать

 

IceStudent
А как изменится решение, если файл не лезет в оперативную память?

 

Кстати и без partial registers получается не хуже

Код (Text):

1.   ;ОКОНЧАТЕЛЬНО ИСПРАВЛЕННЫЙ ВАРИАНТ
2.   mov esi,[dwSize]
3.   mov eax,255
4.   mov edx,255
5. align 16
6. @@:
7.   movzx ecx,byte [edi]
8.   movzx ebx,byte [edi+1]
9.   add edi,2
10.   xor ecx,0Dh
11.   xor ebx,0Dh
12.   add eax,ecx  ;подсчет числа символов != 0Dh
13.   add edx,ebx
14.   or eax,255
15.   or edx,255
16.   sub esi,2
17.   jg @B
18.   shr eax,8
19.   shr edx,8
20.   add edx,eax
21.   mov eax,[dwSize]  ;определяем число символов 0Dh
22.   add eax,1             ;выравниваем на четное число
23.   and eax,-2
24.   sub eax,edx
25.  
26.   ;--- Тоже с тривиальным разворотом на 2 ---
27.   ;размер буфера д.б. кратен 4-м (можно заполнить остатки нулями)
28.   mov esi,[dwSize]
29.   mov eax,255
30.   mov edx,255
31. align 16
32. @@:
33.   movzx ecx,byte [edi]
34.   movzx ebx,byte [edi+1]
35.   xor ecx,0Dh
36.   xor ebx,0Dh
37.   add eax,ecx          ;подсчет числа символов != 0Dh
38.   add edx,ebx
39.   or eax,255
40.   or edx,255
41.   movzx ecx,byte [edi+2]
42.   movzx ebx,byte [edi+3]
43.   add edi,4
44.   xor ecx,0Dh
45.   xor ebx,0Dh
46.   add eax,ecx
47.   add edx,ebx
48.   or eax,255
49.   or edx,255
50.   sub esi,4
51.   jg @B
52.   shr eax,8
53.   shr edx,8
54.   add edx,eax
55.   mov eax,[dwSize]   ;определяем число символов 0Dh
56.   add eax,3              ;выравниваем вверх на 4
57.   and eax,-4
58.   sub eax,edx

Если данные в кэше, то на P4 получается ~2.5 тика на байт или ~2.0 если еще развернуть в два раза (на атлоне должно быть примерно тоже, а вот на P6 доп.разворот может ничего не дать, т.к.АЛУ всего два)

Еще вариантик с параллельным подсчетом 4-х сумм

Код (Text):

1.   mov ecx,[dwSize]
2.   add ecx,3       ;считаем, что размер буфера выравнен на 4
3.   and ecx,-4
4.   xor eax,eax     ;три частичные суммы
5.   xor esi,esi     ;основная сумма
6.   push ebp
7.   mov ebp,250     ;число частичных суммирований
8. align 16
9. @@:
10.   mov edx,[edi]
11.   add edi,4
12.   xor edx,0D0D0D0Dh
13.   mov ebx,edx
14.   and edx,01010101h
15.   add edx,0FEFEFEFEh
16.   add edx,ebx     ;побайтные переносы, если не 0Dh
17.   adc esi,0       ;подсчет числа символов != 0Dh
18.   and edx,01010100h
19.   add eax,edx
20.   sub ebp,1
21.   jz  save        ;один непредсказанный переход на 250*4 = 1000 байт
22.   sub ecx,4
23.   jg @B
24. save:
25.   shr eax,8       ;добавляем частичные суммы к esi
26.   mov edx,eax
27.   shr edx,8
28.   and eax,0FFh
29.   add esi,eax
30.   mov eax,edx
31.   shr edx,8
32.   and eax,0FFh
33.   add esi,eax
34.   add esi,edx
35.   xor eax,eax
36.   mov ebp,250
37.   sub ecx,4
38.   jg @B
39.   pop ebp
40.   mov eax,[dwSize]
41.   add eax,3
42.   and eax,-4       ;всего символов
43.   sub eax,esi      ;символов 0Dh

Если данные в кэше, то на P4 получается ~1.53 тика на байт, на PIII ~1.9

 

leo

Как всегда суперкруто!!!
А почему у меня так глухо тормрозит ~6 тиков на байт, хотя по задумке должно использовать разницу в скорости ядра и памяти на полную катушку

Код (Text):

1.     mov ebx, 0
2.     mov ecx, [size_File]
3.     shr ecx, 2  ; /4
4.     mov [loop_Count], ecx
5.     mov edi, [mem_File]
6.     mov ebx, [edi]  ; текущий DWORD
7.     add edi, 4
8.     ALIGN 16   
9.         @@:
10. ;           mov esi, [edi + 12] ; упреждающее кэширование < - у меня только замедляет
11.             xor eax, eax    ; обнуляем временный счётчик
12.             mov ecx, [edi]  ; следующий DWORD
13.             add edi, 4
14.             mov edx, ebx
15.             and edx, 0FFFFh ; проверка по маске
16.             cmp edx,  0A0Dh ; <- в константе обратный порядок байт !!!
17.               sete ah
18.               add  al, ah   ; временный счётчик
19.             shrd ebx, ecx, 8    ; сдвиг со вдвигом для проверки на границе DWORD
20.             REPEAT 2        ; <-- развёрнутый цикл
21.               mov edx, ebx
22.               and edx, 0FFFFh   ; проверка по маске
23.               cmp edx,  0A0Dh
24.                 sete ah
25.                 add  al, ah ; временный счётчик
26.               shr ebx, 8    ; сдвиг к следующему значению
27.             ENDM
28.             cmp ebx,  0A0Dh ; проверка по маске
29.               sete ah
30.               add  al, ah   ; временный счётчик
31.             xor ah, ah      ; <- устраняем частичную задержку
32.             add [Count_EndStr], eax ; кидаем временный счётчик в постоянный
33.             mov ebx, ecx    ; сделать следующий DWORD текущим
34.             dec [loop_Count]
35.         jnz @B

 

ММХ версия.
Для массивов помещающихся в кеш получается от 4.7 до 5.5 байтов на такт (хвост не кратный 2048 обрабатывается медленее).
Для массива в 16Мб получается 0.55 байта на такт, то есть в 10 раз хуже. Здесь можно сделать какую-то предвыборку или атлонуХР это не поможет?

Код (Text):

1. ;esi - указатель на строку(должен быть кратен 8 байтам)
2. ;ecx - число символов
3. sums:
4.         movq mm7,qword [.c0D]   ;EOL
5.         pxor mm5,mm5            ;sum8
6.         pxor mm4,mm4            ;sum8
7.         pxor mm6,mm6            ;sum32
8.         add ecx,esi
9.         mov edx,ecx
10.         and edx,-2048            ;16 счётчиков от 0 до 128
11.         cmp esi,edx
12.         jae .l1
13.     .l0:
14.         movq mm0,[esi]
15.         movq mm1,[esi+8]
16.         movq mm2,[esi+16]
17.         movq mm3,[esi+24]
18.         pcmpeqb mm0,mm7
19.         pcmpeqb mm1,mm7
20.         psubb mm4,mm0
21.         psubb mm5,mm1
22.         pcmpeqb mm2,mm7
23.         pcmpeqb mm3,mm7
24.         psubb mm4,mm2
25.         psubb mm5,mm3
26.         movq mm0,[esi+32]
27.         movq mm1,[esi+40]
28.         movq mm2,[esi+48]
29.         movq mm3,[esi+56]
30.         add esi,64
31.         pcmpeqb mm0,mm7
32.         pcmpeqb mm1,mm7
33.         psubb mm4,mm0
34.         psubb mm5,mm1
35.         test esi,2047
36.         pcmpeqb mm2,mm7
37.         pcmpeqb mm3,mm7
38.         psubb mm4,mm2
39.         psubb mm5,mm3
40.         jnz .l0
41.         pxor mm0,mm0
42.         movq mm2,mm4
43.         movq mm3,mm5
44.         punpcklbw mm2,mm0
45.         punpcklbw mm3,mm0
46.         punpckhbw mm4,mm0
47.         punpckhbw mm5,mm0
48.         paddw mm4,mm2
49.         paddw mm5,mm3
50.         paddw mm4,mm5
51.         movq mm2,mm4
52.         punpckhwd mm4,mm0
53.         punpcklwd mm2,mm0
54.         paddd mm6,mm4
55.         cmp esi,edx
56.         pxor mm4,mm4
57.         pxor mm5,mm5
58.         paddd mm6,mm2
59.         jb .l0
60.     .l1:
61.         mov edx,ecx
62.         and edx,-32
63.         cmp esi,edx
64.         jae .l3
65.     .l2:
66.         movq mm0,[esi]
67.         movq mm1,[esi+8]
68.         movq mm2,[esi+16]
69.         movq mm3,[esi+24]
70.         add esi,32
71.         pcmpeqb mm0,mm7
72.         pcmpeqb mm1,mm7
73.         psubb mm4,mm0
74.         psubb mm5,mm1
75.         cmp esi,edx
76.         pcmpeqb mm2,mm7
77.         pcmpeqb mm3,mm7
78.         psubb mm4,mm2
79.         psubb mm5,mm3
80.         jb .l2
81.     .l3:
82.         sub ecx,esi
83.         jz .l4
84.         xor ecx,31
85.         movq mm0,[.mask+ecx]
86.         movq mm1,[.mask+ecx+8]
87.         movq mm2,[.mask+ecx+16]
88.         movq mm3,[.mask+ecx+24]
89.         pand mm0,[esi]
90.         pand mm1,[esi+8]
91.         pand mm2,[esi+16]
92.         pand mm3,[esi+24]
93.         pcmpeqb mm0,mm7
94.         pcmpeqb mm1,mm7
95.         psubb mm4,mm0
96.         psubb mm5,mm1
97.         pcmpeqb mm2,mm7
98.         pcmpeqb mm3,mm7
99.         psubb mm4,mm2
100.         psubb mm5,mm3
101.     .l4:        
102.         pxor mm0,mm0
103.         movq mm2,mm4
104.         movq mm3,mm5
105.         punpcklbw mm2,mm0
106.         punpcklbw mm3,mm0
107.         punpckhbw mm4,mm0
108.         punpckhbw mm5,mm0
109.         paddw mm4,mm2
110.         paddw mm5,mm3
111.         paddw mm4,mm5
112.         movq mm2,mm4
113.         punpckhwd mm4,mm0
114.         punpcklwd mm2,mm0
115.         paddd mm6,mm4
116.         cmp esi,edx
117.         pxor mm4,mm4
118.         pxor mm5,mm5
119.         paddd mm6,mm2
120.         sub esp,8
121.         movq [esp],mm6
122.         pop eax
123.         pop edx
124.         add eax,edx
125.         ret
126. .c0D dd $0D0D0D0D,$0D0D0D0D
127. label .mask qword
128.         times 31 db 255
129.         times 31 db 0

 

Y_Mur

Black_mirror

О какой разнице "на полную катушку" идет речь ? Для большинства пеньковых конфигураций отношение предельной скорости чтения из ОЗУ (Rram = Fram*8, байт\сек) к частоте процессора Fcpu составляет Rram/Fcpu ~ (0.8..1.1) байт за такт. Реальная скорость получается несколько меньше из-за потерь на инициализацию чтения пакетов. Поэтому, во-первых, при чтении данных из ОЗУ получить скорость обработки лучше Rram/Fcpu <~ 1 байт за такт по любому не выйдет. Поэтому при обработке заведомо больших объемов данных не имеет большого смысла извращаться с супер-разворотами циклов в расчете получить скорость лучше 0.5-1.0 такта на байт. Во-вторых, для алгоритмов расчитанных на макс.скорость заметно ниже этого предела (т.е. 2-3 и более тактов на 1 байт) получается практически без разницы - находятся данные в кэше или грузятся из ОЗУ. В частности, для мягко говоря не самого быстрого, если не сказать тормозного варианта Y_Mur ни о каких "полных катушках" речи быть не может, т.к. данные грузятся из памяти быстрее чем обрабатываются и никакие префетчи тут не помогут (тем более неправильные . А вот для быстрого варианта MMX предварительный блок-префетч может повысить скорость обработки на десяток-другой процентов на P4 и более на атлонах и P6 (в мануалах AMD "проскакивают" цифры до 30% при копировании c movntq и где-то аж до 50% при чтении). На P4 выигрыш получается меньше, т.к. у него и буферов чтения побольше и данные читаются из ОЗУ секторами по 128 байт, а не по 64 как в других архитектурах, и поэтому процент накладных расходов на оверхеды и так меньше. Но разумеется префетч позволяет лишь приблизится к заветной цифре Rram/Fcpu - выше головы не прыгнешь

Y_Mur

Угу, а на Pentium D еще "круче" - до 10 тиков на байт
Ты б для начала заглянул в Фога или IA-32 Optim и посмотрел бы латентности shrd и setcc, да и add al,ah по мелочи ))

 

cresta

При +2 зависает на второй строке. А так тоже виснет, но на 3й

leo
1й вариант даёт в среднем 21 000 000. Второй в среднем 250 тиков и определяет первые 3 строки Третий вариант с параллельным подсчётом 14 000 000, корректен. На ПМ 37 000 000 и 16 000 000 1й и 3й варианты. Получается, распараллеливание работает одинаково хорошо на обоих процессорах, с 1м вариантом же у ПМ что-то не сложилось (не могу сказать, что).

Да, и что имеется ввиду под "N тиков на байт" — байт кода?

Black_mirror
Находит 12202 строки. Но за алгоритм спасибо, я долго размышлял над масками, прежде чем понял strlen.

crypto
Он не изменится. После прохода dwSize подкачивается следующая порция.

 

IceStudent

Упс, "не фиг се", действительно опечатка на опечатке - ес-но нужен отдельный регистр для счетчика циклов и разумеется xor ebx,0Dh и add edx,ebx ((
Исправил там же, чтобы не позориться

А у тебя точно 13 модель ? Т.к. на предыдущих и должен быть partial register stall. Да вообще-то 1-й вариант мне только "изящным" размерчиком понравился, а так фигня конечно
PS: у первых двух вариантов еще и макс.значение суммы ограничено 2*0FFFFFFh ~ 33.5 млн - в 1-м варианте это число строк, а во втором - макс.размер буфера в байтах

Да нет, на байт текста конечно. Если ты проверяешь на тексте 7.5Мб, то 14 млн. тиков дает скорость 14млн/7.5Мб ~ 1.8 такта на байт - вполне нормально по сравнению с моими 1.53 c учетом подкачки данных из ОЗУ и различия камней (P4 все-таки может в пике до 4 операций за такт выполнять, а Атлон - 3)

 

leo
Intel Pentium M 725 (Dothan) Family / Model / Stepping = 6 D 8

 

Мой не рабочий точно, от leo у меня наоборот, первый не работает (находит 47 строк из 100-строчного файла) , второй работает. От Black_mirror не смотрел.
А вообще, тут рабочие коды есть? ))

Может начать со скорости 100 тиков/байт, но чтобы надёжно
Файлик чтобы был какой-то определенный (алго по его созданию). Прежде чем быстро бежать, надо хорошо подготовиться

 

cresta
Рабочие есть и самый быстрый - 3й вариант от leo.

Файлик сгенерил не мудрствуя лукаво - PasswordsPro, там в комплекте DictionaryGenerator. Настройки: 0-9, 0-988888. Получается ровно миллион строк, файл 7.5 мб. Строки в данном случае короткие, но это для тестирования. Сгенерировать можно любой файл

 

IceStudent
Со вторым вариантом без partial stall меня опять глюкануло - просто наваждение какое-то (
Ес-но, он также как и 3-й вариант подсчитвает число символов != 0Dh, поэтому в конце нужно брать eax = (dwSize+1) & (-2) - eax. Исправил на старом месте - на этот раз проверено, мин нет

cresta

Видимо это злосчастный второй (

 

Чем больше сталкиваюсь с оптимизацией, тем больше убеждаюсь, что фигня все эти скорости. Взял три самых быстрых кода в теме (от leo). На пеньках у них заявлено порядка 1,5 - 1.6 тика на 1 байт строки. На AthlonXP что-то совсем не радужная картина:
код из поста №6(1) - ~31.1 млн тиков (4.0 тика/байт)
код из поста №8(1) - ~33.5 млн тиков (4.3 тика/байт)
код из поста №8(2) - ~30.0 млн тиков (3.8 тика/байт)
Проверял на файле из аттача.

Попробуйте на пеньках вот это:

Код (Text):

1.          align 16  
2.          _s:  
3.             mov     ebx,[edi]
4.             sub     ecx,4
5.             lea     edi,[edi+4]
6.             jle     _end              
7.             lea     edx,[ebx-0B0B0B0Bh]
8.             not     ebx
9.             and     edx,ebx
10.             and     edx,80808080h
11.             jz      _s
12.             and     edx,00008080h
13.             lea     eax,[eax+1]
14.             jz      _s  
15.             sub     edi,2
16.             add     ecx,2
17.             jmp     _s
18.           _end:

У меня этот код даёт на файле из аттача ~28.1 млн тиков (3.6 тика/байт)

 

cresta
В каком регистре ответ?
Ага, там надо еах обнулить сначала..
Выдаёт на 1 строку меньше, но зато 11 000 000 (1,45 тиков на байт). На ПМ 13 300 000 (1.7 тиков/б)

Оптимизировал под короткие строки?

 

IceStudent

Нужно перед циклом add ecx,4 добавить, иначе при dwSize <= 4 сразу на выход без обработки

cresta

Да уж почти в два раза тормознее чем на других камнях ?! Или память тормозит или два прохода делаешь )
Вот что получается на NetBurst
P4 1.8ГГц 15.2.7 (Northwood, без HT)
код cresta - ~13.5 - 15 млн (нестабильно)
код 3й leo - ~13.6 млн (тоже броски до 15, но редко)
код 2б leo - ~17.2 млн (дост.стабильно) - довесок с доп.разворотом
код 2а leo - ~18-20 млн - злосчастный 2й вариант

Pentium D 930 3.0ГГц 15.6.2
код cresta - ~17.5 - 20 млн (нестабильно)
код 3й leo - ~17.5 млн (дост.стабильно)
код 2б leo - ~17.2 млн (дост.стабильно)
код 2а leo - ~19.9 млн

Код cresta достаточно быстрый, но и достаточно нестабильный - видимо из-за пары jcc, поэтому еще м.б. зависимость от входных данных (статистики длины строк в файле)