[Bug libstdc++/57885] New: unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[Bug libstdc++/57885] New: unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[jhand at austin dot rr.com]

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

            Bug ID: 57885
           Summary: unordered_map find slower in 4.8.1 than 4.7.3 with
                    integer key
           Product: gcc
           Version: 4.8.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jhand at austin dot rr.com

Created attachment 30499
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30499&action=edit
unordered_map.cpp

I have been looking at performance of std::unordered_map versus
tr1::unordered_map using gcc-4.6.3, gcc-4.7.3, and gcc-4.8.1. I am mostly
interested in the performance of find(), although insertion performance is
important too.

I am attaching a simple program that creates a vector of 100,000 integers. It
calls a function that measures the time to insert the vector into an
unordered_map of integers to integers. It does this in a loop five times,
recording the amount spent each time, and clearing the unordered_map at the end
of the loop except the final time through the loop. The time to clear the map
is not measured.

Then within a loop of 5 times, it performs find() on the unordered map using
the original vector of integers. It measures the time spent looking up all of
the integers in the vector 5 times.

On gcc-4.6.3, I get the following output (the numbers are microseconds):
 Container:std::unordered_map<int,int>  Key:int
 Insertion: 10458 4885 4874 4892 4871  min=4871 max=10458
 Lookup:    11609 11613 11597 11611 11594  min=11594 max=11613

 Container:std::tr1::unordered_map<int,int>  Key:int
 Insertion: 12399 4963 4948 4949 4961  min=4948 max=12399
 Lookup:    11580 11573 11562 11559 11570  min=11559 max=11580

On gcc-4.7.3, I get the following output:
 Container:std::unordered_map<int,int>  Key:int
 Insertion: 14454 16288 16499 15830 15753  min=14454 max=16499
 Lookup:    12229 12208 12204 12201 12200  min=12200 max=12229

 Container:std::tr1::unordered_map<int,int>  Key:int
 Insertion: 9926 4978 5000 4972 4971  min=4971 max=9926
 Lookup:    11667 11636 11646 11636 11652  min=11636 max=11667

On gcc-4.8.1, I get the following output:
 Container:std::unordered_map<int,int>  Key:int
 Insertion: 13234 7441 7519 7546 7569  min=7441 max=13234
 Lookup:    14812 14823 14846 14810 14805  min=14805 max=14846

 Container:std::tr1::unordered_map<int,int>  Key:int
 Insertion: 12450 5228 5197 5186 5249  min=5186 max=12450
 Lookup:    11579 11530 11592 11535 11529  min=11529 max=11592

It looks like the tr1::unordered_map implementation performs approximately the
same across compilers.

The std::unordered_map::find() implementation slows down by approximately 5.2%
in gcc-4.7.3 compared to gcc-4.6.3. It slows down by about 27.7% in gcc-4.8.1
compared to gcc-4.6.1. The insertion performance is about 52.7% worse in
gcc-4.8.1 compared to gcc-4.6.1.

The code was compiled with the following:

g++ -std=c++0x -DNDEBUG -O3 -o unordered_map unordered_map.cpp

This is on Linux x86_64 with Intel Xeon X5570 @ 2.93GHz.

I have seen this performance degradation with some of my user defined classes,
but I thought that an integer key best shows the issue.

[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

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

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Cc-ing Francois

[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[paolo.carlini at oracle dot com]

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

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> ---
A few notes. First, lately the std containers, which have different complexity
requirements, share zero code with the tr1 version. In general we should redo
the measurements for 4.9 which has further changes.

In my opinion, in these measurements 4.8.1 was pretty good for Insertion, but
Lookup got worse, that seems to me the most important issue. I would ask
Francois to check why, profile where the additional time is going (assuming
it's still the case for 4.9!)

[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[jhand at austin dot rr.com]

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

--- Comment #3 from Jim Hand <jhand at austin dot rr.com> ---
As a simplification, I tried compiling the following code with gcc-4.6.3 into
assembly with gcc-4.6.3 and 4.8.1:

#include <unordered_map>

bool contains(std::unordered_map<int, int> a) {
   return a.find(5) != a.end();
}

gcc-4.6.3 generates the following assembly:

.LFB574:
    .cfi_startproc
    movq    8(%rdi), %rcx
    movq    16(%rdi), %rdi
    xorl    %edx, %edx
    movl    $5, %eax
    divq    %rdi
    xorl    %eax, %eax
    movq    (%rcx,%rdi,8), %rsi
    movq    (%rcx,%rdx,8), %rdx
    testq    %rdx, %rdx
    jne    .L6
    jmp    .L2
    .p2align 4,,10
    .p2align 3
.L11:
    movq    8(%rdx), %rdx
    testq    %rdx, %rdx
    je    .L10
.L6:
    cmpl    $5, (%rdx)
    jne    .L11
    cmpq    %rdx, %rsi
    setne    %al
.L2:
    rep
    ret
    .p2align 4,,10
    .p2align 3
.L10:
    xorl    %eax, %eax
    ret
    .cfi_endproc

gcc-4.8.1 generates the following assembly:

.LFB1323:
    .cfi_startproc
    movq    8(%rdi), %r8
    xorl    %edx, %edx
    movl    $5, %eax
    divq    %r8
    movq    (%rdi), %rax
    movq    (%rax,%rdx,8), %rax
    movq    %rdx, %r9
    testq    %rax, %rax
    je    .L7
    movq    (%rax), %rcx
    movl    8(%rcx), %esi
    .p2align 4,,10
    .p2align 3
.L3:
    cmpl    $5, %esi
    je    .L5
    movq    (%rcx), %rcx
    testq    %rcx, %rcx
    je    .L7
    movl    8(%rcx), %esi
    xorl    %edx, %edx
    movslq    %esi, %rax
    divq    %r8
    cmpq    %rdx, %r9
    je    .L3
.L7:
    xorl    %eax, %eax
    ret
    .p2align 4,,10
    .p2align 3
.L5:
    movl    $1, %eax
    ret
    .cfi_endproc

In the gcc-4.8.1 code, I see two divq instructions that I think are coming from
line 345 of _Mod_range_hashing in bits/hashtable_policy.h:

 343     result_type
 344     operator()(first_argument_type __num, second_argument_type __den)
const
 345     { return __num % __den; }

I would think that the hash function only needs to be called once for this
function, but I could be misinterpreting the assembly output. It does look to
me like the 4.8 output is doing a lot more than the 4.6.3 output, but I'll
leave it for you to explore.

[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[jhand at austin dot rr.com]

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

--- Comment #4 from Jim Hand <jhand at austin dot rr.com> ---
I compiled 4.9.0-20130714 today and ran the same tests. Here are the results
for the lookup loops with the times for each compiler:

4.6.3: 11536 microseconds
4.7.3: 12150 microseconds  (5.3% slower than 4.6.3)
4.8.2: 14810 microseconds  (28.3% slower than 4.6.3)
4.9.0-20130714 15365 microseconds (33.1% slower than 4.6.3)

I took a look at the assembly for the "return a.find(5) != a.end();" code for
4.9 and it looks very similar to the 4.8 assembly, but contains two extra
instructions at the beginning of the function:

    testq    %r8, %r8
     je    .L8

I guess those two instructions explain the the slightly worse behavior for
4.9.0 than 4.8.2.

[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[fdumont at gcc dot gnu.org]

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

--- Comment #5 from François Dumont <fdumont at gcc dot gnu.org> ---
The biggest performance regression introduced in version 4.8 is coming from an
attempt to enhance unordered containers global performances. The data model has
been modified because the erase operation had become very expensive in some
situations since the Standard requires it to return the iterator following the
erased one. To do so we moved from a vector<forward_list> like data model to a
combination of vector<forward_list::iterator> for buckets and a single
forward_list for elements. In the former model when erasing an element we
needed to look for the next non-empty bucket potentially looping through a lot
of empty ones resulting in very bad performances. In the new model all elements
are linked to the next one and the access is direct.

The drawback is that when looking for an element you need to get its bucket and
then loop on the bucket element. In the former model the loop end condition was
the forward_list::end(). In the new model you need to compute the next element
bucket to check that you can stop because you moved to another bucket. This
explains the additional divq instruction and the performance hint.

Of course your bench is isolating the main drawback of the new data model.
There are benches in libstdc++ testsuite/performance that compares tr1 and std
implementations and globally std ones are better even if you can already see
the performance hint you are reporting here. So we chose to move from a data
model very good on some use cases but very bad on some others to a data model
good in all situations but not very good anymore in your use case.

I agree however that your use case is quite important and the only way I can
think of to restore its performance would be to introduce a concept of empty
node in the data model so that we detect end of bucket without relying on a
divq instruction. The drawback will be a memory overhead, one bool per node to
flag empty/non-empty node and an additional empty node per non empty bucket.
This is perhaps more acceptable for such a container which purpose is not to be
memory efficient but rather performance efficient.

The performance hint of version 4.9 comes from C++11 allocator conformity. I
will avoid details but for exception safety reasons I had to correctly manage
an unordered container instance having no bucket allocated. In this case the
number of bucket is 0 and doing a 'hash code % 0' operation is bad so I had to
introduce some checks on the bucket number at the beginning of some methods
like the find one. It explains the additional testq operation which is I fear
unavoidable for a Standard conforming implementation.
>From gcc-bugs-return-426354-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Thu Jul 18 12:58:46 2013
Return-Path: <gcc-bugs-return-426354-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 15784 invoked by alias); 18 Jul 2013 12:58:45 -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 12852 invoked by uid 48); 18 Jul 2013 12:56:43 -0000
From: "jahns at dkrz dot de" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug fortran/57924] -Werror -Warray-temporaries -Wno-error=array-temporaries fails on array temporary warnings
Date: Thu, 18 Jul 2013 12:58:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: fortran
X-Bugzilla-Version: 4.7.2
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: jahns at dkrz dot de
X-Bugzilla-Status: UNCONFIRMED
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-57924-4-meoj93G6jL@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-57924-4@http.gcc.gnu.org/bugzilla/>
References: <bug-57924-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: 2013-07/txt/msg00861.txt.bz2
Content-length: 197

http://gcc.gnu.org/bugzilla/show_bug.cgi?idW924

--- Comment #2 from Thomas Jahns <jahns at dkrz dot de> ---
Just tried with gfortran 4.8.1 (an Ubuntu 13.04 test release). The problem
persists.

[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[fdumont at gcc dot gnu.org]

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

--- Comment #7 from François Dumont <fdumont at gcc dot gnu.org> ---
I had a try and the result is not good. I attached the modified implementation
if you want to have a try even if it is not perfect cause there are some
exception safety issue.

With the current implementation on my device I have the following result:

Container:std::unordered_map<int,int>  Key:int
Insertion: 23521 13329 13899 13544 13870  min=13329 max=23521
Lookup:    29246 29120 32406 29524 29065  min=29065 max=32406

Container:std::tr1::unordered_map<int,int>  Key:int
Insertion: 24410 10392 10404 10226 10180  min=10180 max=24410
Lookup:    22728 19985 20314 19918 20741  min=19918 max=22728

With the modified solution using empty nodes to mark end of bucket I had:

Container:std::unordered_map<int,int>  Key:int
Insertion: 30080 19250 17861 18955 18350  min=17861 max=30080
Lookup:    35884 36518 38623 35896 36661  min=35884 max=38623

Container:std::tr1::unordered_map<int,int>  Key:int
Insertion: 28912 10112 10046 10447 13026  min=10046 max=28912
Lookup:    22515 20114 19517 20400 19543  min=19517 max=22515

I fear that the memory overhead is not only impacting memory. It is surely not
good for memory cache. If you want to give it a try and check generated
assembly, additional testq should have vanish.

François
>From gcc-bugs-return-427234-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Aug 02 21:31:34 2013
Return-Path: <gcc-bugs-return-427234-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 28284 invoked by alias); 2 Aug 2013 21:31:34 -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 28220 invoked by uid 48); 2 Aug 2013 21:31:32 -0000
From: "fdumont at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/57840] ::std ::result_of is undocumented
Date: Fri, 02 Aug 2013 21:31:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: unknown
X-Bugzilla-Keywords:
X-Bugzilla-Severity: minor
X-Bugzilla-Who: fdumont at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
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: cc attachments.created
Message-ID: <bug-57840-4-TDPRjNC36M@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-57840-4@http.gcc.gnu.org/bugzilla/>
References: <bug-57840-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: 2013-08/txt/msg00158.txt.bz2
Content-length: 548

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

François Dumont <fdumont at gcc dot gnu.org> changed:

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

--- Comment #1 from François Dumont <fdumont at gcc dot gnu.org> ---
Created attachment 30595
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30595&action=edit
To replace hashtable_policy.h in include/bits folder
>From gcc-bugs-return-427235-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Aug 02 21:32:56 2013
Return-Path: <gcc-bugs-return-427235-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 31672 invoked by alias); 2 Aug 2013 21:32:56 -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 31599 invoked by uid 48); 2 Aug 2013 21:32:53 -0000
From: "fdumont at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/57840] ::std ::result_of is undocumented
Date: Fri, 02 Aug 2013 21:32:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: unknown
X-Bugzilla-Keywords:
X-Bugzilla-Severity: minor
X-Bugzilla-Who: fdumont at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
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: attachments.created
Message-ID: <bug-57840-4-NWIqY5G7I3@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-57840-4@http.gcc.gnu.org/bugzilla/>
References: <bug-57840-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: 2013-08/txt/msg00159.txt.bz2
Content-length: 304

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

--- Comment #2 from François Dumont <fdumont at gcc dot gnu.org> ---
Created attachment 30596
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30596&action=edit
The modified hashtable implementation

To replace hashtable.h in include/bits
>From gcc-bugs-return-427236-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Aug 02 21:37:23 2013
Return-Path: <gcc-bugs-return-427236-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 8034 invoked by alias); 2 Aug 2013 21:37:23 -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 7960 invoked by uid 48); 2 Aug 2013 21:37:20 -0000
From: "paolo.carlini at oracle dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key
Date: Fri, 02 Aug 2013 21:37:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 4.8.1
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: paolo.carlini at oracle dot com
X-Bugzilla-Status: UNCONFIRMED
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-57885-4-sgnioTP180@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-57885-4@http.gcc.gnu.org/bugzilla/>
References: <bug-57885-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: 2013-08/txt/msg00160.txt.bz2
Content-length: 165

http://gcc.gnu.org/bugzilla/show_bug.cgi?idW885

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Francois, you attached to the wrong bug.

[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[fdumont at gcc dot gnu.org]

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

--- Comment #9 from François Dumont <fdumont at gcc dot gnu.org> ---
Created attachment 30610
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30610&action=edit
hashtable_policy.h

File to replace the one in include/bits folder
>From gcc-bugs-return-427333-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Aug 04 20:18:26 2013
Return-Path: <gcc-bugs-return-427333-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 19994 invoked by alias); 4 Aug 2013 20:18:26 -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 19919 invoked by uid 48); 4 Aug 2013 20:18:23 -0000
From: "fdumont at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key
Date: Sun, 04 Aug 2013 20:18:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 4.8.1
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: fdumont at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
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: attachments.created
Message-ID: <bug-57885-4-AqeTC5q1oN@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-57885-4@http.gcc.gnu.org/bugzilla/>
References: <bug-57885-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: 2013-08/txt/msg00257.txt.bz2
Content-length: 280

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

--- Comment #10 from François Dumont <fdumont at gcc dot gnu.org> ---
Created attachment 30611
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30611&action=edit
hashtable.h

File to replace the one in include/bits
>From gcc-bugs-return-427334-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Aug 04 20:22:02 2013
Return-Path: <gcc-bugs-return-427334-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 24627 invoked by alias); 4 Aug 2013 20:22:02 -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 24553 invoked by uid 48); 4 Aug 2013 20:22:00 -0000
From: "paolo.carlini at oracle dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/57850] Option -fdump-translation-unit not working
Date: Sun, 04 Aug 2013 20:22: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.8.1
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: paolo.carlini at oracle dot com
X-Bugzilla-Status: UNCONFIRMED
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: cc
Message-ID: <bug-57850-4-XiGjYYBsUD@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-57850-4@http.gcc.gnu.org/bugzilla/>
References: <bug-57850-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: 2013-08/txt/msg00258.txt.bz2
Content-length: 618

http://gcc.gnu.org/bugzilla/show_bug.cgi?idW850

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gdr at gcc dot gnu.org,
                   |                            |rguenther at suse dot de

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Given some "puzzling" comments in the old PR2778, I think we want an expert to
confirm the bug and figure out which kind of functionality we want restored.

[Bug libstdc++/57885] unordered_map find slower in 4.8.1 than 4.7.3 with integer key

[fdumont at gcc dot gnu.org]

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

--- Comment #11 from François Dumont <fdumont at gcc dot gnu.org> ---
I just wanted to let you know about a way to enhance performance of your lookup
if you can afford it. I realized that if you copy the container before running
lookup you greatly enhance results. Here is what I obtain by just doing:

c1 = Container(c1);

between the 2 lookups:

Container:std::unordered_map<int,int>  Key:int
Insertion: 16407 8818 7952 7881 7874  min=7874 max=16407
Lookup1:   15774 15767 15985 15845 15751  min=15751 max=15985
Lookup2:   13613 12725 12685 12678 12861  min=12678 max=13613

Container:std::tr1::unordered_map<int,int>  Key:int
Insertion: 22044 5845 5716 5785 5608  min=5608 max=22044
Lookup1:   12620 12881 12597 12568 12656  min=12568 max=12881
Lookup2:   14385 12506 12043 13122 11970  min=11970 max=14385

You see that lookup 2 is much closer to the tr1 implementation. This is so
because after copy the container has a much better memory localization so less
memory page fault. If allocator keeps on returning memory node adjacent to each
other you end up with all nodes relying in the same memory block.

I have plan to document this. Of course you can only use it if you initialize
once for all or you barely update the content but lookup into it very often.

I am still looking at solutions to restore previous lookup performances.
>From gcc-bugs-return-475956-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Feb 04 01:48:08 2015
Return-Path: <gcc-bugs-return-475956-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 4703 invoked by alias); 4 Feb 2015 01:48:08 -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 4538 invoked by uid 48); 4 Feb 2015 01:47:59 -0000
From: "dmalcolm at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug jit/64257] JIT documentation is not yet on the GCC website
Date: Wed, 04 Feb 2015 01:48:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: jit
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: critical
X-Bugzilla-Who: dmalcolm at gcc dot gnu.org
X-Bugzilla-Status: ASSIGNED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: dmalcolm at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-64257-4-EtEqKUiIRz@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-64257-4@http.gcc.gnu.org/bugzilla/>
References: <bug-64257-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-02/txt/msg00289.txt.bz2
Content-length: 389

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

--- Comment #5 from David Malcolm <dmalcolm at gcc dot gnu.org> ---
https://gcc.gnu.org/ml/gccadmin/2015-q1/msg00077.html had:
  sphinx-build -b html -d _build/doctrees   . _build/html
  Making output directory...
  Running Sphinx v0.6.6

  Theme error:
  no theme named 'pyramid' found (missing theme.conf?)
  make: *** [html] Error 1