[gentoo-dev] -fbranch-probabilities optimisation

[gentoo-dev] -fbranch-probabilities optimisation

[Chris Davies]

Hi,

I had the idea to build -fbranch-probabilities optimisation into portage. This is where a sample run of data is taken using the program compiled with -fprofile-arcs, and that data then used to reorganise the object code so conditional branches are layed out in a more efficient manner.

To give an idea about how much time this optimisation actually saves, I ran a test with bladeenc (an MP3 encoder) encoding an entire album of wav files. The CFLAGS used only differed by a the -fbranch-probabilities, and the test was run 5 times to get an average. The result was that the version with no branch data took 8.35.106s on average to complete the encoding, whereas the the optimised version took only 8.11.502s. The branch data was 64KBs in total. 

Does this sound like something we could work into portage? I initially had the idea of building patches for every package likely to be improved by this optimisation (mainly CPU bound ones) and just applying them to the package before compilation. The user could then choose wether or not to actually use the data by including or excluding -fbranch-probabilities in make.conf.

Obviously I'd have to work up some kind of test rig to automatically generate arc data for packages, but that shouldn't be too much of a problem as long as we keep the number of packages under control. The only problem I can see is that -fbranch-probabilities spits out ugly warnings if no arc data is present, although in this situation gcc defaults back to it's standard behaviour (I think).

Thoughts? Opinions?
Thanks,
C.Davies


--
gentoo-dev@gentoo.org mailing list

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Anupam Kapoor]

hi,

i was under the assumption that most processors already perform branch
prediction. no ? do you think that -fbranch-probabilities provides a
more 'comprehensive' view of the executing program ?

kind regards
anupam

> Hi,
> 
> I had the idea to build -fbranch-probabilities optimisation into
> portage. This is where a sample run of data is taken using the program
> compiled with -fprofile-arcs, and that data then used to reorganise
> the object code so conditional branches are layed out in a more
> efficient manner.
> 
> To give an idea about how much time this optimisation actually saves,
> I ran a test with bladeenc (an MP3 encoder) encoding an entire album
> of wav files. The CFLAGS used only differed by a the
> -fbranch-probabilities, and the test was run 5 times to get an
> average. The result was that the version with no branch data took
> 8.35.106s on average to complete the encoding, whereas the the
> optimised version took only 8.11.502s. The branch data was 64KBs in
> total.
> 
> Does this sound like something we could work into portage? I initially
> had the idea of building patches for every package likely to be
> improved by this optimisation (mainly CPU bound ones) and just
> applying them to the package before compilation. The user could then
> choose wether or not to actually use the data by including or
> excluding -fbranch-probabilities in make.conf.
> 
> Obviously I'd have to work up some kind of test rig to automatically
> generate arc data for packages, but that shouldn't be too much of a
> problem as long as we keep the number of packages under control. The
> only problem I can see is that -fbranch-probabilities spits out ugly
> warnings if no arc data is present, although in this situation gcc
> defaults back to it's standard behaviour (I think).
> 
> Thoughts? Opinions?  Thanks, C.Davies


--
gentoo-dev@gentoo.org mailing list

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Evan Powers]

On Friday 16 May 2003 08:52 pm, Anupam Kapoor wrote:
> i was under the assumption that most processors already perform branch
> prediction. no ? do you think that -fbranch-probabilities provides a
> more 'comprehensive' view of the executing program ?

Yes, modern processors do perform branch prediction. But you're right, the 
compiler can do a much more 'comprehensive' job.

The reason is that CPU branch prediction algorithms tend to forget any 
information they learn that occurred farther away in time or space than 
certain thresholds. The Xeon, I think, retains information only about the 
last 16 branching instructions and the direction of only the last four 
branches on each of those instructions.

GCC, on the other hand, can retain information about all the branches, and 
complete directional statistics over the entire run, but it can only make 
static predictions. (For example, GCC can't take advantage of knowing that 
the branch will go one way for 200 consecutive times, then the other for 
300--it has to predict the branch will go the second way all the time and 
order accordingly.)

So you get the best performance when you combine the two approaches.

Evan

--
gentoo-dev@gentoo.org mailing list

Re: [gentoo-dev] -fbranch-probabilities optimisation

[David Nielsen]

I love it, count me in for testing, I've been talking about this for
some time but I never actually got around to trying profiling out, but
it would be a useful feature to have in portage.

- David

On Sat, 2003-05-17 at 04:49, Chris Davies wrote:
> Hi,
> 
> I had the idea to build -fbranch-probabilities optimisation into portage. This is where a sample run of data is taken using the program compiled with -fprofile-arcs, and that data then used to reorganise the object code so conditional branches are layed out in a more efficient manner.
> 
> To give an idea about how much time this optimisation actually saves, I ran a test with bladeenc (an MP3 encoder) encoding an entire album of wav files. The CFLAGS used only differed by a the -fbranch-probabilities, and the test was run 5 times to get an average. The result was that the version with no branch data took 8.35.106s on average to complete the encoding, whereas the the optimised version took only 8.11.502s. The branch data was 64KBs in total. 
> 
> Does this sound like something we could work into portage? I initially had the idea of building patches for every package likely to be improved by this optimisation (mainly CPU bound ones) and just applying them to the package before compilation. The user could then choose wether or not to actually use the data by including or excluding -fbranch-probabilities in make.conf.
> 
> Obviously I'd have to work up some kind of test rig to automatically generate arc data for packages, but that shouldn't be too much of a problem as long as we keep the number of packages under control. The only problem I can see is that -fbranch-probabilities spits out ugly warnings if no arc data is present, although in this situation gcc defaults back to it's standard behaviour (I think).
> 
> Thoughts? Opinions?
> Thanks,
> C.Davies
> 
> 
> --
> gentoo-dev@gentoo.org mailing list
> 


--
gentoo-dev@gentoo.org mailing list

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Sven Vermeulen]

[-- Attachment #1: Type: text/plain, Size: 786 bytes --]

On Sat, May 17, 2003 at 03:49:11AM +0100, Chris Davies wrote:
> I had the idea to build -fbranch-probabilities optimisation into portage.
> This is where a sample run of data is taken using the program compiled with
> -fprofile-arcs, and that data then used to reorganise the object code so
> conditional branches are layed out in a more efficient manner.

Why implement it in Portage? Isn't it up to the user to define it in the
CFLAGS or not? 

Wkr,
	Sven Vermeulen

-- 
Thanks to DRM, you know that something has been built in environment of 
unspecified degree of security, from source you cannot check, written by 
programmers you don't know, released after passing QA of unknown quality and 
which is released under a license that disclaims any responsibility...

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Werner Van Belle]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 17 May 2003 13:43, Sven Vermeulen wrote:
> On Sat, May 17, 2003 at 03:49:11AM +0100, Chris Davies wrote:
> > I had the idea to build -fbranch-probabilities optimisation into portage.
> > This is where a sample run of data is taken using the program compiled
> > with -fprofile-arcs, and that data then used to reorganise the object
> > code so conditional branches are layed out in a more efficient manner.
>
> Why implement it in Portage? Isn't it up to the user to define it in the
> CFLAGS or not?

This won't be possible because if you want this optimisation you have:

a) To compile the program with -fprofile-arcs
b) Run the program
c) Recompile the program with the same optimisations but with 
- -fbranch-probabilities

- --
Werner,-
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+xde8xiU3uL/NdUYRAiP6AJ0QjEGvQS4QdmjIbQc5GkyILTjp5wCfSQQM
5uusj7sl82+ITMRc9xcEaD4=
=eiol
-----END PGP SIGNATURE-----


--
gentoo-dev@gentoo.org mailing list

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Sven Vermeulen]

[-- Attachment #1: Type: text/plain, Size: 706 bytes --]

On Sat, May 17, 2003 at 08:33:30AM +0200, Werner Van Belle wrote:
> This won't be possible because if you want this optimisation you have:
> 
> a) To compile the program with -fprofile-arcs
> b) Run the program
> c) Recompile the program with the same optimisations but with 
> -fbranch-probabilities

Aah, then I'm completely in favor of adding this to Portage :)

Wkr,
	Sven Vermeulen

-- 
Thanks to DRM, you know that something has been built in environment of 
unspecified degree of security, from source you cannot check, written by 
programmers you don't know, released after passing QA of unknown quality and 
which is released under a license that disclaims any responsibility...

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Werner Van Belle]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 17 May 2003 15:57, Sven Vermeulen wrote:
> Aah, then I'm completely in favor of adding this to Portage :)

Maybe first investigate how good this thing works. I've done a quick check and 
I suspect this technique doesn't work on multithreaded programs. 

Werner,-
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+xkOYxiU3uL/NdUYRAvq8AJ4gjvllvBdBgvF8/KxRyB1+cr/+TACgrSox
II6ICeGh26ThhoWI/vOaFjM=
=fDn9
-----END PGP SIGNATURE-----


--
gentoo-dev@gentoo.org mailing list

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Paul de Vrieze]

[-- Attachment #1: signed data --]
[-- Type: text/plain, Size: 661 bytes --]

On Saturday 17 May 2003 16:13, Werner Van Belle wrote:
> On Saturday 17 May 2003 15:57, Sven Vermeulen wrote:
> > Aah, then I'm completely in favor of adding this to Portage :)
>
> Maybe first investigate how good this thing works. I've done a quick check
> and I suspect this technique doesn't work on multithreaded programs.

If the profiles can be created correctly there should be nothing stopping this 
from working. The problem is thought that this not so much has to be 
implemented by portage as by specific packages that benefit from this.

Paul

-- 
Paul de Vrieze
Researcher
Mail: pauldv@cs.kun.nl
Homepage: http://www.devrieze.net

[-- Attachment #2: signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Chris Davies]

* Paul de Vrieze (pauldv@gentoo.org) wrote:
Content-Description: signed data
> On Saturday 17 May 2003 16:13, Werner Van Belle wrote:
> > On Saturday 17 May 2003 15:57, Sven Vermeulen wrote:
> > > Aah, then I'm completely in favor of adding this to Portage :)
> >
> > Maybe first investigate how good this thing works. I've done a quick check
> > and I suspect this technique doesn't work on multithreaded programs.
> 
> If the profiles can be created correctly there should be nothing stopping this 
> from working. The problem is thought that this not so much has to be 
> implemented by portage as by specific packages that benefit from this.
> 
> Paul
> 

The current release of gcc doesn't contain threadsafe profiling, and indeed may never do. The cfg branch, where this work is being carried out reports that merging threadsafe profiling with main is problematic, and the code may be dropped.

Still, there a whole bunch of single thread programs that can benifit from this stuff, especially on architectures like x86 which have tiny numbers of registers.

Thanks,
C.Davies


--
gentoo-dev@gentoo.org mailing list

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Paul de Vrieze]

[-- Attachment #1: signed data --]
[-- Type: text/plain, Size: 794 bytes --]

On Saturday 17 May 2003 18:47, Chris Davies wrote:
> * Paul de Vrieze (pauldv@gentoo.org) wrote:
> > If the profiles can be created correctly there should be nothing stopping
>
> The current release of gcc doesn't contain threadsafe profiling, and indeed
> may never do. The cfg branch, where this work is being carried out reports
> that merging threadsafe profiling with main is problematic, and the code
> may be dropped.
>
> Still, there a whole bunch of single thread programs that can benifit from
> this stuff, especially on architectures like x86 which have tiny numbers of
> registers.
>

Well, my condition was well chosen I guess. It's a pitty that it doesn't work.

Paul

-- 
Paul de Vrieze
Researcher
Mail: pauldv@cs.kun.nl
Homepage: http://www.devrieze.net

[-- Attachment #2: signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Sven Vermeulen]

[-- Attachment #1: Type: text/plain, Size: 770 bytes --]

On Sat, May 17, 2003 at 05:47:02PM +0100, Chris Davies wrote:
> The current release of gcc doesn't contain threadsafe profiling, and
> indeed may never do. The cfg branch, where this work is being carried out
> reports that merging threadsafe profiling with main is problematic, and the
> code may be dropped.

Concerning safe compilations, does the -fbranch-probabilities break 3rd party
GCC patches, such as propolice and such?

Wkr,
	Sven Vermeulen

-- 
Thanks to DRM, you know that something has been built in environment of 
unspecified degree of security, from source you cannot check, written by 
programmers you don't know, released after passing QA of unknown quality and 
which is released under a license that disclaims any responsibility...

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Chris Davies]

* Sven Vermeulen (swift@gentoo.org) wrote:
> On Sat, May 17, 2003 at 05:47:02PM +0100, Chris Davies wrote:
> > The current release of gcc doesn't contain threadsafe profiling, and
> > indeed may never do. The cfg branch, where this work is being carried out
> > reports that merging threadsafe profiling with main is problematic, and the
> > code may be dropped.
> 
> Concerning safe compilations, does the -fbranch-probabilities break 3rd party
> GCC patches, such as propolice and such?
> 
> Wkr,
> 	Sven Vermeulen

It should not do. I'll test this, but I'm pretty sure the answer is no.

Thanks,
C.Davies

--
gentoo-dev@gentoo.org mailing list

Re: [gentoo-dev] -fbranch-probabilities optimisation

[Matt Tucker]

-- Sven Vermeulen <swift@gentoo.org> spake thusly:

> On Sat, May 17, 2003 at 03:49:11AM +0100, Chris Davies wrote:
>> I had the idea to build -fbranch-probabilities optimisation into
>> portage. This is where a sample run of data is taken using the
>> program compiled with -fprofile-arcs, and that data then used to
>> reorganise the object code so conditional branches are layed out in
>> a more efficient manner.
> 
> Why implement it in Portage? Isn't it up to the user to define it in
> the CFLAGS or not? 

This isn't a simple matter of turning on a compiler flag.

>From 'man gcc':

	After running a program compiled with -fprofile-arcs, you can
	compile it a second time using -fbranch-probabilities, to
	improve optimizations based on the number of times each branch
	was taken.  When the program compiled with -fprofile-arcs exits
	it saves arc execution counts to a file called sourcename.da for
	each source file The information in this data file is very
	dependent on the structure of the generated code, so you must
	use the same source code and the same optimization options for
	both compilations.

However, the problem with trying to integrate this into portage is that
it must either:

 1) Compile programs on the user's machine, allow the user to run
    them, and then rebuild using the generated data. Quite a
    lengthy process, and fraught with issues.

or

 2) Distribute the profile data along with the source code. The
    trouble with this is that (as the man page says) it requires
    using the same source code and optimization options. So not only
    must the CFLAGS used be the same as with the profiled code, but
    the configure settings (which alter #define's and therefore the
    source) must be the same as well.


--
gentoo-dev@gentoo.org mailing list