[Vm-dev] Cog Primitive Performance

[Eliot Miranda]

Hi All, Hi David,

On Tue, Apr 18, 2017 at 7:03 AM, David T. Lewis <lewis at mail.msen.com> wrote:

>
> On Tue, Apr 18, 2017 at 10:27:41AM +0200, Nicolas Cellier wrote:
> >
> > 2017-04-18 4:02 GMT+02:00 Andres Valloud <avalloud at smalltalk.
> comcastbiz.net>
> > :
> >
> > >
> > > On 4/17/17 16:45 , Eliot Miranda wrote:
> > >
> > >> FYI, hash multiply is
> > >> hashMultiply
> > >> | low |
> > >> low := self bitAnd: 16383.
> > >> ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * low)
> > >> bitAnd: 16383) * 16384))
> > >> bitAnd: 16r0FFFFFFF
> > >>
> > >> and when written as a primitive is
> > >> hashMultiply
> > >> | low |
> > >> low := self bitAnd: 16383.
> > >> ^(16r260D * low + (16r260D * (self bitShift: -14) + (16r0065 * low) *
> > >> 16384))
> > >> bitAnd: 16r0FFFFFFF
> > >> because we don't care about the multiply by 16384 overflowing; when
> > >> written as a primitive it won't overflow into a LargePositiveInteger.
> > >>
> > >
> > > Hopefully this doesn't mean the primitive got implemented by actually
> > > doing these operations verbatim.  As you have probably seen, that
> > > convoluted arithmetic is done this way in Smalltalk only to simulate a
> > > 32x32 multiplication bit-anded down to 28 bits without overflowing into
> > > large integers (the original code from August 2000 had my initials).
> > >
> > > At a sufficiently low level such as C, all that complexity is just an
> > > unsigned multiplication by 1664525.  The image code should still have a
> > > comment to that effect, did it get lost?
> > >
> > > Andres.
> > >
> >
> > More: if it's a 64 bit image, then we have 60 bit long unsigned small int
> > since 1664525 highBit = 21, and self is a hash result not exceeding 30
> > bits, we can implement hashMultiply as
> >     ^self * 1664525 bitAnd: 16r0FFFFFFF
> >
> > Maybe the JIT can be given a second chance too.
>
> AFAIK, primitiveStringHash has always been translated directly from
> ByteArray class>>hashBytes:startingWith: and the hashMultiply logic that
> we are
> discussing here currently is repeated in four different methods in Squeak
> trunk
> (String class>>stringHash:initialHash:, TypeString
> class>>stringHash:initialHash:,
> SmallInteger hashMultiply, and ByteArray class hashBytes:startingWith:).
>
> At this point, and particularly given the differences in various VMs, it
> would
> make sense to reimplement primitiveStringHash directly in
> MiscPrimitivesPlugin
> with whatever optimizations are needed (maybe differently based on size of
> a
> small integers), rather than translating it from a default implementation
> in
> the image.
>
> But I think we may be missing Eliot's main point. There is overhead
> associated
> with accessing the stack (at least on a stack interpreter) and in returning
> values to image, and this will be the case regardless of what calculations
> are
> being done in the primitive itself. So at least for some VMs we may be
> reaching
> the point where that overhead becomes a significant part of the
> performance profile.
>

Exactly.  This thread is about the overhead associated with invoking the
various forms of primitive.  Interpreter primitives, which access their
receiver and arguments via the global stackPointer variable, are very slow,
and the measurements show that it is accessing arguments and returning
results through the stackPointer global that is the main issue.


> Whether that overhead would justify creating a new primitive callout
> mechanism
> may be another question, but it is certainly worth understanding where the
> overhead occurs, and how that performance profile changes as the Cog jit
> and
> Sista progress.
>

My conclusion is that we should stop using MiscPrimitivePlugin and
reimplement its performance-critical primitives not to use interpreter
primitives.  More of that in a follow up on what to do about string hashing.


> Dave
>

-- 
_,,,^..^,,,_
best, Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20170418/61ceeb6d/attachment.html>