<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">2017-04-18 16:03 GMT+02:00 David T. Lewis <span dir="ltr"><<a href="mailto:lewis@mail.msen.com" target="_blank">lewis@mail.msen.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5"><br>
On Tue, Apr 18, 2017 at 10:27:41AM +0200, Nicolas Cellier wrote:<br>
><br>
> 2017-04-18 4:02 GMT+02:00 Andres Valloud <<a href="mailto:avalloud@smalltalk.comcastbiz.net">avalloud@smalltalk.<wbr>comcastbiz.net</a>><br>
> :<br>
><br>
> ><br>
> > On 4/17/17 16:45 , Eliot Miranda wrote:<br>
> ><br>
> >> FYI, hash multiply is<br>
> >> hashMultiply<br>
> >> | low |<br>
> >> low := self bitAnd: 16383.<br>
> >> ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * low)<br>
> >> bitAnd: 16383) * 16384))<br>
> >> bitAnd: 16r0FFFFFFF<br>
> >><br>
> >> and when written as a primitive is<br>
> >> hashMultiply<br>
> >> | low |<br>
> >> low := self bitAnd: 16383.<br>
> >> ^(16r260D * low + (16r260D * (self bitShift: -14) + (16r0065 * low) *<br>
> >> 16384))<br>
> >> bitAnd: 16r0FFFFFFF<br>
> >> because we don't care about the multiply by 16384 overflowing; when<br>
> >> written as a primitive it won't overflow into a LargePositiveInteger.<br>
> >><br>
> ><br>
> > Hopefully this doesn't mean the primitive got implemented by actually<br>
> > doing these operations verbatim.  As you have probably seen, that<br>
> > convoluted arithmetic is done this way in Smalltalk only to simulate a<br>
> > 32x32 multiplication bit-anded down to 28 bits without overflowing into<br>
> > large integers (the original code from August 2000 had my initials).<br>
> ><br>
> > At a sufficiently low level such as C, all that complexity is just an<br>
> > unsigned multiplication by 1664525.  The image code should still have a<br>
> > comment to that effect, did it get lost?<br>
> ><br>
> > Andres.<br>
> ><br>
><br>
> More: if it's a 64 bit image, then we have 60 bit long unsigned small int<br>
> since 1664525 highBit = 21, and self is a hash result not exceeding 30<br>
> bits, we can implement hashMultiply as<br>
>     ^self * 1664525 bitAnd: 16r0FFFFFFF<br>
><br>
> Maybe the JIT can be given a second chance too.<br>
<br>
</div></div>AFAIK, primitiveStringHash has always been translated directly from<br>
ByteArray class>>hashBytes:startingWith: and the hashMultiply logic that we are<br>
discussing here currently is repeated in four different methods in Squeak trunk<br>
(String class>>stringHash:initialHash:<wbr>, TypeString class>>stringHash:initialHash:<wbr>,<br>
SmallInteger hashMultiply, and ByteArray class hashBytes:startingWith:).<br>
<br>
At this point, and particularly given the differences in various VMs, it would<br>
make sense to reimplement primitiveStringHash directly in MiscPrimitivesPlugin<br>
with whatever optimizations are needed (maybe differently based on size of a<br>
small integers), rather than translating it from a default implementation in<br>
the image.<br>
<br></blockquote><div>Hi David,<br></div><div>My opinion is rather that we should get rid of MiscPrimitivesPlugin.<br></div><div>1) If String hash is performance critical (and it is), it's not really Misc.<br></div><div>2) Eliot's post shows that regular primitive invocation is slow vs modern spur/jit, so it might not pay<br></div><div>3) other than that, we don't properly version control MiscPrimitivePlugin source code<br></div><div>   it's not handled in VMMaker repository nor in one of the well identified external plugin repositories.<br>   but it's spreaded over Squeak and/or Pharo packages, and thus subject to uncontrolled changes and divergences</div><div> <br></div><div>Maybe it's time to do it.<br><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
But I think we may be missing Eliot's main point. There is overhead associated<br>
with accessing the stack (at least on a stack interpreter) and in returning<br>
values to image, and this will be the case regardless of what calculations are<br>
being done in the primitive itself. So at least for some VMs we may be reaching<br>
the point where that overhead becomes a significant part of the performance profile.<br>
<br>
Whether that overhead would justify creating a new primitive callout mechanism<br>
may be another question, but it is certainly worth understanding where the<br>
overhead occurs, and how that performance profile changes as the Cog jit and<br>
Sista progress.<br>
<br>
Dave<br>
<br></blockquote><div><br></div><div>Yes, exactly, but the new callout mechanism has severe stack limitations preventing general purpose usage.<br></div><div>Concerning the specific case of hashMultiply, since it's just an imul and a bitAnd, the primitive should be inlined by the VM just like other basic arithmetic operations IMO.<br></div><div>So the remarks of Andres makes sense, even if we can't generalize to other Misc primitives.<br></div></div><br></div></div>