www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.ldc - Profile-guided optimization (PGO)

reply Johan Engelen <j j.nl> writes:
Hi all,
   I have been working on getting rudimentary PGO going in LDC. 
It's pretty much ready! [1]
(does not work on Windows yet... I have to fix LLVM's compile-rt 
code)

I've implemented something very similar to Clang: LDC uses 
profile information (generated by an instrumented executable 
built by LDC) to tag each branch in the code with branch weights. 
The actual optimizations are done by LLVM; at the moment LDC only 
adds metadata to the IR.

At this point, I want your input: commandline option naming, easy 
to use? (llvm-profdata is needed...), do you get substantial 
performance boosts, runtime library inclusion or separate lib for 
profile data file writing, bugs, uninstrumented 
branches/switches, etc.
All comments are welcome (please be kind ;-).

Before I announce it in the "Announce" forum, I want to hear your 
thoughts first.

Thanks!
   Johan


[1]
http://wiki.dlang.org/LDC_LLVM_profiling_instrumentation#Profile-Guided_Optimization_.28PGO.29_status_in_LDC
Dec 08 2015
next sibling parent reply David Nadlinger via digitalmars-d-ldc <digitalmars-d-ldc puremagic.com> writes:
Hi Johan,

On 8 Dec 2015, at 20:13, Johan Engelen via digitalmars-d-ldc wrote:

 I've implemented something very similar to Clang: LDC uses profile 
 information (generated by an instrumented executable built by LDC)


Did you also try using it with sample profiles acquired by an external 
profiler yet, as described in the Clang page on PGO?

  — David
Dec 08 2015
next sibling parent reply Johan Engelen <j j.nl> writes:
On Tuesday, 8 December 2015 at 20:08:15 UTC, David Nadlinger 
wrote:

 
 Did you also try using it with sample profiles acquired by an 
 external profiler yet, as described in the Clang page on PGO?


Hi David,
   No, I have not look at that yet.
Thanks a lot for the testcase you posted on Github. Will sink my 
teeth in fixing that first.
Dec 08 2015
next sibling parent reply David Nadlinger via digitalmars-d-ldc <digitalmars-d-ldc puremagic.com> writes:
On 8 Dec 2015, at 23:35, Johan Engelen via digitalmars-d-ldc wrote:

 Thanks a lot for the testcase you posted on Github. Will sink my teeth 
 in fixing that first.


You're welcome – I hope it's enough information to reproduce it, but I 
don't have a debug build of LLVM on this machine right now.

  — David
Dec 08 2015
parent reply Johan Engelen <j j.nl> writes:
On Tuesday, 8 December 2015 at 22:41:22 UTC, David Nadlinger 
wrote:

 On 8 Dec 2015, at 23:35, Johan Engelen via digitalmars-d-ldc 
 wrote:

 Thanks a lot for the testcase you posted on Github. Will sink 
 my teeth in fixing that first.


 You're welcome – I hope it's enough information to reproduce 
 it, but I don't have a debug build of LLVM on this machine 
 right now.


After two more bug fixes: the regexp microbench now works.

Results with the regexp bench (bench.d):

 time ldc2 bench.d -O3 -of=bench_normal --> 52s


   time ./bench_normal --> 2.55s 98%cpu


 time ldc2 bench.d -fprofile-instr-generate -of=bench_instr --> 
 11s


   time ./bench_instr --> 6.72s 99%cpu
   llvm-profdata merge default.profraw -o bench.profdata
   time ldc2 bench.d -O3 -fprofile-instr-use=bench.profdata 
-of=bench_pgo
     --> 48.35s
   time ./bench_pgo --> 2.48s 98%cpu

(timing numbers for bench_normal and bench_pgo are +- 0.01)

So PGO brings it from 2.55 to 2.48 sec, ~3% improvement.
Disappointing, but well... it works!
Dec 10 2015
next sibling parent reply David Nadlinger via digitalmars-d-ldc <digitalmars-d-ldc puremagic.com> writes:
On 11 Dec 2015, at 1:26, Johan Engelen via digitalmars-d-ldc wrote:

 After two more bug fixes: the regexp microbench now works.
 […]
 Disappointing, but well... it works!


Don't forget that this was just a random program I pulled from the 
Rosettacode compilation, though – I didn't have a benchmark ready 
where I know that branch prediction or inlining improvements would make 
a difference.

  — David
Dec 10 2015
parent reply Johan Engelen <j j.nl> writes:
What do you think about "llvm-profdata"? Should we ship that with 
LDC?
Dec 10 2015
parent reply David Nadlinger via digitalmars-d-ldc <digitalmars-d-ldc puremagic.com> writes:
On 11 Dec 2015, at 1:38, Johan Engelen via digitalmars-d-ldc wrote:

 What do you think about "llvm-profdata"? Should we ship that with LDC?


Yes, we should probably ship it with the binary packages. For distro 
packages, we are of course dependent on the LLMV packages to include the 
tools, but at least the Homebrew package actually does.

What is left to do before we can merge a first version into the main 
repository? A partial list:

  - Deal with the remaining FIXME comments (at least open separate 
GitHub issues for them), as well as with commented-out fragments from 
the Clang implementation.

  - Find some way to avoid ICE-type regressions on real-world D code, 
for example by building the druntime/Phobos unit tests with 
instrumentation on.

  - Decide on a name for the command line switches. The GCC-style "-f" 
prefix isn't currently used for most of the options, but that's not 
necessarily much of an argument.

On a rather unrelated note, did you try whether the profile data also 
gives sensible results with llvm-cov? If yes, that might be something 
nice to mention in that upcoming announcement, even though we also have 
DMD-style -cov support, of course.

  — David
Dec 13 2015
next sibling parent reply Johan Engelen <j j.nl> writes:
On Sunday, 13 December 2015 at 13:21:33 UTC, David Nadlinger 
wrote:

 What is left to do before we can merge a first version into the 
 main repository? A partial list:

  - Deal with the remaining FIXME comments (at least open 
 separate GitHub issues for them), as well as with commented-out 
 fragments from the Clang implementation.


Yep :-)  That's what the FIXME comments are there for: so I don't 
forget :-)
The plan is to deal with all FIXME's, and remove the unused 
commented-out Clang fragments.


  - Find some way to avoid ICE-type regressions on real-world D 
 code, for example by building the druntime/Phobos unit tests 
 with instrumentation on.


I just fixed two more ICEs, and now the dmd-testsuite succeeds 
with -fprofile-instr-generate. Running the druntime/Phobos 
unittests now with -fprofile-instr-generate.

Also, I added a pragma(LDC_profile_instr, true|false) to 
enable/disable instrumentation codegen for specific functions. My 
main reason for this is to help people speed up instrumented 
binaries, and it also helps circumventing ICEs.
See tests/ir/profile/pragma.d.
(perhaps you think of a better name for the pragma)


  - Decide on a name for the command line switches. The 
 GCC-style "-f" prefix isn't currently used for most of the 
 options, but that's not necessarily much of an argument.


I have absolutely no preference here. I think we should do what 
the world is already familiar with. Iirc, 
-fprofile-instr-generate is a Clang option, and that Clang is 
moving towards / will support GCC's option naming 
(-fprofile-generate, -fprofile-use).
DMD has a -profile option, but I have not read up on what that 
will do.
I guess we will not add any option for PGO to ldmd2?


 On a rather unrelated note, did you try whether the profile 
 data also gives sensible results with llvm-cov? If yes, that 
 might be something nice to mention in that upcoming 
 announcement, even though we also have DMD-style -cov support, 
 of course.


Did not look into this at all yet. Clang's PGOGen code has some 
extra functions for gcov support and more. It's all commented out 
for now, but it looks like we can support more tools relatively 
easily with the current implementation. I also see hints of 
sampling-based PGO in the code, for example.

Another important TODO item: remove the profiling runtime from 
druntime, and instead add a separate runtime-profiling lib 
(suggestions for a name?  ldc-profile.lib?).
Dec 13 2015
parent reply David Nadlinger via digitalmars-d-ldc <digitalmars-d-ldc puremagic.com> writes:
On 13 Dec 2015, at 14:59, Johan Engelen via digitalmars-d-ldc wrote:

 I just fixed two more ICEs, and now the dmd-testsuite succeeds with 
 -fprofile-instr-generate. Running the druntime/Phobos unittests now 
 with -fprofile-instr-generate.


Nice!


 I have absolutely no preference here. I think we should do what the 
 world is already familiar with. Iirc, -fprofile-instr-generate is a 
 Clang option, and that Clang is moving towards / will support GCC's 
 option naming (-fprofile-generate, -fprofile-use).


Yeah, me neither.


 DMD has a -profile option, but I have not read up on what that will 
 do.


It makes DMD's druntime emit some profiling info as text files 
(trace.def/trace.log) at program exit. This is for manual analysis only, 
no PGO-type functionality in sight.


 I guess we will not add any option for PGO to ldmd2?


Yeah, as DMD does not have any PGO functionality. Of course it will 
still pass the ldc2 options through.


 Another important TODO item: remove the profiling runtime from 
 druntime, and instead add a separate runtime-profiling lib 
 (suggestions for a name?  ldc-profile.lib?).


Maybe add a "rt" suffix to make clear that this is the actual program 
runtime part? Ultimately does not really matter, though.

  — David
Dec 13 2015
parent Johan Engelen <j j.nl> writes:
On Sunday, 13 December 2015 at 14:16:53 UTC, David Nadlinger 
wrote:

 On 13 Dec 2015, at 14:59, Johan Engelen via digitalmars-d-ldc 
 wrote:

 I guess we will not add any option for PGO to ldmd2?


 Yeah, as DMD does not have any PGO functionality. Of course it 
 will still pass the ldc2 options through.


Lol, I should try to read up on these simple things first...
To do the tests, I had modified ldmd to recognize 
-fprofile-instr-generate...
Dec 13 2015
prev sibling parent Johan Engelen <j j.nl> writes:
Hi David,
   Could you have a look at the PR again?
I think it is almost ready for merging. (two FIXME's left that I 
hope to address soon)

On Sunday, 13 December 2015 at 13:21:33 UTC, David Nadlinger 
wrote:

 On 11 Dec 2015, at 1:38, Johan Engelen via digitalmars-d-ldc 
 wrote:

 What do you think about "llvm-profdata"? Should we ship that 
 with LDC?


 Yes, we should probably ship it with the binary packages.


I have added llvm-profdata to the repo, and renamed the built 
executable to ldc-profdata (it has to be in-sync with the LLVM 
version that LDC was built with, and so the renaming prevents 
potential name clashing with a system installed profdata version).


 What is left to do before we can merge a first version into the 
 main repository? A partial list:

  - Deal with the remaining FIXME comments (at least open 
 separate GitHub issues for them), as well as with commented-out 
 fragments from the Clang implementation.


I think I will just remove all unused Clang implementation code 
(it is related to coverage stuff, which I think we should 
implement in a different branch after PGO is merged).

Thanks!
   Johan
Jan 10 2016
prev sibling parent reply Kagamin <spam here.lot> writes:
On Friday, 11 December 2015 at 00:26:22 UTC, Johan Engelen wrote:

 So PGO brings it from 2.55 to 2.48 sec, ~3% improvement.
 Disappointing, but well... it works!


PGO can also reduce physical memory consumption due to less code 
loaded into memory.
Dec 11 2015
parent Johan Engelen <j j.nl> writes:
On Friday, 11 December 2015 at 14:07:56 UTC, Kagamin wrote:

 On Friday, 11 December 2015 at 00:26:22 UTC, Johan Engelen 
 wrote:

 So PGO brings it from 2.55 to 2.48 sec, ~3% improvement.
 Disappointing, but well... it works!


 PGO can also reduce physical memory consumption due to less 
 code loaded into memory.


Yes, indeed. I'd like to find a good example of code where this 
shows up in practice, so that PGO really does improve performance 
significantly (say, >10%).
Dec 11 2015
prev sibling parent reply David Nadlinger <code klickverbot.at> writes:
On Tuesday, 8 December 2015 at 22:35:11 UTC, Johan Engelen wrote:

 Thanks a lot for the testcase you posted on Github. Will sink 
 my teeth in fixing that first.


Speaking of test cases: This might be an obvious and/or stupid 
suggestion, but did you try building the Phobos unit tests (and 
maybe also dmd-testsuite/runnable) with PGO? I'd suspect it would 
give you quite a broad coverage of basic language constructs.

  - David
Dec 10 2015
parent Johan Engelen <j j.nl> writes:
On Thursday, 10 December 2015 at 14:27:59 UTC, David Nadlinger 
wrote:

 Speaking of test cases: This might be an obvious and/or stupid 
 suggestion, but did you try building the Phobos unit tests (and 
 maybe also dmd-testsuite/runnable) with PGO? I'd suspect it 
 would give you quite a broad coverage of basic language 
 constructs.


Nope didn't do that yet :S :S   Looks like it is needed to iron 
out some remaining bugs.

I underestimated the complexity of D's AST (some objects are 
placed in multiple locations in the AST?), which gave rise to an 
assertion fail in your testcase; plus I forgot to add throw 
statements to the AST tree walker, leading to another assertion 
fail. Those issues have been fixed now, and now it breaks with 
the same error you found. It is confusing because I did not (mean 
to) change any of the codegen, other than adding counter 
increment instructions and branch instruction metadata (both 
trivial additions).  But I did have to add extra basicblocks for 
switch statements... perhaps I can search there first.
Hope to have a resolution for your test case quickly.

I also have not tested at all how this works with multiple object 
files linked together, or other possibly more complicated things. 
I thought a fun testcase would be to compile DDMD with PGO 
enabled, compile itself as a profiling run, rebuild with PGO and 
test if compiling, say, Phobos is quicker/slower.

I am very curious to see what constructs will see a significant 
performance boost, if any at all.
Dec 10 2015
prev sibling parent reply David Nadlinger <code klickverbot.at> writes:
On Tuesday, 8 December 2015 at 20:08:15 UTC, David Nadlinger 
wrote:

 Did you also try using it with sample profiles acquired by an 
 external profiler yet, as described in the Clang page on PGO?


Let me add that this would probably be something nice to have for 
the initial release, as users could fall back to using perf, etc. 
if the instrumentation part is still buggy or incomplete for 
their code.

  - David
Dec 10 2015
parent reply Liran Zvibel via digitalmars-d-ldc <digitalmars-d-ldc puremagic.com> writes:
Also, for use cases like ours, where the system runs for extended periods of
time, and optimizing the init time, which may be minutes is not interesting at
all, just being able to run perf while the system is doing something
interesting to improve is a big plus.

Liran


 On Dec 10, 2015, at 16:30, David Nadlinger via digitalmars-d-ldc
<digitalmars-d-ldc puremagic.com> wrote:
 
 On Tuesday, 8 December 2015 at 20:08:15 UTC, David Nadlinger wrote:

 Did you also try using it with sample profiles acquired by an external
profiler yet, as described in the Clang page on PGO?


 
 Let me add that this would probably be something nice to have for the initial
release, as users could fall back to using perf, etc. if the instrumentation
part is still buggy or incomplete for their code.
 
 - David
Dec 10 2015
parent reply Kagamin <spam here.lot> writes:
On Thursday, 10 December 2015 at 14:38:19 UTC, Liran Zvibel wrote:

 Also, for use cases like ours, where the system runs for 
 extended periods of time, and optimizing the init time, which 
 may be minutes is not interesting at all, just being able to 
 run perf while the system is doing something interesting to 
 improve is a big plus.


As I understand, if the profiling runs long enough, the 
long-running statistics will dominate startup statistics?
Dec 23 2015
parent Johan Engelen <j j.nl> writes:
On Wednesday, 23 December 2015 at 13:10:33 UTC, Kagamin wrote:

 On Thursday, 10 December 2015 at 14:38:19 UTC, Liran Zvibel 
 wrote:

 Also, for use cases like ours, where the system runs for 
 extended periods of time, and optimizing the init time, which 
 may be minutes is not interesting at all, just being able to 
 run perf while the system is doing something interesting to 
 improve is a big plus.


 As I understand, if the profiling runs long enough, the 
 long-running statistics will dominate startup statistics?


The profiling is pretty simple: it is just a bunch of counters 
whereever the code branches. So indeed, long runs will have 
long-running statistics dominate startup statistics.
Dec 23 2015
prev sibling next sibling parent Johan Engelen <j j.nl> writes:
On Tuesday, 8 December 2015 at 19:13:41 UTC, Johan Engelen wrote:

 (does not work on Windows yet... I have to fix LLVM's 
 compile-rt code)


I fixed a nasty [*] bug in compile-rt's profile writing code, and 
now it also works on Windows. (The IR tests fail on Windows 
because running a compiled executable from LIT fails for some 
reason on Windows.)

[*] 
https://stackoverflow.com/questions/5537066/strange-0x0d-being-added-to-my-binary-file
Now I know what to look for first if I see 0x0D's in my files...
Dec 08 2015
prev sibling next sibling parent reply Johan Engelen <j j.nl> writes:
On Tuesday, 8 December 2015 at 19:13:41 UTC, Johan Engelen wrote:

 Before I announce it in the "Announce" forum, I want to hear 
 your thoughts first.


Clearly I was too optimistic about the quality of my work so far, 
hehe.
Dec 10 2015
parent David Nadlinger via digitalmars-d-ldc <digitalmars-d-ldc puremagic.com> writes:
On 10 Dec 2015, at 19:43, Johan Engelen via digitalmars-d-ldc wrote:

 Clearly I was too optimistic about the quality of my work so far, 
 hehe.


Quite the contrary – you chose to start with the hard part 
(instrumentation-based instead of sampling-based), and DMD's AST is 
notoriously, uh, fluid in meaning and under-documented.

  — David
Dec 10 2015
prev sibling parent Johan Engelen <j j.nl> writes:
On Tuesday, 8 December 2015 at 19:13:41 UTC, Johan Engelen wrote:

 Hi all,
   I have been working on getting rudimentary PGO going in LDC. 
 It's pretty much ready!


It now works with LLVM 3.7 and LLVM 3.8 (trunk), on Mac OS X, 
Linux (tested on Ubuntu), and Windows! I have not tested other 
platforms.
Dec 23 2015