De como alguna vez se hicieron las cosas FW: [Squeak 0006348]: [FIX] Improve performance of weak key dictionaries

Esto me llego hoy originado en Mantis, el sistema que algunos usamos alguna
vez

Es simplemente para mostrar a los detractores y a los Pharopatas que alguna
vez las cosas se hicieron bien.

Hoy tenemos el KAOS y no esta mas Maxwell Smart para defendernos.

Lo bueno es que el comando lo tiene alguien que merece todo el apoyo y
admiración ,

Chris Muller, un chico que promete y de quien esperamos grandes cosas

------ Forwarded Message
From: <[hidden email]>
Date: Sun, 6 Feb 2011 23:48:09 +0000
To: <[hidden email]>
Subject: [Squeak 0006348]: [FIX] Improve performance of weak key
dictionaries


The following issue has been CLOSED
======================================================================
http://bugs.squeak.org/view.php?id=6348
======================================================================
Reported By:                loewis
Assigned To:                leves
======================================================================
Project:                    Squeak
Issue ID:                   6348
Category:                   Kernel
Reproducibility:            always
Severity:                   major
Priority:                   normal
Status:                     closed
Resolution:                 fixed
Fixed in Version:           4.1
======================================================================
Date Submitted:             03-18-2007 14:11 UTC
Last Modified:              02-06-2011 23:48 UTC
======================================================================
Summary:                    [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.
======================================================================
Relationships       ID      Summary
----------------------------------------------------------------------
related to          0002910 WeakKeyDictionary performance improvement
======================================================================

----------------------------------------------------------------------
 loewis - 03-28-07 10:16
----------------------------------------------------------------------
Uploaded new version, which fixes a problem when growing dictionaries with
nil keys.

----------------------------------------------------------------------
 edgardec - 04-15-07 10:01
----------------------------------------------------------------------
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

----------------------------------------------------------------------
 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

----------------------------------------------------------------------
 edgardec - 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

 

----------------------------------------------------------------------
 fminjat - 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.

 

----------------------------------------------------------------------
 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.

----------------------------------------------------------------------
 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
======================================================================


------ End of Forwarded Message