[WWDC] Link fast: Improve build and launch times — Static Linking

WWDC 2022 Link fast: Improve build and launch times 세션 Static Linking 부분 정리

naljin

18 min readJul 19, 2022

들어가기 전에

의역이 포함되어있습니다. 나중에 제가 정독하기 위해서 정리합니다. 한 50% 정도 이해한듯요?ㅠ

여기서는 Static Link / Dynamic Link 중 Static Link 에 대해서만 다룹니다. Dynamic 은 따로 나누겠음 ◠‿◠ ,,

잘못 번역한 부분이 있거나 더 좋은 표현이 있다면 알려주세여

Link fast: Improve build and launch times

거두절미하고 linking 이란 무엇일까요?

당신이 작성한 코드도 있겠지만, 다른 사용자가 라이브러리 또는 프레임워크 형태로 작성한 코드도 사용할 때가 있을 것입니다. 이러한 라이브러리를 사용하려면 링커가 필요합니다.

linking 은 아래 두가지 타입으로 나뉩니다.

static linking — 앱을 빌드(build) 할 때 발생. 앱이 빌드되는 데 걸리는 시간과 앱의 크기에 영향을 미칠 수 있음.
dynamic linking — 앱이 실행(launched) 될 때 발생. 유저가 앱이 시작될 때까지 기다려야 하는 시간에 영향을 미칠 수 있음.

이제 순서대로 설명해보겠습니다.

What is static linking?

초기에는 프로그램이 단순했습니다. 소스 파일이 하나뿐이었기 때문에 빌드하는 것도 쉬웠죠. 그냥 하나의 소스 파일로 컴파일러를 실행하고, executable 프로그램을 생성했습니다.

하지만 모든 소스 코드를 하나의 파일에 포함시키는 것은 확장에 용이하지 않았습니다. 큰 텍스트 파일의 편집을 피하기 위해서 뿐만 아니라, 빌드할 때마다 모든 function 을 다시 컴파일하고 싶지 않았기 때문에 코드를 여러 개의 소스 파일로 나눌 필요성이 생겼습니다.

이렇게 나눠진 여러 개의 소스 파일을 어떻게 빌드를 했을까요?

바로 컴파일러를 두 부분으로 나누어 여러개의 소스 파일을 빌드했습니다.

첫번째 부분에서는 소스 코드를 새로운 중간(intermediate) “relocatable object” 파일로 컴파일합니다.

두번째 부분에서는 relocatable.o file 을 읽고 executable 프로그램을 생성합니다.

우리는 여기서 두 번째 ld 부분을 정적 링커라고 부릅니다 (참고로 ld 는 “load” 의 약어이며, linker 는 원래 loader 라고 불렸다고 합니다).

이제 static linker 의 유래를 알게되었죠?

소프트웨어가 진화함에 따라, 사람들은 .o 파일들을 주고받는 것을 번거롭게 느꼈습니다. 따라서 누군가 “.o 파일들을 ‘라이브러리’로 묶으면 좋지 않을까?”라고 생각했습니다.

당시의 파일을 묶는 표준적인 방법은 아카이브 도구인 ‘ar’ 을 사용하는 것이었습니다. 이는 백업과 배포에 사용되었습니다.

아래 그림과 같이 여러 개의 .o 파일을 ‘ar’ 해서 archive 로 만들 수 있게 되었고, 링커는 .o 파일들을 archive 파일로부터 직접 읽는 방법을 알도록 향상되었습니다. 이는 공통 코드 공유를 위한 큰 개선이었습니다.

그 당시에는 그냥 library 또는 archive라고 불렸지만, 오늘날 우리는 이것을 static library 라고 부릅니다.

하지만 이제 최종 프로그램은 라이브러리에서 몇개의 함수만 사용했을지라도 수천개의 모든 함수들이 복사되어 점점 커지는 문제점이 있었습니다.

이에 링커는 static library에서 모든 .o 파일들을 사용하는 대신, undefined symbol 을 해결(resolve) 하는데 필요한 .o 파일만을 static library 에서 꺼내 사용하는 식으로 최적화가 되었습니다.

이는 어떤 사람이 모든 C standard library 함수를 포함하는 큰 libc.a static libary 를 만들 수 있다는 것을 의미합니다. 모든 프로그램은 하나의 libc.a와 링크될 수 있지만, 각 프로그램은 프로그램이 실제로 필요로 하는 libc 의 부분만을 얻습니다.

우리는 여전히 이 최적화 모델을 사용합니다.

하지만 static libraries 로부터의 선택적 로딩 개념은 모호하고 많은 프로그래머들을 괴롭힙니다. 따라서 정적 라이브러리의 선택적 로딩을 조금 더 명확하게 하기 위해, 간단한 시나리오를 통해 설명하겠습니다.

main.c에서는 foo 함수를 호출하는 main 함수가 있습니다.

foo.c에서는 bar 를 호출하는 foo가 있습니다.

bar.c에서는 bar와 함께, 사용하지 않는 unused 함수가 구현됩니다.

baz.c에서는 undef 라는 함수를 호출하는 함수 baz가 있습니다.

이제 우리는 각각을 .o 파일로 컴파일합니다. 이때 각 파일에 정의되지 않은 함수(foo, bar, undef) 는 회색 상자가 없는 것을 볼 수 있습니다 . 즉, 정의(definition)가 아닌 심볼(symbol)을 사용합니다.

이제 bar.o와 baz.o를 libbarbaz.a 라는 정적 라이브러리에 결합했다고 가정해 보겠습니다. 이제 실제 프로그램에서 무슨 일이 일어나는지 살펴봅시다.

처음으로 링커는 명령 순서대로 파일을 처리합니다.

제일 먼저 main.o 를 찾았기 때문에

main.o를 로드하고 symbol 테이블에 표시된 “main”에 대한 정의(definition)을 찾습니다. 그러나 곧 main.o 에는 정의되지 않은 “foo”가 있음을 발견합니다.

링커는 command line 의 다음 파일인 foo.o 를 parse합니다.

이 파일을 통해 “foo”의 정의(definition)를 추가합니다. 이제 foo 는 더 이상 undefined 된 상태가 아닙니다.

그러나 foo.o를 로드하면 “bar” 라는 정의되지 않은 새로운 심볼이 추가됩니다.

이제 command line에 있는 .o 파일이 모두 로드되었으므로 링커는 정의되지 않은 심볼(undefined symbol)이 남아 있는지 확인합니다. 이 경우 “bar”가 undefined 상태로 남아있습니다.

따라서 링커는 라이브러리가 undefined symbol “bar”를 충족하는지 확인하기 위해 command line에서 라이브러리를 살펴보기 시작합니다.

링커는 정적 라이브러리에서 bar.o가 심볼 “bar”를 정의하는 것을 찾고, 아카이브에서 bar.o를 로드합니다.

이제 더 이상 정의되지 않은 심볼이 없으므로 링커는 라이브러리 처리를 중단합니다.

이제 링커는 다음 단계로 이동하여 프로그램에 있어야할 모든 함수와 데이터에 주소를 할당합니다.

그리고 모든 함수와 데이터를 output 파일에 복사합니다. 이렇게 output 프로그램이 생겼습니다!

위에서 살펴봤듯, 링커가 정적 라이브러리에서 선택적으로 로드하는 방식으로 동작하기 때문에 baz.o는 정적 라이브러리에 있었지만 프로그램에 로드되지 않았습니다.

이는 알아차리기 어렵지만 정적 라이브러리의 주요한 특징입니다.

Recent ld64 improvements

이제 static linking 과 static 라이브러리의 기본을 이해했으니 ld64로 알려진 애플의 static linker에 대한 최근 개선 사항으로 넘어가 봅시다.

대중의 요구에 따라 우리는 올해 ld64를 최적화하는 데 시간을 보냈고, 그 결과 올해의 링커는 많은 프로젝트에서 두 배 더 빠릅니다.

우선 개발 시스템의 코어를 더 잘 활용하는 방향으로 이를 달성했습니다. 여러 개의 코어를 사용하여 링커 작업을 병렬로 수행할 수 있는 여러 영역을 발견했습니다. 여기에는 입력에서 출력 파일로 콘텐츠를 복사하고, LINKEDIT의 다른 부분을 병렬로 빌드하고, UUID 계산과 코드 서명 해시를 병렬로 변경하는 것이 포함됩니다.

다음으로, 우리는 많은 알고리즘을 개선했습니다. C++ string_view 객체를 사용하여 각 심볼의 문자열 슬라이스를 나타내도록 전환하면 exports-tree builder가 매우 잘 작동합니다. 또한 바이너리 UUID를 계산할 때 하드웨어 가속을 활용하는 최신 암호화 라이브러리를 사용했고, 다른 알고리즘도 개선했습니다.

Static linking best practices

링커 성능을 개선하기 위해 작업하는 동안, 일부 앱에서 링크 시간에 영향을 미치는 configuration 문제를 발견했습니다. 이제 링크 시간을 개선하기 위해 프로젝트에서 무엇을 할 수 있는지에 대해 다섯 가지 주제로 나눠 다루겠습니다.

정적 라이브러리를 사용해야 하는지 여부 (whether you should use static libraries).
링크 시간에 큰 영향을 미치는 잘 알려지지 않은 세 가지 옵션
여러분을 놀라게 할 수 있는 정적 링크 동작 (static linking behavior)

1. 정적 라이브러리를 사용해야할 때

정적 라이브러리로 빌드되는 소스 파일을 작업하는 경우에는 빌드 시간이 느려집니다. 파일이 컴파일된 후에는 contents 의 table을 포함하여 전체 정적 라이브러리가 다시 빌드되어야 하기 때문입니다. 이렇게 추가적인 I/O 가 많이 발생합니다.

따라서 정적 라이브러리는 코드가 활발히 변경되지 않는 안정적인 코드에 가장 적합합니다. 빌드 시간을 줄이기 위해서 현재 개발 중인 코드를 정적 라이브러리 밖으로 이동하는 것을 고려해야 합니다.

2. -all_load

앞서 살펴 본 archives에서 선택적 로드의 단점은 링커의 속도를 늦춘다는 것입니다. 그 이유는 빌드를 재현할 수 있게(reproducible) 하고 전통적인 정적 라이브러리 시맨틱을 따르도록 하기 위해 링커는 고정된 직렬 순서로 정적 라이브러리를 처리해야 하기 때문입니다. 이는 ld64의 병렬화의 장점 중 일부를 정적 라이브러리와 함께 사용할 수 없다는 것을 의미합니다.

그러나 이러한 선택적 로드가 필요하지 않은 경우 “all load ” 링커 옵션을 사용하여 빌드 속도를 높일 수 있습니다. 이 옵션은 링커에게 모든 정적 라이브러리에서 모든 .o 파일을 무작위로 로드하도록 지시하기 때문에, 앱이 선택적인 로딩을 하지만 결국 모든 정적 라이브러리로부터 대부분의 컨텐츠를 로드하는 경우라면 유용합니다. -all_load 를 사용하면 링커가 모든 정적 라이브러리와 해당 콘텐츠를 병렬로 parse할 수 있습니다.

그러나 앱이 동일한 symbol 을 구현하는 여러 정적 라이브러리가 있고, 정적 라이브러리의 command line 순서에 따라 어떤 구현이 사용될지 결정되는 영리한 트릭을 쓴다면 이 옵션은 적합하지 않습니다. 왜냐하면 링커는 모든 구현(implementations)을 로드하기 때문에 반드시 regular static linking mode 에서 발견된 symbol semantics 을 얻는 것은 아니기 때문입니다.

-all_load 의 또 다른 단점은 “미사용” 코드가 추가되기 때문에 프로그램을 더 크게 만들 수 있다는 것입니다. 이를 보완하기 위해 링커 옵션 -dead_strip을 사용할 수 있습니다. 이 옵션을 선택하면 링커가 unreachable 한 코드와 데이터를 제거합니다. dead stripping 알고리즘은 빠르고, 일반적으로 출력 파일의 크기를 줄임으로써 자체적인 비용을 지불합니다.

그러나 -all_load 및 -dead_strip을 사용하려는 경우에는, 해당 옵션의 사용/미사용 케이스의 링커 시간을 측정해서 당신의 사례에 적합한지 확인해야 합니다.

실제로 엑스코드에서 “Other Linker Flags” 에서 -all_load 를 설정할 수 있고, “Dead Code Stripping” 또한 설정 할 수 있습니다.

3. -no_exported_symbols

다음으로 살펴볼 링커 옵션은 -no_exported_symbols 입니다.

여기에는 배경 지식이 조금 포함되는데, 링커가 생성하는 LINKEDIT 세그먼트의 한 부분은 export 트리입니다. 여기서 export 트리는 모든 exported symbol 의 이름, 주소 및 플래그를 인코딩하는 접두사 트리를 뜻합니다.

이 세그먼트에는 심볼 및 문자열 테이블, 압축된 동적 링킹 정보, 코드 서명 정보 및 간접 심볼 테이블과 같은 링커에 대한 raw data 가 포함됩니다. 이 모든 데이터는 load 명령어에 의해 지정된 대로 영역을 점유합니다. (참고 — A curious case of Mach-O Executable)

모든 dylibs은 exported symbol 을 가져야 하는 반면, 메인 앱 바이너리는 일반적으로 exported symbol을 필요로 하지 않습니다. 즉, 일반적으로 어떤 것도 main executable(실행 파일)에서 심볼을 찾지 않습니다.

이 경우 앱 타겟에 -no_exported_symbols를 사용하여 LINKEDIT 에서 트리 데이터 구조 생성을 건너뛰도록 설정할 수 있습니다. 이를 통해 링크 시간이 향상됩니다.

그러나 앱이 메인 실행파일(main executable)에 다시 링크하는 플러그인을 로드하거나 xctest 번들을 실행하기 위해 앱과 함께 xctest를 호스트 환경으로 사용하는 경우에는 앱에 모든 exports가 있어야 합니다. 즉, 이러한 구성에는 -no_exported_symbols를 사용할 수 없습니다.

이제는 exports 트리가 크면 줄이려고(suppress) 생각할 수 있습니다. 아래의 dyld_info 명령을 실행하여 exported symbols 의 개수를 셀 수 있습니다.

dyld_info -exports /path/to/binary | wc -l

dyld_info 툴에 대해서는 이 세션의 뒷부분에서 자세히 말씀드리겠습니다.

우리가 본 한 대형 앱에는 약 백만 개의 exported symbols 이 있었고, 링커는 그 많은 심볼들에 대한 exports 트리를 만드는 데 2~3초가 걸렸습니다. 따라서 -no_exported_symbols를 추가하면 해당 앱의 링크 시간이 2~3초 단축되었습니다.

4. -no_deduplicate

다음 옵션은 -no_deduplicate입니다.

몇 년 전, 우리는 동일한 명령어(instructions)를 가지고 있지만 다른 이름을 가진 함수들을 병합하기 위해 링커에 새로운 패스(pass)를 추가했습니다. 그리고 C++ template expansions 에서 이러한 함수들이 많다는 것을 발견했습니다.

하지만 이를 찾는 알고리즘은 고비용이었습니다. 링커는 중복을 찾기 위해 모든 함수의 명령어를 재귀적으로 해시해야 했습니다. 이로 인해, 우리는 알고리즘을 제한하여 링커가 weak-def symbols 만 보도록 했습니다. 이 심볼들은 C++ 컴파일러가 인라인되지 않은 template expansions을 위해 내보내는 것입니다. (Those are the ones the C++ compiler emits for template expansions that were not inlined.)

중복 제거(de-dup)는 크기에 대한 최적화입니다. 하지만 Debug 모드에서 빌드할 때 중요한것은 크기가 아닌, 빠른 속도 입니다. 따라서 기본적으로 Xcode는 Debug configuration 의 링커에 -no_deduplicate를 전달하여 중복 제거 최적화를 비활성화합니다 (즉 중복 허용).

또한 clang link line을 -O0(no optimization)으로 실행하면 clang은 no-dedup 옵션을 링커에 전달할 것입니다.

요약하면 C++를 사용하고 custom build가 있는 경우, 즉 Xcode에서 비표준(non-standard) 구성을 사용하거나 다른 빌드 시스템을 사용하는 경우 링크 시간을 개선하기 위해 디버그 빌드에 -no_deduplicate가 추가되었는지 확인해야 합니다.

5. static linking behavior

이제 정적 라이브러리를 사용할 때 경험할 수 있는 몇 가지 놀라운 점들에 대해 이야기해보겠습니다.

1. 첫 번째는 앱이 정적 라이브러리를 링크한다고 해도, 라이브러리 안에 있는 모든 소스 코드가 최종 앱에 포함되지 않는 것입니다.

예를 들어 어떤 함수에 __attribute__((used)) 를 추가했다거나, Objective-C 카테고리가 있다고 해봅시다. 이때 링커는 선택적 로딩을 수행하기 때문에, 정적 라이브러리에 있는 해당 object 파일이 링크 과정 중에 필요한 심볼을 정의하지 않는다면 해당 object 파일을 로드하지 않습니다.

2. 두번째로 정적 라이브러리와 dead stripping 간의 상호작용도 흥미로운데요, dead stripping 은 정적 라이브러리의 많은 문제를 숨길 수 있습니다.