터무니없는 최적화 이야기

불합리하기 전에

일단 지루해서 내 소프트웨어를 프로파일링하기로 결정했습니다. Styx 이라는 취미 언어용 컴파일러입니다.

부스트래핑하면서 얻은 프로파일러 데이터에서 비용이 일정하지 않은 함수를 발견했습니다.



기능은

function isImported(Declaration* node): bool
{
    return node.symbol.parentUnit():u8* != unitNode:u8*;
} 

우리는 컴파일러에 있습니다. 이 함수는 처리 중인 컴파일 단위에서 선언이 선언되었는지 여부를 알려줍니다.

호출

function parentUnit(): UnitDeclaration*
{
    if kind == $unit do
        return *((&astNode):UnitDeclaration**);
    return parent.parentUnit();
} 

이 함수는 인스턴스가 선언과 연결된 Symbol 클래스의 멤버입니다. AST에 존재하지 않는 "상위"관계를 생성할 수 있습니다. 일반적으로 식별자 조회에 사용되지만 컴파일 단위("모듈"이라고도 함)를 찾을 수도 있습니다.

따라서 여기에 O(n) 상황이 있으며 n은 선언과 해당 단위 사이의 어휘 범위 수입니다. 훌륭하지도 끔찍하지도 않습니다. 하지만 O(1)로 만드는 것은 가능합니다. 왜요 ?

각 컴파일 단위는 파일 이름과 연결됩니다. 파일 이름은 선언이 도입하는 범위를 통해 직접 검색할 수 있습니다. 그 위에 문자열이 다시 계산됩니다. 즉, 컴파일 단위 파일 이름의 포인터와 선언 범위의 포인터만 비교하면 됩니다. 엄청난.

이제 함수는 다음과 같습니다.

function isImported(Declaration* node): bool
{
    return node.scope.filename.ptr != unitNode.filename.ptr;
} 

이제 프로파일러 UI로 변경 사항을 확인해보자



정돈된 ! 이 함수에 대한 호출은 이제 상수 시간입니다.

터무니없는 부분

그래서 여기서 무엇을 했습니까? 괜찮은 최적화. 함수는 O(n)이었지만 이제는 O(1)입니다. 하지만 그것이 무의미하다면?

실제로 최적화는 소프트웨어의 아주 미미한 부분만 변경합니다. 아마도 CPU 시간의 15%는 내 코드 때문일 것입니다. 나머지 85%는 동적 라이브러리인 LLVM에서 사용합니다.