Помогите с оптимизацией

[alcaedo]

Сообщение от f.hump

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

10 секунд это в цикле во время сравнительного теста, НЕ для определения состояния. То есть обе функции запускались, скажем по 1000000 раз и сравнивалось время миллиона запусков.

Сообщение от f.hump

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

Да, потому, что существует "словарь состояний, которые уже обрабатывались в программе" и "рабочий набор состояний" и ещё может какие-то массивы. Всего каких-то 67 миллионов состояний и 2 Гб памяти занято. На этот случай в программе предусмотрен сброс части данных на диск, но к этой теме всё это не относится. Вся эта затея с симметриями как раз, чтобы уменьшить общий объём данных. Если начальное, самое первое состояние обладает, например, всеми симметриями, то объём уменьшается по крайней мере в 8 раз. Можно провести первую серию работы и сразу отсеять 7/8 результата. Нужно ли будет отсеивать на втором шаге - не уверен, наверное да.

Сообщение от f.hump

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

Да, у меня был вариант сделать что-то вроде этого. На каждый тип преобразования массив из 256-и байт. В каждом элементе этого массива новый номер бита. Но описывать сами состояния 256-ю байтами вместо 32-х не вариант.

Сообщение от Stilet

Это мне упрек? А ты думал я все за тебя писать буду?
Я только идею подал.

Идею я не уловил, т.к. 32 бита - это прямоугольник 8x4, но никак не квадрат. Скинь свой вариант, только для 64-х бит или для 36-и или для 25.

[f.hump]

Всего каких-то 67 миллионов состояний и 2 Гб памяти занято.

а зачем хранить проверенные состояния? если выполняется, к примеру, последовательный поиск, нужно определить оператор сравнения двух состояний, генерить состояния так чтобы current_state > previous_state. тогда можно игнорить current_state который дает symmerty_state < current_state.

[Stilet]

Скинь свой вариант, только для 64-х бит или для 36-и или для 25.

Хочешь чтоб я написал за тебя? Во-первых тебе мое предложение, как мы уже выяснили, не подходит. Во-вторых, я надеюсь, ты понимаешь что процессор все равно не будет оперировать битом. Процессор всегда все равно будет оперировать своей разрядностью, как бы ты его не оптимизировал.
Поэтому с высказыванием:

нужна не оптимизация, а хорошее решение.

я согласен полностью.

[alcaedo]

Сообщение от f.hump

а зачем хранить проверенные состояния? если выполняется, к примеру, последовательный поиск, нужно определить оператор сравнения двух состояний, генерить состояния так чтобы current_state > previous_state. тогда можно игнорить current_state который дает symmerty_state < current_state.

Суть всей программы такая: любое состояние можно "обработать", получив на выходе от 0 до 320 состояний с большей "глубиной обработки". В качестве аналогии такой пример: шашечная доска с шашками, изначально есть какое-то количество шашек и какое-то количество способов сделать ход (от 0 до 320). Обработав первый ход получаем массив состояний с "глубиной" 1. Теперь из каждого такого состояния можно опять сделать от 0 до 320 ходов, чтобы прийти к какому-то состоянию с глубиной 2. Вот на втором ходе могут уже возникать полностью одинаковые состояния. Их можно и нужно отсеивать. Я развиваю параллельно 2 способа (работают в двух потоках, друг другу не мешают, можно сравнивать время работы на одинаковых начальных данных).

Первый: создаётся массив-словарь. Каждый раз при генерации какой-то пачки (размером от 0 до 320) состояний проверяется эта пачка. Не генерировалось ли каждое из её составляющих раньше. Если да, то такое состояние удаляется из пачки. Затем пачка уникальных для этого шага состояний добавляется к "рабочему набору". Получается лишний расход памяти, но этот "рабочий набор" нужен на случай, если в будущем с одним словарём будут работать несколько потоков программы. Каждый со своим "рабочим набором". Этот способ на данном этапе разработки работает примерно на 50% быстрее второго, на одном конкретном начальном состоянии и на небольшой глубине

Второй: на каждой глубине генерируются все возможные состояния. Они по очереди добавляются в "рабочий массив", и после каждого добавления из этого "рабочего массива" удаляются дубликаты. Функция удаления дубликатов учитывает, что в начале массива элементы уже проверены на уникальность. Способ хорош тем, что не требует держать словарь, но не позволяет распараллелить процесс, т.к. большую часть времени работает функция удаления дубликатов. Этот способ догоняет по времени работы первый способ на большой глубине и на конкретном начальном состоянии.

Начальная глубина везде 0.
Первый столбик - конечная глубина.
Второй - размер выходных данных программы, в скобках - сумма на всех обработанных глубинах.
Третий - время, затраченное на работу в секундах.
Четвёртый - время в годах-днях-часах-минутах-секундах.
Для глубины больше 10 написаны предположения. До 10 включительно - проверено.
Начальное состояние одно конкретное. На другом время и выходные данные будут другим.
0 - 1 (1)
1 - 8 (9)               /        0     =              00
2 - 52 (61)             /        0     =              00
3 - 284 (345)           /        0     =              00
4 - 1398 (1743)         /        0.002 =              00
5 - 6092 (7835)         /        0.054 =              00
6 - 23802 (31637)       /        0.840 =              01
7 - 84008 (115645)      /       10.609 =              11
8 - 270837 (386482)     /      205.574 =           03:26
9 - 798268 (1184768)    /     2526.451 =           42:06
10 - 2137170 (3321938)  /    21137.292 =        05:52:17
11 - 5350000 !?         /   200000.000 =      2 07:33:20
12 - 13357312 !?        /  2000000.000 =     23 03:33:20
13 - 25000000 !?        / 20000000.000 =    231 11:33:20
14                                    =  6 124 19:33:20
15                                    = 63 153 03:33:20
16                                    = 634 71 11:33:20

Пример с шашечной доской только для наглядности. На самом деле, правила генерации состояний - это не шашечные ходы. У меня на каждой следующей глубине количество "шашек", то есть включенных битов в 256-битной переменной уменьшается. Отсюда следует, что:
- конечная глубина не может быть больше начального количества включенных битов;
- количество возможных "ходов" на каждой глубине сначала может возрастать (Но не может превысить 320. Почему - отдельная тема на другом форуме математиков), а потом обязательно уменьшается.

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

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

Суть задачи: как так не накладно избавится от лишних

      MOVNTPS [T]+$C0,XMM3            // 7
      MOVNTPS [T]+$D0,XMM3            // 7.5
...
      BTS     [T]+$C0,R9          // DVH x=15-y, y=15-x
      XOR     R9b,$0F
...
      BTS     [T]+$C0,R10         // DVH x=15, y=15

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

[f.hump]

ОК.
основной принцип поднятия производительности - развертка циклов.

поэтому есть предложение развернуть

       MOV     R9,255

        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

в

        MOV     R9,255

        BT      [F],R9        
        ADC     R9b, -1
        
  @bitset255_00:
        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

        BT      [F],R9        
        ADC     R9b, -1
        
  @bitset255_01:
        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

.......

[alcaedo]

а можно пояснить смысл вот этого:

ADC     R9b, -1

У нас в CF было значение бита с номером 255 из "источника". Мы значение этого бита добавляем к "номеру минус один". Получается, если в источнике под номером 255 был установлен бит, то сам номер не изменится, а если был сброшен, то номер уменьшится.
Дальше устанавливаются (в любом случае (всегда (при всяком раскладе))) биты во всех приёмниках. Какие именно - определяется начальным номером и тем, был установлен или сброшен бит с этим номере в источнике.

Или тут не всё и надо додумать самому?

[f.hump]

это были мои мысли про

      BT      [F],R9
        JC      @bitset255_1
        DEC     R9b
        JNZ     @work255_1

r9b уменьшается (пропускается шаг цикла) если бит сброшен, и если делать развертку то это можно представить в форме ADC

[alcaedo]

Тут подумал, учитывая вот это:

Сообщение от alcaedo

Кстати, симметрии DH и DV встречаются только одновременно с VH. То есть, если квадрат 16х16 бит обладает симметрией DH то там есть и DV и VH. Но симметрия VH может встречаться отдельно от других.

получается, что биты DV и DV могут быть или одновременно включены
dv-dh-11.png
или выключены
dv-dh-00.png
то есть, ведут себя как один бит. Тогда общее количество вариантов уменьшается до 128.
Дальше: бит VH. Если DV и DH выключены, то VH может быть 0 или 1. Но если DV и DH включены, то VH только 1
dv-dh-vh-111.png
Можно сократить количество вариантов ещё на четверть: 96.
Ну и нулевой бит можно проверять только в начале функции (как и сделано в моей заготовке в первых постах). Остаётся 48 вариантов. Можно просто выставить вначале 47 проверок, ведущих на 47 меток. Вроде не такой уж большой текст по объёму. Отсюда вопрос к знатокам, является ли это:

   TEST aType,1
   JZ @skip_xxx
   // тут копируется исходное состояние в нулевой элемент массива
   ADD [T],$20
skip_xxx:
   AND aType,11111110b // теперь нулевой бит уже не нужен, его можно выключить, чтобы не мешал
   CMP aType,00000010b // H
   JE @metka_H
   CMP aType,00000100b // V
   JE @metka_V
   CMP aType,00000110b // V,H
   JE @metka_V_H
   CMP aType,00001000b // VH
   JE @metka_VH
   CMP aType,00001010b // VH,H
   JE @metka_VH_H
   CMP aType,00001100b // VH,V
   JE @metka_VH_V
   CMP aType,00001110b // VH,V,H
   JE @metka_VH_V_H
...
   CMP aType,11111100b // DVH,DV,DH,D,VH,V
   JE @metka_DVH_DV_DH_D_VH_V // переход к 47-й метке
   // если дошли до сюда, значит остался только вариант DVH,DV,DH,D,VH,V,H
   // код для DVH,DV,DH,D,VH,V,H
   // JMP @finish
@metka_H: // 1-я метка
   // код для H
   JMP @finish
@melta_V: // 2-я метка
   // код для V
   JMP @finish
...
@metka_DVH_DV_DH_D_VH_V: 47-я метка
   // код для DVH,DV,DH,D,VH,V   
@finish:

оптимальным вариантом c 47-ю метками?

Можно ещё на некорректный aType проверить, но тогда будет 48 меток

Ещё вроде бы симметрии V,H и VH могут существовать либо по одиночке, либо все вместе. Мне это не кажется таким-же очевидным, как с поворотными симметриями, но не удаётся раскрасить квадрат 16х16 в клеточку, чтобы он был симметричен только по двум из них, но не по третьей. Если всё так, то можно будет сократить количество вариантов ещё на 3/8, до 30 (29 меток, если без проверки на некорректность aType).

[f.hump]

вообще-то, если все так плохо, делается массив jump_targets/handlers индексированный aType

LEA rdx, [jump_targets]
MOV rax, [aType]

JMP [rdx + rax*8]

или

LEA rdx, [handlers]
MOV rax, [aType]

CALL [rdx + rax*8]

[alcaedo]

Тут мне математики подсказали, что в моём случае будет всего 8 вариантов. То есть, достаточно семи CMP и семи JE. А про ваш вариант с jump_targets/handlers я подозревал, что что-то такое есть, но сам не в курсе. Можно подробнее или ссылку?