Evaluate using Profile-Guided Optimization (PGO) and Post-Link Optimization (PLO)

[zamazan4ik]

Hi!

Recently I checked Profile-Guided Optimization (PGO) and Post-Link Optimization (PLO) improvements on multiple projects. The results are available here. According to the tests, these optimizations can help with achieving better performance in many cases for many applications: networking apps like HAproxy and Envoy, many databases, parsing utilities like Vector, runtimes like V8, etc. Since this, I think trying to optimize or-tools with PGO and PLO can be a good idea.

I can suggest the following action points:

• Perform PGO benchmarks on or-tools. If it shows improvements - add a note to the documentation about possible improvements in or-tools performance with PGO.
• Providing an easier way (e.g. a build option) to build scripts with PGO can be helpful for the end-users and maintainers since they will be able to optimize or-tools according to their workloads.
• Optimize pre-built or-tools binaries

Testing Post-Link Optimization techniques (like LLVM BOLT or Google Propeller) would be interesting too (Clang and Rustc already use BOLT as an addition to PGO) but I recommend starting from the usual PGO.

Examples of how PGO optimization is integrated into other projects:

• Rustc: a CI script for the multi-stage build
• GCC:
  • Official docs, section "Building with profile feedback" (even AutoFDO build is supported)
  • A part in a "wonderful" configure script
• Clang: Docs
• Python:
  • CPython: README
  • Pyston: README
• Go: Bash script
• V8: Bazel flag
• ChakraCore: Scripts
• Chromium: Script
• Firefox: Docs
  • Thunderbird has PGO support too
• PHP - Makefile command and old Centminmod scripts
• MySQL: CMake script
• YugabyteDB: GitHub commit
• FoundationDB: Script
• Zstd: Makefile
• Foot: Scripts
• Windows Terminal: GitHub PR
• Pydantic-core: GitHub PR
• file.d: GitHub PR
• OceanBase: CMake flag

I have some examples of how PGO information looks in the documentation:

• ClickHouse: https://clickhouse.com/docs/en/operations/optimizing-performance/profile-guided-optimization
• Databend: https://databend.rs/doc/contributing/pgo
• Vector: https://vector.dev/docs/administration/tuning/pgo/
• Nebula: https://docs.nebula-graph.io/3.5.0/8.service-tuning/enable_autofdo_for_nebulagraph/
• GCC: Official docs, section "Building with profile feedback" (even AutoFDO build is supported)
• Clang:
  • https://llvm.org/docs/HowToBuildWithPGO.html
  • https://llvm.org/docs/AdvancedBuilds.html
• tsv-utils: https://github.com/eBay/tsv-utils/blob/master/docs/BuildingWithLTO.md

Regarding LLVM BOLT integration, I have the following examples:

• Rustc:
  • Rustc itself (GitHub PR)
  • LLVM in Rustc (Reddit)
• CPython: GitHub PR
• YDB: GitHub comment
• Clang:
  • Slides
  • Results on building Clang
  • Linaro results
  • on AMD 7950X3D
  • GitHub comment from LLVM
• LDC: GitHub comment
• HHVM, Proxygen and others: Facebook paper
• NodeJS: Blog
• Chromium: Blog
• MySQL, MongoDB, memcached, Verilator: Paper

[lperron]

PGO and other improvements of the sort provide substantial gains.
But they require a training dataset, which is not part of OR-Tools.

So to me, this should be done at the application level, when linking the final binary,
Of course, this only applies to C++.

Bottomline, I am sure this can help. but:

• we do not have the resource to set this up
• as I said, it should be done down the path
• They can provide a few % speedup, while improving CP-SAT can bring exponential gain. So I should not spend my time on it.
• PR welcome.

[zamazan4ik]

Of course, this only applies to C++.

It also applies to the Python version since it's the library. You can build a PGO-optimized version of OR-Tools for Python since PGO works not only for applications but also for libraries.

as I said, it should be done down the path

If you prepare a dataset (which is not part of OR-Tools yet, as you mentioned above) - you can prebuilt PGO-optimized versions. So persons who decide to use the library would be able to use already PGO-optimized versions. Of course, if they want to optimize calculations according to their specific case, they would be able to recompile OR-Tools with their PGO profile.

Another point - documenting the PGO effects on the library and setting up the documentation for this process. If user sees performance in the documentation performance improvement numbers from PGO, they can decide - do they want to spend their time on PGO optimizing OR-Tools or not. Right now as far as I understand there is no such information. Hopefully, someone in the future could share the numbers here.

I suggest leaving this discussion open. Maybe someone would be ready to contribute in this area to OR-Tools.

Thank you a lot for your answer!