[PATCH] Improving Hash Thawing
Aaron Sherman
ajs at ajs.com
Thu Aug 5 18:28:50 UTC 2010
On Thu, Aug 5, 2010 at 2:10 PM, chromatic <chromatic at wgz.org> wrote:
> 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?
The first approach is specific to this need. The second approach seems more
generally useful. I'm always a fan of providing useful hints up-front.
--
Aaron Sherman
Email or GTalk: ajs at ajs.com
http://www.ajs.com/~ajs
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.parrot.org/pipermail/parrot-dev/attachments/20100805/0aafb905/attachment.html>
More information about the parrot-dev
mailing list