Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Низкоуровневое программирование > Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.10.2015, 11:31   #1
alcaedo
Пользователь
 
Регистрация: 05.09.2015
Сообщений: 28
По умолчанию Помогите с оптимизацией

Delphi XE8, x64

В программе используются 256-битные переменные, логически представляющие из себя квадрат 16x16 бит. У такого квадрата существует 7 симметричных состояний (включая исходное 8). Симметричные состояния можно получить:
  • Отражением по горизонтали (H)
  • Отражением по вертикали (V)
  • Отражением по диагонали из левого верхнего угла {0;0} в правый нижний {15;15} (D)
  • Комбинацией трёх предыдущих отражений (DVH). Так получается отражение по диагонали из левого нижнего угла {0;15} в правый верхний {15;0}
  • Тремя оставшимися комбинациями (VH, DH, DV) - это повороты на 180, на 90 влево и на 90 градусов вправо
Кстати, симметрии DH и DV встречаются только одновременно с VH. То есть, если квадрат 16х16 бит обладает симметрией DH то там есть и DV и VH. Но симметрия VH может встречаться отдельно от других.

TBGWState - какой-нибудь тип размером в 256 бит (32 байта)
PBGWState - указатель на переменную этого типа

Есть процедура, которая преобразует квадрат всеми возможными способами и помещает результат в массив
Код:
procedure _GetSimmetryAllAsm(T,F:PBGWState);
asm
        // RCX = T - адрес нулевого элемента массива, куда будут помещены все 8 состояний
        // RDX = F - адрес исходного состояния
        MOVAPS  XMM0,[F]
        MOVAPS  XMM1,[F]+$10
        MOVNTPS [T],XMM0                // 0
        MOVNTPS [T]+$10,XMM1            // 0.5
        ADD     T,$20
        XORPS   XMM3,XMM3
        MOVNTPS [T],    XMM3            // 1
        MOVNTPS [T]+$10,XMM3            // 1.5
        MOVNTPS [T]+$20,XMM3            // 2
        MOVNTPS [T]+$30,XMM3            // 2.5
        MOVNTPS [T]+$40,XMM3            // 3
        MOVNTPS [T]+$50,XMM3            // 3.5
        MOVNTPS [T]+$60,XMM3            // 4
        MOVNTPS [T]+$70,XMM3            // 4.5
        MOVNTPS [T]+$80,XMM3            // 5
        MOVNTPS [T]+$90,XMM3            // 5.5
        MOVNTPS [T]+$A0,XMM3            // 6
        MOVNTPS [T]+$B0,XMM3            // 6.5
        MOVNTPS [T]+$C0,XMM3            // 7
        MOVNTPS [T]+$D0,XMM3            // 7.5
        MOV     R9,255
        SFENCE
        JMP     @work255_1
  @bitset255_1:
        XOR     R9b,$0F
        BTS     [T],    R9          // xxH x=x, y=15-y
        XOR     R9b,$FF
        BTS     [T]+$20,R9          // xVx x=15-x, y=y
        XOR     R9b,$0F
        BTS     [T]+$40,R9          // xVH x=15-x, y=15-y
        ROL     R9b,4
        BTS     [T]+$C0,R9          // DVH x=15-y, y=15-x
        XOR     R9b,$0F
        BTS     [T]+$A0,R9          // DVx x=15-y, y=x
        XOR     R9b,$FF
        BTS     [T]+$80,R9          // DxH x=y, y=15-x
        XOR     R9b,$0F
        BTS     [T]+$60,R9          // Dxx x=y, y=x
        ROL     R9b,4
        DEC     R9b
        JZ      @work0
  @work255_1:
        BT      [F],R9
        JC      @bitset255_1
        DEC     R9b
        JNZ     @work255_1
  @work0:
        BT      [F],0
        JNC     @finish
        MOV     R9b,$F0
        MOV     RAX,$FF
        BTS     [T],    $F          // xxH x=0, y=15
        BTS     [T]+$20,R9          // xVx x=15, y=0
        BTS     [T]+$40,RAX         // xVH x=15, y=15
        BTS     [T]+$C0,RAX         // DVH x=15, y=15
        BTS     [T]+$A0,R9          // DVx x=15, y=0
        BTS     [T]+$80,$F          // DxH x=0, y=15
        BTS     [T]+$60,0           // Dxx x=0, y=0
  @finish:
end;

Последний раз редактировалось alcaedo; 17.10.2015 в 12:31.
alcaedo вне форума Ответить с цитированием
Старый 17.10.2015, 11:34   #2
alcaedo
Пользователь
 
Регистрация: 05.09.2015
Сообщений: 28
По умолчанию

Есть функция, которая возвращает 8 бит информации о том, какими симметриями обладает заданное состояние (заданный квадрат, заданная переменная). Нулевой бит результата всегда установлен и соответствует тому, что исходное состояние без преобразований равно самому себе.
Код:
function _GetSimmetryTypeAsm(F:PBGWState):byte;
asm
        // RCX = F - адрес исходного состояния
        // AL = Result - возвращаемый байт
        // BGWBuffer256byte - выровненный на 16 адрес буфера
        XORPS   XMM3,XMM3
        MOV     RDX,BGWBuffer256byte
        MOVNTPS [RDX],    XMM3            // 1
        MOVNTPS [RDX]+$10,XMM3            // 1.5
        MOVNTPS [RDX]+$20,XMM3            // 2
        MOVNTPS [RDX]+$30,XMM3            // 2.5
        MOVNTPS [RDX]+$40,XMM3            // 3
        MOVNTPS [RDX]+$50,XMM3            // 3.5
        MOVNTPS [RDX]+$60,XMM3            // 4
        MOVNTPS [RDX]+$70,XMM3            // 4.5
        MOVNTPS [RDX]+$80,XMM3            // 5
        MOVNTPS [RDX]+$90,XMM3            // 5.5
        MOVNTPS [RDX]+$A0,XMM3            // 6
        MOVNTPS [RDX]+$B0,XMM3            // 6.5
        MOVNTPS [RDX]+$C0,XMM3            // 7
        MOVNTPS [RDX]+$D0,XMM3            // 7.5
        MOV     R9,255
        SFENCE
        JMP     @work255_1
  @bitset255_1:
        XOR     R9b,$0F
        BTS     [RDX],    R9          // xxH x=x, y=15-y
        XOR     R9b,$FF
        BTS     [RDX]+$20,R9          // xVx x=15-x, y=y
        XOR     R9b,$0F
        BTS     [RDX]+$40,R9          // xVH x=15-x, y=15-y
        ROL     R9b,4
        BTS     [RDX]+$C0,R9          // DVH x=15-y, y=15-x
        XOR     R9b,$0F
        BTS     [RDX]+$A0,R9          // DVx x=15-y, y=x
        XOR     R9b,$FF
        BTS     [RDX]+$80,R9          // DxH x=y, y=15-x
        XOR     R9b,$0F
        BTS     [RDX]+$60,R9          // Dxx x=y, y=x
        ROL     R9b,4
        DEC     R9b
        JZ      @work0
  @work255_1:
        BT      [F],R9
        JC      @bitset255_1
        DEC     R9b
        JNZ     @work255_1
  @work0:
        BT      [F],0
        JNC     @counttype
        MOV     R9b,$F0
        MOV     RAX,$FF
        BTS     [RDX],    $F          // xxH x=0, y=15
        BTS     [RDX]+$20,R9          // xVx x=15, y=0
        BTS     [RDX]+$40,RAX         // xVH x=15, y=15
        BTS     [RDX]+$C0,RAX         // DVH x=15, y=15
        BTS     [RDX]+$A0,R9          // DVx x=15, y=0
        BTS     [RDX]+$80,$F          // DxH x=0, y=15
        BTS     [RDX]+$60,0           // Dxx x=0, y=0
====>>>
alcaedo вне форума Ответить с цитированием
Старый 17.10.2015, 11:36   #3
alcaedo
Пользователь
 
Регистрация: 05.09.2015
Сообщений: 28
По умолчанию

Код:
====>>>

  @counttype:
        MOV     RAX,1

        MOV     R8,[F]
        CMP     R8,[RDX]
        JNE     @rno_xxH
        MOV     R8,[F+$08]
        CMP     R8,[RDX+$08]
        JNE     @rno_xxH
        MOV     R8,[F+$10]
        CMP     R8,[RDX+$10]
        JNE     @rno_xxH
        MOV     R8,[F+$18]
        CMP     R8,[RDX+$18]
        JNE     @rno_xxH
        OR      AL,2
  @rno_xxH:

        MOV     R8,[F]
        CMP     R8,[RDX+$20]
        JNE     @rno_xVx
        MOV     R8,[F+$08]
        CMP     R8,[RDX+$20+$08]
        JNE     @rno_xVx
        MOV     R8,[F+$10]
        CMP     R8,[RDX+$20+$10]
        JNE     @rno_xVx
        MOV     R8,[F+$18]
        CMP     R8,[RDX+$20+$18]
        JNE     @rno_xVx
        OR      AL,4
  @rno_xVx:

        MOV     R8,[F]
        CMP     R8,[RDX+$40]
        JNE     @rno_xVH
        MOV     R8,[F+$08]
        CMP     R8,[RDX+$40+$08]
        JNE     @rno_xVH
        MOV     R8,[F+$10]
        CMP     R8,[RDX+$40+$10]
        JNE     @rno_xVH
        MOV     R8,[F+$18]
        CMP     R8,[RDX+$40+$18]
        JNE     @rno_xVH
        OR      AL,8
  @rno_xVH:

        MOV     R8,[F]
        CMP     R8,[RDX+$60]
        JNE     @rno_Dxx
        MOV     R8,[F+$08]
        CMP     R8,[RDX+$60+$08]
        JNE     @rno_Dxx
        MOV     R8,[F+$10]
        CMP     R8,[RDX+$60+$10]
        JNE     @rno_Dxx
        MOV     R8,[F+$18]
        CMP     R8,[RDX+$60+$18]
        JNE     @rno_Dxx
        OR      AL,16
  @rno_Dxx:

        MOV     R8,[F]
        CMP     R8,[RDX+$80]
        JNE     @rno_DxH
        MOV     R8,[F+$08]
        CMP     R8,[RDX+$80+$08]
        JNE     @rno_DxH
        MOV     R8,[F+$10]
        CMP     R8,[RDX+$80+$10]
        JNE     @rno_DxH
        MOV     R8,[F+$18]
        CMP     R8,[RDX+$80+$18]
        JNE     @rno_DxH
        OR      AL,32
  @rno_DxH:

        MOV     R8,[F]
        CMP     R8,[RDX+$A0]
        JNE     @rno_DVx
        MOV     R8,[F+$08]
        CMP     R8,[RDX+$A0+$08]
        JNE     @rno_DVx
        MOV     R8,[F+$10]
        CMP     R8,[RDX+$A0+$10]
        JNE     @rno_DVx
        MOV     R8,[F+$18]
        CMP     R8,[RDX+$A0+$18]
        JNE     @rno_DVx
        OR      AL,64
  @rno_DVx:

        MOV     R8,[F]
        CMP     R8,[RDX+$C0]
        JNE     @rno_DVH
        MOV     R8,[F+$08]
        CMP     R8,[RDX+$C0+$08]
        JNE     @rno_DVH
        MOV     R8,[F+$10]
        CMP     R8,[RDX+$C0+$10]
        JNE     @rno_DVH
        MOV     R8,[F+$18]
        CMP     R8,[RDX+$C0+$18]
        JNE     @rno_DVH
        OR      AL,128
  @rno_DVH:
end;
alcaedo вне форума Ответить с цитированием
Старый 17.10.2015, 11:36   #4
alcaedo
Пользователь
 
Регистрация: 05.09.2015
Сообщений: 28
По умолчанию

Нужна функция, которая будет возвращать не все 8 состояний, а только заданные. Можно конечно тупо взять функцию _GetSimmetryAllAsm и в конце удалить из массива ненужные состояния. При этом придётся либо делать ещё временный массив, либо как-то смещать состояния в массиве во время удаления лишних. Это всё добавит кучу времени на выполнение, а участок кода, где это будет использоваться ко времени критичен. Подскажите, как оптимизировать?

Вот, заготовка:
Код:
function _GetSimmetryListAsm(T,F:PBGWState;aType:byte):byte;
asm
        // RCX = T - адрес нулевого элемента массива, куда поместятся симметричные состояния
        // RDX = F - адрес исходного состояния
        // R8b = aType - тип симметрии. Если 0-й бит сброшен, то исходное состояние не возвращается в массиве
        // RAX - Result - количество состояний, которые вернула функция в массиве
        XOR     RAX,RAX
        TEST    R8b,1
        JZ      @skip_xxx
        MOVAPS  XMM0,[F]
        MOVAPS  XMM1,[F]+$10
        MOVNTPS [T],XMM0                // 0
        MOVNTPS [T]+$10,XMM1            // 0.5
        ADD     RAX,$20
        ADD     T,$20
  @skip_xxx:
        XORPS   XMM3,XMM3
        MOVNTPS [T],    XMM3            // 1
        MOVNTPS [T]+$10,XMM3            // 1.5
        MOVNTPS [T]+$20,XMM3            // 2
        MOVNTPS [T]+$30,XMM3            // 2.5
        MOVNTPS [T]+$40,XMM3            // 3
        MOVNTPS [T]+$50,XMM3            // 3.5
        MOVNTPS [T]+$60,XMM3            // 4
        MOVNTPS [T]+$70,XMM3            // 4.5
        MOVNTPS [T]+$80,XMM3            // 5
        MOVNTPS [T]+$90,XMM3            // 5.5
        MOVNTPS [T]+$A0,XMM3            // 6
        MOVNTPS [T]+$B0,XMM3            // 6.5
        MOVNTPS [T]+$C0,XMM3            // 7
        MOVNTPS [T]+$D0,XMM3            // 7.5
        MOV     R9,255
        SFENCE
        JMP     @work255_1
  @bitset255_1:
        XOR     R9b,$0F
        BTS     [T],    R9          // xxH x=x, y=15-y
        XOR     R9b,$FF
        BTS     [T]+$20,R9          // xVx x=15-x, y=y
        XOR     R9b,$0F
        BTS     [T]+$40,R9          // xVH x=15-x, y=15-y
        ROL     R9b,4
        BTS     [T]+$C0,R9          // DVH x=15-y, y=15-x
        XOR     R9b,$0F
        BTS     [T]+$A0,R9          // DVx x=15-y, y=x
        XOR     R9b,$FF
        BTS     [T]+$80,R9          // DxH x=y, y=15-x
        XOR     R9b,$0F
        BTS     [T]+$60,R9          // Dxx x=y, y=x
        ROL     R9b,4
        DEC     R9b
        JZ      @work0
  @work255_1:
        BT      [F],R9
        JC      @bitset255_1
        DEC     R9b
        JNZ     @work255_1
  @work0:
        BT      [F],0
        JNC     @finish
        MOV     R9b,$F0
        MOV     R10,$FF
        BTS     [T],    $F          // xxH x=0, y=15
        BTS     [T]+$20,R9          // xVx x=15, y=0
        BTS     [T]+$40,R10         // xVH x=15, y=15
        BTS     [T]+$C0,R10         // DVH x=15, y=15
        BTS     [T]+$A0,R9          // DVx x=15, y=0
        BTS     [T]+$80,$F          // DxH x=0, y=15
        BTS     [T]+$60,0           // Dxx x=0, y=0
  @finish:
end;
alcaedo вне форума Ответить с цитированием
Старый 17.10.2015, 11:48   #5
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,097
По умолчанию

Можно полюбопытствовать почему именно на ассемблере вставками нужно решать сию задачу?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 17.10.2015, 12:29   #6
alcaedo
Пользователь
 
Регистрация: 05.09.2015
Сообщений: 28
По умолчанию

Это самый быстрый из известных мне способов.
_GetSimmetryAllAsm написана просто так, в программе не планируется её использовать. Ну, разве что для отладки.
_GetSimmetryTypeAsm используется в программе несколько (мало) раз. Выполняется на 23-30% быстрее обычного Deplhi на типе "set of byte". Написана просто так.
_GetSimmetryListAsm очень нужная и важная функция. Должна будет использоваться постоянно. Ну, там миллионы раз в секунду, или как железо позволит.

Если не придумается способ оптимизации, то, наверное, придётся клепать ещё 255 вариантов _GetSimmetryAllAsm0..._GetSimmetryA llAsm254 и заводить переменную-указатель на какой-то из этих вариантов. Тип симметрии меняется в программе редко. С его изменением будет меняться переменная-указатель-на-вариант-функции.

Последний раз редактировалось alcaedo; 17.10.2015 в 12:59.
alcaedo вне форума Ответить с цитированием
Старый 17.10.2015, 12:47   #7
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,097
По умолчанию

Цитата:
Отражением по горизонтали (H)
Код:
program Project1;
const sq:array[1..2,1..2] of byte=(
 (1,2),
 (3,4)
);
var
  i,j,k,v,n:integer;
begin
  for i:=1 to 2 do begin
    for j:=2 downto 1 do begin
      v:=sq[i,j];     n:=0;
      for k:=1 to 8 do begin
       n:=n+(v and 1);
       n:=n shl 1;
       v:=v shr 1
      end;
      write(n:5);
    end;
    writeln;
  end;
  readln;
end.
Достаточно быстро?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 17.10.2015, 13:05   #8
alcaedo
Пользователь
 
Регистрация: 05.09.2015
Сообщений: 28
По умолчанию

Цитата:
Сообщение от Stilet Посмотреть сообщение
Достаточно быстро?
Я там успел подредактировать....
Не думаю, что достаточно, мне каждый такт дорог.

Вариант функции, которая определяет тип симметрии, на чистом Delphi выглядел так. То, что эта функция проделывает на 10 секунд, ASM-вариант делает за 7.
Код:
Type
   TBGWsob = set of byte;
   TBGWState = array[0..31] of byte;

function _GetSimmetryType(S:TBGWState):byte;
var
  L:array[0..7] of TBGWState;
  x,y:byte;
begin
  for x:=1 to 7 do L[x]:=[];L[0]:=TBGWsob(S);
  for x:=0 to 15 do for y:=0 to 15 do if (x*16+y) in L[0] then
    begin
      include(L[1],(00+x)*16+(15-y)); // xxH
      include(L[2],(15-x)*16+(00+y)); // xVx
      include(L[3],(15-x)*16+(15-y)); // xVH
      include(L[4],(00+y)*16+(00+x)); // Dxx
      include(L[5],(00+y)*16+(15-x)); // DxH
      include(L[6],(15-y)*16+(00+x)); // DVx
      include(L[7],(15-y)*16+(15-x)); // DVH
    end;
  Result:=1+(byte(S=L[1]) shl 1)+(byte(S=L[2]) shl 2)+(byte(S=L[3]) shl 3)+(byte(S=L[4]) shl 4)+(byte(S=L[5]) shl 5)+(byte(S=L[6]) shl 6)+(byte(S=L[7]) shl 7);
end;
Цитата:
Сообщение от Stilet Посмотреть сообщение
Код:
const sq:array[1..2,1..2] of byte=(
 (1,2),
 (3,4)
);
это 4 байта = 32 бита, а не 32 байта = 256 бит

Последний раз редактировалось Stilet; 17.10.2015 в 14:04.
alcaedo вне форума Ответить с цитированием
Старый 17.10.2015, 14:05   #9
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,097
По умолчанию

Цитата:
это 4 байта = 32 бита, а не 32 байта = 256 бит
Это мне упрек? А ты думал я все за тебя писать буду?
Я только идею подал.
Цитата:
мне каждый такт дорог.
Тогда забудь про Делфи насовсем - пиши в ассемблере полностью.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 17.10.2015, 14:12   #10
f.hump
C/C++, Asm
Участник клуба
 
Аватар для f.hump
 
Регистрация: 02.03.2010
Сообщений: 1,323
По умолчанию

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

а 256 бит обязательно использовать? или можно систему описать 256-ю байтами?

char box[256], symmetry_val;

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

char main_diagonal_map[256], side_diagonal_map[256], corner_flip[256] ...

symmetry_val = 0;
for (unsigned int i(0);i<256;i++)
symmetry_val |= (box[i] ^ box[main_diagonal_map[i]]);

success = (symmetry_val == 0);
f.hump вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите с оптимизацией!!!((( X@NDER Фриланс 2 30.10.2013 21:28
Проблема с оптимизацией julia9311 Microsoft Office Excel 3 31.05.2013 02:36
Проблема с оптимизацией скрипта Andrey[SF] PHP 1 19.05.2009 19:20
Нужна помощь с оптимизацией t3ns0r Общие вопросы C/C++ 1 07.03.2009 14:58