[Bug lto/50165] New: [4.7 regression] Huge build time regression (Firefox lto build)

[Bug lto/50165] New: [4.7 regression] Huge build time regression (Firefox lto build)

[markus at trippelsdorf dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

             Bug #: 50165
           Summary: [4.7 regression] Huge build time regression (Firefox
                    lto build)
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: lto
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: markus@trippelsdorf.de
                CC: dnovillo@google.com


Since Diegos patches (rev. 177571, 177661, 177704) went in
lto1 seems to run forever (I've killed it after 40 minutes) when libxul
is linked during a Firefox LTO build. 
It used to finish in 4-5 minutes before.

This is a profile captured during the lto1 run:
("perf record -ag sleep 5" and then "perf report -v -g --stdio")

 # Events: 5K cycles
#
# Overhead          Command                                    Shared Object   
                                                  Symbol
# ........  ...............  ............................................... 
..........................................................
#
    93.93%         lto1-wpa  /usr/libexec/gcc/x86_64-pc-linux-gnu/4.7.0/lto1 
0x74a633         d [.] htab_expand
                   |
                   --- htab_expand

     1.05%          swapper  [kernel.kallsyms]                               
0xffffffff810460c2 k [k] default_idle
...

and sometimes (much more infrequent) this profile:

    40.25%         lto1-wpa  /usr/libexec/gcc/x86_64-pc-linux-gnu/4.7.0/lto1 
0x74ad05         d [.] htab_find_slot_with_hash
                   |
                   --- htab_find_slot_with_hash

    30.74%         lto1-wpa  /usr/libexec/gcc/x86_64-pc-linux-gnu/4.7.0/lto1 
0x225b10         d [.] eq_string_slot_node
                   |
                   --- eq_string_slot_node

     2.06%         lto1-wpa  /lib/libz.so.1.2.5   
...

[Bug lto/50165] [4.7 regression] Huge build time regression (Firefox lto build)

[markus at trippelsdorf dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #1 from Markus Trippelsdorf <markus at trippelsdorf dot de> 2011-08-23 16:38:22 UTC ---
This regression is caused by revision 177571.
Reverting only 177661 and 177704 doesn't solve the problem.
Reverting all three revisions (77571, 177661 and 177704) solves the problem.

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011-08-24
   Target Milestone|---                         |4.7.0
            Summary|[4.7 regression] Huge build |[4.7 Regression] Huge build
                   |time regression (Firefox    |time regression (Firefox
                   |lto build)                  |lto build)
     Ever Confirmed|0                           |1

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-24 08:29:05 UTC ---
Using memcmp instead of strcmp may be one reason this is slower (I think
we inline strcmp but don't have any fancy memcmp inline implementations).

Thus, you might want to try s/memcmp/strcmp/ in eq_string_slot_node.

Also the hash-function changed by using an initial value of ds->len
instead of zero.  And (unsigned)ds->s[i] is not equal to (unsigned
char)ds->s[i]
(but no difference on x86_64).

I also wonder if we can speed up string hashing by use of some fancy
SSE12345 instructions.

Now, in general I think we lose all the bitpack compile-time optimizations
by no longer being able to inline them. They were crafted so that doing

bp_pack_value (bp, val1, 12);
bp_pack_value (bp, val2, 4);

results in a single shift and or instructions.  Now it's going to be
function calls :/  Please consider moving those primitives back to a
header file.

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[markus at trippelsdorf dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #3 from Markus Trippelsdorf <markus at trippelsdorf dot de> 2011-08-24 09:53:24 UTC ---
The following patch fixes the problem for me:

diff --git a/gcc/data-streamer.h b/gcc/data-streamer.h
index c413a75..acf1305 100644
--- a/gcc/data-streamer.h
+++ b/gcc/data-streamer.h
@@ -92,12 +92,7 @@ static inline hashval_t
 hash_string_slot_node (const void *p)
 {
   const struct string_slot *ds = (const struct string_slot *) p;
-  hashval_t r = ds->len;
-  int i;
-
-  for (i = 0; i < ds->len; i++)
-     r = r * 67 + (unsigned)ds->s[i] - 113;
-  return r;
+  return (hashval_t) htab_hash_string (ds->s);
 }

 /* Returns nonzero if P1 and P2 are equal.  */
@@ -107,11 +102,7 @@ eq_string_slot_node (const void *p1, const void *p2)
 {
   const struct string_slot *ds1 = (const struct string_slot *) p1;
   const struct string_slot *ds2 = (const struct string_slot *) p2;
-
-  if (ds1->len == ds2->len)
-    return memcmp (ds1->s, ds2->s, ds1->len) == 0;
-
-  return 0;
+  return strcmp (ds1->s, ds2->s) == 0;
 }

 /* Returns a new bit-packing context for bit-packing into S.  */

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-24 10:16:56 UTC ---
(In reply to comment #3)
> The following patch fixes the problem for me:
> 
> diff --git a/gcc/data-streamer.h b/gcc/data-streamer.h
> index c413a75..acf1305 100644
> --- a/gcc/data-streamer.h
> +++ b/gcc/data-streamer.h
> @@ -92,12 +92,7 @@ static inline hashval_t
>  hash_string_slot_node (const void *p)
>  {
>    const struct string_slot *ds = (const struct string_slot *) p;
> -  hashval_t r = ds->len;
> -  int i;
> -
> -  for (i = 0; i < ds->len; i++)
> -     r = r * 67 + (unsigned)ds->s[i] - 113;
> -  return r;
> +  return (hashval_t) htab_hash_string (ds->s);
>  }
> 
>  /* Returns nonzero if P1 and P2 are equal.  */
> @@ -107,11 +102,7 @@ eq_string_slot_node (const void *p1, const void *p2)
>  {
>    const struct string_slot *ds1 = (const struct string_slot *) p1;
>    const struct string_slot *ds2 = (const struct string_slot *) p2;
> -
> -  if (ds1->len == ds2->len)
> -    return memcmp (ds1->s, ds2->s, ds1->len) == 0;
> -
> -  return 0;
> +  return strcmp (ds1->s, ds2->s) == 0;
>  }
> 
>  /* Returns a new bit-packing context for bit-packing into S.  */

Can you check if keeping the ds1->len == ds2->len check in eq_string_slot_node
but using strcmp works as well?  If not, then it seems ->len is not
properly initialized in all cases (which would explain that changing the
hash is also important).

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-24 10:37:18 UTC ---
Btw, as ->len includes the trailing zero, the new hash function hashes in
a zero and the memcmp compares one byte unnecessarily.  To make the transform
1:1 it would be

static inline hashval_t
hash_string_slot_node (const void *p)
{
  const struct string_slot *ds = (const struct string_slot *) p;
  hashval_t r = 0;
  int i;

  for (i = 0; i < ds->len - 1; i++)
     r = r * 67 + (unsigned char)ds->s[i] - 113;
  return r;
}

static inline int
eq_string_slot_node (const void *p1, const void *p2)
{
  const struct string_slot *ds1 = (const struct string_slot *) p1;
  const struct string_slot *ds2 = (const struct string_slot *) p2;

  if (ds1->len == ds2->len)
    return strncmp (ds1->s, ds2->s, ds1->len - 1) == 0;

  return 0;
}

which, if it works fine, would be ok with me.

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[markus at trippelsdorf dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #6 from Markus Trippelsdorf <markus at trippelsdorf dot de> 2011-08-24 10:41:15 UTC ---
(In reply to comment #4)
> > -
> > -  if (ds1->len == ds2->len)
> > -    return memcmp (ds1->s, ds2->s, ds1->len) == 0;
> > -
> > -  return 0;
> > +  return strcmp (ds1->s, ds2->s) == 0;
> >  }
> > 
> >  /* Returns a new bit-packing context for bit-packing into S.  */
> 
> Can you check if keeping the ds1->len == ds2->len check in eq_string_slot_node
> but using strcmp works as well?  If not, then it seems ->len is not
> properly initialized in all cases (which would explain that changing the
> hash is also important).

No, keeping the (ds1->len == ds2->len) check doesn't work.

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-24 10:46:17 UTC ---
(In reply to comment #6)
> (In reply to comment #4)
> > > -
> > > -  if (ds1->len == ds2->len)
> > > -    return memcmp (ds1->s, ds2->s, ds1->len) == 0;
> > > -
> > > -  return 0;
> > > +  return strcmp (ds1->s, ds2->s) == 0;
> > >  }
> > > 
> > >  /* Returns a new bit-packing context for bit-packing into S.  */
> > 
> > Can you check if keeping the ds1->len == ds2->len check in eq_string_slot_node
> > but using strcmp works as well?  If not, then it seems ->len is not
> > properly initialized in all cases (which would explain that changing the
> > hash is also important).
> 
> No, keeping the (ds1->len == ds2->len) check doesn't work.

Oh dear.  I'll leave it for Diego to investigate then :)

At this point (well, and everywhere else, including in the hash function)

 gcc_assert (ds1->len == strlen (ds1->s) + 1
             && ds2->len == strlen (ds2->s) + 1);

should hold.

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[matz at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

Michael Matz <matz at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matz at gcc dot gnu.org

--- Comment #8 from Michael Matz <matz at gcc dot gnu.org> 2011-08-26 12:20:32 UTC ---
Try this:

Index: lto-streamer-in.c
===================================================================
--- lto-streamer-in.c   (revision 178040)
+++ lto-streamer-in.c   (working copy)
@@ -113,6 +113,7 @@ canon_file_name (const char *string)
       new_slot = XCNEW (struct string_slot);
       strcpy (saved_string, string);
       new_slot->s = saved_string;
+      new_slot->len = len;
       *slot = new_slot;
       return saved_string;
     }

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[dnovillo at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #9 from dnovillo at google dot com <dnovillo at google dot com> 2011-08-26 12:21:33 UTC ---
I will be with limited e-mail access until 7-Sep-2011. I will read
your message when I get back.


Diego.

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[markus at trippelsdorf dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #10 from Markus Trippelsdorf <markus at trippelsdorf dot de> 2011-08-26 13:25:33 UTC ---
(In reply to comment #8)
> Try this:
> 
> Index: lto-streamer-in.c
> ===================================================================
> --- lto-streamer-in.c   (revision 178040)
> +++ lto-streamer-in.c   (working copy)
> @@ -113,6 +113,7 @@ canon_file_name (const char *string)
>        new_slot = XCNEW (struct string_slot);
>        strcpy (saved_string, string);
>        new_slot->s = saved_string;
> +      new_slot->len = len;
>        *slot = new_slot;
>        return saved_string;
>      }

Yes, this fixes the issue. Thanks Michael.

(This if branch is from 2009-10-03 according to "git blame",
so the other hasher must be more permissive)

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[matz at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

--- Comment #11 from Michael Matz <matz at gcc dot gnu.org> 2011-08-26 16:02:21 UTC ---
Author: matz
Date: Fri Aug 26 16:02:17 2011
New Revision: 178118

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=178118
Log:
    PR lto/50165
    * lto-streamer-in.c (canon_file_name): Initialize new_slot->len;
    don't call strlen twice, use memcpy.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/lto-streamer-in.c

[Bug lto/50165] [4.7 Regression] Huge build time regression (Firefox lto build)

[markus at trippelsdorf dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50165

Markus Trippelsdorf <markus at trippelsdorf dot de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

--- Comment #12 from Markus Trippelsdorf <markus at trippelsdorf dot de> 2011-08-26 16:14:13 UTC ---
fixed