[Bug c++/56493] New: Performance regression in google dense hashmap

[Bug c++/56493] New: Performance regression in google dense hashmap

[andrewjcg at gmail dot com]

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

             Bug #: 56493
           Summary: Performance regression in google dense hashmap
    Classification: Unclassified
           Product: gcc
           Version: 4.7.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: andrewjcg@gmail.com


When compared to gcc-4.6.2, gcc-4.7.1 shows about a 10-20% performance
regression when inserting into a google dense hashmap in a tight loop.  A small
sample program is attached and was compiled with '-O3' and on a linux x86_64
box (using -std=gnu++0x, as required by sparsehash).  Potentially related, the
generated binary under gcc-4.7 is also over 50% bigger.

[Bug c++/56493] Performance regression in google dense hashmap

[andrewjcg at gmail dot com]

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

--- Comment #1 from Andrew Gallagher <andrewjcg at gmail dot com> 2013-03-01 13:11:30 UTC ---
Created attachment 29561
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29561
Sample program using dense hashmap

[Bug c++/56493] Performance regression in google dense hashmap

[andrewjcg at gmail dot com]

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

--- Comment #2 from Andrew Gallagher <andrewjcg at gmail dot com> 2013-03-01 13:12:41 UTC ---
I also see this same perf regression on trunk (as of r195725).

[Bug c++/56493] Performance regression in google dense hashmap

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2013-03-01
     Ever Confirmed|0                           |1

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-03-01 14:29:24 UTC ---
Instead of expecting everyone who looks at this bug to find and download the
dense hash map code please provide preprocessed source as requested in the bug
reporting guidelines that you were prominently asked to read before you entered
this bug report: http://gcc.gnu.org/bugs/

[Bug c++/56493] Performance regression in google dense hashmap

[andrewjcg at gmail dot com]

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

--- Comment #4 from Andrew Gallagher <andrewjcg at gmail dot com> 2013-03-01 22:09:10 UTC ---
Created attachment 29565
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29565
Preprocessed test program source

[Bug c++/56493] Performance regression in google dense hashmap

[andrewjcg at gmail dot com]

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

--- Comment #5 from Andrew Gallagher <andrewjcg at gmail dot com> 2013-03-01 22:10:14 UTC ---
Ah, sorry.  Just attached preprocessed sources now (which had to be compressed
to it in the 1K size limit).

[Bug c++/56493] Performance regression in google dense hashmap

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |UNCONFIRMED
     Ever Confirmed|1                           |0

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-03-02 00:56:53 UTC ---
thanks

[Bug c++/56493] Performance regression in google dense hashmap

[andrewjcg at gmail dot com]

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

--- Comment #7 from Andrew Gallagher <andrewjcg at gmail dot com> 2013-03-09 04:17:39 UTC ---
I was able to bisect this to
http://gcc.gnu.org/viewcvs?view=revision&revision=172430.  I haven't had time
to dig in further, but that rev looks like it has plenty of inlining changes,
which makes sense.

[Bug c++/56493] Performance regression in google dense hashmap

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-03-09 10:57:06 UTC ---
Thanks for bisecting it

[Bug c++/56493] Performance regression in google dense hashmap

[cberner at fb dot com]

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

--- Comment #9 from Christopher Berner <cberner at fb dot com> 2013-04-13 01:37:27 UTC ---
Created attachment 29864
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29864
Simple test case

Here's an even simpler test case. It seems that there's a fairly serious
regression with inlining. Even adding the attribute always_inline doesn't seem
to restore performance. However, manually inlining the code with a macro
restores performance to gcc 4.6 level

[Bug c++/56493] Performance regression in google dense hashmap

[andrewjcg at gmail dot com]

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

--- Comment #10 from Andrew Gallagher <andrewjcg at gmail dot com> 2013-04-13 01:44:27 UTC ---
I did several attempts at bisecting this.  Whenever I (hackily) reverted the
change which caused the regression, it just popped up a few hundred revs later.
 This seems to be gcc assigning new weights to functions, which determines
whether the functions is early inlined or not.  So I *think* this is really an
early inlining v. late inlining issue, and we happened to get lucky with the
weights that 4.6 selected (I don't think there is a really effective way for
gcc to predict how subsequent optimizations will/can benefit by early
inlining).

Also, as far as I can see, there is no way to force early inlining (other than
switching to macros).

[Bug c++/56493] Performance regression in google dense hashmap

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |ktietz at gcc dot gnu.org,
                   |                            |law at gcc dot gnu.org

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The reduced testcase has been slowed down by r176072, aka PR45437.  If you want
to speed it up by source code changes, q += (unsigned int) f(i); would do
instead of q += f(i);, or you can do q = q + f(i);.
Before that bugfix, the C++ FE produced
(void) (q = (int) ((unsigned int) f (i) + (unsigned int) q))
which is generally wrong (say if q was addressable and f could modify it),
after it we generate
(void) (q = TARGET_EXPR <D.2078, f (i)>;, (int) ((long unsigned int) q +
D.2078);)
The question is why the narrowing of the operation (to be done on unsigned int
rather than long unsigned int) isn't performed here, that is something we do
right now solely in the FE.  There are PRs (PR45397 and PR47477) about lack of
type demotion (and promotion) on GIMPLE, but don't know what the current state
of that is.

[Bug c++/56493] Performance regression in google dense hashmap

[jim at meyering dot net]

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

jim at meyering dot net changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jim at meyering dot net

--- Comment #12 from jim at meyering dot net ---
Thank you, Jakub.

[Bug c++/56493] Performance regression in google dense hashmap

[jakub at gcc dot gnu.org]

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

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 30312
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30312&action=edit
gcc49-pr56493.patch

Untested patch that in the FE restores the performance on the simplified
testcase.  Haven't tried the original.  Of course, having this optimization be
performed in GIMPLE will be much more worthwhile, but likely not backportable.

[Bug c++/56493] Performance regression in google dense hashmap

[ubizjak at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

--- Comment #14 from Uroš Bizjak <ubizjak at gmail dot com> ---
According to Comment #0 and Comment #9, this PR should be confirmed as a 
regression from 4.6.
>From gcc-bugs-return-469310-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Dec 03 09:40:51 2014
Return-Path: <gcc-bugs-return-469310-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 17263 invoked by alias); 3 Dec 2014 09:40:51 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 16905 invoked by uid 48); 3 Dec 2014 09:40:46 -0000
From: "mpolacek at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/64105] [4.9/5 Regression] ICE: in strip_typedefs, at cp/tree.c:1326
Date: Wed, 03 Dec 2014 09:40:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Version: 4.9.2
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: mpolacek at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.9.3
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cf_reconfirmed_on cc target_milestone short_desc everconfirmed
Message-ID: <bug-64105-4-hoULNUdTqK@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-64105-4@http.gcc.gnu.org/bugzilla/>
References: <bug-64105-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-12/txt/msg00317.txt.bz2
Content-length: 823

https://gcc.gnu.org/bugzilla/show_bug.cgi?idd105

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-12-03
                 CC|                            |mpolacek at gcc dot gnu.org
   Target Milestone|---                         |4.9.3
            Summary|ICE: in strip_typedefs, at  |[4.9/5 Regression] ICE: in
                   |cp/tree.c:1326              |strip_typedefs, at
                   |                            |cp/tree.c:1326
     Ever confirmed|0                           |1

--- Comment #1 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Confirmed.

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|2013-03-01 00:00:00         |2014-12-03
            Summary|Performance regression in   |[4.8/4.9/5 Regression]
                   |google dense hashmap        |Performance regression in
                   |                            |google dense hashmap
     Ever confirmed|0                           |1

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
We are using that #c13 patch successfully for almost 18 months now in Fedora.
As type promotion/demotion patch is not (sadly) going to happen for GCC 5, I
still think it would be worthwhile to apply it temporarily, until type
promotion/demotion is written.

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #15)
> We are using that #c13 patch successfully for almost 18 months now in Fedora.
> As type promotion/demotion patch is not (sadly) going to happen for GCC 5, I
> still think it would be worthwhile to apply it temporarily, until type
> promotion/demotion is written.

Works for me.

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

--- Comment #17 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, I think that

(int) ((long unsigned int) q + D.2078)

to

(int) ((unsigned int) q + (unsigned int) D.2078)

doesn't look like an always profitable pattern on GIMPLE (more stmts).  Also
take into consideration what targets PROMOTE_MODE (mode-of-q/D.2078) do
and prefer types according to that.

The vectorizer prefers single type sizes throughout computations to avoid
re-packing.

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.8.4

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

--- Comment #18 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #17)
> Btw, I think that
> 
> (int) ((long unsigned int) q + D.2078)
> 
> to
> 
> (int) ((unsigned int) q + (unsigned int) D.2078)
> 
> doesn't look like an always profitable pattern on GIMPLE (more stmts).  Also
> take into consideration what targets PROMOTE_MODE (mode-of-q/D.2078) do
> and prefer types according to that.
> 
> The vectorizer prefers single type sizes throughout computations to avoid
> re-packing.

Which is why the proposal was to do demotion early and promote back depending
on machine description (and, perhaps on separate IL copy, in between ifcvt and
vectorizer also promote to decrease re-packing).  The demotion would help with
avoiding unnecessary computations (e.g. those affecting just the high bits),
canonicalizing the IL and in some cases allowing bigger parts of computations
with the same type bitsizes, and promotion would be an attempt to help with
sub-word arithmetics on word only arithmetics targets, etc.
Dunno why Kai has stopped working on that :(.

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

--- Comment #19 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #18)
> (In reply to Richard Biener from comment #17)
> > Btw, I think that
> > 
> > (int) ((long unsigned int) q + D.2078)
> > 
> > to
> > 
> > (int) ((unsigned int) q + (unsigned int) D.2078)
> > 
> > doesn't look like an always profitable pattern on GIMPLE (more stmts).  Also
> > take into consideration what targets PROMOTE_MODE (mode-of-q/D.2078) do
> > and prefer types according to that.
> > 
> > The vectorizer prefers single type sizes throughout computations to avoid
> > re-packing.
> 
> Which is why the proposal was to do demotion early and promote back
> depending on machine description (and, perhaps on separate IL copy, in
> between ifcvt and vectorizer also promote to decrease re-packing).  The
> demotion would help with avoiding unnecessary computations (e.g. those
> affecting just the high bits), canonicalizing the IL and in some cases
> allowing bigger parts of computations with the same type bitsizes, and
> promotion would be an attempt to help with sub-word arithmetics on word only
> arithmetics targets, etc.
> Dunno why Kai has stopped working on that :(.

Because I pushed back hard.  He ended up with multiple passes here and there,
and mostly motivated things by better folding with less conversions in the IL.

I also think you can't really separate demotion and promotion (demotion
is just making range information a little bit more "explicit" in the IL,
and thus IMHO tied to VRP if it runs).  Promotion (which can of course also
be effective demotion if legal) is to make things aligned with the target.

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

--- Comment #20 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Dec  4 09:46:45 2014
New Revision: 218345

URL: https://gcc.gnu.org/viewcvs?rev=218345&root=gcc&view=rev
Log:
    PR c++/56493
    * convert.c (convert_to_real, convert_to_expr, convert_to_complex):
    Handle COMPOUND_EXPR.

    * c-c++-common/pr56493.c: New test.

Added:
    trunk/gcc/testsuite/c-c++-common/pr56493.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/convert.c
    trunk/gcc/testsuite/ChangeLog

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

--- Comment #21 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Dec  4 09:47:54 2014
New Revision: 218346

URL: https://gcc.gnu.org/viewcvs?rev=218346&root=gcc&view=rev
Log:
    PR c++/56493
    * convert.c (convert_to_real, convert_to_expr, convert_to_complex):
    Handle COMPOUND_EXPR.

    * c-c++-common/pr56493.c: New test.

Added:
    branches/gcc-4_9-branch/gcc/testsuite/c-c++-common/pr56493.c
Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/convert.c
    branches/gcc-4_9-branch/gcc/testsuite/ChangeLog

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

--- Comment #22 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Thu Dec  4 09:48:54 2014
New Revision: 218347

URL: https://gcc.gnu.org/viewcvs?rev=218347&root=gcc&view=rev
Log:
    PR c++/56493
    * convert.c (convert_to_real, convert_to_expr, convert_to_complex):
    Handle COMPOUND_EXPR.

    * c-c++-common/pr56493.c: New test.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/c-c++-common/pr56493.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/convert.c
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog

[Bug c++/56493] [4.8/4.9/5 Regression] Performance regression in google dense hashmap

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56493

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED
      Known to fail|                            |4.8.3, 4.9.2

--- Comment #23 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.