Re: [Pharo-project] Another fixes to finalization (was Re: [update 1.2] #12161 - #12172)
so let us know in the bug entry what is the conclusion :)
On 2 October 2010 19:47, Stéphane Ducasse<stephane.ducasse@inria.fr>
wrote:
Hi igor
do you understand why the previous definition was
cachedDefinitions Definitions ifNil: [Definitions := WeakIdentityKeyDictionary new. WeakArray addWeakDependent: Definitions]. ^ Definitions
i don't. :)
It just a way to free memory as fast as possible. But its really not worth spending so much CPU in order to save few bytes of memory.
Without registering the dict for finalization, the values won't ever be removed with the current implementation.
They are removed. After each package load/unload operation. I don't see a reason to do this more often.
If they are removed explicitly, then yes. But then again, if that's the case, why use a weak dictionary in the first place?
i don't know much about MC to tell for sure.
Which can be somewhat hampering to performance once you have lots of nil-keyed elements all stashed from index 1 and onwards after a rehash.
In Pharo, weak dict knows how to reuse expired associations:
And when do they expire? Only when they are either finalized, or removed explicitly. So if you do neither, they will stay indefinately without being removed/reused.
no. they expiring when key become nil.
You'd think so, yes. However, see implementor of WeakKeyAssociation>>#expired, and senders of #expire.
Oh, you are right. They are not reused unless marked as expired (associatin's value == association). But concerning speed, then my benchmark should show an opposite results. :)
cache holding a pairs of: compiledmethod -> MCMethodDefinitions.
Compiled methods usually gone when you either recompiling class or removing it from system. This is why i put #finalizeValues after package loading/unloading. But if you think it worth adding it into some other places, then tell me where. Still, putting it into FinalizationDependents is bad idea.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig.
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On 4 October 2010 22:09, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e. [ self loadsomething ] timeToRun before and after patch. And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :)
On 2 October 2010 19:47, Stéphane Ducasse<stephane.ducasse@inria.fr>
 wrote:
Hi igor
do you understand why the previous definition was
cachedDefinitions     Definitions ifNil: [Definitions := WeakIdentityKeyDictionary new.  WeakArray addWeakDependent: Definitions].     ^ Definitions
i don't. :)
It just a way to free memory as fast as possible. But its really not worth spending so much CPU in order to save few bytes of memory.
Without registering the dict for finalization, the values won't ever be removed with the current implementation.
They are removed. After each package load/unload operation. I don't see a reason to do this more often.
If they are removed explicitly, then yes. But then again, if that's the case, why use a weak dictionary in the first place?
i don't know much about MC to tell for sure.
Which can be somewhat hampering to performance once you have lots of nil-keyed elements all stashed from index 1 and onwards after a rehash.
In Pharo, weak dict knows how to reuse expired associations:
And when do they expire? Only when they are either finalized, or removed explicitly. So if you do neither, they will stay indefinately without being removed/reused.
no. they expiring when key become nil.
You'd think so, yes. However, see implementor of WeakKeyAssociation>>#expired, and senders of #expire.
Oh, you are right. They are not reused unless marked as expired (associatin's value == association). But concerning speed, then my benchmark should show an opposite results. :)
cache holding a pairs of: compiledmethod -> MCMethodDefinitions.
Compiled methods usually gone when you either recompiling class or removing it from system. This is why i put #finalizeValues after package loading/unloading. But if you think it worth adding it into some other places, then tell me where. Still, putting it into FinalizationDependents is bad idea.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig.
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig.
On 04.10.2010 21:47, Igor Stasenko wrote:
On 4 October 2010 22:09, Stéphane Ducasse<stephane.ducasse@inria.fr> wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e.
[ self loadsomething ] timeToRun
before and after patch.
And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :) I already have:
http://code.google.com/p/pharo/issues/detail?id=1628#c13 Cheers, Henry
On 4 October 2010 22:51, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote:
 On 04.10.2010 21:47, Igor Stasenko wrote:
On 4 October 2010 22:09, Stéphane Ducasse<stephane.ducasse@inria.fr>  wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e.
[ self loadsomething ] timeToRun
before and after patch.
And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :)
I already have:
emm.. wait. WeakKeyDict should not delete associations with nil-ed keys automatically, because otherwise you won't be able to use it in weak finalization scheme. There is two distinct use cases of weak-key dicts: a) for weak finalization b) for attaching some extra info(value) per object(key), which can be automatically discarded once object become garbage so, while in case (b) you can mercilessly kill/reuse associations with nil keys, once they discovered in case (a) you should preserve them until there is explicit request from outside to finalize values. The need in (a), apparently prohibits from using (b) in most efficient manner. So, i think, the solution would be to introduce a specialized weak-key dicts, which can work much better for (b).
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig.
On Mon, 4 Oct 2010, Igor Stasenko wrote:
On 4 October 2010 22:51, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote: Â On 04.10.2010 21:47, Igor Stasenko wrote:
On 4 October 2010 22:09, Stéphane Ducasse<stephane.ducasse@inria.fr>  wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e.
[ self loadsomething ] timeToRun
before and after patch.
And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :)
I already have:
emm.. wait. WeakKeyDict should not delete associations with nil-ed keys automatically, because otherwise you won't be able to use it in weak finalization scheme. There is two distinct use cases of weak-key dicts: a) for weak finalization b) for attaching some extra info(value) per object(key), which can be automatically discarded once object become garbage so, while in case (b) you can mercilessly kill/reuse associations with nil keys, once they discovered in case (a) you should preserve them until there is explicit request from outside to finalize values. The need in (a), apparently prohibits from using (b) in most efficient manner. So, i think, the solution would be to introduce a specialized weak-key dicts, which can work much better for (b). Squeak's implementation works well in both cases. Levente
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On 04.10.2010 22:26, Levente Uzonyi wrote:
On Mon, 4 Oct 2010, Igor Stasenko wrote:
On 4 October 2010 22:51, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote: On 04.10.2010 21:47, Igor Stasenko wrote:
On 4 October 2010 22:09, Stéphane Ducasse<stephane.ducasse@inria.fr> wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e.
[ self loadsomething ] timeToRun
before and after patch.
And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :)
I already have:
emm.. wait. WeakKeyDict should not delete associations with nil-ed keys automatically, because otherwise you won't be able to use it in weak finalization scheme. It could in 1.0, without anyone noticing. #rehash truncated duplicate nil keys, thus if it was triggered (f.ex. by a manual removal, or adding enough to cause growth) in a thread with priority higher than finalization process (ie ran after GC but before finalization thread), the nil keys could be truncated before finalization being run. An unlikely scenario, I admit, which I guess is why noone encountered it. #grow suffered the same problem. (well, actually, it didn't add any of the nil keyed associations)
There is two distinct use cases of weak-key dicts: a) for weak finalization b) for attaching some extra info(value) per object(key), which can be automatically discarded once object become garbage
so, while in case (b) you can mercilessly kill/reuse associations with nil keys, once they discovered in case (a) you should preserve them until there is explicit request from outside to finalize values. Yes, that's the point I've been trying to make these past couple of months :)
The need in (a), apparently prohibits from using (b) in most efficient manner. So, i think, the solution would be to introduce a specialized weak-key dicts, which can work much better for (b). The difference between a and b, and the fact Pharo 1.1's implementation severly screws with the performance if b) (and honestly, isn't that good for a) either) is the point I've been trying to make for months now...
In Pharo 1.1 we've moved to the other extreme compared to 1.0, nil keys are never removed. b) always works, but a) HAS to be registered to work satisfactory at all. It was changed to do an extra step of keeping finalized assocs in a special state where they can be simply replaced without rehashing after finalization instead of doing rehash, but that's not really the major result of the change.
Squeak's implementation works well in both cases.
Levente
The way I read it (correct me if I'm wrong), the solution in Squeak was adding a finalizer inst var to WeakKeyDictionary, that way you can distinguish the two cases and handle them appropriately. (in addition there were speed improvements for rehashing, growing, etc.) I looked for another solution which would keep WeakKeyDictionary oblivious to whether or not it was being finalized or not and could not find one, thus I think it is worth porting. Keeping the (pardon my fren.. err, norwegian) POS that is currectly in 1.1, or reverting to the 1.0 version for 1.2, is not a good alternative. Cheers, Henry
Sorry for the duplications in last mail, there comes a point where I just think "screw it", stop editing, and just press send :) Cheers, Henry
On Mon, 4 Oct 2010, Henrik Sperre Johansen wrote:
On 04.10.2010 22:26, Levente Uzonyi wrote:
On Mon, 4 Oct 2010, Igor Stasenko wrote:
On 4 October 2010 22:51, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote: On 04.10.2010 21:47, Igor Stasenko wrote:
On 4 October 2010 22:09, Stéphane Ducasse<stephane.ducasse@inria.fr> wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e.
[ self loadsomething ] timeToRun
before and after patch.
And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :)
I already have:
emm.. wait. WeakKeyDict should not delete associations with nil-ed keys automatically, because otherwise you won't be able to use it in weak finalization scheme. It could in 1.0, without anyone noticing. #rehash truncated duplicate nil keys, thus if it was triggered (f.ex. by a manual removal, or adding enough to cause growth) in a thread with priority higher than finalization process (ie ran after GC but before finalization thread), the nil keys could be truncated before finalization being run. An unlikely scenario, I admit, which I guess is why noone encountered it.
That's not true. People experienced the issues (leaking Sockets), but didn't find the cause of the problem, because it was hardly reproducible. Creating a new Socket could trigger #grow in the WeakRegistry's dictionary which could trigger a GC when the new array was allocated. For example ConnectionQueue's #listenLoop uses #highIOPriority (70) and creates new sockets.
#grow suffered the same problem. (well, actually, it didn't add any of the nil keyed associations)
There is two distinct use cases of weak-key dicts: a) for weak finalization b) for attaching some extra info(value) per object(key), which can be automatically discarded once object become garbage
so, while in case (b) you can mercilessly kill/reuse associations with nil keys, once they discovered in case (a) you should preserve them until there is explicit request from outside to finalize values.
Yes, that's the point I've been trying to make these past couple of months :)
The need in (a), apparently prohibits from using (b) in most efficient manner. So, i think, the solution would be to introduce a specialized weak-key dicts, which can work much better for (b).
The difference between a and b, and the fact Pharo 1.1's implementation severly screws with the performance if b) (and honestly, isn't that good for a) either) is the point I've been trying to make for months now...
In Pharo 1.1 we've moved to the other extreme compared to 1.0, nil keys are never removed. b) always works, but a) HAS to be registered to work satisfactory at all.
Um, no. Associations with nil keys are lost during #rehash. objects := (1 to: 1000) collect: [ :each | Object new ]. dictionary := WeakKeyDictionary new. objects do: [ :each | dictionary at: each put: 1 ]. objects := nil. Smalltalk garbageCollect. counter := 0. dictionary allAssociationsDo: [ :each | counter := counter + 1 ]. self assert: counter = 1000. dictionary rehash. counter := 0. dictionary allAssociationsDo: [ :each | counter := counter + 1 ]. self assert: counter = 1000 "This will fail, because counter = 0."
It was changed to do an extra step of keeping finalized assocs in a special state where they can be simply replaced without rehashing after finalization instead of doing rehash, but that's not really the major result of the change.
Squeak's implementation works well in both cases.
Levente
The way I read it (correct me if I'm wrong), the solution in Squeak was adding a finalizer inst var to WeakKeyDictionary, that way you can distinguish the two cases and handle them appropriately. (in addition there were speed improvements for rehashing, growing, etc.)
The original goal of the finalizer was to make finalization run in O(n) time instead of O(n^2). But it's also handy for doing proper finalization. And there are other improvements, like #remove: triggers the finalizer and cleans up the slots in the removed element's "chain". So both addition (via #grow) and removal of elements can free slots held by GC'd keys. The implementation in Pharo 1.1 still has an O(n^2) issue. Not expired associations with nil keys, are added to the front of the array during #grow (see #noCheckAdd:). The free slot for the association is found by a linear search started from the first slot in the array (OMG). If there are k such elements, then it takes k * (k + 1) / 2 = O(k^2) time. Since k can be n if the dictionary is not registered to the finalization process, this means O(n^2) time: objects := (1 to: 10000) collect: [ :each | Object new ]. dictionary := WeakKeyDictionary new. objects do: [ :each | dictionary at: each put: 1 ]. objects := nil. Smalltalk garbageCollect. counter := 0. dictionary allAssociationsDo: [ :each | counter := counter + 1 ]. self assert: counter = 10000. [ dictionary grow ] timeToRun "===> 1830" Levente
I looked for another solution which would keep WeakKeyDictionary oblivious to whether or not it was being finalized or not and could not find one, thus I think it is worth porting. Keeping the (pardon my fren.. err, norwegian) POS that is currectly in 1.1, or reverting to the 1.0 version for 1.2, is not a good alternative.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On 05.10.2010 00:25, Levente Uzonyi wrote:
On Mon, 4 Oct 2010, Henrik Sperre Johansen wrote:
On 04.10.2010 22:26, Levente Uzonyi wrote:
On Mon, 4 Oct 2010, Igor Stasenko wrote:
On 4 October 2010 22:51, Henrik Sperre Johansen <henrik.s.johansen@veloxit.no> wrote: On 04.10.2010 21:47, Igor Stasenko wrote:
On 4 October 2010 22:09, Stéphane Ducasse<stephane.ducasse@inria.fr> wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e.
[ self loadsomething ] timeToRun
before and after patch.
And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :)
I already have:
emm.. wait. WeakKeyDict should not delete associations with nil-ed keys automatically, because otherwise you won't be able to use it in weak finalization scheme. It could in 1.0, without anyone noticing. #rehash truncated duplicate nil keys, thus if it was triggered (f.ex. by a manual removal, or adding enough to cause growth) in a thread with priority higher than finalization process (ie ran after GC but before finalization thread), the nil keys could be truncated before finalization being run. An unlikely scenario, I admit, which I guess is why noone encountered it.
That's not true. People experienced the issues (leaking Sockets), but didn't find the cause of the problem, because it was hardly reproducible. Creating a new Socket could trigger #grow in the WeakRegistry's dictionary which could trigger a GC when the new array was allocated. For example ConnectionQueue's #listenLoop uses #highIOPriority (70) and creates new sockets. Hum, ok. Didn't know that, must've missed a thread or something :)
#grow suffered the same problem. (well, actually, it didn't add any of the nil keyed associations)
There is two distinct use cases of weak-key dicts: a) for weak finalization b) for attaching some extra info(value) per object(key), which can be automatically discarded once object become garbage
so, while in case (b) you can mercilessly kill/reuse associations with nil keys, once they discovered in case (a) you should preserve them until there is explicit request from outside to finalize values.
Yes, that's the point I've been trying to make these past couple of months :)
The need in (a), apparently prohibits from using (b) in most efficient manner. So, i think, the solution would be to introduce a specialized weak-key dicts, which can work much better for (b).
The difference between a and b, and the fact Pharo 1.1's implementation severly screws with the performance if b) (and honestly, isn't that good for a) either) is the point I've been trying to make for months now...
In Pharo 1.1 we've moved to the other extreme compared to 1.0, nil keys are never removed. b) always works, but a) HAS to be registered to work satisfactory at all.
Um, no. Associations with nil keys are lost during #rehash. Whoops, had the impression it was fixed, not sure how I got that. So, in short, the 1.1 implementation keeps the worst aspects of 1.0, and adds a few new ones.
It was changed to do an extra step of keeping finalized assocs in a special state where they can be simply replaced without rehashing after finalization instead of doing rehash, but that's not really the major result of the change.
Squeak's implementation works well in both cases.
Levente
The way I read it (correct me if I'm wrong), the solution in Squeak was adding a finalizer inst var to WeakKeyDictionary, that way you can distinguish the two cases and handle them appropriately. (in addition there were speed improvements for rehashing, growing, etc.)
The original goal of the finalizer was to make finalization run in O(n) time instead of O(n^2). But it's also handy for doing proper finalization. And there are other improvements, like #remove: triggers the finalizer and cleans up the slots in the removed element's "chain". So both addition (via #grow) and removal of elements can free slots held by GC'd keys. <3
The implementation in Pharo 1.1 still has an O(n^2) issue. Not expired associations with nil keys, are added to the front of the array during #grow (see #noCheckAdd:). The free slot for the association is found by a linear search started from the first slot in the array (OMG). If there are k such elements, then it takes k * (k + 1) / 2 = O(k^2) time. Since k can be n if the dictionary is not registered to the finalization process, this means O(n^2) time: Yeah, I've mentioned that before and didn't want to repeat myself ;)
Cheers, Henry
2010/10/4 Levente Uzonyi <leves@elte.hu>:
On Mon, 4 Oct 2010, Igor Stasenko wrote:
On 4 October 2010 22:51, Henrik Sperre Johansen
<henrik.s.johansen@veloxit.no> wrote:
 On 04.10.2010 21:47, Igor Stasenko wrote:
On 4 October 2010 22:09, Stéphane Ducasse<stephane.ducasse@inria.fr>  wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e.
[ self loadsomething ] timeToRun
before and after patch.
And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :)
I already have:
emm.. wait. WeakKeyDict should not delete associations with nil-ed keys automatically, because otherwise you won't be able to use it in weak finalization scheme.
There is two distinct use cases of weak-key dicts: a) for weak finalization b) for attaching some extra info(value) per object(key), which can be automatically discarded once object become garbage
so, while in case (b) you can mercilessly kill/reuse associations with nil keys, once they discovered in case (a) you should preserve them until there is explicit request from outside to finalize values.
The need in (a), apparently prohibits from using (b) in most efficient manner. So, i think, the solution would be to introduce a specialized weak-key dicts, which can work much better for (b).
Squeak's implementation works well in both cases.
Trust me, scanning a whole dict to detect nil keys is not what can be called 'well' :) My point is, that these two scenarios should use different classes/implementors each optimized for own case. Moreover, case (b) comes from the inability to dynamically add extra slot(s) to object, which you can easily do in Self or JavaScript, but can't do in smalltalk.
Levente
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
--
-- Best regards, Igor Stasenko AKA sig.
On Tue, 5 Oct 2010, Igor Stasenko wrote:
2010/10/4 Levente Uzonyi <leves@elte.hu>: On Mon, 4 Oct 2010, Igor Stasenko wrote:
On 4 October 2010 22:51, Henrik Sperre Johansen
<henrik.s.johansen@veloxit.no> wrote:
 On 04.10.2010 21:47, Igor Stasenko wrote:
On 4 October 2010 22:09, Stéphane Ducasse<stephane.ducasse@inria.fr>  wrote:
so let us know in the bug entry what is the conclusion :)
I think someone should verify my benchmarks i.e.
[ self loadsomething ] timeToRun
before and after patch.
And conclusion is better be written by Henrik, because he's having concerns about speed, while i don't. :)
I already have:
emm.. wait. WeakKeyDict should not delete associations with nil-ed keys automatically, because otherwise you won't be able to use it in weak finalization scheme.
There is two distinct use cases of weak-key dicts: a) for weak finalization b) for attaching some extra info(value) per object(key), which can be automatically discarded once object become garbage
so, while in case (b) you can mercilessly kill/reuse associations with nil keys, once they discovered in case (a) you should preserve them until there is explicit request from outside to finalize values.
The need in (a), apparently prohibits from using (b) in most efficient manner. So, i think, the solution would be to introduce a specialized weak-key dicts, which can work much better for (b).
Squeak's implementation works well in both cases.
Trust me, scanning a whole dict to detect nil keys is not what can be called 'well' :) My point is, that these two scenarios should use different classes/implementors each optimized for own case. Moreover, case (b) comes from the inability to dynamically add extra slot(s) to object, which you can easily do in Self or JavaScript, but can't do in smalltalk. It can be done better, with extra VM features, but without those, it's pretty close to best possible solution IMHO. There are already two different classes for a) and b): WeakRegistry and WeakKeyDictionary (and subclasses). Levente
Levente
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
--
-- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
participants (4)
-
Henrik Sperre Johansen -
Igor Stasenko -
Levente Uzonyi -
Stéphane Ducasse