어디에서이 최적화 문제를 시작할 수 있습니까?

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를 기반으로하는 검사보다 훨씬 빠릅니다. 각 필터 "opcode"에는 이와 관련된 시간 클래스가 있습니다. MD5는 높은 타이밍 번호를 가지며, ISFILE은 낮은 타이밍 번호를 얻습니다.

이 실행 계획의 순서를 변경하여 오랜 시간이 소요되는 opcode가 가능한 한 거의 실행되지 않도록하고 싶습니다. (적어도에 따라 세 개의 주소 코드에 대한 NP-전체 문제를 실행의 가장 좋은 순서입니다 따기 "드래곤 도서"에 따르면

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 

: 위의 계획을 위해, 그게 될 것 의미 그 텍스트의 두 번째 판의 511 쪽),이 경우 그들은 레지스터 할당과 기계의 다른 문제에 대해 이야기하고있다. 제 경우에는 실제 "중간 코드"가 훨씬 간단합니다. 근원 IL을 최적의 실행 계획으로 재주문 할 수있는 계획이 있는지 궁금합니다. 여기

은 또 다른 예입니다
{C : \ WINDOWS \ Inf를 * 및 -TP} 또는 {-tf AND NOT C : \ WINDOWS \ SYSTEM32 \ 드라이버 *} :

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 아래로 귀하의 opcodes. 구문 분석 트리가 있고 가능한 한 "평평"한 경우 각 노드에 점수를 할당 한 다음 각 노드의 하위를 가장 낮은 총 점수로 먼저 정렬 할 수 있습니다. 예를 들어

:

{ 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, 또는 추출 노드로 두 아이들과 함께 무엇이든, 필요한 경우 NOT 삽입하십시오 잎의 부모 노드를 참조하여 잎에 대한 모든 참조를 교체)

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. 을 정의 OR.

2. 루트가 AND 인 경우 참조가 실패인지 확인하고 성공으로 참조되는 하위 루트와 분리로 삽입해야 할 경우 invert 조건부를 삽입하십시오. 결과

:

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