From f7888fb3078a781ecc947ded0b064d1a901d5887 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Wed, 6 Apr 2011 14:33:10 +0000 Subject: Tweaked the hash table resizer, it now is more careful about increasing the size of the table when it can reclaim empty space from deletes, and it allows the table to shrink if little enough space is being used. --- src/hash.h | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) (limited to 'src/hash.h') diff --git a/src/hash.h b/src/hash.h index 26b16c7..5c7bc78 100644 --- a/src/hash.h +++ b/src/hash.h @@ -42,10 +42,22 @@ namespace Bu */ struct __calcNextTSize_fast { - uint32_t operator()( uint32_t nCapacity, uint32_t, uint32_t nDeleted ) const + uint32_t operator()( uint32_t nCapacity, uint32_t nFilled, + uint32_t nDeleted ) const { - if( nDeleted >= nCapacity/2 ) + // This frist case will allow hashtables that are mostly deleted + // items to reset to small allocations + if( nFilled-nDeleted <= nCapacity/4 ) + { + nCapacity = 11; + while( nCapacity < nFilled*5/4 ) + nCapacity = nCapacity*2+1; + return nCapacity; + } + // This will hopefully prevent hash tables from growing needlessly + if( nFilled-nDeleted <= nCapacity/2 ) return nCapacity; + // Otherwise, just increase the capacity return nCapacity*2+1; } }; -- cgit v1.2.3