[FR] ndk-build support for order file generation

[DanAlbert]

Description

Order files (much like PGO) need to be handled in steps of build instrumented -> run -> rebuild. Order files have some annoying requirements like not using -O0 and other flag juggling as well. We could add a LOCAL_ORDERFILE and NDK_GENERATE_ORDER_FILES (the second being a command line option) to make that workflow a bit more obvious.

[smeenai]

How is the NDK generating order files? At Meta, we introduced a lightweight IR PRO instrumentation mode specifically for mobile and an order file generation mode algorithm aimed at minimizing page faults: https://reviews.llvm.org/D147812. That might be interesting for the NDK as well.

[DanAlbert]

@appujee

[appujee]

How is the NDK generating order files? At Meta, we introduced a lightweight IR PRO instrumentation mode specifically for mobile and

Yeah, we are using the -forder-file-instrumentation to generate order file. Apart from that we have scripts to:

• generate order file from the profraw files
• clean the order file
• validate order file
• merge N order files (will be upstreamed soon)

The scripts (except for merging order files) and the documentation, and developer guide (with example use cases) have been upstreamed to ndk repository. See:

• https://developer.android.com/ndk/guides/orderfile
• https://android.googlesource.com/toolchain/llvm_android/+/refs/heads/main/orderfiles/

an order file generation mode algorithm aimed at minimizing page faults: https://reviews.llvm.org/D147812. That might be interesting for the NDK as well.

This is interesting, i'm seeing this for the first time but it seems to be doing something similar to what we have for merging order files. It seems the time complexity of this implementation might be affecting build times? I haven't looked in detail but we have something that converges very fast.

We have a script that implements a linear time algorithm to merge the order files. Maybe our implementation has a few more things that could be helpful in implementing in llvm-profdata, I'll update more once everything is upstreamed.

[smeenai]

IIRC -forder-file-instrumentation is older and has higher binary size overhead than lightweight IR PGO. I'll ask Ellis (who contributed lightweight PGO) to comment here though.

[appujee]

just finished reading: https://discourse.llvm.org/t/rfc-temporal-profiling-extension-for-irpgo/68068. Is there a plan to deprecate the -forder-file-instrumentation ?

If we have a way to merge multiple profraw files (with orderfile data), everything on our end should still keep working (with whatever replaces the -forder-file-instrumentation) otherwise we'll need to update the scripts a little bit. As our goal is to collect order file from different app launch instances (across multiple device classes), we'll have a variety of profraw files in a general case.

[ellishg]

I would like to deprecate -forder-file-instrumentation, but I didn't know how widespread its usage was. Temporal Profiling supports the same functionality but with better integration with existing tools and you won't need the mapping file (-orderfile-write-mapping=). If you incorporate Lightweight Instrumentation then the binary size overhead is also improved. I would also like to support function order optimizations simply by passing in the profile via -fprofile-use instead of --symbol-ordering-file=, but I don't have an explicit plan for that yet.

Temporal Profiling can merge traces from multiple profraw files, but you might need to set -max-temporal-profile-trace-length and -temporal-profile-trace-reservoir-size if you have many (>100) raw profiles. llvm-profdata order will converge quickly to give you a single function order.

I would be interested to know if Temporal Profiling works out for your use case. Let me know if you have any questions.

[appujee]

It makes sense to support both order file collection modes. The advantage with using -forder-file-instrumentation is that older toolchains can also use it but in the long term we'll be in a better position if we support temporal profiling.

[appujee]

Update: https://android-developers.googleblog.com/2023/11/orderfiles-in-android.html has the details of our implementation along with links to scripts and documentation.