Mantis - Squeak
Viewing Issue Advanced Details
2910 Collections feature always 02-18-06 17:45 02-06-11 23:48
lewis  
leves  
normal  
closed  
fixed  
none    
none 4.1  
0002910: WeakKeyDictionary performance improvement
WeakRegistry and other users of WeakKeyDictionary display poor performance as size increases. Most of the performance problem is associated with removing objects from WeakKeyDictionaries, an operation that generates a lot of rehashing activity.

I am attaching WeakKeyDictionarySpeedup-dtl.cs, which improves performance considerably for explicit removal of items from a WeakKeyDictionary. WeakArray finalization performance is a related issue, and is not addressed by this change set (although WeakArray finalization will be improved by applications that explicitly remove objects whenever possible).
WeakKeyDictionarySpeedup-dtl.cs greatly improves performance of explicit deletion from a WeakKeyDictionary. It does not address the related issue of finalization, in which entries are removed as a result of the garbage collector signaling the finalization process. Note however that an application may be able to reduce the amount of finalization activity by explicitly deleting entries whenever possible, in which case this change set should produce significant performance improvement.

To see the bottleneck:

  | reg r |
  reg _ WeakRegistry new: 800.
  r _ Random new.
  TimeProfileBrowser onBlock:
      [(1 to: 10000 by: 7) do: [:e | reg add: (r nextInt: e)].
      reg asArray do: [:e | reg remove: e]].

WeakKeyDictionarySpeedup-dtl.cs improves performance by one and a half orders of magnitude for the above example by reducing unecessary rehashing, eliminating unnecessary checks for array size increases, and with a minor tweak to the key lookup. The new #rehashFrom: method implements the limited rehashing, replacing #fixCollisionsFrom: when explicitly removing a single item from the collection.

The strategy employed, following deletion of an element of the collection, is to rehash only up to the next nil slot in the collection array, while removing any elements with nil keys. A check for array size expansion is eliminated because removing an element from a collection does not make the collection larger.
related to 0006348closed leves [FIX] Improve performance of weak key dictionaries 
 WeakKeyDictionarySpeedup-dtl.3.cs [^] (3,575 bytes) 02-18-06 17:45

Notes
(0004420)
lewis   
03-10-06 13:25   
Andreas responded as follows on squeak-dev:
-----------------
Unfortunately, this doesn't work. The reason for using #rehash was that
when a key in a weak key dictionary gets eliminated that key's hash
changes. Your implementation doesn't account for that and will break in
the face of some actual finalized keys in the dictionary.

Cheers,
  - Andreas
-----------------
FWIW, I think that my implementation *does* work, because it addresses only the limited case of deleting an item from the collection and not the general case of responding to finalization events from the VM. Nevertheless, reviewers would be well advised to trust Andreas and not me ;)
(0010447)
loewis   
03-18-07 17:41   
I think I agree with Andreas that the patch is incorrect in the presence of values that still need to be finalized. When a key is removed, an unknown number of associations in the collection may have a nil key, and the finalization process may not yet have had a chance to rehash the dictionary.

IIRC, your patch will simply drop associations with a nil key from the dictionary. This is incorrect: they need to be preserved, as later there may be a need to call finalizeValues on their values (specifically, if this WeakKeyDictionary belongs to a weak registry).

A wider-reaching problem to solve the same problem is at

http://bugs.squeak.org/view.php?id=6348 [^]
(0013914)
leves   
11-07-10 03:28   
It's fixed in Squeak 4.1 by the reimplementation of #fixCollisionsFrom:.