[Bug libstdc++/51386] New: [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[Bug libstdc++/51386] New: [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[hp at gcc dot gnu.org]

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

             Bug #: 51386
           Summary: [4.7 Regression]:
                    23_containers/unordered_set/hash_policy/load_factor.cc
                    execution timeout
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: hp@gcc.gnu.org
                CC: fdumont@gcc.gnu.org
              Host: x64_86-unknown-linux-gnu
            Target: cris-axis-elf


With revision r181675 this test passed.
>From revision r181679 and on, this test has failed as follows:

Running
/tmp/hpautotest-gcc1/gcc/libstdc++-v3/testsuite/libstdc++-dg/conformance.exp
...
WARNING: program timed out.
FAIL: 23_containers/unordered_set/hash_policy/load_factor.cc execution test

With the message in the logfile being uninteresting:

PASS: 23_containers/unordered_set/hash_policy/load_factor.cc (test for excess
errors)
WARNING: program timed out.
FAIL: 23_containers/unordered_set/hash_policy/load_factor.cc execution test

The timeout is 10 minutes.
Author of patches in suspect revision range CC:ed.

Note: cris-elf is tested as a simulator target, the host is a Core2 Duo E8400 @
3GHz.

The load_factor.cc test itself has iterations with numbers like 100000 which
seem like they should be lowered for simulator targets just as is done for
other tests.  But, the timeout is a red flag; it seems one or more of the
changes in the revision-range pessimized the library performance-wise.  All the
suspect changes ones are to libstdc++-v3 itself.  Without a timeout, that test
take more than 25 minutes after the changes.  I'll add a new comment with the
measured time some time after the test has finished.

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[paolo.carlini at oracle dot com]

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

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-12-02 10:12:26 UTC ---
Francois, please take a look asap.

Hans-Peter, can it be a memory issue? The recent changes imply that more memory
is used by these data structures, and that is largely unavoidable, thus if
there is nothing wrong algorithmically and the slow down is due to more memory
being used, there isn't much we can do, besides tweaking the test for
simulators, of course.

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011-12-02
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com
     Ever Confirmed|0                           |1

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-12-02 11:06:01 UTC ---
Thus, I did a couple of timings for current mainline vs Rev 181676 and there is
a HUGE slowdown, on native too: from a fraction of second to tens of seconds
(I'm intentionally being inaccurate, doesn't matter here)

Thus we should really analyze what is going on, the issue seems serious.

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[hp at gcc dot gnu.org]

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

--- Comment #3 from Hans-Peter Nilsson <hp at gcc dot gnu.org> 2011-12-02 11:07:20 UTC ---
(In reply to comment #1)
> Hans-Peter, can it be a memory issue? The recent changes imply that more memory
> is used by these data structures, and that is largely unavoidable,

Unavoidable, really?

> thus if
> there is nothing wrong algorithmically

But if there's no algorithmic effect and just using more memory, then what's
the improvement?  Ah ok, looking at the changes I see, maybe...is the fix for
empty buckets maybe exposing load_factor.cc as an odd case not worth
optimizing?

Oh, I see floating-point changes, has the patch perhaps increased the number of
floating-point computations very much?  Bad for soft-float targets.

> and the slow down is due to more memory
> being used, there isn't much we can do, besides tweaking the test for
> simulators, of course.

Memory access cost is practically free in a simulator, so I'd expect to see
effects the other way round, i.e. non-simulator setups (where cache misses
really hurt) would suffer more than (non-cache) simulator setups. :)  Ok,
half-joking: an increased number of instructions would mean...getting just the
same effect.

At least the simulation finally ended, taking:
/tmp/hpautotest-gcc1/cris-elf/pre/bin/cris-elf-run load_factor.exex  6766.54s
user 0.61s system 84% cpu 2:13:52.65 total

Yes, two hours, close to fourteen minutes instead of less than 0 hours ten
minutes.  So, if this comes down to just tweaking the test-case, I'd suggest
trivially reducing the loops for simulator targets with a factor of twenty more
than the expected scaled timeout, taken to one significant figure, i.e.
20*6800/600 ~= 200.

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[paolo.carlini at oracle dot com]

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

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-12-02 11:10:36 UTC ---
(In reply to comment #3)
> (In reply to comment #1)
> > Hans-Peter, can it be a memory issue? The recent changes imply that more memory
> > is used by these data structures, and that is largely unavoidable,
> 
> Unavoidable, really?

**If** where only a memory issue would be unavoidable yes. This is a long,
long, discussion which took place in various LWG ISO Meetings, about the
performance of erase, which we can't summarize here. Unavoidably a C++11
conforming hashed container uses more memory that a legacy HP/SGI hash_map /
hash_set.

But I don't think is a memory issue, now.

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[paolo.carlini at oracle dot com]

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

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-12-02 11:12:20 UTC ---
Note the huge slow down is entirely in the third block, for
max_load_factor(.3), we must do something about it.

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[hp at gcc dot gnu.org]

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

--- Comment #6 from Hans-Peter Nilsson <hp at gcc dot gnu.org> 2011-12-02 11:15:54 UTC ---
(In reply to comment #3)

(My reply probably seems slightly odd due to the mid-air collision with comment
#2.)

> Oh, I see floating-point changes, has the patch perhaps increased the number of
> floating-point computations very much?  Bad for soft-float targets.

FWIW, I see the test started failing for armv7l-unknown-linux-gnueabi too:
http://gcc.gnu.org/ml/gcc-testresults/2011-11/msg02488.html compared to
http://gcc.gnu.org/ml/gcc-testresults/2011-11/msg02424.html.
And that is a primary target for gcc-4.7.

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.7.0

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[fdumont at gcc dot gnu.org]

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

--- Comment #7 from François Dumont <fdumont at gcc dot gnu.org> 2011-12-05 20:55:59 UTC ---
The problem is in the hash policy, while computing _M_prev_resize the max load
factor is not always considered. The result is that when max load factor is
lower than 1 the hashtable is rehashed almost each time we insert a new
element.

I have submitted a patch on mailing list and wait for its approval. Sorry for
the inconvenience.

Note that memory was not really a suspect cause the hash code is not put in
cache for integral types like the int used in the test.

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[fdumont at gcc dot gnu.org]

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

--- Comment #8 from François Dumont <fdumont at gcc dot gnu.org> 2011-12-07 19:47:08 UTC ---
Author: fdumont
Date: Wed Dec  7 19:47:03 2011
New Revision: 182085

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=182085
Log:
2011-12-07  François Dumont <fdumont@gcc.gnu.org>

    PR libstdc++/51386
    * include/bits/hashtable_policy.h (_Prime_rehash_policy::_M_next_bkt):
    Fix computation of _M_prev_resize so that hashtable do not keep on
    being rehashed when _M_max_load_factor is lower than 1.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/hashtable_policy.h

[Bug libstdc++/51386] [4.7 Regression]: 23_containers/unordered_set/hash_policy/load_factor.cc execution timeout

[paolo.carlini at oracle dot com]

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

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

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

--- Comment #9 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-12-07 20:24:46 UTC ---
Fixed.