[Pharo-project] New problem with rehash [WAS] Re: MethodDictionary fast #rehash
Hi. With this latest new #rehash there is a problem. I took Levente changes from Squeak. @Levente: the same happens in squeak so this may interest you. The #rehash is right now rehash | newInstance | newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" 1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ]. self copyFrom: newInstance The problem is that #new: does: new: numberOfElements "Create an instance large enough to hold numberOfElements without growing. Note that the basic size must be a power of 2. It is VITAL (see grow) that size gets doubled if numberOfElements is a power of 2" | size | size := self sizeFor: numberOfElements. ^(self basicNew: size) initialize: size And #sizeFor: does: sizeFor: numberOfElements "Return the minimum capacity of a dictionary that can hold numberOfElements elements. At least 25% of the array must be empty and the return value must be a power of 2." ^1 bitShift: (numberOfElements * 4 // 3) highBit So....the problem is that you always increase the size of the MD. So when you do: newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" if fact you are creating a MD of a different size, which means that the capacity is different and hence, using #copyFrom: will create inconsisten MD loosing methods, which causes the crash now. You could add a newInstance capacity = self capacity ifTrue: [ self copyFrom: newInstance ] ifFalse: [ self becomeForward: newInstance ] but that doesn't make sense because you always increase, so you will end up using always the become. I guess you can change to this: newInstance := self species new: self size. "Make sure it has the same capacity" but the problem is if in the future we change again #sizeFor. So....I think a correct solution could be something like this: newInstance := (self species basicNew: self basicSize) initialize: self basicSize. "Make sure it has the same capacity" or..move that to MethodDict class side and do: newInstance := (self species newWithExactBasicSize: self basicSize) "Make sure it has the same capacity" newWithExactBasicSize: basicSize ^(self basicNew: basicSize) initialize: basicSize what do you think ? Cheers On Sun, Sep 18, 2011 at 8:13 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
On Sun, Sep 18, 2011 at 5:40 PM, Nicolas Cellier < nicolas.cellier.aka.nice@gmail.com> wrote:
I'm not quite sure it is correct. The problem is if another Process want to use this MethodDictionary while it is in an inconsistent state... Or if you are rehashing on of the MethodDictionary which contains one of the methods used by the rehashing itself.
Interesting. Thanks Nicolas for the pointer.
See recent changes from Levente in trunk.
heheheheh it seems Levente is still reading the Pharo mailing list. So...I took his commits of today, and I have made a Pharo change set. I have put all the information here: http://code.google.com/p/pharo/issues/detail?id=4826
Basically, he used #copyFrom: which is primitive and hence it avoids the inconsistent state.
If someone can check the changeset and give the OK, we can integrate it.
Thanks a lot
Nicolas
2011/9/17 Mariano Martinez Peck <marianopeck@gmail.com>:
On Sat, Sep 17, 2011 at 10:26 PM, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
2011/9/17 Mariano Martinez Peck <marianopeck@gmail.com>:
Hi guys. I was checking MethodDictionary >> rehash and this is
terribly
slow because of the #become. Then I saw #rehashWithoutBecome but it answers a different instance. I need a #rehash that does the rehash in the real object and answers self. So...I need the regular #rehash but I want to avoid the #become. Is that possible somehow?
This is the current implementation:
rehashWithoutBecome
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" 1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ]. ^newInstance
I am terrible bad with Collection and friends, but cannot we do soemthing like this:
rehashWithoutBecome
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity"
1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ].
1 to: newInstance basicSize do: [ :index | (newInstance basicAt: index) ifNotNil: [ :key | self at: key put: (newInstance array at: index) ] ].
^ self
I guess you should at least also copy the nil entries... Maybe something like
1 to: newInstance basicSize do: [ :index | self basicAt: index put: (newInstance basicAt: index). array at: index put: (newInstance array at: index)].
Good point. So....I was not that mistaken ;) I have just replaced CompiledMethod >> hash with this new method and at least all the tests in MethodDictionaryTest are green. Do you think this implementation is correct or there can be problems? because it is really MUCH faster than the original one.
Thanks in advance
Thanks for any help.
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Tue, 27 Sep 2011, Mariano Martinez Peck wrote:
Hi. With this latest new #rehash there is a problem. I took Levente changes from Squeak. @Levente: the same happens in squeak so this may interest you.
The #rehash is right now
rehash
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" 1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ]. self copyFrom: newInstance
The problem is that #new: does:
new: numberOfElements "Create an instance large enough to hold numberOfElements without growing. Note that the basic size must be a power of 2. It is VITAL (see grow) that size gets doubled if numberOfElements is a power of 2"
| size | size := self sizeFor: numberOfElements. ^(self basicNew: size) initialize: size
And #sizeFor: does:
sizeFor: numberOfElements "Return the minimum capacity of a dictionary that can hold numberOfElements elements. At least 25% of the array must be empty and the return value must be a power of 2."
^1 bitShift: (numberOfElements * 4 // 3) highBit
So....the problem is that you always increase the size of the MD. So when you do: newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" if fact you are creating a MD of a different size, which means that the capacity is different and hence, using #copyFrom: will create inconsisten MD loosing methods, which causes the crash now.
You could add a
newInstance capacity = self capacity ifTrue: [ self copyFrom: newInstance ] ifFalse: [ self becomeForward: newInstance ]
but that doesn't make sense because you always increase, so you will end up using always the become.
I guess you can change to this:
newInstance := self species new: self size. "Make sure it has the same capacity"
but the problem is if in the future we change again #sizeFor.
So....I think a correct solution could be something like this:
newInstance := (self species basicNew: self basicSize) initialize: self basicSize. "Make sure it has the same capacity"
or..move that to MethodDict class side and do:
newInstance := (self species newWithExactBasicSize: self basicSize) "Make sure it has the same capacity"
newWithExactBasicSize: basicSize
^(self basicNew: basicSize) initialize: basicSize
what do you think ?
Nice find. I think your last suggestion is the way to go, though I'd call the method #newWithCapacity: instead of #newWithExactBasicSize:. Levente
Cheers
On Sun, Sep 18, 2011 at 8:13 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
On Sun, Sep 18, 2011 at 5:40 PM, Nicolas Cellier < nicolas.cellier.aka.nice@gmail.com> wrote:
I'm not quite sure it is correct. The problem is if another Process want to use this MethodDictionary while it is in an inconsistent state... Or if you are rehashing on of the MethodDictionary which contains one of the methods used by the rehashing itself.
Interesting. Thanks Nicolas for the pointer.
See recent changes from Levente in trunk.
heheheheh it seems Levente is still reading the Pharo mailing list. So...I took his commits of today, and I have made a Pharo change set. I have put all the information here: http://code.google.com/p/pharo/issues/detail?id=4826
Basically, he used #copyFrom: which is primitive and hence it avoids the inconsistent state.
If someone can check the changeset and give the OK, we can integrate it.
Thanks a lot
Nicolas
2011/9/17 Mariano Martinez Peck <marianopeck@gmail.com>:
On Sat, Sep 17, 2011 at 10:26 PM, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
2011/9/17 Mariano Martinez Peck <marianopeck@gmail.com>:
Hi guys. I was checking MethodDictionary >> rehash and this is
terribly
slow because of the #become. Then I saw #rehashWithoutBecome but it answers a different instance. I need a #rehash that does the rehash in the real object and answers self. So...I need the regular #rehash but I want to avoid the #become. Is that possible somehow?
This is the current implementation:
rehashWithoutBecome
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" 1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ]. ^newInstance
I am terrible bad with Collection and friends, but cannot we do soemthing like this:
rehashWithoutBecome
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity"
1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ].
1 to: newInstance basicSize do: [ :index | (newInstance basicAt: index) ifNotNil: [ :key | self at: key put: (newInstance array at: index) ] ].
^ self
I guess you should at least also copy the nil entries... Maybe something like
1 to: newInstance basicSize do: [ :index | self basicAt: index put: (newInstance basicAt: index). array at: index put: (newInstance array at: index)].
Good point. So....I was not that mistaken ;) I have just replaced CompiledMethod >> hash with this new method and at least all the tests in MethodDictionaryTest are green. Do you think this implementation is correct or there can be problems? because it is really MUCH faster than the original one.
Thanks in advance
Thanks for any help.
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
On Tue, Sep 27, 2011 at 5:18 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Tue, 27 Sep 2011, Mariano Martinez Peck wrote:
Hi. With this latest new #rehash there is a problem. I took Levente
changes from Squeak. @Levente: the same happens in squeak so this may interest you.
The #rehash is right now
rehash
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" 1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ]. self copyFrom: newInstance
The problem is that #new: does:
new: numberOfElements "Create an instance large enough to hold numberOfElements without growing. Note that the basic size must be a power of 2. It is VITAL (see grow) that size gets doubled if numberOfElements is a power of 2"
| size | size := self sizeFor: numberOfElements. ^(self basicNew: size) initialize: size
And #sizeFor: does:
sizeFor: numberOfElements "Return the minimum capacity of a dictionary that can hold numberOfElements elements. At least 25% of the array must be empty and the return value must be a power of 2."
^1 bitShift: (numberOfElements * 4 // 3) highBit
So....the problem is that you always increase the size of the MD. So when you do: newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" if fact you are creating a MD of a different size, which means that the capacity is different and hence, using #copyFrom: will create inconsisten MD loosing methods, which causes the crash now.
You could add a
newInstance capacity = self capacity ifTrue: [ self copyFrom: newInstance ] ifFalse: [ self becomeForward: newInstance ]
but that doesn't make sense because you always increase, so you will end up using always the become.
I guess you can change to this:
newInstance := self species new: self size. "Make sure it has the same capacity"
but the problem is if in the future we change again #sizeFor.
So....I think a correct solution could be something like this:
newInstance := (self species basicNew: self basicSize) initialize: self basicSize. "Make sure it has the same capacity"
or..move that to MethodDict class side and do:
newInstance := (self species newWithExactBasicSize: self basicSize) "Make sure it has the same capacity"
newWithExactBasicSize: basicSize
^(self basicNew: basicSize) initialize: basicSize
what do you think ?
Nice find. I think your last suggestion is the way to go, though I'd call the method #newWithCapacity: instead of #newWithExactBasicSize:.
Thanks, I also think the better solution is the last one. Ok, I will take the suggestion of #newWithCapacity: Now...what I am not sure is whether we could have this problem in another place apart from #rehash:. For example, what about #removeAll: ? If you can help me with that... Cheers!
Levente
Cheers
On Sun, Sep 18, 2011 at 8:13 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
On Sun, Sep 18, 2011 at 5:40 PM, Nicolas Cellier < nicolas.cellier.aka.nice@**gmail.com<nicolas.cellier.aka.nice@gmail.com>> wrote:
I'm not quite sure it is correct.
The problem is if another Process want to use this MethodDictionary while it is in an inconsistent state... Or if you are rehashing on of the MethodDictionary which contains one of the methods used by the rehashing itself.
Interesting. Thanks Nicolas for the pointer.
See recent changes from Levente in trunk.
heheheheh it seems Levente is still reading the Pharo mailing list.
So...I took his commits of today, and I have made a Pharo change set. I have put all the information here: http://code.google.com/p/**pharo/issues/detail?id=4826<http://code.google.com/p/pharo/issues/detail?id=4826>
Basically, he used #copyFrom: which is primitive and hence it avoids the inconsistent state.
If someone can check the changeset and give the OK, we can integrate it.
Thanks a lot
Nicolas
2011/9/17 Mariano Martinez Peck <marianopeck@gmail.com>:
On Sat, Sep 17, 2011 at 10:26 PM, Nicolas Cellier <nicolas.cellier.aka.nice@**gmail.com<nicolas.cellier.aka.nice@gmail.com>> wrote:
2011/9/17 Mariano Martinez Peck <marianopeck@gmail.com>:
Hi guys. I was checking MethodDictionary >> rehash and this is
terribly
slow
because of the #become. Then I saw #rehashWithoutBecome but it
answers
a
different instance. I need a #rehash that does the rehash in the real object and answers self. So...I need the regular #rehash but I want to avoid the #become. Is that possible somehow?
This is the current implementation:
rehashWithoutBecome
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure
it
has
the same capacity" 1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ]. ^newInstance
I am terrible bad with Collection and friends, but cannot we do soemthing like this:
rehashWithoutBecome
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure
it
has
the same capacity"
1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ].
1 to: newInstance basicSize do: [ :index | (newInstance basicAt: index) ifNotNil: [ :key | self at: key put: (newInstance array at: index) ] ].
^ self
I guess you should at least also copy the nil entries... Maybe something like
1 to: newInstance basicSize do: [ :index | self basicAt: index put: (newInstance basicAt: index). array at: index put: (newInstance array at: index)].
Good point. So....I was not that mistaken ;) I have just replaced CompiledMethod >> hash with this new method and at least all the tests in MethodDictionaryTest are green. Do you think this implementation is correct or there can be problems? because it is really MUCH faster than the original one.
Thanks in advance
Thanks for any help.
-- Mariano http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
On Tue, Sep 27, 2011 at 5:28 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
On Tue, Sep 27, 2011 at 5:18 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Tue, 27 Sep 2011, Mariano Martinez Peck wrote:
Hi. With this latest new #rehash there is a problem. I took Levente
changes from Squeak. @Levente: the same happens in squeak so this may interest you.
The #rehash is right now
rehash
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" 1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ]. self copyFrom: newInstance
The problem is that #new: does:
new: numberOfElements "Create an instance large enough to hold numberOfElements without growing. Note that the basic size must be a power of 2. It is VITAL (see grow) that size gets doubled if numberOfElements is a power of 2"
| size | size := self sizeFor: numberOfElements. ^(self basicNew: size) initialize: size
And #sizeFor: does:
sizeFor: numberOfElements "Return the minimum capacity of a dictionary that can hold numberOfElements elements. At least 25% of the array must be empty and the return value must be a power of 2."
^1 bitShift: (numberOfElements * 4 // 3) highBit
So....the problem is that you always increase the size of the MD. So when you do: newInstance := self species new: self basicSize - 1. "Make sure it has the same capacity" if fact you are creating a MD of a different size, which means that the capacity is different and hence, using #copyFrom: will create inconsisten MD loosing methods, which causes the crash now.
You could add a
newInstance capacity = self capacity ifTrue: [ self copyFrom: newInstance ] ifFalse: [ self becomeForward: newInstance ]
but that doesn't make sense because you always increase, so you will end up using always the become.
I guess you can change to this:
newInstance := self species new: self size. "Make sure it has the same capacity"
but the problem is if in the future we change again #sizeFor.
So....I think a correct solution could be something like this:
newInstance := (self species basicNew: self basicSize) initialize: self basicSize. "Make sure it has the same capacity"
or..move that to MethodDict class side and do:
newInstance := (self species newWithExactBasicSize: self basicSize) "Make sure it has the same capacity"
newWithExactBasicSize: basicSize
^(self basicNew: basicSize) initialize: basicSize
what do you think ?
Nice find. I think your last suggestion is the way to go, though I'd call the method #newWithCapacity: instead of #newWithExactBasicSize:.
Thanks, I also think the better solution is the last one. Ok, I will take the suggestion of #newWithCapacity: Now...what I am not sure is whether we could have this problem in another place apart from #rehash:. For example, what about #removeAll: ?
Wel...#removeAll: is not necessary because even if you would do a copyFrom: from a bigger object to an smaller one it is not a problem because they are all empty and the result of the object will be the smaller of the two... Anyway, I think it is clearer if I use newWithCapacity: here as well. Ahhh and it was funny why the tests didn't show up this bug: testRehashPreservesCapacity | oldDictionary rehashedDictionary | oldDictionary := self modifiedMethodDictionaryCopy. rehashedDictionary := oldDictionary copy; rehash; yourself. self assertPreservesCapacity: oldDictionary comparedTo: rehashedDictionary. and testRehashPreservesElements | oldDictionary rehashedDictionary | oldDictionary := self modifiedMethodDictionaryCopy. rehashedDictionary := oldDictionary copy; rehash; yourself. self assertPreservesElements: oldDictionary comparedTo: rehashedDictionary. self assertPreservesElements: rehashedDictionary comparedTo: oldDictionary. They were testing against the SAME instance hehhehehe. I have just fix them as well. Cheers
If you can help me with that...
Cheers!
Levente
Cheers
On Sun, Sep 18, 2011 at 8:13 PM, Mariano Martinez Peck < marianopeck@gmail.com> wrote:
On Sun, Sep 18, 2011 at 5:40 PM, Nicolas Cellier < nicolas.cellier.aka.nice@**gmail.com<nicolas.cellier.aka.nice@gmail.com>> wrote:
I'm not quite sure it is correct.
The problem is if another Process want to use this MethodDictionary while it is in an inconsistent state... Or if you are rehashing on of the MethodDictionary which contains one of the methods used by the rehashing itself.
Interesting. Thanks Nicolas for the pointer.
See recent changes from Levente in trunk.
heheheheh it seems Levente is still reading the Pharo mailing list.
So...I took his commits of today, and I have made a Pharo change set. I have put all the information here: http://code.google.com/p/**pharo/issues/detail?id=4826<http://code.google.com/p/pharo/issues/detail?id=4826>
Basically, he used #copyFrom: which is primitive and hence it avoids the inconsistent state.
If someone can check the changeset and give the OK, we can integrate it.
Thanks a lot
Nicolas
2011/9/17 Mariano Martinez Peck <marianopeck@gmail.com>:
On Sat, Sep 17, 2011 at 10:26 PM, Nicolas Cellier <nicolas.cellier.aka.nice@**gmail.com<nicolas.cellier.aka.nice@gmail.com>> wrote:
2011/9/17 Mariano Martinez Peck <marianopeck@gmail.com>:
Hi guys. I was checking MethodDictionary >> rehash and this is
terribly
slow
because of the #become. Then I saw #rehashWithoutBecome but it
answers
a
different instance. I need a #rehash that does the rehash in the real object and answers self. So...I need the regular #rehash but I want to avoid the #become. Is that possible somehow?
This is the current implementation:
rehashWithoutBecome
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure
it
has
the same capacity" 1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ]. ^newInstance
I am terrible bad with Collection and friends, but cannot we do soemthing like this:
rehashWithoutBecome
| newInstance | newInstance := self species new: self basicSize - 1. "Make sure
it
has
the same capacity"
1 to: self basicSize do: [ :index | (self basicAt: index) ifNotNil: [ :key | newInstance at: key put: (array at: index) ] ].
1 to: newInstance basicSize do: [ :index | (newInstance basicAt: index) ifNotNil: [ :key | self at: key put: (newInstance array at: index) ] ].
^ self
I guess you should at least also copy the nil entries... Maybe something like
1 to: newInstance basicSize do: [ :index | self basicAt: index put: (newInstance basicAt: index). array at: index put: (newInstance array at: index)].
Good point. So....I was not that mistaken ;) I have just replaced CompiledMethod >> hash with this new method and at least all the tests in MethodDictionaryTest are green. Do you think this implementation is correct or there can be problems? because it is really MUCH faster than the original one.
Thanks in advance
Thanks for any help.
-- Mariano http://marianopeck.wordpress.**com<http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.**com <http://marianopeck.wordpress.com>
-- Mariano http://marianopeck.wordpress.com
-- Mariano http://marianopeck.wordpress.com
participants (2)
-
Levente Uzonyi -
Mariano Martinez Peck