Reimplementing WeakKeyDictionary
Andreas Raab
andreas.raab at gmx.de
Sun Mar 18 19:46:26 UTC 2007
Martin v. Löwis wrote:
> In essence, this introduces two changes:
> - when values are finalized or keys removed from the dictionary,
> it is not always rehashed anymore. Instead, the dictionary just
> releases the value, and marks the association as expired. Expired
> associations can then be reused if a new value is to be inserted
> under the same has. Rehashing is only done when so many entries
> have expired. Expired entries don't count towards the size of the
> dictionary, and aren't reported when iterating over the dictionary.
That's an interesting approach. I would expect this to impact the time
it takes to insert/find elements in the dict, no? Like:
wd := WeakKeyDictionary new.
1 to: 100 do:[:i| wd at: i put: i].
1 to: 99 do:[:i| wd removeKey: i].
After this point I'd expect the operations to be slower since we have
about a hundred expired elements in the dict. Nothing that a good
#rehash can't fix of course, but I'm wondering if at some point the WKD
shouldn't recognize the ratio of expired/free/used slots and act
accordingly. In any case, it's definitely an improvement.
> - WeakKeyAssociation was rewritten to be a weak class, with a fixed
> slot for the value, and a weak slot for the key (currently, it
> has two fixed slots, with the key slot referring to a WeakArray
> of length 1).
Hah! Finally ;-) When I wrote the weak dicts I was concerned about the
usage of associations for literal bindings in code and whether any such
weak associations might be used for this purpose (the problem is that
the VM accesses those directly and not having the right values in the
right slots will give you "interesting" results). However, that concern
never even remotely materialized so it's basically a waste of perfectly
good resources. Thanks for cleaning that part up.
Cheers,
- Andreas
More information about the Squeak-dev
mailing list
|