Posted by Aditya Kumar – Software Engineer
Context: Binary layout using a symbol order file (also known as binary order file or linker order file) is a well-known link-time optimization. The linker uses the order of symbols in the order file to lay out symbols in the binary. Order file-based binary layout improves application launch time as well as other critical user journeys.
Order file generation is typically a multi-step process where developers use different tools at every stage. We are providing a unified set of tools and documentation that will allow every native app developer to leverage this optimization. Both Android app developers and the AOSP community can benefit from these tools.
Background: Source code is typically structured to facilitate software development and comprehension. The layout of functions and variables in a binary is also impacted by their relative ordering in the source code. The binary layout impacts application performance, as the operating system has no way of knowing which symbols will be required in the future and typically uses spatial locality as one of the cost models for prefetching subsequent pages. But the order of symbols in a binary may not reflect the program execution order.
When an application executes, fetching symbols that are not present in memory would result in page faults.
For example, consider the following program:
// Test.cpp
int foo() { /* */ }
int bar() { /* */ }
// Other functions…
int main() {
bar();
foo();
}
Which gets compiled into:
# Test.app
page_x: _foo
page_y : _bar
# Other symbols
page_z: _main
When Test.app starts, its entry point _main is fetched first, then _bar followed by _foo. Executing Test.app can lead to page faults for fetching each function. Compare this to the following binary layout where all the functions are located on the same page (assuming the functions are small enough).
# Test.app
page_1: _main
page_1: _bar
page_1: _foo
# Other symbols
In this case, when _main gets fetched, _bar and _foo can get fetched in memory at the same time. In case these symbols are large and they are located in consecutive pages, there is a high chance the operating system may prefetch those pages, resulting in fewer page faults.
Because the execution order of functions during an application lifecycle may depend on various factors, it is impossible to have a unique order of symbols that is most efficient. Fortunately, the application startup sequence is fairly deterministic and stable in general. It is also possible to build a binary with a desired symbol order with the help of linkers like lld, which is the default linker for the Android NDK toolchain.
Order file is a text file containing a list of symbols. The linker uses the order of symbols in the order file to lay out symbols in the binary. An order file having functions that get called during the app startup sequence can reduce page faults, resulting in improved launch time.
Order files can improve the launch time of mobile applications by more than 2%. The benefits of order files are more meaningful on larger apps and lower-end devices. A more mature order file generation system can improve other critical user journeys.
Design: The order file generation involves the following steps:
1. Collect app startup sequence using compiler instrumentation techniques
2. Use compiler instrumentation to report every function invocation
3. Run the instrumented binary to collect the launch sequence in a (binary) profraw file
4. Generate an order file from the profraw files
5. Validate order file
6. Merge multiple order files into one
7. Recompile the app with the merged order file
Overview: The order file generation is based on LLVM’s compiler instrumentation process. LLVM has a stage to generate the order file, then recompile the source code using the order file.
Collect app startup sequence: The source code is instrumented by passing -forder-file-instrumentation to the compiler. Additionally, the -orderfile-write-mapping flag is also required for the compiler to generate a mapping file. The mapping file is generated during compilation and used while processing the profraw file. The mapping file shows the mapping from MD5 hash to function symbol.
In order to find the function names corresponding to the MD5 hashes in a profraw file, a corresponding mapping file is used. Note: The compiler instrumentation for order files (-forder-file-instrumentation) only works when an optimization flag (01, 02, 03, 0s, 0z) is passed. So, if -O0 (compiler flag typically used for debug builds) is passed, the compiler will not instrument the binary. In principle, one should use the same optimization…
(Truncated)
Source: Android Developers Blog