Mantis - Squeak
Viewing Issue Advanced Details
6348 Kernel major always 03-18-07 14:11 02-06-11 23:48
closed 3.9  
none 4.1  
0006348: [FIX] Improve performance of weak key dictionaries
This patch reimplements WeakKeyDictionary in order to improve its performance, by avoiding frequent rehashing. In measurements, the current code takes 4..5 times as long as the new code.

The main strategy is to give WeakKeyAssociation an "expired" state, meaning that the key has been garbage-collected, and the values has been finalized. Expired association are left in the dictionary, rather than rehashing the dictionary. Plain removal of the association is not possible, since the following slots in the array may be collisions from the slot that expired. So leaving the expired association in allows to find the subsequen entries.

When an entry is removed, the association is forcefully expired, but also left in the dictionary, avoiding reorganizations on removal.

When a new entry is added to the dictionary, it may either replace an expired entry, or must go into a nil array slot; replacing an association with a nil key that is not expired is not possible, as the value may need to see finalization still.

A counter expired is kept in the dictionary to count how many expired associations had been created since the last reorganization; this may be larger than the number of expired associations if some of them had been reused. fullCheck has been extended to rehash the dictionary if the number of expired entries is larger than a quarter of the array size.

WeakKeyAssociation has been reimplemented in two ways. First, the expired "state" was introduced: an expired association is one that has itself as its value. Furthermore, the key item of the association is now a weak slot itself, rather than holding a WeakArray of size 1. As Squeak does not allow to change a class with fixed slots into a weak subclass, a new class WeakKeyAssociation2 is introduced; the class method install will then replace WeakKeyAssociation2 with WeakKeyAssociation.

The old implementation was inconsistent in what keys you get when iterating over a dictionary: should the associations with collected keys be considered or not (in particular, keysDo: would skip them, associationsDo: would report them). The new implementation consistently suppresses them. For use in the WeakRegistry, unexpired associations with nil keys must be detected; to support this case, allAssociationsDo: was added.

In reviewing the code, I found that there is a lot of duplication in scanFor:, scanForNil:, and rehash that I would have to change in an atomic manner in order to avoid breakage. I refactored the code so that subclasses don't have to override the entire scan algorithm, but can just replace the way equality works and the way the start index for the scan is computed.

The patch is provided as two sets of changesets. weakdictall includes all changed code in a single set, but introduces the new classes under the names WeakKeyDictionary2 and WeakKeyAssociation2.

The second set of changesets, weakfix1..weakfix4, actually changes the existing classes, in an order to avoid breakage. This is derived from weakdictall in the following manner:
- weakfix1 introduces all new selectors, installs WeakKeyAssociation2 (renaming it to WeakKeyAssociation afterwards), and adds the expired field to WeakKeyDictionary (setting it to 0 on all instances)
- weakfix2 rewrites scanFor: and scanForNil: and removes it from WeakIdentityKeyDictionary
- weakfix3 replaces all methods for WeakKeyDictionary with their new code
- weakfix4 replaces all methods that aren't need anymore or should not be called.
related to 0002910closed leves WeakKeyDictionary performance improvement 
 weakdictall.2.cs [^] (21,806 bytes) 03-18-07 14:11
 weakfix1.1.cs [^] (12,499 bytes) 03-18-07 14:12
 weakfix2.1.cs [^] (1,950 bytes) 03-18-07 14:12
 weakfix3.1.cs [^] (5,260 bytes) 03-18-07 14:13
 weakfix4.1.cs [^] (1,355 bytes) 03-18-07 14:13
 license.txt [^] (1,059 bytes) 03-19-07 10:02 [^] (7,813 bytes) 03-28-07 10:16 [^] (1,377 bytes) 04-15-07 20:04
 MessageTallyWithAndWithoutTheFIX.txt [^] (26,201 bytes) 07-18-07 13:30

03-28-07 10:16   
Uploaded new version, which fixes a problem when growing dictionaries with nil keys.
04-15-07 10:01   
Reminder sent to: loewis

Could you add a example for timing before and after ?
This way I could add to 3.10, look [^]
ttp:// [^]
04-15-07 20:05   
I have attached a copy of two WeakKeyDictionaryTest class methods which can be used to measure the timing improvements. To run them, print

WeakKeyDictionaryTest timingLarge


WeakKeyDictionaryTest timingMany
04-16-07 11:38   
WeakKeyDictionaryTest timingLarge 1414 6247
WeakKeyDictionaryTest timingMany 1345 6890

Wow ! I wish put this as 7089WeakWeakKeyDictionaryEnh

Very thanks for this work !

But you should send mail to Ralph for he authorize me to do this in old style update.
That is what in some cases using our procedure "Monticello way", sometimes image blow or wait forever and do not complete the update.
If I install in order the .cs, all works

07-18-07 13:31   
Hi !
I am currently trying to use Magma with a big database for a game. The critical process reifies all the databases, apply an update method on it and commit the changes. This process takes ~ 15min so I wanted to optimize it a bit more and tried this improvement of WeakKeyDictionary.
But the results are very bad : ~ 85min with the exact same conditions except for the fix.
I don't know if my experiment can be of any help for you but you can find the two MessageTally attached in MessageTallyWithAndWithoutTheFIX.txt.

09-21-07 07:17   
Please review my 'hack' of weak registry. [^]
i don't have WeakKeyDictionaryTest class, but it works fine for me over 3 weeks or so in my image.
It should improve finalization process speed even more.
11-23-10 09:04   
A simpler enhancement was applied in Squeak 4.1 which doesn't have the bottlenecks introduced by these changes. Reimplementing WeakKeyAssociation may still give a minor performance improvement at the cost of method duplication.