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

leo
Интересно, у тебя твой 3й вариант от последнего варианта cresta почти не отличается по скорости, у меня же они отличаются на 3 млн и на АМД, и на ПМ. Почему? Думаю, надо подключать код к wintest

 

IceStudent

Моему коду скорее подойдут длинные строки, чем такие короткие как в твоем файле. Все-таки за один проход проверяется сразу 4 байта. Чем длиннее строка, тем реже будет происходить промах мимо "нахождения 0Ah во второй паре проверяемых байт" и соот-но реже будет выполняться вторая половина кода (после первого jz) которая отбрасывает указатель назад на 2 байта.

А чем до сих пор мерял?

leo
Нет, твой код на атлоне не тормознее в два раза чем на пнях. Просто понятия тика различаются.
О нестабильности: у меня все коды выдают нестабильность в пределах 2-3 млн. Это не в самих кодах дело. На малых файлах (до значений порядка 200000 тиков) никаких нестабильностей нет. Она возникает при большом размере файла. Винда не выделяет достаточного количества времени коду одним куском, и вынуждена переключаться на другие задачи. И вклинивает свои дела в счётчик. Дела разные, и результаты разные.
Я всегда беру наименьший результат, там где винда меньше всего отвлекается на посторонние дела.

 

IceStudent
Хе-хе, ну и файл ты подсунул - просто идеальные условия для кода cresta Мало того, что строки упорядочены по возрастанию длины, так еще и 90% файла состоит из строк длиной 6 символов + 2 на 0D0Ah, итого 8 - просто идеально, первый jz стабильно срабатывает через раз, второй всегда выполняется и никаких промахов и штрафов - замечательно

cresta

Я имел ввиду, что все твои цифры на AthlonXP существенно больше, чем на P4, PM и Athlon64, хотя последний по архитектуре практически не отличается от AthlonXP, поэтому дело скорее всего в скорости чтения данных из памяти

Нестабильность нестабильности рознь - когда проскакивает 0-1-2 завышенных значения из 10-ти это одно. Но когда результаты скачут внутри каждой серии, да еще почему-то на одном коде, а на других нет, то объяснить это происками винды сложно, скорее всего это какие-то прибамбасы с предсказанием переходов Причем 13-15 млн тиков на 1.8ГГц это менее 8мс, т.е. меньше половины кванта да еще и с real-time приоритетом

PS: Кстати, твой код не расчитан на символы табуляции - одиночные посчитает наравне с разделителями строк, а сдвоенные будет считать за один

 

Про 09h я знаю, но в файле их нет, поэтому закрыл на это глаза. Кстати, код также реагирует на ноль (конец файла). Если учитывать и табуляцию, то заодно можно учесть и ноль. Это избавляет от необходимости постоянно проверять счетчик байт (ecx). И сам счётчик не нужен вообще. В одном (09h) теряем, в другом (0) приобретаем.
Даже если сделать определение, какой символ сработал (09, 0A или 0), путем примитивного
cmp ...0A
jcc
cmp ...09
jcc
end
получается практически те же 31-32 млн тиков.

Но это всё меркнет на фоне такого кода:

Код (Text):

1.             mov     edi,hMemory
2.             xor     eax,eax
3.          _start:
4.             inc     edi  
5.             cmp     byte ptr[edi],0Ah
6.             jg      _start
7.             jl      _zero
8.             inc     eax
9.             jmp     _start
10.          _zero:
11.             cmp     byte ptr[edi],0
12.             jne     _start

Самый тупой и прямолинейный. Был сделан чисто для контроля правильности подсчета количества строк. Результат этого кода 33 млн тиков. Т.е. он уступает всем нашим наворотам максимум 10%.
Спрашивается, какого чёрта мы тут оптимизируем? Из-за несчастных нескольких процентов такой сыр-бор развели ))

 

Не совсем. Твой предыдущий вариант в 2.7 раза быстрее. Другое дело, что у тебя он почти не отличается от 1 варианта leo..

 

Перенёс на wintest. AMD64. (Наконец тема перелистнулась)

Эх, опечатка закралась. Читалось 12 тыс строк

Утром сделаю результаты.

 

cresta
Похоже ты зациклился на своем древнем атлоне с тормозным ОЗУ
Сравни разные варианты, когда данные на 100% умещаются в кэше и почувствуй разницу
А если данных в кэше нет, то начинает влиять скорость их поступления из ОЗУ и если она меньше скорости исполнения кода, то как ты не извращайся, а все варианты у тебя нивелируются и будут давать твои +-10%. Но на других процах, ОЗУ тормозит меньше и разница получается значительно больше

IceStudent
А почему цифры маленькие, где знакомые десятки миллионов ?
Или ты решил исключить влияние ОЗУ и потестить на малых dwSize

 

IceStudent
В моём коде esi на самом деле должен быть выровнен на 64 (а не на 8 как написано в комментарии).

 

Можете смыть ваши мозги в унитаз.

Код (Text):

1.  mov esi,УказательНаПамятьСПрочитаннымФайлом
2.   mov ecx,[dwSize]
3.   shr ecx,2
4.   xor edx,edx
5.   xor ebx,ebx
6. Цикл:
7.   mov eax,dword[esi]
8.   add esi,4
9.   sub eax,0e000000h
10.   adc edx,ebx
11.   sub ah,0eh
12.   adc edx,ebx
13.   sub ecx, 1
14.    jnz Цикл

Я как всегда лидер. Всем спать.

 

izebars
Вообще-то для получения случайного числа достаточно одной команды rdtsc...
Ты бы для разнообразия извлёк свои мозги (где ты там говоришь их хранишь?) и посмотрел, что за результат твой код выдаёт на реальном файле.

 

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

могут ли 0D либо 0A появляться отдельно ? если нет то простое и быстрое решение очевидно

>> для получения случайного числа достаточно одной команды rdtsc

это не верно rdtsc выдает не рандом а счетчик тактов

 

Пожалуйста с кодом, дающим правильное количество строк на реальном текстовом файле, и реально обгоняющий ранее описанное )
Там был вариант который один символ ищет, а второй проверяет только если первый найден, соответственно тормоза от этого в % не столь велики.

Спасибо - просветил )) но есть тонкость: что результат rdtsc, что кода от izebars совсем не похож на количество строк в файле ))

 

не вижу смысл писать код пока не ясны входные условия
а решение тут многие напишут если выкинут из своего кода лишнее

 

fr0b-p

ты абсолютно прав
Y_Mur
Ну ты сейчас всех поразил своей тупостью. Знаешь почему IceStudent, leo, cresta, Black_mirror молчат. Так это, потому что они на порядок выше, чем ты и c легкостью разобрались в нем.
Для тебя я все уясню подробней:
1)создаеш asm файл, открываешь его в FASM, копируеш код приведенный ниже.
2)в ту же директорию суешь любой текстовый файл с именем 'ТекстовыйФайл.txt'
3)компилируешь его
4)ставишь прерывание на функцию ret в отладчике, и запускаешь.
5)после чего в edx получится шестнадцатеричное число количества строк.
(если не знаешь как перевести шестнадцатеричное в десятеричное см. мультфильм 38 попугаев)

Код (Text):

1. format PE GUI 4.0
2. include 'win32a.inc'
3.        mov esi,УказательНаПамятьСПрочитаннымФайлом
4.        mov ecx,[dwSize]
5.        shr ecx,2
6.        xor edx,edx
7.        xor ebx,ebx
8. Цикл:  mov eax,dword[esi]
9.        add esi,4
10.        sub eax,0e000000h
11.        adc edx,ebx
12.        sub ah,0eh
13.        adc edx,ebx
14.        sub ecx, 1
15.        jnz Цикл
16.        ret
17. УказательНаПамятьСПрочитаннымФайлом file 'ТекстовыйФайл.txt'
18. dwSize dd $-УказательНаПамятьСПрочитаннымФайлом

И ваще запомни на будущее: ищи ошибки в себе, а не в других.
Если захочешь напишу еще подробнее.

 

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

 

чувствуется пид... эээ лидер, ага

не, лучше поподробнее про архиватор, сжимающий все круче всех

 

Сам код действительно неплох: ~8,6 млн тиков на атлоне. Самый быстрый был у leo (~12 млн тиков).
Чего не скажешь об авторе - правила форума игнорирует начисто

 

masquer
Я уже давал комментарии по поводу архиватора, только модератор её удалил, наверно не любит рекламу. Там было написано, что любому желающему, в том числе и для вас, я могу предоставить уникальную возможность, совершенно бесплатно, испробовать демо-версию моего архиватора. Его отличия от полной версии это всего лишь то, что он не разжимает. Но зато для любых файлов или дисков обладает поразительным архивированием, гораздо лучшим, чем в оригинале, превосходящим любые архиваторы созданные когда-либо в мире, сжимает ровно до 0 байт.

 

izebars
А реклама запрещена здесь. Тем более, ты вряд ли предоставишь полную версию, которая сможет распаковать этот файл.

 

SSE2 решает!

Код (Text):

1. strs:;(buf +4, len +8)
2.         movdqu xmm7,dqword [.eol]
3.         pxor xmm6,xmm6
4.         mov edx,[esp+4]
5.         mov ecx,[esp+8]
6.         push ecx
7.         shr ecx,11
8.         jz .l1
9.     .l0:
10.         push ecx
11.         mov ecx,64
12.         call .loop
13.         pop ecx
14.         loop .l0
15.     .l1:
16.         pop ecx
17.         push ecx
18.         shr ecx,5
19.         and ecx,3Fh
20.         jz .l2
21.         call .loop
22.     .l2:
23.         pop ecx
24.         xor eax,eax
25.         and ecx,31
26.         jz .l5
27.     .l3:
28.         cmp byte [edx],13
29.         jnz .l4
30.         inc eax
31.     .l4:
32.         inc edx
33.         loop .l3        
34.     .l5:
35.         sub esp,16
36.         movdqu [esp],xmm6
37.         pop edx
38.         add eax,edx
39.         pop edx
40.         add eax,edx
41.         pop edx
42.         add eax,edx
43.         pop edx
44.         add eax,edx
45.         ret 8
46.     .loop:
47.         pxor xmm5,xmm5
48.         pxor xmm4,xmm4
49.     .loop_1:
50.         movdqu xmm0,[edx]
51.         movdqu xmm1,[edx+16]
52.         add edx,32
53.         pcmpeqb xmm0,xmm7
54.         pcmpeqb xmm1,xmm7
55.         psubb xmm5,xmm0
56.         psubb xmm4,xmm1
57.         loop .loop_1
58.         paddb xmm5,xmm4
59.         pxor xmm0,xmm0
60.         movdqa xmm4,xmm5
61.         punpckhbw xmm5,xmm0
62.         punpcklbw xmm4,xmm0
63.         paddw xmm5,xmm4
64.         movdqa xmm4,xmm5
65.         punpckhwd xmm5,xmm0
66.         punpcklwd xmm4,xmm0
67.         paddd xmm6,xmm5
68.         paddd xmm6,xmm4
69.         ret
70.     .eol dd $0D0D0D0D,$0D0D0D0D,$0D0D0D0D,$0D0D0D0D