powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Микширование бит
25 сообщений из 104, страница 3 из 5
Микширование бит
    #40022934
L1G
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp, таблицы статикой в код ведь можно забить!
(btw, если их генерацию вставить перед миллионным циклом, как в тесте - он, как ни странно, ускоряется! за счет разогрева кэша, очевидно.)

Aleksandr Sharahov, результат операции не совпадает с таковым у других версий.

У меня тоже ошибочки вкрались в генерацию таблиц:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
procedure InitTables();
  var i, j, d, mask: word;
begin
  for i:=0 to 255 do
  begin
    d := 0;
    for j := 0 to 7 do
    begin
      mask := 1 shl j;
      d := d or ((i and mask) shl j);
    end;
    tbl0[i] := d shl 1;
    tbl1[i] := d;
  end;
end;

...
Рейтинг: 0 / 0
Микширование бит
    #40022946
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp
Aleksandr Sharahov,

Кстати, если её вручную на ассемблер перевести, то там прилично так в скорости прибавляется, чуть больше 20 процентов.
Всё-таки у новых дельфей с оптимизатором беда... 😒


я пишу на D7 - у меня там ассемблер = паскаль )
...
Рейтинг: 0 / 0
Микширование бит
    #40022948
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
Aleksandr Sharahov
alekcvp
Aleksandr Sharahov,

Кстати, если её вручную на ассемблер перевести, то там прилично так в скорости прибавляется, чуть больше 20 процентов.
Всё-таки у новых дельфей с оптимизатором беда... 😒


я пишу на D7 - у меня там ассемблер = паскаль )


Тут принято всех, кто до сих пор на D7, ногами топтать !
...
Рейтинг: 0 / 0
Микширование бит
    #40022950
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L1G
Aleksandr Sharahov, результат операции не совпадает с таковым у других версий.


Значит, надо искать ошибку у других версий )
И разумеется, аргументы должны быть из диапазона 0..$FFFF
...
Рейтинг: 0 / 0
Микширование бит
    #40022953
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L1G

Aleksandr Sharahov, результат операции не совпадает с таковым у других версий.

Совпадает пока там параметры как DWORD объявлены, если поменять на Word то перестаёт совпадать.

Вот ассемблерный вариант того когда с правильными параметрами, у него всё совпадает и он даже ещё чуточку быстрее:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
function MixAsm3( w1, w2 : word ) : dWord; assembler; register;
asm
  push    ebx

  movzx   ebx, ax
  movzx   ecx, dx
  shl     eax, 8
  shl     edx, 8
  or      eax, ebx
  or      edx, ecx
  and     eax, $00FF00FF
  and     edx, $00FF00FF

  mov     ebx, eax
  mov     ecx, edx
  shl     ebx, 4
  shl     ecx, 4
  or      eax, ebx
  or      edx, ecx
  and     eax, $0F0F0F0F
  and     edx, $0F0F0F0F

  mov     ebx, eax
  mov     ecx, edx
  shl     ebx, 2
  shl     ecx, 2
  or      eax, ebx
  or      edx, ecx
  and     eax, $33333333
  and     edx, $33333333

  mov     ebx, eax
  mov     ecx, edx
  shl     ebx, 1
  shl     ecx, 1
  or      eax, ebx
  or      edx, ecx
  and     eax, $55555555
  and     edx, $55555555

  shl     eax, 1
  or      eax, edx

  pop     ebx
end;

...
Рейтинг: 0 / 0
Микширование бит
    #40022957
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
alekcvp,

так немного быстрее
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
function ShaMix(w1, w2: dword): dword;
begin;
  w1:=(w1 or w1 shl 8) and $00FF00FF;
  w2:=(w2 or w2 shl 8) and $00FF00FF;
  w1:=(w1 or w1 shl 4) and $0F0F0F0F;
  w2:=(w2 or w2 shl 4) and $0F0F0F0F;
  w1:=(w1 or w1 shl 2) and $33333333;
  w2:=(w2 or w2 shl 2) and $33333333;
  w1:=(w1 or w1 shl 1) and $55555555;
  w2:=(w2 or w2 shl 1) and $55555555;
  w1:=w1+w1;
  w1:=w1+w2;
  Result:=w1;
  end;



Голова!
Расскажи, как мыслил, выводя такой подход
У меня не хватило соображалки )
...
Рейтинг: 0 / 0
Микширование бит
    #40022958
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp

Вот ассемблерный вариант того когда с правильными параметрами, у него всё совпадает и он даже ещё чуточку быстрее:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
function MixAsm3( w1, w2 : word ) : dWord; assembler; register;
asm
  push    ebx

  movzx   ebx, ax
  movzx   ecx, dx
  shl     eax, 8
  shl     edx, 8
  or      eax, ebx
  or      edx, ecx
  and     eax, $00FF00FF
  and     edx, $00FF00FF

  mov     ebx, eax
  mov     ecx, edx
  shl     ebx, 4
  shl     ecx, 4
  or      eax, ebx
  or      edx, ecx
  and     eax, $0F0F0F0F
  and     edx, $0F0F0F0F

  mov     ebx, eax
  mov     ecx, edx
  shl     ebx, 2
  shl     ecx, 2
  or      eax, ebx
  or      edx, ecx
  and     eax, $33333333
  and     edx, $33333333

  mov     ebx, eax
  mov     ecx, edx
  shl     ebx, 1
  shl     ecx, 1
  or      eax, ebx
  or      edx, ecx
  and     eax, $55555555
  and     edx, $55555555

  shl     eax, 1
  or      eax, edx

  pop     ebx
end;



Сравни это с результатом компилятора D7, у него код быстрее )

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
function ShaAsm(w1, w2: dword): dword;
asm
  mov ecx, eax
  shl ecx, 8
  or  eax, ecx
  and eax, $00FF00FF
  mov ecx, edx
  shl ecx, 8
  or  edx, ecx
  and edx, $00FF00FF

  mov ecx, eax
  shl ecx, 4
  or  eax, ecx
  and eax, $0F0F0F0F
  mov ecx, edx
  shl ecx, 4
  or  edx, ecx
  and edx, $0F0F0F0F

  mov ecx, eax
  shl ecx, 2
  or  eax, ecx
  and eax, $33333333
  mov ecx, edx
  shl ecx, 2
  or  edx, ecx
  and edx, $33333333

  mov ecx, eax
  shl ecx, 1
  or  eax, ecx
  and eax, $55555555
  mov ecx, edx
  shl ecx, 1
  or  edx, ecx
  and edx, $55555555

  add eax, eax
  add eax, edx
  end;

...
Рейтинг: 0 / 0
Микширование бит
    #40022959
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L1G
Вы что-то, ребята, затупили и с таблицами не попробовали.
Сибиряков правильно подсказал, они небольшие. Только их 2 нужно:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
var tbl0, tbl1: array[Byte] of Word;

procedure InitTables();
  var i, j, d, mask: byte;
begin
  for i:=0 to 255 do
  begin
    d := 0;
    for j := 0 to 7 do
    begin
      mask := 1 shl j;
      d := d or ((j and mask) shl j);
    end;
    tbl0[i] := d shl 1;
    tbl1[i] := d;
  end;
end;

function TableMix(w1, w2: word): dWord;
begin
  Result := ((tbl0[Hi(w1)] or tbl1[Hi(w2)]) shl 16) or tbl0[Lo(w1)] or tbl1[Lo(w2)];
end;



Просто через таблицы понятно как решать :)
...
Рейтинг: 0 / 0
Микширование бит
    #40022960
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
Сравни это с результатом компилятора D7, у него код быстрее )

Во-первых, сделай входящие параметры Word, чтобы сравнение было в одинаковых условиях.

Во-вторых, да у новых дельфей с оптимизатором беда, согласен.

В-третьих, тут скорее от процессора зависит, потому что перестановка местами команд в теле и замена add на shl/or у меня давала прирост в производительности. Возможно это как-то влияет на кэш/распараллелливание инструкций.
...
Рейтинг: 0 / 0
Микширование бит
    #40022963
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp
Aleksandr Sharahov
Сравни это с результатом компилятора D7, у него код быстрее )

Во-первых, сделай входящие параметры Word, чтобы сравнение было в одинаковых условиях.


В ассемблерном варианте (тот который ShaAsm) можешь нарисовать любые параметры, код будет работать.
Я смотрю на вещи ширше )

alekcvp

Во-вторых, да у новых дельфей с оптимизатором беда, согласен.


Речь не о новых дельфи.
А о том, что компилятор D7 часто порождает код лучше человеков.
...
Рейтинг: 0 / 0
Микширование бит
    #40022964
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp,

Оптимизация новых Delphi не хуже, чем Delphi 7
Скорее у тебя не включен флаг оптимизации

P.S. Перевести Word в Cardinal - плёвое дело
...
Рейтинг: 0 / 0
Микширование бит
    #40022967
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU
Оптимизация новых Delphi не хуже, чем Delphi 7
Скорее у тебя не включен флаг оптимизации

1. Хуже, уже неоднократно проверялось.
2. Он по-умолчанию включён для Release.
...
Рейтинг: 0 / 0
Микширование бит
    #40022968
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alekcvp,

На операциях с управляемыми типами - да
Там дополнительные операции вставлены
Но здесь нет управляемых типов
...
Рейтинг: 0 / 0
Микширование бит
    #40022969
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU
alekcvp,

На операциях с управляемыми типами - да
Там дополнительные операции вставлены
Но здесь нет управляемых типов


Попробуй откомпилировать 22239616
и сравнить результат с 22239671
Это подлинная выдача из D7
...
Рейтинг: 0 / 0
Микширование бит
    #40022975
L1G
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov, извиняюсь, с входными параметрами dword - всё ОК

кстати, идея dword-параметров - отличная! табличный метод резко вырывается вперед (в 2 раза быстрее стал!)
Код: pascal
1.
2.
3.
4.
function TableMix1(w1, w2: dword): dword;
begin
  Result := (((tbl1[Hi(w1)] shl 1) or tbl1[Hi(w2)]) shl 16) or (tbl1[Lo(w1)] shl 1) or tbl1[Lo(w2)];
end;


и с одной таблицей даже чуть быстрее, чем с двумя.

SOFT FOR YOU, интересно ведь скорости-то сравнить.
если "наивный" (легко понятный) код еще и быстрее оказывается - зачем что-то еще?

И т.к. Александр не "рассказал, как мыслил", могу предположить:
- 16 бит нам нужно сместить на разные смещения, от 0 до 15
- смещать биты можно и по нескольку сразу, но на одинаковый оффсет
- если оффсеты будут степенями двойки - можно уменьшить количество нужных смещений логарифмически
- начинать нужно с больших оффсетов, т.е. сначала весь старший байт - влево на 8
- дальше - дело техники.
...
Рейтинг: 0 / 0
Микширование бит
    #40022986
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov

Сравни это с результатом компилятора D7, у него код быстрее )

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
function ShaAsm(w1, w2: dword): dword;
asm
  mov ecx, eax
  shl ecx, 8
  or  eax, ecx
  and eax, $00FF00FF
  mov ecx, edx
  shl ecx, 8
  or  edx, ecx
  and edx, $00FF00FF

  mov ecx, eax
  shl ecx, 4
  or  eax, ecx
  and eax, $0F0F0F0F
  mov ecx, edx
  shl ecx, 4
  or  edx, ecx
  and edx, $0F0F0F0F

  mov ecx, eax
  shl ecx, 2
  or  eax, ecx
  and eax, $33333333
  mov ecx, edx
  shl ecx, 2
  or  edx, ecx
  and edx, $33333333

  mov ecx, eax
  shl ecx, 1
  or  eax, ecx
  and eax, $55555555
  mov ecx, edx
  shl ecx, 1
  or  edx, ecx
  and edx, $55555555

  add eax, eax
  add eax, edx
  end;



Добавляем первой строкой весьма безобидную ни на что не влияющую операцию
Код: pascal
1.
  xor  ecx, ecx


и получаем замедление где-то в 1.5 раза
Уш-да-уш... Оптимизация asm - дело тонкое ...
...
Рейтинг: 0 / 0
Микширование бит
    #40022988
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Polesov

Добавляем первой строкой весьма безобидную ни на что не влияющую операцию
Код: pascal
1.
  xor  ecx, ecx


и получаем замедление где-то в 1.5 раза
Уш-да-уш... Оптимизация asm - дело тонкое ...


Ты сейчас с компилятором разговариваешь? ))
Это его выхлоп.
...
Рейтинг: 0 / 0
Микширование бит
    #40022989
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L1G
могу предположить:
- 16 бит нам нужно сместить на разные смещения, от 0 до 15
- смещать биты можно и по нескольку сразу, но на одинаковый оффсет
- если оффсеты будут степенями двойки - можно уменьшить количество нужных смещений логарифмически
- начинать нужно с больших оффсетов, т.е. сначала весь старший байт - влево на 8
- дальше - дело техники.


Да, так и думал. Это стандартный прием. Но на таблицах, конечно быстрее будет.

версия на таблицах
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
var
  tbl: array[0..255] of dword;

procedure FillTable;
var
  i, j, k, m: integer;
begin;
  for i:=0 to 255 do begin;
    j:=0; m:=1;
    repeat;
      k:=i and m;
      j:=j + k*k;
      m:=m+m;
      until m>=256;
    tbl[i]:=j;
    end;
  end;

function ShaTableAsm(w1, w2: dword): dword;
asm
  movzx ecx, dh
  xor ecx, eax
  movzx eax, al
  xor ecx, eax
  mov eax, [eax*4+tbl]
  add eax, eax
  movzx edx, dl
  or eax, [edx*4+tbl]
  movzx edx, ch
  mov edx, [edx*4+tbl]
  add edx, edx
  movzx ecx, cl
  or edx, [ecx*4+tbl]
  shl edx, 16
  add eax, edx
  end;

...
Рейтинг: 0 / 0
Микширование бит
    #40022991
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
Polesov

Добавляем первой строкой весьма безобидную ни на что не влияющую операцию
Код: pascal
1.
  xor  ecx, ecx


и получаем замедление где-то в 1.5 раза
Уш-да-уш... Оптимизация asm - дело тонкое ...


Ты сейчас с компилятором разговариваешь? ))
Это его выхлоп.

Да нет - речь о том, что даже, на первый взгляд, незначительное изменение кода может существенно повлиять на скорость выполнения.
...
Рейтинг: 0 / 0
Микширование бит
    #40022994
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L1G

SOFT FOR YOU, интересно ведь скорости-то сравнить.
если "наивный" (легко понятный) код еще и быстрее оказывается - зачем что-то еще?


Я тут экспериментирую с SIMD
По сути появится возможность анализировать 16 символов за раз
Там классная возможность в том, что проведя ряд манипуляций, ты получаешь маску из 16 бит, где ты видишь, символ удовлетворяет твоему условию или нет

Например, самое важное условие - является ли символ ASCII (т.е. <= $7f)
Но по факту возникает необходимость анализировать сразу несколько условий
Например, тебе так же нужно по-особому реагировать на символы перевода каретки или пробельные символы. В кодировке FlexString (Flex Unicode) ключевое значение имеет символ $ff

Получается ты считал 16 символов из памяти. Проанализировал их, получил маску (2 маски по 16 бит)
А потом постепенно вычитываешь эти символы из SIMD-регистра и обрабатываешь согласно имеющейся маске

Так вот я подумал было бы классно объединить 2 маски в одну и анализировать каждый символ как последовательность 2 бит (первая маска плюс вторая)
Я думал можно сделать это за пару тактов. Каким-то простым способом. Таблицы уже не резонно. Остальные методы ещё хуже. Придётся усложнить анализ маски - первые 16 бит будут в младшем слове, а вторые в старшем. В данном случае мы просто разминаем мозги на тему как и что можно реализовать. Да, кстати, можно провести сравнительное тестирование. Мне кажется вариант Шарахова будет примерно таким же :)
...
Рейтинг: 0 / 0
Микширование бит
    #40022995
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
alekcvp,

так немного быстрее
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
function ShaMix(w1, w2: dword): dword;
begin;
  w1:=(w1 or w1 shl 8) and $00FF00FF;
  w2:=(w2 or w2 shl 8) and $00FF00FF;
  w1:=(w1 or w1 shl 4) and $0F0F0F0F;
  w2:=(w2 or w2 shl 4) and $0F0F0F0F;
  w1:=(w1 or w1 shl 2) and $33333333;
  w2:=(w2 or w2 shl 2) and $33333333;
  w1:=(w1 or w1 shl 1) and $55555555;
  w2:=(w2 or w2 shl 1) and $55555555;
  w1:=w1+w1;
  w1:=w1+w2;
  Result:=w1;
end;



Rio - почти идентично. Пара сдвигов заменены на инкремент

P.S. ты кстати не ответил на вопрос :)
22239670
...
Рейтинг: 0 / 0
Микширование бит
    #40022997
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Ответил 22239731
Думал, что это более-менее очевидно. Прокрути алгоритм по шагам.
После первого сдвига остаются пары одинаковых сдвигов, и т.д.
...
Рейтинг: 0 / 0
Микширование бит
    #40022999
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L1G
- 16 бит нам нужно сместить на разные смещения, от 0 до 15

От 0 до 17 )

Polesov

Добавляем первой строкой весьма безобидную ни на что не влияющую операцию
Код: pascal
1.
  xor  ecx, ecx


и получаем замедление где-то в 1.5 раза
Уш-да-уш... Оптимизация asm - дело тонкое ...


Выложи текущий вариант модуля
Чтобы мы тоже погоняли и сравнили
...
Рейтинг: 0 / 0
Микширование бит
    #40023000
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

у тебя какой-то странный листинг.

Возьми мои ассемблерные 22239671 и 22239731 .
...
Рейтинг: 0 / 0
Микширование бит
    #40023001
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov
SOFT FOR YOU,

у тебя какой-то странный листинг.

Возьми мои ассемблерные 22239671 и 22239731 .


Справа и есть твой листинг (2 первые строки идентичны, на скриншот не поместились)
Слева Rio
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
    mov ecx,eax
    shl ecx,$08
    or eax,ecx
    and eax,$00ff00ff
    mov ecx,edx
    shl ecx,$08
    or edx,ecx
    and edx,$00ff00ff
    mov ecx,eax
    shl ecx,$04
    or eax,ecx
    and eax,$0f0f0f0f
    mov ecx,edx
    shl ecx,$04
    or edx,ecx
    and edx,$0f0f0f0f
    mov ecx,eax
    add ecx,ecx
    add ecx,ecx
    or eax,ecx
    and eax,$33333333
    mov ecx,edx
    add ecx,ecx
    add ecx,ecx
    or edx,ecx
    and edx,$33333333
    mov ecx,eax
    add ecx,ecx
    or eax,ecx
    and eax,$55555555
    mov ecx,edx
    add ecx,ecx
    or edx,ecx
    and edx,$55555555
    add eax,eax
    add eax,edx




Насчёт стандартного подхода
А можно это как-то где-то почитать?
Желательно на русском
...
Рейтинг: 0 / 0
25 сообщений из 104, страница 3 из 5
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Микширование бит
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]