[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