Dear Squeakers, What is the computational complexity of become: and becomeForward:? Best wishes, Mateusz
On Wed, 26 Sep 2012, Mateusz Grotek wrote:
Dear Squeakers, What is the computational complexity of become: and becomeForward:?
Both of those methods use primitives which scan the whole objectMemory. So it's O(the number of all objects in the image).
Levente
Best wishes, Mateusz _______________________________________________ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
I forgot to mention that in Smalltalks which have an object table, the cost of these methods is O(1). Igor had a proposal to add support for O(1) cost versions of these methods by using relay objects, but it doesn't work well with compact classes and it would use up the last free bit in the object header. I think the conclusion was that only the new object format will support it. In some edge cases [1] you can use #copyFrom: instead of #becomeForward:. The former has O(1) runtime cost.
Levente
[1] The argument must have the same class and the same number of slots as the receiver. If there are objects which point to the argument already, then those will keep pointing the same object - which will be different than the receiver, so changes done to the argument after #copyFrom: won't affect the receiver and vica versa.
On Wed, 26 Sep 2012, Levente Uzonyi wrote:
On Wed, 26 Sep 2012, Mateusz Grotek wrote:
Dear Squeakers, What is the computational complexity of become: and becomeForward:?
Both of those methods use primitives which scan the whole objectMemory. So it's O(the number of all objects in the image).
Levente
Best wishes, Mateusz _______________________________________________ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Levente Uzonyi pisze:
I forgot to mention that in Smalltalks which have an object table, the cost of these methods is O(1). Igor had a proposal to add support for O(1) cost versions of these methods by using relay objects, but it doesn't work well with compact classes and it would use up the last free bit in the object header. I think the conclusion was that only the new object format will support it. In some edge cases [1] you can use #copyFrom: instead of #becomeForward:. The former has O(1) runtime cost.
Levente
[1] The argument must have the same class and the same number of slots as the receiver. If there are objects which point to the argument already, then those will keep pointing the same object - which will be different than the receiver, so changes done to the argument after #copyFrom: won't affect the receiver and vica versa.
Thank you very much for a very comprehensive answer!
beginners@lists.squeakfoundation.org
-
Levente Uzonyi -
Mateusz Grotek