[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] hash: declare some functions with the warn_unused_result att
From: |
Jim Meyering |
Subject: |
Re: [PATCH] hash: declare some functions with the warn_unused_result attribute |
Date: |
Wed, 17 Jun 2009 21:20:13 +0200 |
Eric Blake wrote:
> + /* Guarantee that once we start moving entries into the new table,
> + we will not need any further memory allocations. We only need
> + new allocations if the hasher consolidates multiple buckets from
> + the old size into one bucket with the new size (a sign of a bad
> + hasher, but we must deal with it). Therefore, we need merely
> + check that there are at least table->n_buckets_used-1 entries on
> + the free entry list for the worst case collision (everything gets
> + combined into one bucket during the rehash). */
That strikes me as pessimistic.
Imagine that we have a full table, with n_buckets_used == 20
and n_buckets == 23.
When rehashing to say 31, odds are very good that we can
get by with *no* entries on the free list -- if we're careful.
So requiring 22 is a recipe for unnecessary failure.
Right after your initial report, I began rewriting hash_rehash
to work as follows:
allocate new table
[ optimization to minimize possibility of unnecessary failure:
in the old table,
liberate any overflow (chained) entries by moving "data"
into empty buckets ]
iterate through old table members, hashing them into the new table,
[Possible optimization: process all overflow-entries before
any single-entry bucket. But that means two passes.
Alternatively: one pass through buckets, but for chains of
length > 1, process all allocated entries before the first,
non-allocated one, which (hence) might require an allocation
in the new table. ]
If, in spite of all that, allocation is required, restore to
the original table any entries that we've moved into the new one
and free the new one and return false. However, restoring them
may be tricky, so we'd have to be careful there, too.
This approach has the added advantage of decreasing the memory
footprint slightly, since we're more likely to reuse existing
allocated entries than to allocate new ones that would eventually
end up on the free list.
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute, (continued)
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute, Eric Blake, 2009/06/16
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute, Jim Meyering, 2009/06/16
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute, Eric Blake, 2009/06/16
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute, Ben Pfaff, 2009/06/16
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute, Jim Meyering, 2009/06/16
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute, Eric Blake, 2009/06/16
- alt hash implementation (was: [PATCH] hash: declare some functions with the warn_unused_result attribute), Eric Blake, 2009/06/17
- Re: alt hash implementation, Jim Meyering, 2009/06/17
- Re: alt hash implementation, Eric Blake, 2009/06/17
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute, Eric Blake, 2009/06/18
- Re: [PATCH] hash: declare some functions with the warn_unused_result attribute,
Jim Meyering <=
- hash_rehash allocatino failure (was: [PATCH] hash: declare some functions with the warn_unused_result attribute), Eric Blake, 2009/06/17
- Re: hash_rehash allocatino failure, Jim Meyering, 2009/06/17
- Re: hash_rehash allocatino failure, Eric Blake, 2009/06/18
- Re: hash_rehash allocation failure, Eric Blake, 2009/06/19
- hash resizing bug (was: [PATCH] hash: declare some functions with the warn_unused_result attribute), Eric Blake, 2009/06/17
- Re: hash resizing bug, Eric Blake, 2009/06/17
- Re: hash resizing bug, Eric Blake, 2009/06/17
- Re: hash resizing bug, Jim Meyering, 2009/06/17
- Re: hash resizing bug, Eric Blake, 2009/06/17
- Re: hash resizing bug, Jim Meyering, 2009/06/17