[Newbies] Computational complexity of become: and becomeForward:
Levente Uzonyi
leves at elte.hu
Wed Sep 26 10:23:31 UTC 2012
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 at lists.squeakfoundation.org
>> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>>
> _______________________________________________
> Beginners mailing list
> Beginners at lists.squeakfoundation.org
> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>
More information about the Beginners
mailing list