[Vm-dev] Re: Spur-3126 problem with #instVarAt:

Eliot Miranda eliot.miranda at gmail.com
Fri Nov 7 17:52:01 UTC 2014


HiChris, Hi All,

   Chris, forgive me for replying to vm-dev, but I want to canvas responses
to the solutions I'm proposing, (and I want to spread this good news) so
I'm begging forgiveness instead of asking permission ;-)

On Thu, Nov 6, 2014 at 7:31 PM, Chris Muller <ma.chris.m at gmail.com> wrote:

> Hi Eliot.  The good news is, with a minor tweak to a timeout delay,
> the Magma test suite actually *finished to completion*!
> Yeeeeeaaaaahhh!!!
>

Fantastic news.  Your's is a great test of the system.  Thanks for your
efforts in getting us this far!

But its that required minor tweak that exposes the bad news, though --
> there seems to be some sort of performance issue when accessing via
> #instVarAt:.
>
> In the following script, Cog reports 18M per second where Spur reports
> 120K per second.
>
> | arr| arr := Array new: 1000.
> [arr instVarAt: 1000] bench
>
> Also, observe changing the Array size to 1 and instVarAt: 1 speeds up
> dramatically.  This makes me think there is some sort of enumerating /
> looping going on in #instVarAt: primitive.
>

Actually it is going on in the primitive failure machinery, not the
primitive itself, but ok...  this performance is to be expected.  Here's
the definition of instVarAt:

instVarAt: index
"Primitive. Answer a fixed variable in an object. The numbering of the
variables corresponds to the named instance variables. Fail if the index
is not an Integer or is not the index of a fixed variable. Essential. See
Object documentation whatIsAPrimitive."

<primitive: 73>
"Access beyond fixed variables."
^self basicAt: index - self class instSize

You see that the primitive is defined to access /only/ named inst vars, and
to fail if access is attempted beyond the named inst vars. Now Array has no
named inst vars, and so the primtiive will always fail. Now Spur provides
transparent forwarding (and hence fast become with direct pointers) by
checking for forwarding on message send (see your second issue) /and/ on
primitive failure. So whenever the instVarAt: primitive fails the VM scans
the receiver and arguments to the primitive's "accessor depth" (in this
case 1, 0 comprising stack references to the arguments, 1 comprising inst
vars of the receiver and arguments), looking for forwarding pointers, and
if it finds any, eliminating them by following them and updating the
reference, and then retrying the primitive. If none are found, or the
primitive fails a second time, execution proceeds, failing the primitive
and activating its method.

The accessor depth for a primitive is computed by analysing the primitive's
parse tree (actually the closure of the primitive's parse tree over any
calls it makes).  In this case the analysis concludes the depth is 1,
whereas a depth of 0 would be ok in cases where there are no forwarded
references in the Array; if the primitive were to answer a forwarded
object, the forwarding pointer would be followed when it was sent a
message.  Lots of accesses to the same slot in the ARray. if it yielded a
forwarding object, would push forwarding costs to where that result was
used.  So there's a toss up between eagerly following or not.

The reason why changing the size of the array makes such a difference is
that the VM has to scan the entire array and so does ~ 1000 times as much
work when it has length 1000 than when it has length 1.  The assumption
behind my architecture here is that primitive failure is relatively rare.
That's clearly not true in this case.   Fortunately there are a number of
solutions I can think of here:


1. in Magma you can implement a new method for accessing slots, lets call
it slotAt:, and it would be defined like this:

Object>>slotAt: index
"Access the nth slot of an object.  Use the instVarAt: primitive for speed
with fixed, non-variable objects."

<primitive: 73>
"Access beyond fixed variables."
^self basicAt: index - self class instSize

Array>>slotAt: index
"Access the nth slot of an object.  Use the basicAt:: primitive for speed
with variable objects."

<primitive: 60>
index isInteger ifTrue:
[self class isVariable
ifTrue: [self errorSubscriptBounds: index]
ifFalse: [self errorNotIndexable]].
index isNumber
ifTrue: [^self slotAt: index asInteger]
ifFalse: [self errorNonIntegerIndex]

This only works if Array has no subclasses with named inst vars, or at
least, if there are any Magma makes no use of them.

2. I can add a slotAt: primitive that does not fail when access is made
beyond the named inst vars, but provides useful, flat access to all the
slots.  This will be very fast, but requires a little work.

3. re the point about what the forwarding depth should be, I could provide
a "manual override" of the depth for specific primtiives, so that the depth
for instVarAt: would be 0.  This is a little work but might have more uses
beyond instVarAt:.

I'm leaning to 2.  But want to hear waht others think, including any
additional solutions.

Anyway, interesting.  A behaviour wonderous strange, no doubt :-)


(Problem #2) -- Now, here's something weird that I could not begin to
> guess at.  Switching to plain #at: (instead of #instVarAt:), and then
> compare the output with vs. without become:
>
> "without become"
> | arr| arr := Array new: 1000.
> [arr at: 1000] bench
>
>           '56,600,000 per second.'
>
> to same measurement after becomed: to the same.
>
> | arr| arr := Object new.
> arr becomeForward: (Array new: 1000).
> [arr at: 1000] bench
>
>        '4,060,000 per second.'
>
> So my reified Proxy's are operating much more slowly.  This
> degradation does not exist in Cog.
>

So what's happening here is that when the become occurs, the Object new
version of arr is changed to a forwarder to an (Array new: 1000).  When the
message is sent to arr, the send fails, the send failure code scans the
temp vars of the stack frame, updates arr to point directly to the (Array
new: 1000) version of arr, completing the become: operation, and the send
is retried.  If you change the benchmarks to

| arr| arr := Array new: 1000.
[1 to: 1000 do: [:i| arr at: i]] bench

| arr| arr := Object new.
arr becomeForward: (Array new: 1000).
[1 to: 1000 do: [:i| arr at: i]] bench

you should see much less difference:



| arr| arr := Array new: 1000.
[1 to: 1000 do: [:i| arr at: i]] bench '163,000 per second.'

| arr| arr := Object new.
arr becomeForward: (Array new: 1000).
[1 to: 1000 do: [:i| arr at: i]] bench '161,000 per second.'

So how common is it that you become an object and send a message to it only
once from a reference?  Do you have any macro benchmarks?  If the macro
benchmarks show substantial speedups even though micro-benchmarks show
slow-downs there's no issue.  The costs in the micro operations are being
paid to gain substantial advantages at the macro level.

PS -- Why is #instVarAt: so much slower than #at:?  Is there any way
> to make it just as fast?
>

See above.


> PPS -- that line-ending problem when using the Clipboard that Levente
> mentioned the other day has dogged me all year as well.  Would it be
> possible to include the -textenc UTF8 by default in the squeak script
> that you release?
>

Yes.  I think I can just make this the default in all VMs and/or just the
Spur ones.  IIRC I found out what the name to use for the defalt was just
the other day.  I'm going to go find it again, but yes, I'll make this the
default.  I'd prefer to make it the only choice.  Is that OK with folks?



> Thank you for this (soon-to-be) awesome piece of software..
>

sigh ;-)
-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20141107/576ebb9a/attachment.htm


More information about the Vm-dev mailing list