Android Builders Weblog: Order Information in Android

Mobile News

Android Builders Weblog: Order Information in Android

geeks-news.com

November 7, 2023

Android Builders Weblog: Order Information in Android

[ad_1]

Posted by Aditya Kumar – Software program Engineer

Context

Binary structure utilizing a logo order file (also referred to as binary order file or linker order file) is a widely known link-time optimization. The linker makes use of the order of symbols so as file to put out symbols within the binary. Order file primarily based binary structure improves utility launch time in addition to different crucial person journeys. Order file era is usually a multi-step course of the place builders use totally different instruments at each stage. We’re offering a unified set of instruments and documentation that can enable each native app developer to leverage this optimization. Each Android app builders and the AOSP neighborhood can profit from the instruments.

Background

Supply code is usually structured to facilitate software program growth and comprehension. The structure of features and variables in a binary can also be impacted by their relative ordering within the supply code. The binary structure impacts utility efficiency because the working system has no means of understanding which symbols will likely be required in future and usually makes use of spatial locality as one of many price fashions for prefetching subsequent pages.

However the order of symbols in a binary could not replicate this system execution order. When an utility executes, fetching symbols that aren’t current in reminiscence would lead to web page faults. For instance, take into account the next program:

// Check.cpp
int foo() { /* */ }
int bar() { /* */ }
// Different features...

int essential() {
  bar();
  foo();
}

Which will get compiled into:

# Check.app page_x: _foo page_y: _bar # Different symbols page_z:_main

When Check.app begins, its entrypoint _main is fetched first then _bar adopted by _foo. Executing Check.app can result in web page faults for fetching every operate. Evaluate this to the next binary structure the place all of the features are positioned in the identical web page (assuming the features are sufficiently small).

# Check.app page_1: _main page_1: _bar page_1: _foo # Different symbols

On this case when _main will get fetched, _bar and _foo can get fetched within the reminiscence on the similar time. In case these symbols are massive and they’re positioned in consecutive pages, there’s a excessive probability the working system could prefetch these pages leading to much less web page faults.

As a result of execution order of features throughout an utility lifecycle could depend upon varied components it’s unimaginable to have a novel order of symbols that’s best. Happily, utility startup sequence is pretty deterministic and secure basically. And additionally it is attainable to construct a binary having a desired image order with the assistance of linkers like lld which is the default linker for Android NDK toolchain.

Order file is a textual content file containing an inventory of symbols. The linker makes use of the order of symbols in order file to put out symbols within the binary. An order file having features that get referred to as in the course of the app startup sequence can scale back web page faults leading to improved launch time. Order recordsdata can enhance the launch time of cell purposes by greater than 2%. The advantages of order recordsdata are extra significant on bigger apps and decrease finish units. A extra mature order file era system can enhance different crucial person journeys.

Design

The order file era entails the next steps

Acquire app startup sequence utilizing compiler instrumentation approach

Use compiler instrumentation to report each operate invocation
Run the instrumented binary to gather launch sequence in a (binary) profraw file

Generate order file from the profraw recordsdata
Validate order file
Merge a number of order recordsdata into one
Recompile the app with the merged order file

Overview

The order file era is predicated on LLVM’s compiler instrumentation course of. LLVM has a stage to generate the order file then recompile the supply code utilizing the order file. ALT TEXT

Acquire app startup sequence

The supply code is instrumented by passing -forder-file-instrumentation to the compiler. Moreover, the -orderfile-write-mapping flag can also be required for the compiler to generate a mapping file. The mapping file is generated throughout compilation and it’s used whereas processing the profraw file. The mapping file reveals the mapping from MD5 hash to operate image (as proven beneath).

# Mapping file MD5 db956436e78dd5fa essential MD5 83bff1e88ac48f32 _GLOBAL__sub_I_main.cpp MD5 c943255f95351375 _Z5mergePiiii MD5 d2d2238cf08db816 _Z9mergeSortPiii MD5 11ed18006e729e73 _Z4partPiii MD5 3e897b5ee8bebbd1 _Z9quickSortPiii

The profile (profraw file) is generated each time the instrumented utility is executed. The profile knowledge within the profraw file accommodates the MD5 hash of the features executed in chronological order. The profraw file doesn’t have duplicate entries as a result of every operate solely outputs its MD5 hash on first invocation. A typical run of binary containing the features listed within the mapping file above can have the next profraw entries.

# Profraw file 00000000 32 8f c4 8a e8 f1 bf 83 fa d5 8d e7 36 64 95 db |2...........6d..| 00000010 16 b8 8d f0 8c 23 d2 d2 75 13 35 95 5f 25 43 c9 |.....#..u.5._%C.| 00000020 d1 bb be e8 5e 7b 89 3e 00 00 00 00 00 00 00 00 |....^{.>........| 00000030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|

With a purpose to discover the operate names similar to the MD5 hashes in a profraw file, a corresponding mapping file is used.

Notice: The compiler instrumentation for order recordsdata (-forder-file-instrumentation) solely works when an optimization flag (01, 02, 03, 0s, 0z) is handed. So, if -O0 (compiler flag usually used for debug builds) is handed, the compiler is not going to instrument the binary. In precept, one ought to use the identical optimization flag for instrumentation that’s utilized in delivery launch binaries.

The Android NDK repository has scripts that automate the order file era given a mapping file and an order file.

Recompiling with Order File

After you have an order file, you present the trail of the order file to the linker utilizing the –symbol-ordering-file flag.

Detailed design

Creating Order File Construct Property

The Android Open Supply Challenge (AOSP) makes use of a construct system referred to as soong so we will leverage this construct system to move the flags as obligatory. The order file construct property has 4 essential fields:

instrumentation
load_order_file
order_file_path
cflags

The cflags are supposed to add different obligatory flags (like mapping flags) throughout compilation. The load_order_file and order_file_path tells the construct system to recompile with the order file relatively than set it to the profiling stage. The order recordsdata should be in saved in certainly one of two paths:

toolchain/pgo-profiles/orderfiles
vendor/google_data/pgo_profile/orderfiles

# Profiling
orderfile: {
    instrumentation: true,
    load_order_file: false,
    order_file_path: "",
    cflags: [
        "-mllvm",
        "-orderfile-write-mapping=<filename>-mapping.txt",
    ],
}

#Recompiling with Order File
orderfile: {
    instrumentation: true,
    load_order_file: true,
    order_file_path: "<filename>.orderfile",
}

Creating order recordsdata

We offer a python script to create an order file from a mapping file and a profraw file. The script additionally permits eradicating a selected image or creating an order file till a selected image.

Script Flags:

Profile file (–profile-file):

Description: The profile file generated by operating a binary compiled with -forder-file-instrumentation

Mapping file (–mapping-file):

Description: The mapping file generated throughout compilation that maps MD5 hashes to image names

Output file (–output):

Description: The output file title for the order file. Default Identify: default.orderfile

Deny Checklist (–denylist):

Description: Symbols that you just need to exclude from the order file

Final image (–last-symbol):

Description: The order file will finish on the handed final image and ignore the symbols after it. If you would like an order file just for startup, it’s best to move the final startup image. Final-symbol has precedence over leftover so we’ll output till the final image and ignore the leftover flag.

Leftover symbols (–leftover):

Description: Some symbols (features) may not have been executed so they won’t seem within the profile file. If you would like these symbols in your order file, you should utilize this flag and it’ll add them on the finish.

Validating order recordsdata

As soon as we get an order file for a library or binary, we have to verify whether it is legitimate primarily based on a set of standards. Some order recordsdata might not be of excellent high quality so they’re higher discarded. This will occur on account of a number of causes like utility terminated unexpectedly, the runtime couldn’t write the entire profraw file earlier than exiting, an undesired code-sequence was collected within the profile, and so forth. To automate this course of, we offer a python script that may assist builders verify for:

Partial order that must be within the order file
Symbols that must be current so as file
Symbols that shouldn’t be current so as file
Minimal variety of symbols to make an order file

Script Flags:

Order file (–order-file):

Description: The order file you’re validating on the beneath standards.

Partial Order (–partial):

Description: A partial order of symbols that should be held within the order file.

Allowed Lists (–allowlist):

Description: Symbols that should be current within the order file.

Denied Lists (–denylist):

Description: Symbols that shouldn’t be within the order file. Denylist flag has precedence over allowlist.

Minimal Variety of Entries (–min):

Description: Minimal variety of symbols wanted for an order file

Merging order recordsdata

At a better stage, the order file symbols in a set of order recordsdata approximate a partial order (poset) of operate names with order outlined by time of execution. Throughout totally different runs of an utility, the order recordsdata may need variations. These variations could possibly be on account of OS, gadget class, construct model, person configurations and so forth. Nonetheless, the linker can solely take one order file to construct an utility. With a purpose to have one order file that gives the specified advantages, we have to merge these order recordsdata right into a single order file. The merging algorithm additionally must be environment friendly in order to not decelerate the construct time. There are non-linear clustering algorithms that won’t scale effectively for merging massive numbers of order recordsdata, every having many symbols. We offer an environment friendly merging algorithm that converges shortly. The algorithm permits for customizable parameters, such that builders can tune the result.

Merging N partial order units will be performed both pessimistically (merging a choice of order recordsdata all the best way till there may be one order file left) or optimistically (merging all of them without delay). The pessimistic strategy will be inefficient in addition to sub-optimal. In consequence, it’s higher to work with all N partial order units without delay. With a purpose to have an environment friendly implementation it helps to signify all N posets with a weighted directed Graph (V,E) the place:

V: Parts of partial order units (symbols) and the variety of occasions it seems in numerous partial order units. Notice that the frequency of vertices could also be better than the sum of all incoming edges due to invocations from uninstrumented elements of binary, dependency injection and so forth.
E (V1 -> V2): An edge happens if the component of V2 instantly succeeds V1 in any partial order set with its weight being the variety of occasions this occurs.

For a binary executable, there may be one root (e.g., essential) vertex, however shared libraries may need many roots primarily based on which features are referred to as within the binary utilizing them. The graph will get sophisticated if the appliance has threads as they incessantly lead to cycles. To have a topological order, cycles are eliminated by preferring the very best chance path over others. A Depth-First traversal that selects the very best weighted edge serves the aim.

Eradicating Cycles:

- Mark again edges throughout a Depth-First traversal - For every Cycle (c): - Add the weights of all in-edges of every vertex (v) within the cycle excluding the sides within the cycle - Take away the cycle edge pointing **to** the vertex with highest sum

After cycles are eliminated, the identical depth first traversal provides a topological order (the order file) when all of the ahead edges are eliminated. Basically, the algorithm computes a minimum-spanning-tree of maximal weights and traverses the tree in topological order.

Producing an order:

printOrderUtil(G, n, order):
   - If n was visited:
        - return
   - Add n to the top of order
   - Type all out edges primarily based on weight
   - For each out_edge (n, v):
       - printOrderUtil(G, v, order) 

printOrder(G):
   - Get all roots
   - order = []
   - For every root r:
       - printOrderUtil(G, r, order)
   - return order

Instance:

Given the next order recordsdata:

essential -> b -> c -> d
essential -> a -> c
essential -> e -> f
essential -> b
essential -> b
essential -> c -> b

The graph to the best is obtained by eradicating cycles.

DFS: essential -> b-> c -> b
Again edge: c -> b
Cycle: b -> c-> b
Cycle edges: [b -> c, c -> b]
b’s sum of in-edges is 3
c’s sum of in-edges is 2
This suggests b will likely be traversed from a better frequency edge, so c -> b is eliminated
Ignore ahead edges a->c, main->c
The DFS of the acyclic graph on the best will produce an order file essential -> b -> c -> d -> a -> e -> f after ignoring the ahead edges.

Amassing order recordsdata for Android Apps (Java, Kotlin)

The order file instrumentation and profile knowledge assortment is just enabled for C/C++ purposes. In consequence, it can’t profit Java or Kotlin purposes. Nonetheless, Android apps that ship compiled C/C++ libraries can profit from order file.

To generate order file for libraries which can be utilized by Java/Kotlin purposes, we have to invoke the runtime strategies (referred to as as a part of order file instrumentation) on the proper locations. There are three features that customers must name:

__llvm_profile_set_filename(char *f): Set the title of the file the place profraw knowledge will likely be dumped.

__llvm_profile_initialize_file: Initialize the file set by __llvm_profile_set_filename

__llvm_orderfile_dump: Dumps the profile(order file knowledge) collected whereas operating instrumented binary

Equally, the compiler and linker flags ought to be added to construct configurations. We offer template construct system recordsdata e.g, CMakeLists.txt to compile with the proper flags and add a operate to dump the order recordsdata when the Java/Kotlin utility calls it.

# CMakeLists.txt

set(GENERATE_PROFILES ON)
#set(USE_PROFILE "${CMAKE_SOURCE_DIR}/demo.orderfile")

add_library(orderfiledemo SHARED orderfile.cpp)
target_link_libraries(orderfiledemo log)

if(GENERATE_PROFILES)
    # Producing profiles require any optimization flag except for -O0.
    # The mapping file will not generate and the profile instrumentation does not work with out an optimization flag.
    target_compile_options( orderfiledemo PRIVATE -forder-file-instrumentation -O2 -mllvm -orderfile-write-mapping=mapping.txt )
    target_link_options( orderfiledemo PRIVATE -forder-file-instrumentation )
    target_compile_definitions(orderfiledemo PRIVATE GENERATE_PROFILES)
elseif(USE_PROFILE)
    target_compile_options( orderfiledemo PRIVATE -Wl,--image-ordering-file=${USE_PROFILE} -Wl,--no-warn-image-ordering )
    target_link_options( orderfiledemo PRIVATE -Wl,--image-ordering-file=${USE_PROFILE} -Wl,--no-warn-image-ordering )
endif()

We additionally present a pattern app to dump order recordsdata from a Kotlin utility. The pattern app creates a shared library referred to as “orderfiledemo” and invokes the DumpProfileDataIfNeeded operate to dump the order file. This library will be taken out of this pattern app and will be repurposed for different purposes.

// Order File Library

#if outlined(GENERATE_PROFILES)
extern "C" int __llvm_profile_set_filename(const char *);
extern "C" int __llvm_profile_initialize_file(void);
extern "C" int __llvm_orderfile_dump(void);
#endif

void DumpProfileDataIfNeeded(const char *temp_dir) {

#if outlined(GENERATE_PROFILES)

  char profile_location[PATH_MAX] = {};
  snprintf(profile_location, sizeof(profile_location), "%s/demo.output",
           temp_dir);
  __llvm_profile_set_filename(profile_location);
  __llvm_profile_initialize_file();
  __llvm_orderfile_dump();
  __android_log_print(ANDROID_LOG_DEBUG, kLogTag, "Wrote profile knowledge to %s",
                      profile_location);
#else
  __android_log_print(ANDROID_LOG_DEBUG, kLogTag,
                      "Didn't write profile knowledge as a result of the app was not "
                      "constructed for profile era");
#endif
}

extern "C" JNIEXPORT void JNICALL
Java_com_example_orderfiledemo_MainActivity_runWorkload(JNIEnv *env,
                                                        jobject /* this */,
                                                        jstring temp_dir) {
  DumpProfileDataIfNeeded(env->GetStringUTFChars(temp_dir, 0));
}

# Kotlin Utility
class MainActivity : AppCompatActivity() {

    non-public lateinit var binding: ActivityMainBinding

    override enjoyable onCreate(savedInstanceState: Bundle?) {
        tremendous.onCreate(savedInstanceState)

        binding = ActivityMainBinding.inflate(layoutInflater)
        setContentView(binding.root)
        runWorkload(applicationContext.cacheDir.toString())
        binding.sampleText.textual content = "Howdy, world!"
    }

    /**
     * A local technique that's carried out by the 'orderfiledemo' native library,
     * which is packaged with this utility.
     */
    exterior enjoyable runWorkload(tempDir: String)

    companion object {
        // Used to load the 'orderfiledemo' library on utility startup.
        init {
            System.loadLibrary("orderfiledemo")
        }
    }
}

Limitation

order file era solely works for native binaries. The validation and merging scripts will work for any set of order recordsdata.

References

Exterior References

[ad_2]

Context

Design

Limitation

References

Exterior References

LEAVE A REPLY Cancel reply