This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [dataflow][patch] Convert conflict graph to lower triangular bit matrix
- From: Peter Bergner <bergner at vnet dot ibm dot com>
- To: Joern RENNECKE <joern dot rennecke at st dot com>
- Cc: Kenneth Zadeck <zadeck at naturalbridge dot com>, Daniel Berlin <dberlin at dberlin dot org>, gcc-patches at gcc dot gnu dot org
- Date: Thu, 02 Feb 2006 12:48:01 -0600
- Subject: Re: [dataflow][patch] Convert conflict graph to lower triangular bit matrix
- References: <43E2346F.3030509@st.com>
On Thu, 2006-02-02 at 16:33 +0000, Joern RENNECKE wrote:
> This is a very bad idea. The algorithm that examines conflicts is
> quadratic in time. For functions with lots of registers, you get a very
> large, sparce matrix. Using a symmetric matrix saves us a linear time
> factor of about 64, since we can scan a row of the matrix one word at a
> time.
It's not as bad as you make it out. Yes the old method has the constant
(not linear) factor of 64 benefit. However, you don't credit the new
method for completely eliminating the O(n^2) call to mirror_conflicts.
Admittedly the old method has slightly better cache behavior than the
new method, but from a practical standpoint there's not much difference
between the two. The worst case slowdown I saw was about 1.5% on my
BIGGEST test case. The majority of the differences were in the noise
and not detectable.
I could continue to try and defend the patch, but it's a moot point
since in a follow on patch I'll be submitting soon, I'll be adding
an adjacency list which will be more efficient than the old method.
Note that this particular patch is not targeted at the moment to
mainline. However, when it is, it will be submitted with the adjacency
list follow on patch, so you won't see any slowdown.
Peter