Mantis Bugtracker
  

Viewing Issue Simple Details Jump to Notes ] View Advanced ] Issue History ] Print ]
ID Category Severity Reproducibility Date Submitted Last Update
0006348 [Squeak] Kernel major always 03-18-07 14:11 02-06-11 23:48
Reporter loewis View Status public  
Assigned To leves
Priority normal Resolution fixed  
Status closed   Product Version 3.9
Summary 0006348: [FIX] Improve performance of weak key dictionaries
Description 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.
Additional Information
Attached Files  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
 weakfix2.zip [^] (7,813 bytes) 03-28-07 10:16
 WeakKeyDictionaryTest.st [^] (1,377 bytes) 04-15-07 20:04
 MessageTallyWithAndWithoutTheFIX.txt [^] (26,201 bytes) 07-18-07 13:30

- Relationships
related to 0002910closed leves WeakKeyDictionary performance improvement 

- Notes
(0010468 - 84 - 84 - 84 - 84 - 84 - 84)
loewis
03-28-07 10:16

Uploaded new version, which fixes a problem when growing dictionaries with nil keys.
 
(0010547 - 161 - 179 - 413 - 413 - 413 - 413)
edgardec
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
http://wiki.squeak.org/squeak/5975 [^]
ttp://wiki.squeak.org/squeak/5976 [^]
 
(0010551 - 219 - 255 - 255 - 255 - 255 - 255)
loewis
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

and

WeakKeyDictionaryTest timingMany
 
(0010558 - 444 - 520 - 520 - 520 - 520 - 520)
edgardec
04-16-07 11:38
edited on: 04-16-07 12: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

 
(0010891 - 527 - 557 - 557 - 557 - 557 - 557)
fminjat
07-18-07 13:31
edited on: 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.

 
(0011177 - 239 - 257 - 385 - 385 - 385 - 385)
sig
09-21-07 07:17

Please review my 'hack' of weak registry.
http://bugs.squeak.org/view.php?id=6652 [^]
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.
 
(0013942 - 227 - 227 - 227 - 227 - 227 - 227)
leves
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.
 

- Issue History
Date Modified Username Field Change
03-18-07 14:11 loewis New Issue
03-18-07 14:11 loewis File Added: weakdictall.2.cs
03-18-07 14:12 loewis File Added: weakfix1.1.cs
03-18-07 14:12 loewis File Added: weakfix2.1.cs
03-18-07 14:13 loewis File Added: weakfix3.1.cs
03-18-07 14:13 loewis File Added: weakfix4.1.cs
03-18-07 16:29 lewis Issue Monitored: lewis
03-19-07 10:02 loewis File Added: license.txt
03-19-07 23:05 lewis Relationship added related to 0002910
03-20-07 23:01 loewis Issue Monitored: loewis
03-28-07 10:16 loewis Note Added: 0010468
03-28-07 10:16 loewis File Added: weakfix2.zip
04-15-07 10:01 edgardec Note Added: 0010547
04-15-07 20:04 loewis File Added: WeakKeyDictionaryTest.st
04-15-07 20:05 loewis Note Added: 0010551
04-16-07 11:38 edgardec Note Added: 0010558
04-16-07 12:38 edgardec Note Edited: 0010558
07-18-07 13:30 fminjat File Added: MessageTallyWithAndWithoutTheFIX.txt
07-18-07 13:31 fminjat Note Added: 0010891
07-18-07 13:31 fminjat Note Edited: 0010891
09-21-07 07:17 sig Note Added: 0011177
11-23-10 09:04 leves Status new => resolved
11-23-10 09:04 leves Fixed in Version  => 4.1
11-23-10 09:04 leves Resolution open => fixed
11-23-10 09:04 leves Assigned To  => leves
11-23-10 09:04 leves Note Added: 0013942
02-06-11 23:48 leves Status resolved => closed


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