Задачка о случайной модицикации массива бит

Вот какое безобразие получилось у меня:

Код (Text):

1. include '%fasminc%\win32ax.inc'
2.  
3. .data
4.  
5. t0 db       'alloc     '
6. ta db 13,10,'fill      '
7. tf db 13,10,'inc1      '
8. t1 db 13,10,'inc2      '
9. t2 db 13,10,'correct  Y'
10. ty db 0,0
11. time_10 dd 10
12. time_last dd ?
13. am dd 1
14. a dd ?
15. b dd ?
16.  
17. .code
18.  
19. time:
20.     invoke GetTickCount
21.     sub eax,[time_last]
22.     add [time_last],eax
23.     mov ecx,[esp+4]
24.     jecxz .exit
25. .loop:
26.     xor edx,edx
27.     div [time_10]
28.     add dl,'0'
29.     dec ecx
30.     mov [ecx],dl
31.     test eax,eax
32.     jnz .loop
33. .exit:
34.     ret 4
35.  
36. rdall:
37.     mov edx,[esp+4]
38.     mov ecx,[esp+8]
39. .loop:
40.     mov eax,[edx]
41.     add edx,4096
42.     loop .loop
43.     ret 20
44.  
45. fill:
46.     mov edi,[esp+4]
47.     mov ecx,[esp+8]
48.     mov eax,[esp+12]
49. .loop:
50.     stosd
51.     mul dword [esp+16]
52.     add eax,dword [esp+20]
53.     loop .loop
54.     ret 20
55.  
56. inc0:
57.     mov edi,[esp+4]
58.     mov esi,[esp+8]
59.     mov ecx,[esp+12]
60.     xor edx,edx
61. .loop:
62.     lodsd
63.     btr [edi],eax
64.     adc edx,0
65.     loop .loop
66.     ret 12
67.  
68. inc1:
69.     mov edi,[esp+4]
70.     mov esi,[esp+8]
71.     mov ecx,[esp+12]
72.     xor edx,edx
73. .loop:
74.     lodsd
75.     bts [edi],eax
76.     adc edx,0
77.     loop .loop
78.     ret 12
79.  
80. MaxA=100000000h
81. MaxB=  8000000h
82. CCLine=64
83. NLine=8
84. CLine=CCLine*NLine
85. o1=CLine-(CLine-4)/3*3
86. o2=CLine-(CLine-4)/2*2
87. Total=MaxA/8+MaxB*4
88.  
89. inc2:
90. ;подготовка массива sp1, для разбиения элементов B на 256 списков по старшему байту
91.     mov edi,sp1
92.     mov eax,sb1+o1
93.     mov ecx,256
94. .f1:
95.     stosd
96.     add eax,CLine
97.     loop .f1
98.  
99.     mov esi,[esp+8]     ;B
100.     lea ebp,[esi+o1]    ;указатель на свободный блок
101.     mov ecx,[esp+12]    ;N
102.     jmp .c0
103. .s0:
104. repeat NLine
105.     mov ebx,[esi+CLine+(%-1)*CCLine]     ;цикл был разбит для организации предварительной выборки, но малоэффективно
106. end repeat
107.     mov ebx,CLine/4
108. .s1:
109.     movzx edx,byte [esi+3]  ;B[i]>>24
110.     mov eax,[esi]       ;B[i]
111.     mov edi,[sp1+edx*4] ;указатель на начало свободного места в списке sp1[B[i]>>24]
112.     lea esi,[esi+4]     ;i++
113.     mov [edi-4],eax     ;-4 потому что в конец блока еще указатель на следующий нужно положить
114.     lea edi,[edi+3]     ;+3 потому что старший байт B[i] нам не нужен, его из номера списка можно вытащить
115.     lea eax,[ebp+CLine] ;вычисление адреса следующего свободного блока, на случай если текущий потребуется выделить
116.     test edi,CLine-1    ;если место в блоке закончилось
117.     mov [edi-4],ebp     ;на самом деле это нужно только когда блок заполнен, но чтобы не делать проверку
118.     cmovz edi,ebp       ;выделение нового блока
119.     cmovz ebp,eax       ;обновление указателя на свободный блок
120.     sub ebx,1
121.     mov [sp1+edx*4],edi ;обновление указателя на конец списка
122.     jnz .s1
123. .c0:
124.     sub ecx,CLine/4
125.     ja .s0
126.     add ecx,CLine/4
127. .s9:
128.     movzx edx,byte [esi+3]
129.     mov eax,[esi]
130.     mov edi,[sp1+edx*4]
131.     lea esi,[esi+4]
132.     mov [edi-4],eax
133.     lea edi,[edi+3]
134.     lea eax,[ebp+CLine]
135.     test edi,CLine-1
136.     mov [edi-4],ebp
137.     cmovz edi,ebp
138.     cmovz ebp,eax
139.     sub ebx,1
140.     mov [sp1+edx*4],edi
141.     loop .s9
142.  
143.     mov esi,sb1+o1      ;перебираем списки первого уровня
144.     mov ebx,0       ;индекс i1
145.  
146. .s2:
147.     push esi
148. ;подготовка массива sp2, для разбиения списков первого уровня по второму байту
149.     mov edi,sp2
150.     mov eax,sb2+o2
151.     mov ecx,256
152. .f2:
153.     stosd
154.     add eax,CLine
155.     loop .f2
156. ;esi - текущий элемент
157.     lea ebp,[esi-o1+o2] ;указатель на первый свободный блок, берутся из обработанных элементов списка
158.     jmp .c3
159. .s3:
160.     movzx edx,byte [esi-2]  ;чтение старшего байта
161.     mov ax,[esi-4]      ;чтение двух младших байт
162.     mov edi,[sp2+edx*4] ;загрузка указателя на список-приёмник
163.     lea esi,[esi+3]     ;удаление прочитанного элемента
164.     mov [edi-4],ax      ;сохранение двух байт
165.     test esi,CLine-1    ;если читаемый блок закончился
166.     lea edi,[edi+2]
167.     jnz .n1
168.     mov esi,[esi-4]     ;следующий блок для чтения
169. repeat 1;NLine
170.     mov eax,[esi-o1+(%-1)*CCLine]   ;что-то вроде предварительной выборки
171. end repeat
172. .n1:
173.     test edi,CLine-1    ;если записываемый блок закончился
174.     mov eax,[ebp-o2+CLine-4];следующий свободный блок
175.     mov [edi-4],ebp     ;сохранение указателья на следующий блок
176.     lea eax,[eax-o1+o2] ;коррекция указателя если o1 != o2
177.     jnz .n2
178.     mov edi,ebp     ;выделение нового блока для записи
179.     mov ebp,eax     ;обновление указателя на свободный блок
180.     mov eax,[eax-o2]          ;тоже что-то вроде предварительной выборки
181. .n2:
182.     mov [sp2+edx*4],edi ;обновление указателя записи
183. .c3:
184.     cmp esi,[sp1+ebx*4] ;проверка не достигли ли конца списка
185.     jnz .s3
186. ;обработка всех списков второго уровня и установка бит в массиве A
187.     mov edi,[4+esp+4]   ;A
188.     mov esi,sb2+o2
189. .s4:
190.     movzx ebp,bh
191.     push esi
192.     bswap ebx
193.  
194. ;Предварительная выборка блока массива A, тоже почему-то малоэффективна
195.     mov edx,ebx
196.     sar edx,3
197.     add edx,edi
198.     mov ecx,8192/CLine
199. .pf:
200.     mov eax,[edx]
201.     lea edx,[edx+CLine]
202.     loop .pf
203.  
204.     jmp .c5
205. .s5:
206.     mov ecx,ebx     ;два старших байта индекса
207.     mov eax,1
208.     mov cx,word [esi-4] ;добавление к ним младших
209.     lea esi,[esi+2]     ;переход к следующему элементу
210.     shl eax,cl
211.     sar ecx,5
212.     or [edi+ecx*4],eax  ;установка
213.     ;bts [edi],ecx
214.     test esi,CLine-1    ;если конец блока
215.     jnz .n3
216.     mov esi,[esi-4]     ;переход к следующему
217. repeat 1;NLine
218.     mov eax,[esi-o2+(%-1)*CCLine]   ;что-то вроде предварительной выборки
219. end repeat
220. .n3:
221. .c5:
222.     cmp esi,[sp2+ebp*4] ;проверка на конец списка
223.     jnz .s5
224.     xor bx,bx
225.     pop esi
226.     bswap ebx
227.     inc bh
228.     lea esi,[esi+CLine]
229.     jnz .s4
230.  
231.     pop esi
232.     inc bl
233.     lea esi,[esi+CLine]
234.     jnz .s2
235.  
236.  
237.     ret 12
238.  
239. start:
240.     invoke GetCurrentProcess
241.     invoke SetPriorityClass,eax,REALTIME_PRIORITY_CLASS
242.     invoke GetCurrentThread
243.     invoke SetThreadAffinityMask,eax,am, eax,THREAD_PRIORITY_TIME_CRITICAL
244.     invoke SetThreadPriority
245.  
246.     stdcall time,0
247.     invoke VirtualAlloc,0,Total,MEM_COMMIT,PAGE_READWRITE
248.     mov [b],eax
249.     add eax,MaxB*4+MaxA/16
250.     mov [a],eax
251.     stdcall rdall,[b],Total/4096
252.     stdcall time,ta
253.     stdcall fill,[b],MaxB,12345,134775813,1
254.     stdcall time,tf
255.     stdcall inc2,[a],[b],MaxB
256.     stdcall time,t2
257.     stdcall fill,[b],MaxB,12345,134775813,1
258.     stdcall time,0
259.     stdcall inc0,[a],[b],MaxB
260.     cmp edx,MaxB
261.     jz .cor
262.     mov [ty-1],'N'
263. .cor:
264.     stdcall time,t1
265.     invoke MessageBox,0,t0,"time in ms",0
266.     invoke ExitProcess,0
267.  
268. .data
269.  
270. sb1 rb 256*CLine
271. sb2 rb 256*CLine
272. sp1 rd 256
273. sp2 rd 256
274.  
275. .end start

Тестировалось на ноуте с процессором C2D T9400. Частота ядра 266x9.5=2.53ГГц, памяти 400 МГц, L1=32K+32K(на каждое ядро), L2=6M, обмен блоками по 64 байта. Результаты получились следующие: inc1 - 6.5c, inc2 - 1.95c. В общем ускорение более чем в 3 раза. Если кому лень читать исходник, то смысл такой: разбиваем массив B по старшему байту а 256 списков, в списки включаем только младшие 3 байта, потом каждый список разбиваем на 256 списков уже по сторому байту, ну а дальше берем элементы списков и устанавливаем нужные биты. Правда с предварительной выборкой у меня как-то не очень получилось, и метки выравнивать было лень.

 

А если за первый проход раскидать индексы из B по подмассивам, а затем уже обработать их последовательно? (O(2^27)?)
Если все подмассивы влезут в кэш то не должно тормозить....

 

PSR1257
Идея весьма интересная, правда придётся использовать дополнительно почти столько же памяти сколько занимает массив B, и делать дополнительные проходы чтобы узнать какого размера нужны подмассивы. Но операций в циклах должно стать меньше, да и предвыборка должна упроститься.

 

гы. достаточно просто отсортировать B чтобы свести к минимуму перечитывание A в кэш. но я так понял, весь цимис именно в работе с неотсортированным B на больших полях. хотя последние примеры говорят, что от безсортировки уже оказались

Serg50
все верно. там OR а не AND. но что вы хотите от меня, бегинера в асме и в проганьи вообще.

 

Black_mirror

Еще пара соображений. Промежуточные сбросы буферов в процессе первого и единственного прохода.

Допустим, мы начинаем в первом (и единственном) проходе скидывать указатели из B в подмассивы, например по старшему байту. В среднем на каждый такой подмассив нужно ~2^27/2^8~2^19 элементов, но мы будем выделять (допустим) только фиксированные куски только по 2^16 элементов и еще счетчики элементов для каждого из подмассивов (2^8 подмассивов и 2^8 счетчиков).

Все счетчики сначала сбрасываются в 0 и являются циклическими 0xFFFF. Как только на некотором элементе B[] мы обнаруживаем заполнение подмассива с данным старшим байтом - мы останавливаемся и сбрасываем его на конечный массив (при этом очевидно адресуя 2^24 бит или всего 2^16 байт что должно влезть в кэш).

На финальной стадии придется добить подмассивы...

 

PSR1257
Что-то с массивами у меня как-то плохо получается, на домашнем атлоне почему-то один только первый проход занимает больше времени, чем все три прохода в версии со списками. Возможно что массивы получились слишком одинаковой длины и при записе сразу 256 массивов возникают конфликты строк кеша. Может есть смысл дробить не по байтам, а по тетрадам.

 

Black_mirror
А вообще заполнение конечного массива по _упорядоченным_ указателям что-то дает? Т.е. какая разница если заполнять по рандомным указателям (лучше даже для контраста не рандомным а нарочито плохим для кэша - например каждый следующий указатель адресует элемент заведомо за пределами кэша) - и по сортированным?

Это я про то чтобы не потратить много времени на плохую версию

 

PSR1257
В варианте со списками было 1.95 секунд и 6.5 при случайном заполнении. Вообще когда я мерял скорость доступа к памяти и кешам у меня получилось 12Гб/c для L1, 6Гб/с для L2 и 3Гб/с для памяти при последовательном чтении или записи. В теории нам нужно прочитать массив B, раскидать его в 256 массивов. Это 512М/3G+512/3G*2(потому что куда раскидываем тоже нужно прочитать, видимо нужно будет movntq использовать), далее нужно прочитать все 256 массивов, разбить каждый еще на 256, это добавит еще 512M/3G+512M/6G*2(потому что нам не обязательно дробить сразу все 256 массивов, а 512/256 прекрасно помещается в L2 и скорость чтения здесь выше, про пользу movntq здесь сказать затруднительно), потом их все прочитать и установить биты в массиве A, это даст еще 512M/6G+512M/3G*2, то есть в сумме получается 512М/3G+512/3G*2+512M/3G+512M/6G*2+512M/6G+512M/3G*2=512M*(6/3G+3/6G)=1.25c, и еще 1/6 секунды можно выиграть за счёт вашей идеи сначала накапливать строки в кеше, а потом в основную память выгружать. Так же можно еще чуть выиграть за счёт усечения индексов, тогда придётся немного меньше читать и записывать. Но возможно, что процессор уже просто не успевает слишком большое количество команд выполнить, и фокусы с памятью нам ничем не помогут.

 

Black_mirror

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

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

Глядя на приведенные цифры я б хотел надеяццо на 12Гб/сек при сбросе текущего накопленного буфера _малого_ размера, но, видимо, это нереально?

Если можно - даже сырые - исходники, я б попробовал повозиццо или хотя бы посмотреть. (if it is not secret, for sure).

 

до того, как начать чтото бить, попробовал просто предварительно посортировать B.
результат - 1.1с против 25с в исходном алгоритме Black_mirror. (тестовый алг - страницей раньше. только дополненый после заполнения B qsort-ом)
имхо, соревноваться надо с этими цифрами, так как одна только беготня по памяти при разбиениии на блоки сожрет времени больше чем стандарный qsort (который можно и оптимизировать. например, вынеся из библиотеки в основной модуль и избавившись от функции сравнения)

 

qqwe

Не очень понял - 25 секунд работает с неотсортированным, но если его предварительно отсортировать - то сучественно меньше (время сортировки не учитывается?)?.

 

qqwe
Что-то не понял, это вы только время установки битиков оцениваете или это вместе со временем сортировки? А на какой системе?

 

PSR1257

Black_mirror

нет, это просто сравнение времени выполнения алгоса из поста #1 при неотсортированном и отсортированном B.

время работы стандартной МСВС qsort довольно велико - в данном случае и на моей системе - 60c. но кто сказал, что стандартная рантаймовая функция тут оптимальна?
a) переход и возврта на головном вызове.
б) по переходу и возврату на каждом сравнении.
в) остальные моменты там тоже реализованы с оглядкой на универсальность, а не на скорость для данного конкретного случая.

кроме того, почему бы не объединить заполнение B с его сортировкой? (например, тем же методом таблиц. хотя чтото мне говорит, что в вопросе топика как раз оптимизация по скорости сортировки массива B методом таблиц и имеет место. ладно, пойду дальше тупить в свое, ато и вам мешаю, и свое не делаю пока вам мешаю)

во всех случаях система - туриончик х2 на 2гц (иногда почемуто не сразу разгоняется и довольно долго прет на 800мгц) в 32х битной моде под 32xpsp3. памяти 3 гб. кэша 2 - 512кб на ядро (чето экономит амд на кэше)

 

Еще небольшое улучшение для алгоритма со списками блоков - записывать в каждый блок одинаковое число элементов, несмотря на то что после каждого разбиения размер элемента уменьшается на 1 байт. Это позволит сравнять скорость чтения и записи, и освободившиеся блоки будут сидеть в кеше, пока их не выделим для одного из списков. Правда на атлоне выигрыш составил всего 0.5 секунды от 4.6, которые были до оптимизации, и вообще такое ощущение что бонусы есть только от L2. В понедельник попробую на C2D посмотреть что будет.