Где я могу начать с этой проблемы оптимизации? - PullRequest
Новая
       18

Где я могу начать с этой проблемы оптимизации?

3 голосов
/ 02 августа 2010

У меня есть простая программа, которая читает кучу вещей из файловой системы, фильтрует результаты и печатает их. Эта простая программа реализует предметно-ориентированный язык для облегчения выбора. Этот DSL «компилируется» в план выполнения, который выглядит следующим образом (входные данные были C:\Windows\System32\* OR -md5"ABCDEFG" OR -tf): 

Index  Success  Failure  Description
    0        S        1  File Matches C:\Windows\System32\*
    1        S        2  File MD5 Matches ABCDEFG
    2        S        F  File is file. (Not directory)

Фильтр применяется к данному файлу, и в случае успеха указатель индекса переходит к индексу, указанному в поле успеха, и, если он не работает, указатель индекса переходит к числу, указанному в поле сбоя. «S» означает, что файл проходит фильтр, F означает, что файл должен быть отклонен.

Конечно, фильтр, основанный на простой проверке атрибута файла (! FILE_ATTRIBUTE_DIRECTORY), работает намного быстрее, чем проверка, основанная на MD5 файла, которая требует открытия и выполнения фактического хэша файла. Каждый фильтр «код операции» имеет связанный с ним временной класс; MD5 получает высокий временный номер, ISFILE получает низкий временный номер.

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

Index  Success  Failure  Description
    0        S        1  File is file. (Not directory)
    1        S        2  File Matches C:\Windows\System32\*
    2        S        F  File MD5 Matches ABCDEFG

Согласно «Книге Дракона», выбор наилучшего порядка исполнения для трех адресов является проблемой NP-Complete (по крайней мере, в соответствии со страницей 511 второго издания этого текста), но в этом случае они говорят о распределении регистров и других вопросах машины. В моем случае фактический «промежуточный код» намного проще. Мне интересно, существует ли такая схема, которая позволила бы мне переупорядочить исходный IL в оптимальный план выполнения.

Вот еще один пример:
{C: \ Windows \ Inf * AND -tp} ИЛИ {-tf И НЕ C: \ Windows \ System32 \ Drivers *}

Разобрано до: 

Index  Success  Failure  Description
    0        1        2  File Matches C:\Windows\Inf\*
    1        S        2  File is a Portable Executable
    2        3        F  File is file. (Not directory)
    3        F        S  File Matches C:\Windows\System32\Drivers\*

что оптимально: 

Index  Success  Failure  Description
    0        1        2  File is file. (Not directory)
    1        2        S  File Matches C:\Windows\System32\Drivers\*
    2        3        F  File Matches C:\Windows\Inf\*
    3        S        F  File is a Portable Executable

Ответы [ 2 ]

3 голосов
/ 02 августа 2010

Похоже, может быть проще выбрать оптимальный порядок до компиляции ваших кодов операций.Если у вас есть дерево разбора, и оно настолько «плоское», насколько это возможно, то вы можете назначить оценку каждому узлу, а затем отсортировать дочерние элементы каждого узла сначала по наименьшей общей оценке.

Например: 

{ C:\Windows\Inf* AND -tp } OR { -tf AND NOT C:\Windows\System32\Drivers* }
         1             2          3                 4

      OR
     /  \
  AND    AND
 /  \   /   \
1    2 3     4

Можно отсортировать узлы AND (1, 2) и (3, 4) по наименьшему количеству баллов, а затем назначить этот балл каждому узлу.Затем отсортируйте дочерние элементы узла OR по наименьшему количеству их дочерних элементов.

Поскольку AND и OR являются коммутативными, эта операция сортировки не изменит значения вашего общего выражения.

1 голос
/ 02 августа 2010

@ Грег Хьюгилл прав, это легче выполнить на AST, чем на Промежуточном коде. Поскольку вы хотите работать с промежуточным кодом, первой целью является его преобразование в дерево зависимостей (которое будет выглядеть как AST /shrug).

Начните с листьев - и, вероятно, проще всего будет использовать отрицательные предикаты для NOT. 

Index  Success  Failure  Description
0        1        2  File Matches C:\Windows\Inf\*
1        S        2  File is a Portable Executable
2        3        F  File is file. (Not directory)
3        F        S  File Matches C:\Windows\System32\Drivers\*

Извлечь лист (что-либо с обоими дочерними элементами в качестве S, F или извлеченным узлом; при необходимости вставьте НЕ; замените все ссылки на лист со ссылкой на родительский узел листа) 

Index  Success  Failure  Description
0        1        2  File Matches C:\Windows\Inf\*
1        S        2  File is a Portable Executable
2        L1        F  File is file. (Not directory)

L1=NOT(cost(child))
    |
Pred(cost(PATH))

Извлечь узел (Если успех указывает на извлеченный узел, для соединения используется соединение; В отказе используется дизъюнкция; Замените все ссылки на узел со ссылкой на результирующий корень дерева, содержащего узел). 

Index  Success  Failure  Description
0        1        L3  File Matches C:\Windows\Inf\*
1        S        L3  File is a Portable Executable


L3=AND L1 L2 (cost(Min(L1,L2) + Selectivity(Min(L1,L2)) * Max(L1,L2)))
               /           \
L1=NOT(cost(child))     L2=IS(cost(child))
    |                       |
3=Pred(cost(PATH))      2=Pred(cost(ISFILE))

Узел извлечения 

Index  Success  Failure  Description
0        L5       L3  File Matches C:\Windows\Inf\*

L5=OR L3 L4 (cost(Min(L3,L4) + (1.0 - Selectivity(Min(L3,L4))) * Max(L3,L4)))
                    /                          \
                    |                       L4=IS(cost(child))
                    |                           | 
                    |                       1=Pred(cost(PORT_EXE))
                    |
L3=AND L1 L2 (cost(Min(L1,L2) + Selectivity(Min(L1,L2)) * Max(L1,L2)))
               /           \
L1=NOT(cost(child))     L2=IS(cost(child))
    |                       |
3=Pred(cost(PATH))      2=Pred(cost(ISFILE))

Извлечение узла (В случае, когда Успех и Отказ оба ссылаются на Узлы, вам нужно будет внедрить Узел в дерево путем сопоставления с образцом в корне поддерева, определенного Узлом)

  1. Если root - ИЛИ, инвертировать предикат, если необходимо, чтобы убедиться, что ссылка - Успех, и вводить вместе с дочерним элементом, на который не ссылается Ошибка.

  2. Если root равен AND, при необходимости инвертировать предикат для обеспечения ссылки на Failure и внедрить как дизъюнкцию с дочерним корнем, на который ссылается Success.

В результате: 

L5=OR L3 L4 (cost(Min(L3,L4) + (1.0 - Selectivity(Min(L3,L4))) * Max(L3,L4)))
                    /                          \
                    |                       L4=AND(cost(as for L3))
                    |                             /               \
                    |                       L6=IS(cost(child))   L7=IS(cost(child))
                    |                           |                       |
                    |                       1=Pred(cost(PORT_EXE))   0=Pred(cost(PATH))
                    |
L3=AND L1 L2 (cost(Min(L1,L2) + Selectivity(Min(L1,L2)) * Max(L1,L2)))
               /           \
L1=NOT(cost(child))     L2=IS(cost(child))
    |                       |
3=Pred(cost(PATH))      2=Pred(cost(ISFILE))
...