<div dir="ltr">Hi Levente,<div class="gmail_extra"><br><div class="gmail_quote">On Thu, Apr 20, 2017 at 2:08 PM, Levente Uzonyi <span dir="ltr"><<a href="mailto:leves@caesar.elte.hu" target="_blank">leves@caesar.elte.hu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi Chris,<br>
<br>
The recent mails of Andres Valloud answer your questions[1][2].<br></blockquote><div><br></div><div>I still think we could and should make the comment more informative. Andrew' responses are short on references. I understand he has a lot of experience in hashing; all the more reason he should be able to provide a good reference.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
Now that I took a deeper look at the function, I found the following issues:<br>
1. It'll overflow into LargeIntegers during computation for some SmallInteger input. That can and should be fixed by adding a bitAnd: 16r3FFF.<br></blockquote><div><br></div><div>I don't see that for SmallInteger maxVal. Try the following:</div><div>Debug:</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>| v low |</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>v := SmallInteger maxVal.</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>low := v bitAnd: 16383.</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>^ 9741 * low + ((9741</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>* (v bitShift: -14) + (101 * low) bitAnd: 16383)</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>* 16384) bitAnd: 268435455 <br></div><div><br></div><div>and then do run until... ThisContext top class ~= SmallInteger</div><div><br></div><div>When I try this it runs to the end.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
2. It will accept negative integers, but I'm not sure if it will work the same way the primitive does.<br></blockquote><div><br></div><div>It should. The last bitAnd: should produce the same results. I tested this and IIRC it worked. Again easy to test. Create a non-primitive hashMultiply and then test for all the negative SmallIntegers, something quite possible in 32-bits :-)</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
Levente<br>
<br>
[1] <a href="http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024826.html" rel="noreferrer" target="_blank">http://lists.squeakfoundation.<wbr>org/pipermail/vm-dev/2017-Apri<wbr>l/024826.html</a><br>
[2] <a href="http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024831.html" rel="noreferrer" target="_blank">http://lists.squeakfoundation.<wbr>org/pipermail/vm-dev/2017-Apri<wbr>l/024831.html</a><br>
<br>
On Thu, 20 Apr 2017, Chris Muller wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
Okay, but it's a given that hash functions are desired to be fast, so<br>
one can always assume optimized code in them. I was hoping for a<br>
comment that would refer to the origin of this hash function, so one<br>
could research and possibly understand it...<br>
<br>
<br>
On Tue, Apr 18, 2017 at 10:59 AM, <<a href="mailto:commits@source.squeak.org" target="_blank">commits@source.squeak.org</a>> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
David T. Lewis uploaded a new version of Kernel to project The Trunk:<br>
<a href="http://source.squeak.org/trunk/Kernel-dtl.1096.mcz" rel="noreferrer" target="_blank">http://source.squeak.org/trunk<wbr>/Kernel-dtl.1096.mcz</a><br>
<br>
==================== Summary ====================<br>
<br>
Name: Kernel-dtl.1096<br>
Author: dtl<br>
Time: 18 April 2017, 11:59:08.257358 am<br>
UUID: 877ab97f-9ebe-4405-af31-fe9caa<wbr>b25eb6<br>
Ancestors: Kernel-eem.1095<br>
<br>
SmallInteger>>hashMultiply comment provided by Andres Valloud<br>
<br>
=============== Diff against Kernel-eem.1095 ===============<br>
<br>
Item was changed:<br>
----- Method: SmallInteger>>hashMultiply (in category 'bit manipulation') -----<br>
hashMultiply<br>
+ "Multiply by 1664525 mod 2^28 without overflowing into large integers."<br>
| low |<br>
-<br>
low := self bitAnd: 16383.<br>
^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * low) bitAnd: 16383) * 16384))<br>
bitAnd: 16r0FFFFFFF!<br>
<br>
<br>
</blockquote></blockquote>
<br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><span style="font-size:small;border-collapse:separate"><div>_,,,^..^,,,_<br></div><div>best, Eliot</div></span></div></div></div>
</div></div>