컴파일 속도 18% 향상, 절충 없음

Android 런타임 (ART)팀은 컴파일된 코드나 최대 메모리 회귀를 저해하지 않으면서 컴파일 시간을 18% 단축했습니다. 이 개선사항은 메모리 사용량이나 컴파일된 코드의 품질을 희생하지 않으면서 컴파일 시간을 개선하기 위한 2025년 이니셔티브의 일환입니다.

컴파일 시간 속도를 최적화하는 것은 ART에 매우 중요합니다. 예를 들어 적시 (JIT) 컴파일은 애플리케이션의 효율성과 전반적인 기기 성능에 직접적인 영향을 미칩니다. 컴파일 속도가 빨라지면 최적화가 시작되기 전까지의 시간이 줄어들어 더 원활하고 반응성이 뛰어난 사용자 환경을 제공할 수 있습니다. 또한 JIT와 AOT (ahead-of-time) 모두에서 컴파일 시간 속도가 개선되면 컴파일 프로세스 중에 리소스 소비가 줄어들어 배터리 수명과 기기 발열에 도움이 되며, 특히 저사양 기기에서 더욱 그렇습니다.

이러한 컴파일 시간 속도 개선사항 중 일부는 2025년 6월 Android 출시에서 출시되었으며 나머지는 연말 Android 출시에서 제공될 예정입니다. 또한 버전 12 이상의 모든 Android 사용자는 메인라인 업데이트를 통해 이러한 개선사항을 받을 수 있습니다.

최적화 컴파일러 최적화

컴파일러 최적화는 항상 절충이 필요합니다. 속도를 공짜로 얻을 수는 없습니다. 무언가를 포기해야 합니다. Google은 컴파일러를 더 빠르게 만들되 메모리 회귀를 일으키지 않고, 무엇보다도 생성되는 코드의 품질을 저하시키지 않는다는 매우 명확하고 도전적인 목표를 세웠습니다. 컴파일러가 더 빠르지만 앱이 더 느리게 실행된다면 실패한 것입니다.

우리가 기꺼이 투자한 리소스는 엄격한 기준을 충족하는 영리한 솔루션을 찾기 위해 깊이 파고들고 조사하는 데 사용한 개발 시간이었습니다. 개선할 영역을 찾고 다양한 문제에 대한 적절한 해결책을 찾기 위해 Google이 어떻게 노력하고 있는지 자세히 살펴보겠습니다.

가치 있는 최적화 가능성 찾기

측정항목을 최적화하려면 먼저 측정항목을 측정할 수 있어야 합니다. 그렇지 않으면 개선되었는지 여부를 알 수 없습니다. 다행히도 변경 전후에 측정에 사용하는 것과 동일한 기기를 사용하고 기기의 열 제한을 하지 않는 등 몇 가지 예방 조치를 취하면 컴파일 시간 속도가 상당히 일관되게 유지됩니다. 또한 컴파일러 통계와 같은 결정론적 측정을 통해 내부에서 어떤 일이 일어나고 있는지 파악할 수 있습니다.

이러한 개선을 위해 희생한 리소스는 개발 시간이었기 때문에 최대한 빠르게 반복할 수 있기를 원했습니다. 즉, 몇 가지 대표적인 앱 (퍼스트 파티 앱, 서드 파티 앱, Android 운영체제 자체)을 가져와 솔루션의 프로토타입을 제작했습니다. 나중에는 수동 및 자동 테스트를 광범위하게 진행하여 최종 구현이 가치가 있는지 확인했습니다.

엄선된 APK 세트를 사용하여 로컬에서 수동 컴파일을 트리거하고 컴파일 프로필을 가져온 다음 pprof를 사용하여 시간이 소요되는 부분을 시각화합니다.

pprof의 프로필 Flame 그래프 예시

pprof 도구는 매우 강력하며 데이터를 슬라이스, 필터링, 정렬하여 예를 들어 가장 많은 시간이 소요되는 컴파일러 단계 또는 메서드를 확인할 수 있습니다. pprof 자체에 대해서는 자세히 설명하지 않겠습니다. 막대가 클수록 컴파일에 더 많은 시간이 걸렸다는 의미입니다.

이러한 뷰 중 하나는 '상향식' 뷰로, 어떤 메서드가 가장 많은 시간을 차지하는지 확인할 수 있습니다. 아래 이미지에서 컴파일 시간의 1% 이상을 차지하는 Kill이라는 메서드를 확인할 수 있습니다. 다른 주요 방법 중 일부는 이 블로그 게시물의 뒷부분에서 설명합니다.

프로필의 상향식 뷰

최적화 컴파일러에는 전역 값 번호 지정 (GVN)이라는 단계가 있습니다. 전체적으로 어떤 역할을 하는지 걱정할 필요는 없지만, 필터에 따라 일부 노드를 삭제하는 `Kill` 이라는 메서드가 있다는 점을 알아두는 것이 중요합니다. 모든 노드를 반복하고 하나씩 확인해야 하므로 시간이 많이 걸립니다. 그 시점에 활성 상태인 노드와 관계없이 검사가 거짓이 될 것임을 미리 알 수 있는 경우가 있습니다. 이러한 경우 반복을 완전히 건너뛰어 1.023% 에서 약 0.3% 로 줄이고 GVN의 런타임을 약 15% 개선할 수 있습니다.

가치 있는 최적화 구현

시간이 어디에 소요되는지 측정하고 감지하는 방법을 다루었지만 이는 시작에 불과합니다. 다음 단계는 컴파일에 소요되는 시간을 최적화하는 방법입니다.

일반적으로 위의 `Kill` 과 같은 경우에는 노드를 반복하는 방법을 살펴보고, 예를 들어 병렬로 작업을 수행하거나 알고리즘 자체를 개선하여 더 빠르게 처리합니다. 사실 처음에는 그렇게 시도했는데, 아무것도 찾을 수 없었을 때 '잠깐만…' 하는 순간이 있었고, 어떤 경우에는 반복하지 않는 것이 해결책이라는 것을 알게 되었습니다. 이러한 최적화를 수행할 때는 나무만 보고 숲을 놓치기 쉽습니다.

그 외의 경우에는 다음과 같은 다양한 기법을 사용했습니다.

• 휴리스틱을 사용하여 최적화가 가치 있는 결과를 생성하지 못하므로 건너뛸 수 있는지 여부를 결정합니다.
• 추가 데이터 구조를 사용하여 계산된 데이터를 캐시합니다.
• 속도 향상을 위해 현재 데이터 구조 변경
• 경우에 따라 주기를 방지하기 위해 결과를 지연 계산
• 적절한 추상화 사용 - 불필요한 기능은 코드 속도를 저하시킬 수 있음
• 자주 사용되는 포인터를 여러 로드를 통해 추적하지 않음

최적화가 추구할 가치가 있는지 어떻게 알 수 있나요?

그게 바로 이 기능의 장점입니다. 특정 영역에서 컴파일 시간이 많이 소요된다는 것을 감지하고 이를 개선하기 위해 개발 시간을 할애한 후에도 해결책을 찾지 못하는 경우가 있습니다. 아무것도 할 수 없거나, 구현하는 데 너무 오래 걸리거나, 다른 측정항목이 크게 회귀하거나, 코드베이스 복잡성이 증가하는 등의 문제가 있을 수 있습니다. 이 블로그 게시물에서 볼 수 있는 모든 성공적인 최적화에는 결실을 맺지 못한 수많은 다른 최적화가 있다는 점을 알아두세요.

비슷한 상황이라면 가능한 한 적은 작업으로 측정항목을 얼마나 개선할 수 있을지 추정해 보세요. 이는 다음을 의미합니다.

1. 이미 수집한 측정항목을 사용하거나 직감에 따라 추정
2. 빠르고 간단한 프로토타입으로 추정하기
3. 솔루션을 구현합니다.

솔루션의 단점을 추정하는 것도 잊지 마세요. 예를 들어 추가 데이터 구조를 사용하려는 경우 얼마나 많은 메모리를 사용할 의향이 있나요?

자세히 살펴보기

서론은 이만하고, 구현된 변경사항을 살펴보겠습니다.

FindReferenceInfoOf라는 메서드를 최적화하기 위한 변경사항을 구현했습니다. 이 메서드는 벡터의 선형 검색을 실행하여 항목을 찾고 있었습니다. FindReferenceInfoOf가 O(n)이 아닌 O(1)이 되도록 명령어 ID로 색인이 생성되도록 데이터 구조를 업데이트했습니다. 또한 크기 조절을 방지하기 위해 벡터를 미리 할당했습니다. 벡터에 삽입한 항목 수를 계산하는 추가 필드를 추가해야 했기 때문에 메모리를 약간 늘렸지만, 최대 메모리가 증가하지 않았기 때문에 작은 희생이었습니다. 이를 통해 LoadStoreAnalysis 단계가 34~66% 빨라졌으며, 결과적으로 컴파일 시간이 약 0.5~1.8% 개선되었습니다.

여러 위치에서 사용하는 HashSet의 맞춤 구현이 있습니다. 이 데이터 구조를 만드는 데 상당한 시간이 걸렸는데 그 이유를 알아냈습니다. 수년 전 이 데이터 구조는 매우 큰 HashSet을 사용하는 몇 군데에서만 사용되었으며 이에 맞게 최적화되었습니다. 하지만 요즘에는 항목이 몇 개 없고 수명이 짧은 반대 방향으로 사용되었습니다. 즉, 이 거대한 HashSet을 만드는 데 주기를 낭비했지만 몇 개의 항목에만 사용하고 삭제했습니다. 이 변경사항으로 컴파일 시간이 약 1.3~2% 개선되었습니다. 추가적인 이점으로, 이전만큼 큰 데이터 구조를 사용하지 않기 때문에 메모리 사용량이 약 0.5~1% 감소했습니다.

람다에 참조로 데이터 구조를 전달하여 복사를 방지함으로써 컴파일 시간을 약 0.5~1% 개선했습니다. 이는 원래 검토에서 누락되어 수년 동안 코드베이스에 남아 있었습니다. pprof에서 프로필을 살펴본 덕분에 이러한 메서드가 많은 데이터 구조를 만들고 삭제한다는 사실을 알게 되었고, 이를 조사하고 최적화할 수 있었습니다.

계산된 값을 캐싱하여 컴파일된 출력을 작성하는 단계를 가속화했으며, 이를 통해 전체 컴파일 시간이 약 1.3~2.8% 개선되었습니다. 안타깝게도 추가 부기 작업이 너무 많았고 자동 테스트에서 메모리 회귀가 발생했다고 알렸습니다. 나중에 동일한 코드를 다시 살펴보고 메모리 회귀를 처리할 뿐만 아니라 컴파일 시간을 약 0.5~1.8% 더 개선하는 새 버전을 구현했습니다. 이 두 번째 변경에서는 두 데이터 구조 중 하나를 제거하기 위해 이 단계가 작동하는 방식을 리팩터링하고 재구상해야 했습니다.

최적화 컴파일러에는 성능을 개선하기 위해 함수 호출을 인라인하는 단계가 있습니다. 인라인할 메서드를 선택하기 위해 계산을 수행하기 전에 휴리스틱을 사용하고, 작업을 수행한 후 인라인을 완료하기 직전에 최종 확인을 수행합니다. 이 중 하나라도 인라인 처리할 가치가 없다고 감지하면 (예: 너무 많은 새 명령어가 추가됨) 메서드 호출을 인라인 처리하지 않습니다.

시간이 많이 소요되는 계산을 수행하기 전에 인라인 처리의 성공 여부를 추정하기 위해 '최종 검사' 카테고리에서 '휴리스틱' 카테고리로 두 가지 검사를 이동했습니다. 이는 추정치이므로 완벽하지는 않지만, 새로운 휴리스틱이 성능에 영향을 미치지 않으면서 이전에 인라인된 항목의 99.9% 를 처리하는 것을 확인했습니다. 이러한 새로운 휴리스틱 중 하나는 필요한 DEX 레지스터 (약 0.2~1.3% 개선)에 관한 것이고 다른 하나는 명령어 수 (약 2% 개선)에 관한 것입니다.

여러 위치에서 사용하는 BitVector의 맞춤 구현이 있습니다. 특정 고정 크기 비트 벡터의 경우 크기 조절이 가능한 BitVector 클래스를 더 간단한 BitVectorView로 대체했습니다. 이렇게 하면 일부 간접 참조 및 런타임 범위 검사가 제거되고 비트 벡터 객체의 구성 속도가 빨라집니다.

또한 BitVectorView 클래스는 기본 스토리지 유형에서 템플릿화되었습니다 (이전 BitVector로 uint32_t를 항상 사용하는 대신). 이렇게 하면 Union()과 같은 일부 작업이 64비트 플랫폼에서 두 배 많은 비트를 함께 처리할 수 있습니다. Android OS를 컴파일할 때 영향을 받는 함수의 샘플이 총 1% 이상 감소했습니다. 이는 여러 변경사항[1, 2, 3, 4, 5, 6]에 걸쳐 이루어졌습니다.

모든 최적화에 대해 자세히 이야기하려면 하루 종일 걸릴 것입니다. 추가 최적화에 관심이 있다면 Google에서 구현한 다른 변경사항을 살펴보세요.

• 부기 추가: 컴파일 시간이 약 0.6~1.6% 개선됩니다.
• 가능한 경우 데이터를 지연 계산하여 주기를 방지합니다.
• 사용되지 않을 때 사전 계산 작업을 건너뛰도록 코드를 리팩터링합니다.
• 할당자를 다른 위치에서 쉽게 가져올 수 있는 경우 일부 종속 로드 체인을 피합니다.
• 불필요한 작업을 방지하기 위해 검사를 추가하는 또 다른 사례입니다.
• 레지스터 할당자에서 레지스터 유형 (코어/FP)에 대한 빈번한 분기를 피합니다.
• 컴파일 시간에 일부 배열이 초기화되었는지 확인합니다. clang에 의존하지 마세요.
• 루프를 정리합니다. 루프 부작용으로 인해 컨테이너의 내부 포인터를 새로고침할 필요가 없으므로 clang이 더 잘 최적화할 수 있는 범위 루프를 사용합니다. 각 입력에 대해 인라인된 `InputAt(.)` 을 통해 루프에서 가상 함수 `HInstruction::GetInputRecords()` 를 호출하지 않습니다.
• 컴파일러 최적화를 활용하여 방문자 패턴에 Accept() 함수를 사용하지 않습니다.

결론

ART의 컴파일 시간 속도를 개선하기 위한 노력은 상당한 개선을 가져왔으며, Android를 더 원활하고 효율적으로 만드는 동시에 배터리 수명과 기기 발열을 개선하는 데도 기여했습니다. 최적화를 부지런히 식별하고 구현함으로써 메모리 사용량이나 코드 품질을 저하시키지 않으면서도 상당한 컴파일 시간 이득을 얻을 수 있음을 입증했습니다.

이 과정에서 pprof와 같은 도구를 사용한 프로파일링, 반복에 대한 의지, 때로는 성과가 적은 방법을 포기하는 결단이 필요했습니다. ART팀의 공동 노력으로 컴파일 시간이 눈에 띄게 줄었을 뿐만 아니라 향후 발전을 위한 기반도 마련되었습니다.

이러한 모든 개선 사항은 2025년 연말 Android 업데이트에서 제공되며, Android 12 이상의 경우 메인라인 업데이트를 통해 제공됩니다. 최적화 프로세스에 대한 이 심층 분석이 컴파일러 엔지니어링의 복잡성과 이점에 대한 유용한 정보를 제공하기를 바랍니다.