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

Question

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

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

Вот еще один пример:
{C: \ Windows \ Inf * И -ТП} ИЛИ {-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 

Answer 1

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

Например:

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

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

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

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

Answer 2

@Greg Hewgill прав, это легче выполнить в 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)) 

Extract Узел (если «Успех» указывает на «Извлеченный узел», используйте соединение для объединения, «Сбой» использует дизъюнкцию; Замените все ссылки на узел со ссылкой на результирующий корень дерева, содержащего Node).

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)) 

Извлечение узла (В случае, когда успех и неудачи оба относятся к узлам, вам придется вводить узел в дерево по шаблону на корню суб -tree определяется узлом)

1. Если корень OR, инвертировать предикат, если это необходимо для обеспечения ссылка Успех и впрыснуть в сочетании с ребенком не ссылается Failure.

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))