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

leo

Я также проверял свой последний код на DDR400 и у меня вышло меньше 8 млн.
Пусть все услышат честное мнение IceStudentа
(только по поводу того, о чём сейчас идет спор)

 

Тема снова закрыта на время разбирательства с г-ном барсом.

 

Ладно, Leo я понял, что на других компах с более медленным ОЗУ толку от алгоритма совершенно не будет.

Есть другая идея, которую я хочу выдвинуть на суд общества полуночников.

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

и так алгоритм:

Находим период повторений символа конца строки ,скажем, на 100 строках (Экспериментально можно подобрать)

Имеем определенный период на котором располагается 100 строк

В следующем периоде уже несчитаем количество строк.
А делаем заключение (с определенной долей вероятности)
Изменился ли период.
Сейчас у меня есть мысль определять это по последним 16 байтам xmm - регистр
Например изменилось ли место символа конца строки в этом регистре (Хотя тут, возможно, есть лучшие способы)

Если изменился, то пересчитаем количество строк.

и так далее

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

Хотя даже в том тексте, который я сейчас для вас написал можно проследить, определенный период строк.

Я постараюсь проработать этот алгоритм за выходные.
Возможно у меня получится что-нибудь стоящее к понедельнику.

Хотелось бы выслушать ваши идеи по этому поводу.
Только я их врядли прочитаю. Так как до понедельника у меня инета не будет
И все же прошу Ice Student'a не закрывать пока тему

Расти есть куда

 

Посмотри на свой пост =)
И как она отработает на нём? Здесь есть и длинные и средние и короткие строки.

 

Сомневаюсь. Человеческая речь далека от каких-либо законов, в которые её можно было бы втиснуть. Имеется ввиду "поток изложения", а не грамматика.

 

Miller Rabin
Проверил SSE-версии на A64 (память 2x200 МГц, процессор 11х200 МГц):
моя версия 6.15 М тактов
твоя версия 7.5 М тактов
версия невменяемого 13 М тактов

можешь проверить на своей системе?

[аттач забыл]

 

Ну-у-у-у. Блин.
Человеческая речь может быть и далека, а вот расстановка знаков конца строки совсем нет.
Смысл-то их в том, чтобы текст было удобней читать после того как его набрали. Даже там где выполняется перенос по словам символы табуляция и конца строки применяются для того чтобы выделять какое-то место из монолитного текста.

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

Для разных людей точно также как и для разных окон ввода текста свои рамки. Но в, конечном счете он сводится к этому самому периоду.

Ну и наконец мне кажется все из вас знают про таблицу вероятностей букв, встречающихся в тексте.
И хоть "человеческая речь и далека от каких либо законов в которые ее можно было бы втиснуть" На больших текстах эта вероятность выявляется достаточно четко.

О точности же полученных результатов вопрос получается спорный
С одной стороны на файле подобном numbers этот алгоритм даст результат в миллион строк совершенно точно.
Что же касается других файлов: то в этом плане все алгоритмы приведенные выше - вероятностные. Так как для любого из них можно подобрать такой файл на котором он выдаст в корне неправильный результат.

А что касается погрешности вычислений, то варьируя различные условия по которым делается вывод "изменился ли период" можно добиться наилучшего соотношения Скорость <-> Точность в соответствии с каждой конкретной задачей

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

Ха
Я назову его Гамбит-2 (А в жертву походу придется принести выходные)

Black Mirror
твой код я скачал обязательно его протестирую результаты будут в понедельник. Так как на выходных доступа в инет у меня нету

 

IceBars

Ну и что, ведь дело не в абсолютном значении частоты ОЗУ, а в отношении частот ОЗУ и ЦПУ. Прочитать 8Мб из DDR400 можно не быстрее, чем за 8Мб/(400МГц*8байт) = 2.5 мс. Но мы меряем не миллисекунды, а такты, поэтому чем ниже частота ЦПУ, тем меньше тактов укладывается в этих миллисекундах. Если проц 3.2ГГц, то предел > 8 млн, а если скажем 2.2ГГц как у Black_mirror'а, то предел > (2.2ГГц/3.2ГГб/с)*8Мб = 5.5 млн. Поэтому, и Miller Rabin мог получить свои рекордные ~5.2 млн не только за счет "крутого ОЗУ", но и за счет "весьма скромного ЦПУ" )

PS: А твой алгоритм #69 работает неверно - на всем файле результат правильный, а вот на Size=100*1000 выдает на 2 больше. Разбираться лень, но видимо ты цепляешь лишний блок из-за add ecx,1.

Miller Rabin

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

Black_mirror

И ты туда же )
Вот не поленился затестить последние варианты, чтобы показать их действительные, а не "попугайные" различия

Код (Text):

1. P4 Northwood 3.2GHz DDR400
2.                   ----- 100*1000 байт -----   --- 7876550 байт ---
3.                   average  R1    R16     k     average, млн.   k
4. leo #60c           103428  1.13  16.5   2.8    11.3 - 12.6   ~1.22
5. IceBars #69         71546  0.71  11.4   2.0     9.6 - 10.8   ~1.01
6. Miller Rabin #76    62640  0.62  10.2   1.7     9.3 - 10.7   ~1.0
7. Black_mirror #40    36852  0.36   5.9   1.0     9.2 - 10.7    1.0
8. --- демо -------
9. Miller Rabin #70    48540  0.48   7.8           9.0 - 10.5
10. Miller Rabin #77    37640  0.37   6.0           8.3 -  9.4 ?!
11. (R1 - тик/байт, R16 - тик/dqword = на xmm, k - отн.проигрыш в разах)

Как видим, если данные в кэше, то и цифры получаются достаточно стабильные и различия в алгоритмах хорошо видны. А на больших объемах и цифры скачут и разница нивелируется (да еще какие-то странные относительные улучшения демо-вариантов #70 и #77 наблюдаются ?!)

 

Miller Rabin
Тогда ещё нюанс - есть режим отображения текста без переносов, когда строки оканчиваются спец-символом (удобно для программных листингов, но плохо для литературного текста , и с переносом - когда спец-символом заканчивается параграф, а количество строк зависит от размеров экрана

 

Позволю себе запостить свой тупой вариант

Код (Text):

1. macro Ching {
2.   mov  edi,[lpBuf]
3.   mov  ecx,[BufSize]
4.   shr  ecx,2
5.  
6.   xor  esi,esi
7. ;;  mov  al,0Dh
8.  
9. @@CalcEOF:
10.  
11. ;;  repnz scasb
12. ;;  jecxz @@ChingEnd
13. ;;  inc   esi
14. ;;  jmp   @@CalcEOF
15.  
16.   mov  eax,[edi]
17.   add  edi,4
18.  
19.   test eax,0000000F2h
20.   jz   near @@AlmostValid
21.   test eax,00000F200h
22.   jz   near @@AlmostValid
23.   test eax,000F20000h
24.   jz   near @@AlmostValid
25.   test eax,0F2000000h
26.   jz   near @@AlmostValid
27.  
28.   dec  ecx
29.   jnz  @@CalcEOF
30.   jmp  @@ChingEnd
31.  
32. @@AlmostValid:
33.  
34.   mov  ebx,-4h
35.   xor  edx,edx
36.  
37. @@CalcLast:
38.  
39.   cmp  byte [edi+ebx],0Dh
40.   setz dl
41.   add  esi,edx
42.   inc  ebx
43.   jnz  @@CalcLast
44.  
45.   dec  ecx
46.   jnz  @@CalcEOF
47.  
48. @@ChingEnd:
49.  
50.   mov [testresult],esi
51. } ;---------------------------------------------

Результаты тестов:

1. Комп - P3 800, файл размером 1 701 209. Приводятся "average/return".

Mirror_40: 5 927 795 / 2 201 693*
Bars: 5 511 392 / 23 519
leo_60c: 6 433 674 / 47 123
Rabin_76: 9 165 107 / 224 440*
repnz_scasb: 12 515 354 / 47 123
SillyVariantOfChing: 8 713 661 / 47 123

* - отмечено когда "return" плавает (не разбирался - почему. Если нужно, можно попробовать понять. Файл не выложил так как это архив переписки почтового форума WASM.RU ;=).

Погрешность измерения специально не мерял, она составляет примерно +-200 000 .. +-100 000 (для разных алгоритмов).

2. Комп P4 1600, файл примерно 3 Мегабайта (точно счас не помню, он дома).

Mirror_40: 2 621 079 / 32 698
Bars: 2 715 433 / 32 698
leo_60c: 3 182 946 / 32 698
SillyVariantOfChing: 5 270 195 / 32 698

 

Chingachguk видимо результат и время получается неправильным, из-за того что код некорректно выходит из цикла.
Надо это проверить.

На файле нашем любимом файллеNumbers твой код выполняется в среднем за 42 млн тиков
Хотя результат вроде верный 999999

 

Протестировал на файле, скачанном с форума (numbers.dic 7876550 03.10.06 11:41).

Тестирование на P3 800.
cpuid(0)->eax=2,ebx:ecx:edx=756E6547h:6C65746Eh:49656E69h
cpuid(1)->eax=0686h,edx=0383F9FFh

Погрешность порядка ~100 000.

Mirror_40: 10 255 254 / 12 579 549
Bars: 25 509 201 / 500 002
leo_60c: 29 763 213 / 1 000 000
Rabin_76: 12 652 797 / 1 012 348
repnz_scasb: 87 823 114 / 1 000 000
SillyVariantOfChing: 44 740 201 / 1 000 000

 

Chingachguk
То что через / это я так понимаю возвращаемый результат.

Я бы мог согласиться с тобой, если бы ты нашел какой-то файл на котором результаты были бы неверны хоть я тестировал свой код на многих файлах.
Но Numbers.dic??
там у меня присутствует переменная Result она должна быть изначально равна 0. А у тебя видимо она просто объявлена как локальная неинициализированная. Хотя бог его знает. Но мой код и код Black Mirror на файле Numbers.dic выдают корректный результат. И ЭТО ПРОВЕРЕНО

Если кому-нибудь еще вообще еще интересна данная тема, то хочу с акцентировать ваше внимание вот на чем

Состязаться на малых объемах глупо так как счет идет на микросекунды.
Оптимизация имеет смысл только на больших объемах, где эти микросекунды перерастают в
секунды->минуты->часы
либо на том коде, который может вызываться несколько тысяч раз в секунду.
Но если уж такую процедуру когда-нибудь понадобиться вызывать несколько тысяч раз в секунду, то уж лучше сразу пересмотреть входные данные использовать вместо файла дерево какое-нибудь. Если это невозможно, то хотя бы его проиндексировать. Так можно поднять производительность куда лучше. Чем так извращаться.

Что же касается больших объемов данных, то здесь ограничивающий фактор - скорость ОЗУ.

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

При таком подходе скорость работы ОЗУ никогда не перепрыгнуть.
Я немного проработал с механизмом предсказывания строк. Алгоритм конечно получился не ахти какой.
Но все таки он пытается предсказывать положения символов 0Ah в файле.

Код (Text):

1. proc FindPeriod Buffer, MemSize
2.     uses ecx, edi, edx
3.     xor edx, edx
4.     mov al, 0Ah
5.     mov ecx, [MemSize]
6.     mov edi, [Buffer]
7.     repne scasb
8.     lea eax, [edi-1]
9.     cmp BYTE [eax], 0Ah
10.     cmovne eax, edx
11.     jne .lbEnd
12.     sub eax, [Buffer]
13. .lbEnd:
14. uses_end
15. ret
16. endp
17.  
18. proc CountLine Buffer, MemSize
19.     local Periods[100]: QWORD, Count: DWORD, CountLine: DWORD
20.     mov esi, [Buffer]
21.     mov ecx, [MemSize]
22.     xor ebx, ebx
23.     mov [Count], ebx
24.     mov [CountLine], ebx
25.     lea edi, [Periods] 
26.     jmp .lbFindPeriod
27.  
28. .lbCheckPeriod:
29.     mov eax, [edi+ebx*8]
30.     cmp ecx, eax
31.     jna .lbNextPeriod
32.     movzx edx, BYTE [esi+eax]
33.     cmp edx,0Ah
34.     je .lbFound
35.  
36. .lbNextPeriod:
37.     inc ebx
38.     cmp ebx, [Count]
39.     jne .lbCheckPeriod
40.  
41. .lbFindPeriod:
42.     test ecx, ecx
43.     je .lbEnd
44.     stdcall FindPeriod, esi, ecx
45.     test eax, eax
46.     je .lbEnd
47.     mov [edi+ebx*8], eax
48.     mov DWORD [edi+ebx*8+4], 0
49.     inc [Count]
50.     inc [CountLine]
51.     lea esi, [esi+eax+1]
52.     sub ecx, eax
53.     dec ecx
54.     xor ebx, ebx
55.     jmp .lbCheckPeriod
56.  
57. .lbFound:
58.     inc [CountLine]
59.     lea esi, [esi+eax+1]
60.     sub ecx, eax
61.     dec ecx
62.     inc DWORD [edi+ebx*8+4]
63.     test ebx, ebx
64.     je .lbNoChange
65.     mov edx, [edi+ebx*8+4]
66.     cmp edx, [edi+ebx*8-4]
67.     ja .lbChange
68.  
69. .lbNoChange:
70.     xor ebx, ebx
71.     jmp .lbCheckPeriod
72.  
73. .lbChange:
74.     mov eax, [edi+ebx*8-4]
75.     mov [edi+ebx*8-4], edx
76.     mov [edi+ebx*8+4], eax 
77.  
78.     mov eax, [edi+ebx*8]
79.     mov edx, [edi+ebx*8-8]
80.     mov [edi+ebx*8-8], eax 
81.     mov [edi+ebx*8], edx
82.     xor ebx, ebx
83.     jmp .lbCheckPeriod
84. .lbEnd:
85.     mov eax, [CountLine]
86. ret
87. endp

 

на файле Numbers.dic
результат получился в среднем 14мл тиков. Что вобщем не слишком-то хорошо по сравнению
с другими результатами.
Но здесь есть одно небольшое отличие эффективность данного алгоритма зависит от длины строк, чем длиннее
строки тем выше эффективность кода.

Чтобы вы не парились разбираясь что здесь к чему. Я опишу алгоритм

Переменная Periods представляет собой указатель на массив структур
struc Period
.Period DD ?
.Count DD ?
ends

Period хранит длину строки
Count - счетчик сколько раз строки с такой длиной встретились

Это, типа, попытка использовать стиль текстового файла в вычислениях

В начале работы алгоритма вызывается процедура FindPeriod, которая находит первый символ 0Ah
и замеряет длину строки. Дальше мы делаем предположение, следующая строка будет такой же длины.
Проверяем это. Если совпало, то увеличиваем счетчик периода. Если нет, то ищем новый период.
Тогда периодов становится два. И каждый раз, когда не совпадает один, проверяется другой.
В процессе работы новые периоды придется искать все реже, так как хотя бы один из массива обязательно да подойдет. Для ускорения доступа в процессе работы массив периодов сортируется по убыванию .Count. То есть периоды которые встречаются чаще всего в начале,а реже всего в конце.

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

Хотелось бы услышать ваше мнение

 

Miller Rabin

Если что - сорри, я тестировал на примере leo (выше). Вот мой слегка измененный вариант:

 

Miller Rabin

По поводу "интересно ли делать такую задачу". Мне кажецца, что - как только я увидел что лучшее время Ваших алгоритмов стремицца к времени цикла:

Код (Text):

1. @@CalcEOF:
2.   mov  eax,[edx]
3.   add edx,4
4.  
5.   loop @@CalcEOF

Т.е. к просто к чтению памяти - задача сводится к быстрой функции CalcBytesODhInDWORD. Лично для меня это неудобная задача Потому что комбинировать особо нечем А что делать?...

По поводу предсказания... Не знаю, но функция НИКОГДА НЕ МОЖЕТ СКАЗАТЬ ТОЧНЫЙ ОТВЕТ ПОКА НЕ ПОСМОТРИТ НА КАЖДЫЙ БАЙТ ХОТЯ БЫ 1 РАЗ...

 

Miller Rabin

Дык это от соотношения скоростей ядро/память зависит, техника меняется, а красивый алгоритм может эффективным и остаться, тут leo прав - не стоит от хорошего алгоритма отказываться только потому, что он обогнал современную память

В Help 2 вон всё переиндексировали ((
Скорость поиска есть, а произвольное слово фиг найдёшь...
По хорошему сначала индексный поиск для скорости, а затем если результат нулевой, то искать напрямую.

 

Chingachguk

У меня то нормальные (по кр.мере одинаковые) результаты все варианты выдают, и у тебя кстати на P4 тоже. А вот как ты умудряешься на P3 SSE2-код выполнять - непонятно ?! )

 

Chingachguk
Отвечаю на свой вопрос:

Теперь понятно Можно сказать "повезло", т.к. используемые SSE2 команды являются префиксными расширениями соответствующих MMX и для них действует правило

Отсюда и неверные результаты SSE2-вариантов на P3.
PS: Фича надо сказать неприятная, поэтому по жизни нужно проверять поддержку SSE2 по CPUID, или на крайняк вставлять инструкцию, обязательно вызывающую #UD на процах без SSE2, например PINSRW

Miller Rabin
Эко куда тебя понесло )
Во-первых, вопрос на засыпку: на сколько нужно прыгать (какой д.б. Period), чтобы получить (заметный) выигрыш во времени загрузки данных из ОЗУ ?
Дело в том, что данные читаются из ОЗУ в кэш всегда целыми линейками - 32 байта в P6-, 64 байта в P6+ и АМД, 128 байт в P4 (две линейки по 64). Поэтому, чтобы получить заметный выигрыш нужно перепрыгивать целые линейки иначе никакого выигрыша не будет или будет очень незначительный. Например, если читать только один байт или дворд из каждой линейки, то выигрыш м.б. максимум 10-15 % на P4 и чуть больше на P6+ и АМД и этот выигрыш обусловлен не тем, что меньше данных читается из ОЗУ (читается всё), а тем, что, во-первых, процессор может укрупнить пакеты чтения (запрашивать из ОЗУ сразу несколько линеек) и таким образом уменьшить относительные затраты на их инициализацию, во-вторых, мопов чтения становится меньше и переполнение очередей и остановка конвеера в ожидании данных из ОЗУ происходят реже

Во-вторых, раз "теоретически возможны случаи когда алгоритм проскочит строку", то этот алгоритм вероятностный и говорить о точном подсчете числа строк в файле не приходится. Хотя я честно говоря не понимаю для какой-такой практической задачи нужно (быстро) посчитать число строк в Х-мегабайтном файле. А вот приблизительно оценить число строк (например, для выделения массива указателей) можно и по части файла. И какой метод окажется точнее - твой поиск периодичностей или простая оценка по части файла - бабушка надвое сказала ))

 

Провел измерения на файле numbers.dic (numbers.dic 7876550) с форума, но уже на P4. Действительно, на нем все алгоритмы показали одинаковые ответы - 1 000 000 (leo был прав насчет этого... как его...SSE2). Ниже приведены результаты:

Algo / average / return / Approx mistake
leo_60c / 10 798 429 / 1 000 000 / +-400 000
Rabin_76 / 9 138 425 / 1 000 000 / +-50 000
Bars_69 / 9 531 404 / 1 000 000 / +-20 000
Mirror_40 / 9 184 707 / 1 000 000 / +-20 000
SillyVariantOfChing: 32 942 449 / 1 000 000 / +- 500 000
repnz_scasb: 95 133 949 / 1 000 000 / +-100 000

Погрешность померяна "на глазок".