Evaluate Profile-Guided Optimization (PGO) and LLVM BOLT

[zamazan4ik]

Hi!

Recently I did many Profile-Guided Optimization (PGO) benchmarks on multiple projects (including static analysis tools and compilers like Rustc, Clang, Clangd, Clang Tidy, and many others) - the results are available here. So that's why I think it's worth trying to apply PGO to Uiua.

I can suggest the following things to do:

• Evaluate PGO's applicability to Uiua tooling (like the compiler).
• If PGO helps to achieve better performance - add a note to Uiua's documentation about that. In this case, users and maintainers will be aware of another optimization opportunity for Uiua.
• Provide PGO integration into the build scripts. It can help users and maintainers easily apply PGO for their own workloads.
• Optimize prebuilt binaries with PGO.

Here are some examples of how PGO is already integrated into other projects' build scripts:

• 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

After PGO, I can suggest evaluating LLVM BOLT as an additional optimization step after PGO.

For the Rust projects, I recommend starting with cargo-pgo.

[bhansconnect]

I decided to do some testing, cause I have a ray tracer in uiua that theoretically should be a solid enough piece of code for pgo. I was unable to get any discernible improvements from pgo. I don't think that is very surprising. Tight hot loop code with minimal branches should get little to no gains from pgo.

I think this is the case for less useful for array languages than most other software. Still probably has a few percent gains to be had (more gains in poorly written array code that causes the intepreter to branch a lot).

I sadly have been unable to test bolt so far (hitting issues). Will report back if I get things working on my linux box and see anything interesting.

[bhansconnect]

Managed to run my program with bolt as well. Sadly both bolt and pgo do about zero in my case. Not saying that will be the case for uiua as a whole, but I would guess overall there may not be that much impact to be had.

[zamazan4ik]

Thanks a lot for the tests! I suggest leaving the issue open. So maybe in the future, we will find more cases, where PGO could help more with the performance.