Smalltalk › Squeak › Squeak VM

A trick to speedup #become: (but not becomeForward:)

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

12 messages Options

Igor Stasenko

A trick to speedup #become: (but not becomeForward:)

An interesting observation:

if two oops which we need to swap: oop1 and oop2 taking exactly same
space in memory,
then all we need to do is to swap their memory contents, instead of
scanning heap and updating pointers!

This makes a become operation extremely cheap for such pairs!
As for objects of different sizes, we could still use slow algorithm.

But knowing that if two objects with same size will be swapped much
faster, a developers could adapt their algorithms to exploit this
feature
(use fixed-size objects instead of variable-sized ones etc).

Magma using proxies, which then #becomeForward: to real objects when reified.
This is very costly operation and main reason why it so slow on
loading objects from server.
To speed thing up, a special trick can be used:
- each time server sends an object ID (instead of real object) it
could also send its size in bytes (or even more clever - you can
encode object size in its ID ;) ).
Then a client will create a proxy for given object and will try to
match the size, if its possible. (nobody said that proxy can't be
variable-sized, right?)

Then once client requesting to reify given proxy with real object from
database, VM will just overwrite a proxy's memory contents with real
object.

--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko

Re: A trick to speedup #become: (but not becomeForward:)

And it works! All become tests are green.
See attached for VM and image side code.

Now most interesting thing. How much speed we gain?

Before:

| x y |

x := 'ab' copy.
y := 'cd' copy.

[ 100 timesRepeat: [ x become: y ] ] timeToRun

1786

After:

| x y |

x := 'ab' copy.
y := 'cd' copy.

[ 1000000 timesRepeat: [ x become: y ] ] timeToRun

82

So,

(1786 / 100) / (82 / 1000000 ) asFloat 217804.8780487805

217'804 times faster!!!!!! :)

But of course there are caveats if objects involved are
compiled method(s) or symbols (selectors).

A check is required and invalidate cache in this case.
For symbols it is harder, since symbols are not special objects.
A cheapest way to workaround it is just
override #become: for Symbol class to always use slow version.
(oh.. btw, same could be done for CompiledMethod(s)).

So, instead of putting heavyweight logic into this new primitive, if
may be better to just override #become: for critical
classes.
And since become is symmetric, we may need to use double-dispatch to
check that none of pair is system-critical object,
otherwise just fallback to slow version.

--
Best regards,
Igor Stasenko AKA sig.

primitive-swapmemorybecome.1.cs (4K) Download Attachment

fastbecome.1.cs (2K) Download Attachment

Andreas.Raab

Re: A trick to speedup #become: (but not becomeForward:)

On 7/31/2011 6:56, Igor Stasenko wrote:
> And it works! All become tests are green.
> See attached for VM and image side code.

Good idea. But your benchmark is a little off:

> Now most interesting thing. How much speed we gain?
>
> Before:
>
> | x y |
>
> x := 'ab' copy.
> y := 'cd' copy.
>
> [ 100 timesRepeat: [ x become: y ] ] timeToRun

x and y should be young in the above and the performance of #become
should be much faster than when they are old. To wit:

[ 100 timesRepeat: [ 'ab' copy become: 'cd' copy ] ] timeToRun
=> 36

| x y |
x := 'ab' copy.
y := 'cd' copy.
Smalltalk garbageCollect. "make x and y old"
[ 100 timesRepeat: [ x become: y ] ] timeToRun
=> 1248

So I'm not sure how valid your benchmark really is.

Cheers,
- Andreas

Igor Stasenko

Re: A trick to speedup #become: (but not becomeForward:)

On 31 July 2011 10:32, Andreas Raab <[hidden email]> wrote:

>
> On 7/31/2011 6:56, Igor Stasenko wrote:
>>
>> And it works! All become tests are green.
>> See attached for VM and image side code.
>
> Good idea. But your benchmark is a little off:
>
>> Now most interesting thing. How much speed we gain?
>>
>> Before:
>>
>> | x y |
>>
>> x := 'ab' copy.
>> y := 'cd' copy.
>>
>> [ 100 timesRepeat: [ x become: y ] ] timeToRun
>
> x and y should be young in the above and the performance of #become should
> be much faster than when they are old. To wit:
>
> [ 100 timesRepeat: [ 'ab' copy become: 'cd' copy ] ] timeToRun
> => 36
>
> | x y |
> x := 'ab' copy.
> y := 'cd' copy.
> Smalltalk garbageCollect. "make x and y old"
> [ 100 timesRepeat: [ x become: y ] ] timeToRun
> => 1248
>
> So I'm not sure how valid your benchmark really is.
>

It is valid, because i comparing performance of using same method (#become:)
before and after changes.
But of course, a heap-scanning become heavily depends where object(s)
located in young space or old one,
and performs much faster if it needs to scan only new space.

But memory-swapping become apparently having no such dependency. It
only depends on object size to be swapped.

So, okay.. for cases, when both objects residing in new space, it will
be not hundrends of thousands times faster but only tens thousands
times. :)
Which is still a huge advantage.

> Cheers,
> - Andreas
>

--
Best regards,
Igor Stasenko AKA sig.

Andreas.Raab

Re: A trick to speedup #become: (but not becomeForward:)

On 7/31/2011 17:06, Igor Stasenko wrote:

>
> On 31 July 2011 10:32, Andreas Raab<[hidden email]> wrote:
>> On 7/31/2011 6:56, Igor Stasenko wrote:
>>> And it works! All become tests are green.
>>> See attached for VM and image side code.
>> Good idea. But your benchmark is a little off:
>>
>>> Now most interesting thing. How much speed we gain?
>>>
>>> Before:
>>>
>>> | x y |
>>>
>>> x := 'ab' copy.
>>> y := 'cd' copy.
>>>
>>> [ 100 timesRepeat: [ x become: y ] ] timeToRun
>> x and y should be young in the above and the performance of #become should
>> be much faster than when they are old. To wit:
>>
>> [ 100 timesRepeat: [ 'ab' copy become: 'cd' copy ] ] timeToRun
>> => 36
>>
>> | x y |
>> x := 'ab' copy.
>> y := 'cd' copy.
>> Smalltalk garbageCollect. "make x and y old"
>> [ 100 timesRepeat: [ x become: y ] ] timeToRun
>> => 1248
>>
>> So I'm not sure how valid your benchmark really is.
>>
> It is valid, because i comparing performance of using same method (#become:)
> before and after changes.

It's important to measure these things correctly, otherwise one cannot
repeat your results. When executing the code as presented, I was
entirely unable to recreate your results, because the code all but
guarantees that x and y will be young. I just wanted to point that out
to people who like to measure such things.

> But of course, a heap-scanning become heavily depends where object(s)
> located in young space or old one,
> and performs much faster if it needs to scan only new space.
>
> But memory-swapping become apparently having no such dependency. It
> only depends on object size to be swapped.
>
> So, okay.. for cases, when both objects residing in new space, it will
> be not hundrends of thousands times faster but only tens thousands
> times. :)
> Which is still a huge advantage.

Yes. And that's why I said that this is indeed a good idea if it can be
made to work properly. I would expect that there is a need to ensure
that the formats of the objects are the same, no? Otherwise #becoming a
CompiledMethod into an Array could have "interesting" consequences :-)

Cheers,
- Andreas

Igor Stasenko

Re: A trick to speedup #become: (but not becomeForward:)

On 31 July 2011 17:42, Andreas Raab <[hidden email]> wrote:

>
> On 7/31/2011 17:06, Igor Stasenko wrote:
>>
>> On 31 July 2011 10:32, Andreas Raab<[hidden email]> wrote:
>>>
>>> On 7/31/2011 6:56, Igor Stasenko wrote:
>>>>
>>>> And it works! All become tests are green.
>>>> See attached for VM and image side code.
>>>
>>> Good idea. But your benchmark is a little off:
>>>
>>>> Now most interesting thing. How much speed we gain?
>>>>
>>>> Before:
>>>>
>>>> | x y |
>>>>
>>>> x := 'ab' copy.
>>>> y := 'cd' copy.
>>>>
>>>> [ 100 timesRepeat: [ x become: y ] ] timeToRun
>>>
>>> x and y should be young in the above and the performance of #become
>>> should
>>> be much faster than when they are old. To wit:
>>>
>>> [ 100 timesRepeat: [ 'ab' copy become: 'cd' copy ] ] timeToRun
>>> => 36
>>>
>>> | x y |
>>> x := 'ab' copy.
>>> y := 'cd' copy.
>>> Smalltalk garbageCollect. "make x and y old"
>>> [ 100 timesRepeat: [ x become: y ] ] timeToRun
>>> => 1248
>>>
>>> So I'm not sure how valid your benchmark really is.
>>>
>> It is valid, because i comparing performance of using same method
>> (#become:)
>> before and after changes.
>
> It's important to measure these things correctly, otherwise one cannot
> repeat your results. When executing the code as presented, I was entirely
> unable to recreate your results, because the code all but guarantees that x
> and y will be young. I just wanted to point that out to people who like to
> measure such things.
>
>> But of course, a heap-scanning become heavily depends where object(s)
>> located in young space or old one,
>> and performs much faster if it needs to scan only new space.
>>
>> But memory-swapping become apparently having no such dependency. It
>> only depends on object size to be swapped.
>>
>> So, okay.. for cases, when both objects residing in new space, it will
>> be not hundrends of thousands times faster but only tens thousands
>> times. :)
>> Which is still a huge advantage.
>
> Yes. And that's why I said that this is indeed a good idea if it can be made
> to work properly. I would expect that there is a need to ensure that the
> formats of the objects are the same, no?

Currently the primitive checks that object's header types are same (1
, 2, 3 words/header).
Because if their header types are different , you cannot swap memory
contents between them correctly.

An object format is not so important.

> Otherwise #becoming a
> CompiledMethod into an Array could have "interesting" consequences :-)
>

I don't think it will be more interesting than if you try to do it
with usual #become:
:)

> Cheers,
> - Andreas

--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko

Re: A trick to speedup #become: (but not becomeForward:)

I found that similar primitive could be implemented to behave
analogically to becomeForward:
(to copy memory contents of one object over another one).

This is not strictly equivalent to becomeForward, since

if you have objects x , y
and forwarding x -> y
then all who were pointing to x will point to y.

While with copy-over, obviously the pointers remain unchanged. But it
may be not too important, since
the most often use case for #becomeForward: is like:

newObject := SomeClass new.
newObject initAndFillContents bla bla.

SomeGlobalObject becomeForward: newObject

( and newObject is not used anywhere outside this scope)

It is clear in such case, copying newObject contents ->
SomeGlobalObject will be enough for developer's intents,
and therefore an additional primitive which copies bytes from one
object to another could also be useful.

And yes, i'd like to hear your concerns about these primitives in
addition to what Andreas said.
Since i think we should introduce them into VMs to dramatically
speedup become :)

--
Best regards,
Igor Stasenko AKA sig.

Levente Uzonyi-2

Re: A trick to speedup #become: (but not becomeForward:)

On Sun, 31 Jul 2011, Igor Stasenko wrote:

>
> I found that similar primitive could be implemented to behave
> analogically to becomeForward:
> (to copy memory contents of one object over another one).
>
> This is not strictly equivalent to becomeForward, since
>
> if you have objects x , y
> and forwarding x -> y
> then all who were pointing to x will point to y.
>
> While with copy-over, obviously the pointers remain unchanged. But it
> may be not too important, since
> the most often use case for #becomeForward: is like:
>
> newObject := SomeClass new.
> newObject initAndFillContents bla bla.
>
> SomeGlobalObject becomeForward: newObject
>
> ( and newObject is not used anywhere outside this scope)

primitiveCopyObject (#168, Object >> #copyFrom:) can be used for this
already. It only works for pointer objects of the same class and same
size, but I guess this covers most use cases. New features (if
any) should be added to this primitive IMHO.

Btw +1 from me for your #become: speedup idea.

Levente

>
> It is clear in such case, copying newObject contents ->
> SomeGlobalObject will be enough for developer's intents,
> and therefore an additional primitive which copies bytes from one
> object to another could also be useful.
>
>
> And yes, i'd like to hear your concerns about these primitives in
> addition to what Andreas said.
> Since i think we should introduce them into VMs to dramatically
> speedup become :)
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>

Chris Muller-3

Re: A trick to speedup #become: (but not becomeForward:)

In reply to this post by Igor Stasenko

I'm not sure how easy it would be to get the physical size of the
objects which weren't retrieved. As you said, encoding it in the
referencing oid might be the only way - which would require rewriting
of the OidMap and upgrade of legacy repositories. :(

I understand why it won't work with becomeForward: - because that
would be creating two copies of the object. But Magma needs to
becomeForward:, rather than become:, its proxies... (pause to remember
for sure why...). I think because of proxies to Symbol selectors -
you can't become: any object to a Symbol selector or else their
CompiledMethod literals would refer to the Proxy... So that would be
another hurdle to overcome to succeed with your idea.

Just so you know, I _did_ implement your other workaround idea - where
reified proxies are "saved up" into a OrderedCollection which is then
bulk-becomed only once every 30 seconds. I didn't know if you saw it
in the last release (Magma 1.2) - it was a great performance
improvement! Your creative ideas are really helping Magma.

Thanks,
Chris

On Sat, Jul 30, 2011 at 8:12 PM, Igor Stasenko <[hidden email]> wrote:

>
> An interesting observation:
>
> if two oops which we need to swap: oop1 and oop2 taking exactly same
> space in memory,
> then all we need to do is to swap their memory contents, instead of
> scanning heap and updating pointers!
>
> This makes a become operation extremely cheap for such pairs!
> As for objects of different sizes, we could still use slow algorithm.
>
> But knowing that if two objects with same size will be swapped much
> faster, a developers could adapt their algorithms to exploit this
> feature
> (use fixed-size objects instead of variable-sized ones etc).
>
> Magma using proxies, which then #becomeForward: to real objects when reified.
> This is very costly operation and main reason why it so slow on
> loading objects from server.
> To speed thing up, a special trick can be used:
> - each time server sends an object ID (instead of real object) it
> could also send its size in bytes (or even more clever - you can
> encode object size in its ID ;) ).
> Then a client will create a proxy for given object and will try to
> match the size, if its possible. (nobody said that proxy can't be
> variable-sized, right?)
>
> Then once client requesting to reify given proxy with real object from
> database, VM will just overwrite a proxy's memory contents with real
> object.
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>

Igor Stasenko

Re: A trick to speedup #become: (but not becomeForward:)

In reply to this post by Levente Uzonyi-2

On 31 July 2011 20:03, Levente Uzonyi <[hidden email]> wrote:

>
> On Sun, 31 Jul 2011, Igor Stasenko wrote:
>
>>
>> I found that similar primitive could be implemented to behave
>> analogically to becomeForward:
>> (to copy memory contents of one object over another one).
>>
>> This is not strictly equivalent to becomeForward, since
>>
>> if you have objects x , y
>> and forwarding x -> y
>> then all who were pointing to x will point to y.
>>
>> While with copy-over, obviously the pointers remain unchanged. But it
>> may be not too important, since
>> the most often use case for #becomeForward: is like:
>>
>> newObject := SomeClass new.
>> newObject initAndFillContents bla bla.
>>
>> SomeGlobalObject becomeForward: newObject
>>
>> ( and newObject is not used anywhere outside this scope)
>
> primitiveCopyObject (#168, Object >> #copyFrom:) can be used for this
> already. It only works for pointer objects of the same class and same size,
> but I guess this covers most use cases. New features (if any) should be
> added to this primitive IMHO.
>

Yes, thanks for reminder.
I modified this prim to relax requirements (so it is not necessary
that source and dest should be of same format and even more - of same
class)
but it is necessary that their header types and size in memory are the same.

(i added the code to
http://code.google.com/p/cog/issues/detail?id=59
)
> Btw +1 from me for your #become: speedup idea.
>
>
> Levente
>

--
Best regards,
Igor Stasenko AKA sig.

Igor Stasenko

Re: A trick to speedup #become: (but not becomeForward:)

In reply to this post by Chris Muller-3

On 1 August 2011 00:02, Chris Muller <[hidden email]> wrote:
> I'm not sure how easy it would be to get the physical size of the
> objects which weren't retrieved. As you said, encoding it in the
> referencing oid might be the only way - which would require rewriting
> of the OidMap and upgrade of legacy repositories. :(
>

Yes. And if you remember i gave you the code with another oid mapping
implementation,
which avoids using big-integers and a bit more simpler (i hope).
So maybe it is time to check what could be done there?

I don't having time for it right now, hoping that you have it.

> I understand why it won't work with becomeForward: - because that
> would be creating two copies of the object. But Magma needs to
> becomeForward:, rather than become:, its proxies... (pause to remember
> for sure why...). I think because of proxies to Symbol selectors -
> you can't become: any object to a Symbol selector or else their
> CompiledMethod literals would refer to the Proxy... So that would be
> another hurdle to overcome to succeed with your idea.
>

Symbols require special handling anyways: you must check/intern them
once reified.
But for majority of other objects, using these prims could mean a vast
difference.

> Just so you know, I _did_ implement your other workaround idea - where
> reified proxies are "saved up" into a OrderedCollection which is then
> bulk-becomed only once every 30 seconds. I didn't know if you saw it
> in the last release (Magma 1.2) - it was a great performance
> improvement! Your creative ideas are really helping Magma.
>

:)

> Thanks,
> Chris
>
>

--
Best regards,
Igor Stasenko AKA sig.

Chris Muller-3

Re: A trick to speedup #become: (but not becomeForward:)

> Yes. And if you remember i gave you the code with another oid mapping
> implementation,
> which avoids using big-integers and a bit more simpler (i hope).

The current Magma relies on the ".idx" file to lookup locations of
objects in the objects.dat file. Since oids are allocated
consecutively, the file only grows as much as the db allocates new
oids.

Do you happen to remember; whether you had a new scheme for looking up
location of objects in the objects.dat file, since I assume you can no
longer allocate oids consecutively?