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

Тема в разделе "WASM.A&O", создана пользователем Black_mirror, 9 мар 2010.

  1. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Вот какое безобразие получилось у меня:
    Код (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 списков уже по сторому байту, ну а дальше берем элементы списков и устанавливаем нужные биты. Правда с предварительной выборкой у меня как-то не очень получилось, и метки выравнивать было лень.
     
  2. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    А если за первый проход раскидать индексы из B по подмассивам, а затем уже обработать их последовательно? (O(2^27)?)
    Если все подмассивы влезут в кэш то не должно тормозить....
     
  3. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    PSR1257
    Идея весьма интересная, правда придётся использовать дополнительно почти столько же памяти сколько занимает массив B, и делать дополнительные проходы чтобы узнать какого размера нужны подмассивы. Но операций в циклах должно стать меньше, да и предвыборка должна упроститься.
     
  4. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    гы. достаточно просто отсортировать B чтобы свести к минимуму перечитывание A в кэш. но я так понял, весь цимис именно в работе с неотсортированным B на больших полях. хотя последние примеры говорят, что от безсортировки уже оказались

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

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Black_mirror

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

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

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

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

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    PSR1257
    Что-то с массивами у меня как-то плохо получается, на домашнем атлоне почему-то один только первый проход занимает больше времени, чем все три прохода в версии со списками. Возможно что массивы получились слишком одинаковой длины и при записе сразу 256 массивов возникают конфликты строк кеша. Может есть смысл дробить не по байтам, а по тетрадам.
     
  7. PSR1257

    PSR1257 New Member

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

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

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    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 секунды можно выиграть за счёт вашей идеи сначала накапливать строки в кеше, а потом в основную память выгружать. Так же можно еще чуть выиграть за счёт усечения индексов, тогда придётся немного меньше читать и записывать. Но возможно, что процессор уже просто не успевает слишком большое количество команд выполнить, и фокусы с памятью нам ничем не помогут.
     
  9. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Black_mirror

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

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

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

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

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    до того, как начать чтото бить, попробовал просто предварительно посортировать B.
    результат - 1.1с против 25с в исходном алгоритме Black_mirror. (тестовый алг - страницей раньше. только дополненый после заполнения B qsort-ом)
    имхо, соревноваться надо с этими цифрами, так как одна только беготня по памяти при разбиениии на блоки сожрет времени больше чем стандарный qsort (который можно и оптимизировать. например, вынеся из библиотеки в основной модуль и избавившись от функции сравнения)
     
  11. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    qqwe

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

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    qqwe
    Что-то не понял, это вы только время установки битиков оцениваете или это вместе со временем сортировки? А на какой системе?
     
  13. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    PSR1257
    Black_mirror
    нет, это просто сравнение времени выполнения алгоса из поста #1 при неотсортированном и отсортированном B.

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

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

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

    Black_mirror Active Member

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