502352 - RFE: use Milepost GCC enhancements to speed up Firefox

Status: RESOLVED INCOMPLETE

(Firefox Build System :: General, enhancement)

Description

[Neil Harris]

The Milepost GCC enhancement project (see linked URL) uses a combination of execution profiling and machine learning techniques to improve program execution by exploring the space of GCC compiler optimization settings to tune them for particular processor platforms and execution environments. 

Claimed speedups seem to be of the order of 10%, without any changes needed to the program source code. Once learnt, the compiler options can simply be plugged into the default build environment.

Although the machine learning process is lengthy, requiring hundreds of compilation/benchmarking passes, there appears to be no need to re-run the optimization process for every code change, so the optimization process would only need to be repeated at infrequent intervals in order to accommodate the cumulative long-term effects of minor code changes, or if major structural changes are made. 

As a result, this process would not necessarily need to be integrated into the main build environment (although it could be, if the effects are sufficently large to make this desirable.)

This seems like an ideal summer project for a graduate student, since the entire framework is now publically available, and may also be of interest to the original researchers, since Firefox is a high-profile project.

Links:
* http://www.milepost.eu/
* http://ctuning.org/wiki/index.php/CTools:MilepostGCC

Comment 1

[(not currently active) Ted Mielczarek]

Needs someone to try it out, I agree that it's probably a good student project.

Comment 2

[(dormant account)]

So, I've talked to the milepost author and he was quite interested in helping us out.

I think the way to go would be to use dmandelin's sunspider script and focus on spidermonkey.

Milepost can also vary the parameters it is optimizing, so you could optimize for size(which is easier to measure) and would be useful for mobile.

Comment 3

[Neil Harris]

In the short term, if we are choosing only a single set of optimization parameters for the entire codenase, wouldn't it be better to try to optimize performance across a more balanced set of benchmark activities, rather than just concentrating on Javascript execution? 

If this works, then in the longer term it might even be worth considering letting milepost tune the compilation options for the individual major components of the system (eg. javascript, graphics, parsing, DOM manipulation) independently from one another, since they probably have significantly different memory access, branch prediction and cache usage patterns. Since it's based on mathematical optimization, even if only given a single global benchmark, Milepost may well be powerful enough to optimize across all of these at once, including taking into account the interactions of different options between modules.

Comment 4

[Benjamin Smedberg]

The other thing to remember in our codebase is that in general the app performs best when the whole codebase optimizes for size (-Os), and only particularly hot spots optimize for speed. This improves cache lines and overall performance significantly. Currently GCC with PGO is good at highly optimizing the hot functions but is bad at optimizing the cold functions for size. Any improvements that improve -Os speed and size would be felt as much or more than optimizations which focus on unrolling loops, inlining functions, etc which tend to help more in our hot code.

Comment 5

[Nik]

Hi
I am a final year grad student. I want to take this up as a winter project. I have not worked on GCC before this but I believe I can learn soon enough. Can someone please help me with this..?

Comment 6

[David Humphrey (:humph)]

Nik is going to give this a shot as soon as his exams are done in Dec.  Dan (and others), if you see him on irc (Nik is his nick), say hello.  Nik, people in the  #static channel are probably your best bet for any questions.

Comment 7

[[e-mail]]

Awesome, I'll do some reading on it and see if I can help out.

Comment 8

[Nik]

I have done some ground work on Milepost.. I will summarise here the steps we need to perform to compile a simple C program:

1. export environment variables
2. generate passes by calling make with ICI_USE=1,ICI_PLUGIN=save-executed-passes.so, COMPILER=milepost gcc
3. extract static features by calling make with ICI_USE=1,ICI_PLUGIN=extract-static-program-features.so, COMPILER=milepost gcc
4. specify settings like platform id, architecture id, compiler id in a file
5. call "predict_opt" web service for predicting optimization flags (and passes)
6. save returned optimization flags
7. call make with COMPILER=milepost compiler, FLAGS=optimization flags

More details can be found here: http://nikhilkapur.blogspot.com/search/label/Mozilla. But I am stuck now, because I don't know how to move forward from here.. Can someone give me directions?

Comment 9

[Grigori Fursin]

Hi Nik,
Taras pointed me to this thread however I already saw your note on the cTuning discussions mailing list (http://groups.google.com/group/ctuning-discussions/browse_thread/thread/fb7078fcf5f0b44e). I am now back from vacations and this week have a deadline to finish a paper, but plan to check out MILEPOST GCC and web-services next week. By the way, I just found the glitch that the latest version of web-service returns the same flags for all programs while the on-line predictors works correctly - need to check it out. Also, we are now verifying results on several platforms and converting flags to passes so we will be happy to discuss that with you to see if this will be also applicable to MOZILLA builds ...
Will keep in touch,
Grigori

P.S. By the way, sorry for non-intuitive documentation on MILEPOST GCC and cTuning - I had to do it all myself together with most of the programming and publishing and at the end it was driving me crazy since it really takes ages to finish and synchronize all this software - I will try to update during this month ...

Comment 10

[Grigori Fursin]

By the way, just one more thing - I will continue MILEPOST/cTuning related discussions at this thread at cTuning:
http://groups.google.com/group/ctuning-discussions/browse_thread/thread/fb7078fcf5f0b44e
This is mainly because my colleagues who can help us are also on this mailing list. 

Just a few things I will discuss there are:
* methodology for performance evaluation: I tried to optimize Firefox a few years ago and noticed that major improvement may come not from Firefox code itself but from libraries such as jpeg decoding - do you consider the whole Firefox or only specific parts of it?.. Also, do you use oprofile?.. Which datasets you use (here I mean we need to agree to run firefox on some given pages with the same graphics, etc). 
* stability of timing across runs 
* compilation time - there can be slow downs using MILEPOST GCC feature extractor though there can be some gains from predicting lower optimization levels on codes that do not need optimizations. I didn't check it on very large codes so it will be interesting to see what is happening. Actually, it may also be interesting to semi-manually use Collective Optimization Database directly to find best optimizations found for a given architecture for similar programs ...

Talk to you later,
Grigori

Comment 11

[Nik]

Hi
Thank you for your replies. I'll mention here that right now no work
regarding integrating Milepost into Mozilla code has been done.. I am
only a student so its taking me time to learn :) and also I do not
know much about the Mozilla codebase, but yes I am moving forward :).

We do not plan to do it for the whole of firefox right now. I am
starting with a smaller module first and plan to move from module to
module. I had started with Spidermonkey, the jscript engine, but later
we realised that it uses a c++ compiler for most of the part and as
milepost has not been tested yet for c++, I'll have to drop it for now
and concentrate on the parts which are C-only. There are a few which
humph, ted have told me about: nspr, nss, libjpeg, cairo but according
to ted, cairo and libjpeg are already highly optimised. So on there
suggestion I'll start with nspr and see how that turns out and post
details of progress about the same. Right now, I'll just try to
integrate Milepost into the build system and after that I'll bother
you regarding the optimizations achieved, profiling scenarios and the
datasets we'll use :)..

Comment 12

[Nik]

Hi
Thank you for your replies. I'll mention here that right now no work
regarding integrating Milepost into Mozilla code has been done.. I am
only a student so its taking me time to learn :) and also I do not
know much about the Mozilla codebase, but yes I am moving forward :).

We do not plan to do it for the whole of firefox right now. I am
starting with a smaller module first and plan to move from module to
module. I had started with Spidermonkey, the jscript engine, but later
we realised that it uses a c++ compiler for most of the part and as
milepost has not been tested yet for c++, I'll have to drop it for now
and concentrate on the parts which are C-only. There are a few which
humph, ted have told me about: nspr, nss, libjpeg, cairo but according
to ted, cairo and libjpeg are already highly optimised. So on there
suggestion I'll start with nspr and see how that turns out and post
details of progress about the same. Right now, I'll just try to
integrate Milepost into the build system and after that I'll bother
you regarding the optimizations achieved, profiling scenarios and the
datasets we'll use :)..

Comment 13

[Nik]

I am having some of the discussions with the Milepost people on the ctuning google group: http://groups.google.com/group/ctuning-discussions/browse_thread/thread/fb7078fcf5f0b44e?hl=en. I thought I will also paste these over here to keep this bug updated:

Nik:

Hi
There are a few questions that I have..
1. The plugins that I am currently using do not attach a compiled-file-
name to the files that are created, so two files with the same
function name will end up writing/reading to the same file for
features, passes etc.. Is there any workaround for this? For eg. two
files myfile1.c and myfile2.c will create the same file:
ici_passes_function.main.txt if they both have "main" function. Is
there a way to change this files name to
ici_passes_myfile1_function.main.txt and
ici_passes_myfile2_function.main.txt?
2. Is it possible to extract the static features from a group of files
directly instead of a file to file basis.. For eg. a plugin that
somehow extracts features from the whole module of nspr instead of
working on each file in it? As people at mozilla are telling me that
if we try to tune each file in a module it won't be very scalable as
it will take too much time.
Thanks for your help..


Grigori:

Hi Nick,

>1. The plugins that I am currently using do not attach a compiled-file-
>name to the files that are created, so two files with the same
>function name will end up writing/reading to the same file for
>features, passes etc.. Is there any workaround for this? For eg. two
>files myfile1.c and myfile2.c will create the same file:
>ici_passes_function.main.txt if they both have "main" function. Is
>there a way to change this files name to
>ici_passes_myfile1_function.main.txt and
>ici_passes_myfile2_function.main.txt?

Good point. I saw such potential problems and that's why we decided
to use a global XML file for the ICI. My ICT colleagues implemented
that this summer but it is still not released ... Otherwise, I think
you should be able to update the plugin that records/loads plugin
and add a source file name (normally, we should have already added a support
to obtain filename of the compiled source in the version of ICI you are
using)

>2. Is it possible to extract the static features from a group of files
>directly instead of a file to file basis.. For eg. a plugin that
>somehow extracts features from the whole module of nspr instead of
>working on each file in it? As people at mozilla are telling me that
>if we try to tune each file in a module it won't be very scalable as
>it will take too much time.

Another good point. Yes, it is possible - you should prepare a text
file with filename/functions to process and then modify load/store plugin
to extract features only for those filenames/functions (it shouldn't
be too difficult).
Again, we planned to do this control through XML but it's not finished
yet, so you can update the old plugin yourself for now ;) ...

Cheers,
Grigori

Comment 14

[Gregory Szorc [:gps]]

This bug seems to have died. And the Milepost project has morphed into https://github.com/ctuning/ck-autotuning.

Unless someone wants to continue the effort, I don't see a point in keeping this bug open.