[Bug libstdc++/26424] New: tr1/unordered vs 64-bit machines

[Bug libstdc++/26424] New: tr1/unordered vs 64-bit machines

[pcarlini at suse dot de]

The number of buckets is currently limited to ~2^32 (see X<>::primes). This is
a serious issue: for correctness, rehash(n) for n > 2^32 should throw and do
nothing, in order not to violate the post-conditions in Table 21.

We have various options: as suggested by Howard off-line, we could well compute
at run-time prime-numbers. Otherwise, mid-term, if we cannot extend the maximum
number of bucket we have to add throws to the rehashing functions.


-- 
           Summary: tr1/unordered vs 64-bit machines
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pcarlini at suse dot de


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

[Bug libstdc++/26424] tr1/unordered vs 64-bit machines

[falk at debian dot org]

------- Comment #1 from falk at debian dot org  2006-02-22 17:11 -------
Just curious: is the assumption of prime-size buckets hardwired in the TR?
Otherwise, the obvious alternative would be to use power-of-two sizes, which
are much faster in access.


-- 


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

[Bug libstdc++/26424] tr1/unordered vs 64-bit machines

[pcarlini at suse dot de]

------- Comment #2 from pcarlini at suse dot de  2006-02-22 17:23 -------
(In reply to comment #1)
> Just curious: is the assumption of prime-size buckets hardwired in the TR?
> Otherwise, the obvious alternative would be to use power-of-two sizes, which
> are much faster in access.

Yes. Really, I have yet to study the issue in detail (Knuth...), I'm going to
do that. For sure TR1 doesn't mandate a specific policy, but we have got a
default policy, prime_rehash_policy, which is definitely well known and used
elsewhere, it would be nice to fix it, to begin with ;)


-- 


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

[Bug libstdc++/26424] tr1/unordered vs 64-bit machines

[pcarlini at suse dot de]

------- Comment #3 from pcarlini at suse dot de  2006-02-22 18:01 -------
... something considered "obvious" in the literature is that the size policy
goes together with the range-hashing function: e.g., an exponential size-policy
would not work well together with our default modulo range-hashing function.


-- 


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

[Bug libstdc++/26424] tr1/unordered vs 64-bit machines

[pcarlini at suse dot de]

------- Comment #4 from pcarlini at suse dot de  2006-04-19 10:49 -------
Working on it.


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pcarlini at suse dot de
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2006-04-19 10:49:52
               date|                            |


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

[Bug libstdc++/26424] tr1/unordered vs 64-bit machines

[paolo at gcc dot gnu dot org]

------- Comment #5 from paolo at gcc dot gnu dot org  2006-04-19 22:58 -------
Subject: Bug 26424

Author: paolo
Date: Wed Apr 19 22:58:23 2006
New Revision: 113100

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=113100
Log:
2006-04-19  Paolo Carlini  <pcarlini@suse.de>

        PR libstdc++/26424
        * include/tr1/hashtable (X<>::primes): Extend for 64-bit machines.
        (X<>::n_primes): Adjust.
        (prime_rehash_policy::next_bkt, bkt_for_elements, need_rehash): Adjust.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/tr1/hashtable


-- 


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

[Bug libstdc++/26424] tr1/unordered vs 64-bit machines

[pcarlini at suse dot de]

-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.1.1


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

[Bug libstdc++/26424] tr1/unordered vs 64-bit machines

[paolo at gcc dot gnu dot org]

------- Comment #6 from paolo at gcc dot gnu dot org  2006-04-21 17:50 -------
Subject: Bug 26424

Author: paolo
Date: Fri Apr 21 17:49:48 2006
New Revision: 113143

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=113143
Log:
2006-04-21  Paolo Carlini  <pcarlini@suse.de>

        PR libstdc++/26424
        * include/tr1/hashtable (X<>::primes): Extend for 64-bit machines.
        (X<>::n_primes): Adjust.
        (prime_rehash_policy::next_bkt, bkt_for_elements, need_rehash): Adjust.

Modified:
    branches/gcc-4_1-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_1-branch/libstdc++-v3/include/tr1/hashtable


-- 


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

[Bug libstdc++/26424] tr1/unordered vs 64-bit machines

[pcarlini at suse dot de]

------- Comment #7 from pcarlini at suse dot de  2006-04-21 17:51 -------
Fixed for 4.1.1.


-- 

pcarlini at suse dot de changed:

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


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