[Bug c++/67153] integer optimizations 53% slower than std::bitset<>

[Bug c++/67153] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

--- Comment #1 from ncm at cantrip dot org ---
Created attachment 36147
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36147&action=edit
The unsigned int version

[Bug c++/67153] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

ncm at cantrip dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |Linux amd64
      Known to work|                            |4.9.2
               Host|                            |Linux amd64
            Version|5.1.0                       |5.1.1
      Known to fail|                            |5.1.1
              Build|                            |Linux amd64

--- Comment #2 from ncm at cantrip dot org ---
The 4.9.2 release, "Debian 4.9.2-10", does not exhibit this bug.  When built 
with g++-4.9, the unsigned int version is slightly faster than the
std::bitset<> 
version.  The g++-5 release used was "Debian 5.1.1-9 20150602".

The Haswell host is running under a virtualbox VM, with /proc/cpuinfo
reporting stepping 3, microcode 0x19, and flags: fpu vme de pse tsc msr 
pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 
ht syscall nx rdtscp lm constant_tsc rep_good nopl pni ssse3 lahf_lm

The compiler used for the test on the Westmere M520, that appears not to 
exhibit the bug, was a snapshot "g++ (GCC) 6.0.0 20150504".

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Target|Linux amd64                 |x86_64-*-*
          Component|c++                         |tree-optimization
               Host|Linux amd64                 |
   Target Milestone|---                         |5.3
            Summary|integer optimizations 53%   |[5/6 Regression] integer
                   |slower than std::bitset<>   |optimizations 53% slower
                   |                            |than std::bitset<>
              Build|Linux amd64                 |

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

--- Comment #3 from ncm at cantrip dot org ---
Created attachment 36159
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36159&action=edit
bitset, but using an inlined container adapter, not lambdas, and slow

This version compiles just as badly as the integer version, even by gcc-4.9.

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

--- Comment #5 from ncm at cantrip dot org ---
My preliminary conclusion is that a hardware optimization provided in Haswell
but not in Westmere is not recognizing the opportunity in the unsigned int
test case, that it finds in the original bitset version, as compiled by gcc-5.

I have also observed that adding an assertion that the array index is not
negative, before the first array access, slows the program a further 100%, 
on Westmere.

Note that the entire data set fits in L3 cache on all tested targets, so
memory bandwidth does not figure.

To my inexperienced eye the effects look like branch mispredictions.
I do not understand why a 3.4 GHz DDR3 Haswell runs as slowly as a 
2.4 GHz DDR2 Westmere, when branch prediction (or whatever it is) 
fails.

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

--- Comment #6 from ncm at cantrip dot org ---
It seems worth adding that the same failure occurs without "-march=native".

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[ubizjak at gmail dot com]

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

--- Comment #7 from Uroš Bizjak <ubizjak at gmail dot com> ---
(In reply to ncm from comment #6)
> It seems worth adding that the same failure occurs without "-march=native".

Can you experiment a bit with -mno-bmi and/or -mno-bmi2 compile options?
>From gcc-bugs-return-494585-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue Aug 11 18:19:47 2015
Return-Path: <gcc-bugs-return-494585-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 7708 invoked by alias); 11 Aug 2015 18:19:47 -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 7619 invoked by uid 48); 11 Aug 2015 18:19:44 -0000
From: "ubizjak at gmail dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>
Date: Tue, 11 Aug 2015 18:19:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 5.1.1
X-Bugzilla-Keywords: missed-optimization
X-Bugzilla-Severity: normal
X-Bugzilla-Who: ubizjak at gmail dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 5.3
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-67153-4-xxlVeCcp3I@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-67153-4@http.gcc.gnu.org/bugzilla/>
References: <bug-67153-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-08/txt/msg00727.txt.bz2
Content-length: 328

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

--- Comment #8 from Uroš Bizjak <ubizjak at gmail dot com> ---
(In reply to Uroš Bizjak from comment #7)

> Can you experiment a bit with -mno-bmi and/or -mno-bmi2 compile options?

Also, perf is able to record execution profiles, it will help you find hot
spots.
>From gcc-bugs-return-494586-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue Aug 11 18:35:06 2015
Return-Path: <gcc-bugs-return-494586-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 21392 invoked by alias); 11 Aug 2015 18:35:05 -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 20713 invoked by uid 48); 11 Aug 2015 18:35:02 -0000
From: "dje at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug middle-end/66565] Problems and limitation GCC cost metrics and ways to improve the situation
Date: Tue, 11 Aug 2015 18:35:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: middle-end
X-Bugzilla-Version: 6.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: dje at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-66565-4-pM8yIvvbDM@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-66565-4@http.gcc.gnu.org/bugzilla/>
References: <bug-66565-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: 2015-08/txt/msg00728.txt.bz2
Content-length: 537

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

--- Comment #2 from David Edelsohn <dje at gcc dot gnu.org> ---
The high-level consensus at the GNU Cauldron 2015 GCC Cost Model BoF is:

1) Create gimple_costs() instead of creating potentially invalid fragments to
query rtx_costs().

2) Cost models can utilize GCC Pass phase to set expectations for optimization
changes by later passes.

3) Cost models should be queried for relative comparisons of the potential
instruction sequences, not for comparisons against magic constants.

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

--- Comment #9 from ncm at cantrip dot org ---
I did experiment with -m[no-]bmi[2] a fair bit.  It all made a significant
difference in the instructions emitted, but exactly zero difference in 
runtime. That's actually not surprising at all; those instructions get 
decomposed into micro-ops that exactly match those from the equivalent
instructions, and are cached, and the loops that dominate runtime execute 
out of the micro-op cache.  The only real effect is maybe slightly shorter
object code, which could matter in a program dominated by bus traffic
with loops too big to cache well.  I say "maybe slightly shorter" because
instruction-set extension instructions are actually huge, mostly prefixes.

I.e. most of the BMI stuff is marketing fluff, added mainly to make the 
competition waste money matching them instead of improving the product.

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

--- Comment #10 from ncm at cantrip dot org ---
I found this, which at first blush seems like it might be relevant.
The hardware complained about here is the same Haswell i7-4770.

http://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-count-variable-with-64-bit-introduces-crazy-performance

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

--- Comment #11 from ncm at cantrip dot org ---
Aha, Uroš, I see your name in 

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

Please forgive me for "teaching" you about micro-ops.

The code being generated for all versions does use (e.g.)
"popcntq %rax, %rax" almost everywhere.  Not quite everywhere -- I see 
one "popcntq %rax, %rdx" -- but certainly in all the performance-sensitive 
bits.
>From gcc-bugs-return-494701-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Aug 13 02:30:17 2015
Return-Path: <gcc-bugs-return-494701-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 74460 invoked by alias); 13 Aug 2015 02:30:17 -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 74407 invoked by uid 48); 13 Aug 2015 02:30:13 -0000
From: "zhongyunde at huawei dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/67199] New: ICE with compile bug related to vector_size
Date: Thu, 13 Aug 2015 02:30:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 4.9.4
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: zhongyunde at huawei dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-67199-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: 2015-08/txt/msg00843.txt.bz2
Content-length: 1132

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

            Bug ID: 67199
           Summary: ICE with compile bug related to vector_size
           Product: gcc
           Version: 4.9.4
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zhongyunde at huawei dot com
  Target Milestone: ---

testcase:

__attribute__ ((vector_size (16))) g_73 = {0x15FE687EL, 0x5827DF98L,
0xF8411272L, 0x235E695EL};
__attribute__ ((vector_size (16))) g_1124;

int func_1(void)
{
    __attribute__ ((vector_size (16))) l_1117 = {0x15FE688EL, 0x5827DF98L,
0xF8411272L, 0x235E695EL};
    __attribute__ ((vector_size (16))) zhong = ( g_73 <= g_73);
         g_1124 = (((g_73 < l_1117) == (zhong)) << 9)    ;

    return 0;
}

the following issue can be reproduced  with -O2 when the gcc built on 64 bits
system.

internal compiler error: in fold_convert_loc, at fold-const.c:1974
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[ncm at cantrip dot org]

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

--- Comment #12 from ncm at cantrip dot org ---
As regards hot spots, the program has two:

        int score[7] = { 0, };
        for (Letters word : words)
/**/        if (!(word & ~seven))
                for_each_in_seven([&](Letters letter, int place) {
                    if (word & letter)
/**/                    score[place] += (word == seven) ? 3 : 1;
                });

The first is executed 300M times, the second 3.3M times.
Inserting a counter bump before the second eliminates the slowdown:

                    if (word & letter) {
                        ++count;
/**/                    score[place] += (word == seven) ? 3 : 1;
                    }

This fact seems consequential.  The surrounding for_each_in_seven
loop isn't doing popcounts, but is doing "while (v &= -v)".

I have repeated tests using -m[no-]bmi[2], with identical results
(i.e. no effect).

[Bug tree-optimization/67153] [5/6 Regression] integer optimizations 53% slower than std::bitset<>

[miyuki at gcc dot gnu.org]

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

Mikhail Maltsev <miyuki at gcc dot gnu.org> changed:

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

--- Comment #15 from Mikhail Maltsev <miyuki at gcc dot gnu.org> ---
(In reply to ncm from comment #13)
> I am very curious whether this has been reproduced on others' Haswells,
> and on Ivybridge and Skylake.

I could reproduce this with Haswell i7-5820K (affected) and also tested on
Ivybridge i7-3770K (not affected).

Haswell:

GCC 4.9.3 native

real    0m0.150s
user    0m0.149s
sys     0m0.001s
GCC 6.0.0 native

real    0m0.213s
user    0m0.212s
sys     0m0.000s
GCC 6.0.0 native + count

real    0m0.166s
user    0m0.165s
sys     0m0.000s

================

GCC 4.9.3 generic

real    0m0.128s
user    0m0.127s
sys     0m0.001s
GCC 6.0.0 generic

real    0m0.213s
user    0m0.213s
sys     0m0.000s
GCC 6.0.0 generic + count

real    0m0.125s
user    0m0.124s
sys     0m0.000s


Ivybridge:

GCC 4.9.2 native

real    0m0.218s
user    0m0.216s
sys     0m0.000s
GCC 6.0.0 native

real    0m0.186s
user    0m0.184s
sys     0m0.000s
GCC 6.0.0 native + count

real    0m0.266s
user    0m0.264s
sys     0m0.000s

================

GCC 4.9.2 generic

real    0m0.224s
user    0m0.220s
sys     0m0.004s
GCC 6.0.0 generic

real    0m0.183s
user    0m0.180s
sys     0m0.000s
GCC 6.0.0 generic + count

real    0m0.181s
user    0m0.176s
sys     0m0.004s

Here "native" means "-march=native -mtune=native", "generic" means no arch
options. "+count" means adding a counter into the loop and writing it's value
to a global volatile variable after the loop.

[Bug tree-optimization/67153] [9/10/11/12 Regression] integer optimizations 53% slower than std::bitset<>

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|8.5                         |9.4

--- Comment #31 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 8 branch is being closed.

[Bug tree-optimization/67153] [9/10/11/12 Regression] integer optimizations 53% slower than std::bitset<>

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.4                         |9.5

--- Comment #32 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.

[Bug tree-optimization/67153] [10/11/12/13 Regression] integer optimizations 53% slower than std::bitset<>

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.5                         |10.4

--- Comment #33 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9 branch is being closed

[Bug tree-optimization/67153] [10/11/12/13 Regression] integer optimizations 53% slower than std::bitset<>

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #34 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug tree-optimization/67153] [11/12/13/14 Regression] integer optimizations 53% slower than std::bitset<>

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.5                        |11.5

--- Comment #35 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 10 branch is being closed.