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

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

  1. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Имеется массив A размером 2^32 бит(512Мбайт). Массив индексов B размером N=2^27. Генератор псевдослучайных чисел которыми заполняется массив B. Возьмём такой: B[0]=12345, B[n+1]=B[n]*134775813+1, но вообще считаем что числа в массиве B случайные равномерно распределённые. Требуется написать оптимизированную по скорости функцию, которая установит в массиве A все биты, индексы которых есть в массиве B. Функция может использовать всю оставшуюся память(можно выделять до вызова функции), может портить массив B. Ну а сравнивать будем с таким дубовым кодом:
    Код (Text):
    1.   mov edi,A+10000000h
    2.   mov esi,B
    3.   mov ecx,N
    4. .loop:
    5.   lodsd
    6.   bts [edi],eax
    7.   loop .loop
     
  2. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    А EDI инкрементировать :)

    Правильно ли я понял задачу: битовый массив должен быть случайным образом заполнен с условим, что в каждом двойном слове будет выставлен 1 бит?

    Если да, то я бы убрал LODSD, LOOP и BTS :) BTS можно заменить AND/MOV - сделать табличку из 32 однобитовых DWORD, а случайные числа использовать после AND 1Fh как индексы к ней - ведь значение емеют только нижние 5 бит.

    Если я правильно понял могу нарисовать подробнее.
     
  3. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Serg50
    Задачка не в том чтобы случайно заполнить массив A, а в том чтобы установить все биты, индексы которых берутся из массива B. И bts тут не самое тормозное зло.
     
  4. Medstrax

    Medstrax Забанен

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    673
    Пара вопросов.
    1)"размером 2^32 бит(512Мбайт)" ошибка или я что то не понимаю?
    2) Мне неясно понятие "все биты, индексы которых есть в массиве B". Можно уточнить?
     
  5. PSR1257

    PSR1257 New Member

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

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    medstrax1
    Если бы массив A к примеру из char, то требовалось бы оптимизировать следующий код:
    for(int i=0;i<N;i++) A[B]=1;
    Но в массиве лежат биты по 8 штук в байте, поэтому размер массива A - 512Мбайт.
    Вообще посмотрите описание инструкций bts/btr/btc, тогда будет более понятно как они там лежат.

    PSR1257
    Весь прикол задачи в том и состоит что массив B никак не сортированный, но никто не требует устанавливать биты в порядке определяемом массивом B.
     
  7. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Был неправ - без использования BTS хуже:)
    На маленьком массиве(2000h/4 индексов - я мерял ticks) твой код(c добавлением ADD EDI, 4) дал у меня 19300. То о чем я думал дало 13100, но это вероятно за счет кэша. Как только массив был увеличен - результаты стали примерно вдвое хуже чем у твоего кода. Ведь у меня есть еще одно обращение к памяти.
    Относительно LOOP - его замена на DEC ECX/JNZ @B влияет положительно: с 19300 до 17200. А вот LODSD влияет мало - замена на MOV EAX, [ESI]/ADD ESI, 4 улучшает, но совсем чуть чуть, почти незаметно. Практически тоже время дает использование индексации типа BTS [EDI+4*ECX], EAX.
    Кстати если EAX вылезает за пределы 0-1Fh у меня генерировалась ошибка, так что случайные числа я подрезал заранее.
     
  8. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Serg50
    Случайные числа подрезать нельзя, они могут принимать любое из 2^32 значений. Попробуй для начала понять код из первого сообщения, а потом исправлять "ошибки".
     
  9. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Каюсь. Признаюсь в некомпетентности. Достаточно :)?
    Я практически никогда не имел дело с BTS и заинтересовался, что-бы понять получше как она работает. У меня было заблуждение, что выставляется/анализируется бит в пределах адресуемого. Сейчас еще почитал, проверил, и понял что это не так:) И инкрементировать EDI не надо.

    Насчет подрезать я не настолько уверен. В небольших массивах это делать надо, именно оттуда у меня и возникала ошибка. В твоем случае твой массив если я правильно посчитал покрывает все значения EAX. Однако я проверил, и увидел, что команда интерпретирует EAX как знаковое число, и EAX = -1 ставит бит до начал массива. То есть по крайней мере число должно быть положительным.
     
  10. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Еще раз каюсь, за невнимательность! Я понял смысл A+10000000h:)
     
  11. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    Black_mirror
    тестовый код для вашего примера
    Код (Text):
    1. #include <time.h>
    2. #include <stdio.h>
    3.  
    4. #define _CRT_RAND_S
    5. #include <stdlib.h>
    6.  
    7.  
    8. #define TESTS_N 1
    9.  
    10. #define maxA 0x20000000 // (2^32)/8
    11. #define maxB 0x8000000  // 2^27
    12.  
    13. char A[maxA];
    14. int  B[maxB];
    15.  
    16.  
    17. int main()
    18. {
    19.   unsigned int tmp;
    20.   int i, j;
    21.   static clock_t t;
    22.   clock_t t0, t_all, t_max;
    23.  
    24.   t_max = t_all = 0;
    25.  
    26.   for(j = 0; j < TESTS_N; j++){
    27.     printf("- %d\n", j);
    28.  
    29.     for(i = 1; i < maxB; i++){
    30.       rand_s(&tmp);
    31.       B[i] = tmp;
    32.     }
    33.     B[0] = 0;
    34.  
    35.     __asm pusha;
    36.     t0 = clock();
    37.     __asm{
    38.        lea edi,[A+10000000h]
    39.        lea esi,[b]
    40.        mov ecx,maxB
    41.     }
    42. loop_:
    43.     __asm{
    44.       lodsd
    45.       bts [edi],eax
    46.       loop loop_
    47.     }
    48.     t = clock();
    49.     __asm popa;
    50.     t -= t0;
    51.  
    52.     t_all += t;
    53.     if(t > t_max)
    54.       t_max = t;
    55.   }
    56.  
    57.   printf("max time = %.4fs, avg time = %.4fs\n",
    58.               ((double)t_max)/(double)CLOCKS_PER_SEC,
    59.               ((double)t_all/(double)TESTS_N)/(double)CLOCKS_PER_SEC
    60.         );
    61.  
    62.   return 0;
    63. }
    компилилось без оптимизации. показало время ~ 25c

    первое что пришло в голову (может и неправильный алгос. не проверял)
    Код (Text):
    1. #include <time.h>
    2. #include <stdio.h>
    3.  
    4. #define _CRT_RAND_S
    5. #include <stdlib.h>
    6.  
    7.  
    8. #define TESTS_N 1
    9.  
    10. #define maxA 0x20000000 // (2^32)/8
    11. #define maxB 0x8000000  // 2^27
    12.  
    13. char A[maxA];
    14. int  B[maxB];
    15.  
    16. int t_esp;
    17.  
    18. int main()
    19. {
    20.   unsigned int tmp;
    21.   int i, j;
    22.   static clock_t t;
    23.   clock_t t0, t_all, t_max;
    24.  
    25.   t_max = t_all = 0;
    26.  
    27.   for(j = 0; j < TESTS_N; j++){
    28.     printf("- %d\n", j);
    29.  
    30.     for(i = 1; i < maxB; i++){
    31.       rand_s(&tmp);
    32.       B[i] = tmp;
    33.     }
    34.     B[0] = 0;
    35.  
    36.     __asm pusha;
    37.     t0 = clock();
    38.     __asm{
    39.        mov t_esp,esp
    40.        lea esp,[B+maxB]
    41.        lea ebx,[A]
    42.  
    43.        pop eax
    44.     }
    45. loop_:
    46.     __asm{
    47.       mov edx,1
    48.       mov ecx,1fh
    49.  
    50.       and ecx,eax
    51.       shr eax,5
    52.       shl edx,cl
    53.      
    54.       and [ebx + eax],edx
    55.  
    56.       pop eax
    57.  
    58.       test eax,eax
    59.       jnz short loop_
    60.  
    61.       mov esp,t_esp
    62.     }
    63.     t = clock();
    64.     __asm popa;
    65.     t -= t0;
    66.  
    67.     t_all += t;
    68.     if(t > t_max)
    69.       t_max = t;
    70.   }
    71.  
    72.   printf("max time = %.4fs, avg time = %.4fs\n",
    73.               ((double)t_max)/(double)CLOCKS_PER_SEC,
    74.               ((double)t_all/(double)TESTS_N)/(double)CLOCKS_PER_SEC
    75.         );
    76.  
    77.   return 0;
    78. }
    тоже без оптимизации. показало время ~7c

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

    ну и можно еще подумать
     
  12. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    qqwe
    Тебе не кажется, что таким образом обрабатывается только четверть массива B - и цифирьки на это недвусмысленно намекают ~7*4 = 28 ~ 24 c ;)
     
  13. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    PS: Чудес в природе не бывает, и простая замена bts на нечто другое ничего существенного дать не может, т.к. в этой задачке основной тормоз заключается в случайном доступе к массиву А и соотв-но при чисто случайном распределении идексов B кэш отдыхает и в среднем практически каждое значение A грузится из ОЗУ, а это как минимум пара сотен тактов
     
  14. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    leo
    это да, четверть. но это не главная ошибка там. pop в какую сторону esp изменяет? после правки
    Код (Text):
    1. #include <time.h>
    2. #include <stdio.h>
    3.  
    4. #define _CRT_RAND_S
    5. #include <stdlib.h>
    6.  
    7.  
    8.  
    9. #define TESTS_N 1
    10.  
    11. #define maxA 0x20000000 // (2^32)/8
    12. #define maxB 0x8000000  // 2^27
    13.  
    14. char A[maxA];
    15. int  B[maxB];
    16.  
    17. int t_esp;
    18.  
    19. int main()
    20. {
    21.   unsigned int tmp;
    22.   int i, j;
    23.   static clock_t t;
    24.   clock_t t0, t_all, t_max;
    25.  
    26.   t_max = t_all = 0;
    27.  
    28.   for(j = 0; j < TESTS_N; j++){
    29.     printf("- %d\n", j);
    30.  
    31.     for(i = 0; i < maxB; i++){
    32.       rand_s(&tmp);
    33.       B[i] = tmp;
    34.     }
    35.  
    36.     __asm pusha;
    37.     t0 = clock();
    38.     __asm{
    39.        mov t_esp,esp
    40.        lea esp,[b]
    41.        lea ebx,[A]
    42.        lea esi,[esp + (4*maxB)]
    43.     }
    44. loop_:
    45.     __asm{
    46.       pop eax
    47.  
    48.       mov edx,1
    49.       mov ecx,1fh
    50.  
    51.       and ecx,eax
    52.       shr eax,5
    53.       shl edx,cl
    54.      
    55.       and [ebx + eax],edx
    56.  
    57.       cmp esp,esi
    58.       jnz short loop_
    59.  
    60.       mov esp,t_esp
    61.     }
    62.     t = clock();
    63.     __asm popa;
    64.     t -= t0;
    65.  
    66.     t_all += t;
    67.     if(t > t_max)
    68.       t_max = t;
    69.   }
    70.  
    71.   printf("max time = %.4fs, avg time = %.4fs\n",
    72.               ((double)t_max)/(double)CLOCKS_PER_SEC,
    73.               ((double)t_all/(double)TESTS_N)/(double)CLOCKS_PER_SEC
    74.         );
    75.  
    76.   return 0;
    77. }
    итого, ~9.6с

    первый пример по прежнему ~25c
     
  15. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    leo

    тут идет обращение одновременно к 2м разным кускам памяти. может стек имеет преимущество и не выгружается?
     
  16. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Black_mirror
    Пусть первое значение в массиве B 0. Тогда данный код установит не нулевой бит, а бит под номером 10000000h.
    Какое-то это решение некорректное.
     
  17. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    *80000000h
     
  18. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    KeSqueer
    Условие задачи подогнано под команду bts, она номер бита трактует как число со знаком. Но те, кто использует код вида A[i>>5]|=1<<(i&31), тоже не обламываются, потому что могут использовать знаковый сдвиг.
     
  19. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    qqwe

    Я погонял ваш алгоримт. и у меня тоже получились сходные цифры, хотя несколько хуже ~1:2 по времени. Ваше ухищрение с POP EAX не дает преимуществ по сравнению с LODSD. Однако главное - мне кажется, что использование команы AND некорректно, и она должна быть заменена на OR, ибо я не понимаю как AND может выставлять бит в чистом массиве.
     
  20. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Забыл еще одно - команда должна быть не AND [ebx+eax], edx, а OR [ebx+4*eax], edx.