Computational complexity of become: and becomeForward:

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Computational complexity of become: and becomeForward:

Mateusz Grotek
Dear Squeakers,
What is the computational complexity of become: and becomeForward:?
Best wishes,
Mateusz
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Computational complexity of become: and becomeForward:

Levente Uzonyi-2
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
> [hidden email]
> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Computational complexity of become: and becomeForward:

Levente Uzonyi-2
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
>> [hidden email]
>> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://lists.squeakfoundation.org/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: [SPAM] Re: [Newbies] Computational complexity of become: and becomeForward:

Mateusz Grotek
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 mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners