Mantis Bugtracker
  

Viewing Issue Simple Details Jump to Notes ] View Advanced ] Issue History ] Print ]
ID Category Severity Reproducibility Date Submitted Last Update
0002910 [Squeak] Collections feature always 02-18-06 17:45 02-06-11 23:48
Reporter lewis View Status public  
Assigned To leves
Priority normal Resolution fixed  
Status closed   Product Version
Summary 0002910: WeakKeyDictionary performance improvement
Description 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).
Additional Information 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.
Attached Files  WeakKeyDictionarySpeedup-dtl.3.cs [^] (3,575 bytes) 02-18-06 17:45

- Relationships
related to 0006348closed leves [FIX] Improve performance of weak key dictionaries 

- Notes
(0004420 - 671 - 741 - 741 - 741 - 741 - 741)
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 - 668 - 704 - 832 - 832 - 832 - 832)
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 - 72 - 72 - 72 - 72 - 72 - 72)
leves
11-07-10 03:28

It's fixed in Squeak 4.1 by the reimplementation of #fixCollisionsFrom:.
 

- Issue History
Date Modified Username Field Change
02-18-06 17:45 lewis New Issue
02-18-06 17:45 lewis File Added: WeakKeyDictionarySpeedup-dtl.3.cs
02-19-06 13:10 pmm Issue Monitored: pmm
03-10-06 13:25 lewis Note Added: 0004420
03-10-06 13:26 lewis Issue Monitored: lewis
03-18-07 17:41 loewis Note Added: 0010447
03-18-07 19:41 loewis Note Added: 0010448
03-19-07 05:05 loewis Note Deleted: 0010448
03-19-07 23:05 lewis Relationship added related to 0006348
03-20-07 23:01 loewis Issue Monitored: loewis
11-07-10 03:28 leves Status new => resolved
11-07-10 03:28 leves Fixed in Version  => 4.1
11-07-10 03:28 leves Resolution open => fixed
11-07-10 03:28 leves Assigned To  => leves
11-07-10 03:28 leves Note Added: 0013914
02-06-11 23:48 leves Status resolved => closed


Mantis 1.0.8[^]
Copyright © 2000 - 2007 Mantis Group
66 total queries executed.
40 unique queries executed.
Powered by Mantis Bugtracker