[PATCH] Improving Hash Thawing

[chromatic]

The attached patch (for discussion, not application) attempts to resize hashes 
appropriately before thawing them.  The current naive algorithm lets 
parrot_hash_put() double the size of the hash when it runs out of free 
buckets; for a hash which starts with 8 buckets and must contain 240 elements, 
parrot_hash_put() will perform five (to 16, 32, 64, 128, and finally 256 
buckets) reallocations.

... and we *know* the number of desired elements of the hash at the point of 
the thaw.

This patch does not entirely work correctly because it somehow loses the 
free_list information of the hash when resizing.  I have run out of time to 
debug this.

An alternate approach -- which may be more effective in the long term -- is to 
change hash creation such that we can select the most appropriate initial size 
for the hash and avoid resizing at all.  That patch seemed more invasive, but 
it may be easier to write correctly.

Thoughts?

-- c

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hash_thaw_sizing.patch
Type: text/x-patch
Size: 3773 bytes
Desc: not available
URL: <http://lists.parrot.org/pipermail/parrot-dev/attachments/20100805/e28443cd/attachment.bin>