Re: Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)

From: Rutger Nijlunsing <rutger@nospam.com>
Date: Aug 20, 2006, 17:40 UTC
Message-ID: <20060820174054.GB21362@nospam.com>
In-Reply-To: <Pine.LNX.4.63.0608201846110.28360@wbgn013.biozentrum.uni-wuerzburg.de>

> Second, since you call hash_put() once per object, hash->nr cannot grow 
> too big, because grow_hash() doubles hash->alloc. And I call grow_hash() 
> once the hash map is half-full; Somebody once told me that would be the 
> optimal growing strategy.

Optimal growing mainly means to be O(n) (amortized) after n inserts. That translates to at least _doubling_ (factor 2 or more) the capacity once you're too full.

Assume doubling at a percentage full. Assume realloc(s) takes O(s) (where s = number of bytes). Assume we start with 1 element.

We realloc() then when we've got 1 element, then at 2, 4, 8 etc. The size of the realloc() at each point will also be 1, 2, 4, 8 etc. However, this cost of O(s) can be amortized over the number of elements. So the work done _per insert_ is still a constant (amortized again).

Ascilly:

   x x x x x x x x x x ...  (each insert)
     R   R       R     ...  (each realloc)
   1 2 0 4 0 0 0 8 0 0 ...  (cost of those realloc())

This has also to do with the infinite series of the sum(k>0) of 2^-k being a constant.

-- 
Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------