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

Имеется массив 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

 

А EDI инкрементировать

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

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

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

 

Serg50
Задачка не в том чтобы случайно заполнить массив A, а в том чтобы установить все биты, индексы которых берутся из массива B. И bts тут не самое тормозное зло.

 

Пара вопросов.
1)"размером 2^32 бит(512Мбайт)" ошибка или я что то не понимаю?
2) Мне неясно понятие "все биты, индексы которых есть в массиве B". Можно уточнить?

 

Можно требовать чтобы B был как-то упорядочен? (чтобы не тыкать в псевдослучайное место здоровенного блока)

 

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

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

 

Был неправ - без использования 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 у меня генерировалась ошибка, так что случайные числа я подрезал заранее.

 

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

 

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

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

 

Еще раз каюсь, за невнимательность! Я понял смысл A+10000000h

 

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 заполняется. так что, возможно, это частные случаи

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

 

qqwe

Тебе не кажется, что таким образом обрабатывается только четверть массива B - и цифирьки на это недвусмысленно намекают ~7*4 = 28 ~ 24 c

 

PS: Чудес в природе не бывает, и простая замена bts на нечто другое ничего существенного дать не может, т.к. в этой задачке основной тормоз заключается в случайном доступе к массиву А и соотв-но при чисто случайном распределении идексов B кэш отдыхает и в среднем практически каждое значение A грузится из ОЗУ, а это как минимум пара сотен тактов

 

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

 

leo

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

 

Black_mirror

Пусть первое значение в массиве B 0. Тогда данный код установит не нулевой бит, а бит под номером 10000000h.
Какое-то это решение некорректное.

 

*80000000h

 

KeSqueer
Условие задачи подогнано под команду bts, она номер бита трактует как число со знаком. Но те, кто использует код вида A[i>>5]|=1<<(i&31), тоже не обламываются, потому что могут использовать знаковый сдвиг.

 

qqwe

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

 

Забыл еще одно - команда должна быть не AND [ebx+eax], edx, а OR [ebx+4*eax], edx.