<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 18, 2017 at 9:09 AM, Nicolas Cellier <span dir="ltr"><<a href="mailto:nicolas.cellier.aka.nice@gmail.com" target="_blank">nicolas.cellier.aka.nice@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> <br><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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail-m_6658353055967013042HOEnZb"><div class="gmail-m_6658353055967013042h5"><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" target="_blank">avalloud@smalltalk.comcastbiz<wbr>.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></div></div></div></div></blockquote><div><br></div><div>I agree. I am ready to collaborate on this and update the Pharo packages. </div><div><br></div><div>For each primitive, we need to evaluate the performance with and without the primitive. In each case, we either move the primitive to numbered primitive or we just use normal Smalltalk code. We looked into string hashing with Eliot and it seems having only hashMultiply as a primitive is enough. </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);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.</blockquote></div></div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
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></div></div></blockquote><div><br></div><div>The idea there is that each primitive can be analysed to determine if it can be called that way or not. I believe large integers primitives may be able to be called that way for example.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></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>
<br></blockquote></div><br></div></div>