The Trunk: Kernel-dtl.1096.mcz
Locked
 
|
David T. Lewis uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-dtl.1096.mcz ==================== Summary ==================== Name: Kernel-dtl.1096 Author: dtl Time: 18 April 2017, 11:59:08.257358 am UUID: 877ab97f-9ebe-4405-af31-fe9caab25eb6 Ancestors: Kernel-eem.1095 SmallInteger>>hashMultiply comment provided by Andres Valloud =============== Diff against Kernel-eem.1095 =============== Item was changed: ----- Method: SmallInteger>>hashMultiply (in category 'bit manipulation') ----- hashMultiply + "Multiply by 1664525 mod 2^28 without overflowing into large integers." | low | - low := self bitAnd: 16383. ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * low) bitAnd: 16383) * 16384)) bitAnd: 16r0FFFFFFF! |
Re: The Trunk: Kernel-dtl.1096.mcz
|
|
Okay, but it's a given that hash functions are desired to be fast, so
one can always assume optimized code in them. I was hoping for a comment that would refer to the origin of this hash function, so one could research and possibly understand it... On Tue, Apr 18, 2017 at 10:59 AM, <[hidden email]> wrote: > David T. Lewis uploaded a new version of Kernel to project The Trunk: > http://source.squeak.org/trunk/Kernel-dtl.1096.mcz > > ==================== Summary ==================== > > Name: Kernel-dtl.1096 > Author: dtl > Time: 18 April 2017, 11:59:08.257358 am > UUID: 877ab97f-9ebe-4405-af31-fe9caab25eb6 > Ancestors: Kernel-eem.1095 > > SmallInteger>>hashMultiply comment provided by Andres Valloud > > =============== Diff against Kernel-eem.1095 =============== > > Item was changed: > ----- Method: SmallInteger>>hashMultiply (in category 'bit manipulation') ----- > hashMultiply > + "Multiply by 1664525 mod 2^28 without overflowing into large integers." > | low | > - > low := self bitAnd: 16383. > ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * low) bitAnd: 16383) * 16384)) > bitAnd: 16r0FFFFFFF! > > |
Re: The Trunk: Kernel-dtl.1096.mcz
|
|
Hi Chris,
The recent mails of Andres Valloud answer your questions[1][2]. Now that I took a deeper look at the function, I found the following issues: 1. It'll overflow into LargeIntegers during computation for some SmallInteger input. That can and should be fixed by adding a bitAnd: 16r3FFF. 2. It will accept negative integers, but I'm not sure if it will work the same way the primitive does. Levente [1] http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024826.html [2] http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024831.html On Thu, 20 Apr 2017, Chris Muller wrote: > Okay, but it's a given that hash functions are desired to be fast, so > one can always assume optimized code in them. I was hoping for a > comment that would refer to the origin of this hash function, so one > could research and possibly understand it... > > > On Tue, Apr 18, 2017 at 10:59 AM, <[hidden email]> wrote: >> David T. Lewis uploaded a new version of Kernel to project The Trunk: >> http://source.squeak.org/trunk/Kernel-dtl.1096.mcz >> >> ==================== Summary ==================== >> >> Name: Kernel-dtl.1096 >> Author: dtl >> Time: 18 April 2017, 11:59:08.257358 am >> UUID: 877ab97f-9ebe-4405-af31-fe9caab25eb6 >> Ancestors: Kernel-eem.1095 >> >> SmallInteger>>hashMultiply comment provided by Andres Valloud >> >> =============== Diff against Kernel-eem.1095 =============== >> >> Item was changed: >> ----- Method: SmallInteger>>hashMultiply (in category 'bit manipulation') ----- >> hashMultiply >> + "Multiply by 1664525 mod 2^28 without overflowing into large integers." >> | low | >> - >> low := self bitAnd: 16383. >> ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * low) bitAnd: 16383) * 16384)) >> bitAnd: 16r0FFFFFFF! >> >> |
Re: The Trunk: Kernel-dtl.1096.mcz
|
|
That's not the point. I'm saying if you're going to commit a new
version of Kernel solely to improve a comment, then make it something which can lead someone reading it, way in the future, to have a reference link to more information -- like Andres Valloud's name, and/or book title. On Thu, Apr 20, 2017 at 4:08 PM, Levente Uzonyi <[hidden email]> wrote: > Hi Chris, > > The recent mails of Andres Valloud answer your questions[1][2]. > > Now that I took a deeper look at the function, I found the following issues: > 1. It'll overflow into LargeIntegers during computation for some > SmallInteger input. That can and should be fixed by adding a bitAnd: > 16r3FFF. > 2. It will accept negative integers, but I'm not sure if it will work the > same way the primitive does. > > Levente > > [1] > http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024826.html > [2] > http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024831.html > > On Thu, 20 Apr 2017, Chris Muller wrote: > >> Okay, but it's a given that hash functions are desired to be fast, so >> one can always assume optimized code in them. I was hoping for a >> comment that would refer to the origin of this hash function, so one >> could research and possibly understand it... >> >> >> On Tue, Apr 18, 2017 at 10:59 AM, <[hidden email]> wrote: >>> >>> David T. Lewis uploaded a new version of Kernel to project The Trunk: >>> http://source.squeak.org/trunk/Kernel-dtl.1096.mcz >>> >>> ==================== Summary ==================== >>> >>> Name: Kernel-dtl.1096 >>> Author: dtl >>> Time: 18 April 2017, 11:59:08.257358 am >>> UUID: 877ab97f-9ebe-4405-af31-fe9caab25eb6 >>> Ancestors: Kernel-eem.1095 >>> >>> SmallInteger>>hashMultiply comment provided by Andres Valloud >>> >>> =============== Diff against Kernel-eem.1095 =============== >>> >>> Item was changed: >>> ----- Method: SmallInteger>>hashMultiply (in category 'bit >>> manipulation') ----- >>> hashMultiply >>> + "Multiply by 1664525 mod 2^28 without overflowing into large >>> integers." >>> | low | >>> - >>> low := self bitAnd: 16383. >>> ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * >>> low) bitAnd: 16383) * 16384)) >>> bitAnd: 16r0FFFFFFF! >>> >>> > |
Re: The Trunk: Kernel-dtl.1096.mcz
|
|
On Thu, Apr 20, 2017 at 05:14:50PM -0500, Chris Muller wrote:
> That's not the point. I'm saying if you're going to commit a new > version of Kernel solely to improve a comment, then make it something > which can lead someone reading it, way in the future, to have a > reference link to more information -- like Andres Valloud's name, > and/or book title. You're right, the commit notice should have had a reference to the squeak-dev discussion for the benefit of future readers. Sorry! It may seem odd to commit an entire Kernel version just for the sake of a one line comment, but in this case it was a crucial comment that had been accidentally omitted for the last 17 years, so I though it was worth the noise. But I should have documented that in the commit notice. Dave > > On Thu, Apr 20, 2017 at 4:08 PM, Levente Uzonyi <[hidden email]> wrote: > > Hi Chris, > > > > The recent mails of Andres Valloud answer your questions[1][2]. > > > > Now that I took a deeper look at the function, I found the following issues: > > 1. It'll overflow into LargeIntegers during computation for some > > SmallInteger input. That can and should be fixed by adding a bitAnd: > > 16r3FFF. > > 2. It will accept negative integers, but I'm not sure if it will work the > > same way the primitive does. > > > > Levente > > > > [1] > > http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024826.html > > [2] > > http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024831.html > > > > On Thu, 20 Apr 2017, Chris Muller wrote: > > > >> Okay, but it's a given that hash functions are desired to be fast, so > >> one can always assume optimized code in them. I was hoping for a > >> comment that would refer to the origin of this hash function, so one > >> could research and possibly understand it... > >> > >> > >> On Tue, Apr 18, 2017 at 10:59 AM, <[hidden email]> wrote: > >>> > >>> David T. Lewis uploaded a new version of Kernel to project The Trunk: > >>> http://source.squeak.org/trunk/Kernel-dtl.1096.mcz > >>> > >>> ==================== Summary ==================== > >>> > >>> Name: Kernel-dtl.1096 > >>> Author: dtl > >>> Time: 18 April 2017, 11:59:08.257358 am > >>> UUID: 877ab97f-9ebe-4405-af31-fe9caab25eb6 > >>> Ancestors: Kernel-eem.1095 > >>> > >>> SmallInteger>>hashMultiply comment provided by Andres Valloud > >>> > >>> =============== Diff against Kernel-eem.1095 =============== > >>> > >>> Item was changed: > >>> ----- Method: SmallInteger>>hashMultiply (in category 'bit > >>> manipulation') ----- > >>> hashMultiply > >>> + "Multiply by 1664525 mod 2^28 without overflowing into large > >>> integers." > >>> | low | > >>> - > >>> low := self bitAnd: 16383. > >>> ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * > >>> low) bitAnd: 16383) * 16384)) > >>> bitAnd: 16r0FFFFFFF! > >>> > >>> > > > |
Re: The Trunk: Kernel-dtl.1096.mcz
|
|
In reply to this post by Levente Uzonyi
Hi Levente,
On Thu, Apr 20, 2017 at 2:08 PM, Levente Uzonyi <[hidden email]> wrote: Hi Chris, 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.
I don't see that for SmallInteger maxVal. Try the following: Debug: | v low | v := SmallInteger maxVal. low := v bitAnd: 16383. ^ 9741 * low + ((9741 * (v bitShift: -14) + (101 * low) bitAnd: 16383) * 16384) bitAnd: 268435455 and then do run until... ThisContext top class ~= SmallInteger When I try this it runs to the end. 2. It will accept negative integers, but I'm not sure if it will work the same way the primitive does. 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 :-)
_,,,^..^,,,_ best, Eliot |
Re: The Trunk: Kernel-dtl.1096.mcz
|
|
In reply to this post by David T. Lewis
Heh, no need to apologize, I was just taking the opportunity to
express the idea of... sculpting The Class Library (capitalized to garner grand respect) with deliberate consideration for the full audience of present and future consumers. Thanks. On Thu, Apr 20, 2017 at 7:10 PM, David T. Lewis <[hidden email]> wrote: > On Thu, Apr 20, 2017 at 05:14:50PM -0500, Chris Muller wrote: >> That's not the point. I'm saying if you're going to commit a new >> version of Kernel solely to improve a comment, then make it something >> which can lead someone reading it, way in the future, to have a >> reference link to more information -- like Andres Valloud's name, >> and/or book title. > > You're right, the commit notice should have had a reference to the squeak-dev > discussion for the benefit of future readers. Sorry! > > It may seem odd to commit an entire Kernel version just for the sake of a > one line comment, but in this case it was a crucial comment that had been > accidentally omitted for the last 17 years, so I though it was worth the > noise. But I should have documented that in the commit notice. > > Dave > > > > >> >> On Thu, Apr 20, 2017 at 4:08 PM, Levente Uzonyi <[hidden email]> wrote: >> > Hi Chris, >> > >> > The recent mails of Andres Valloud answer your questions[1][2]. >> > >> > Now that I took a deeper look at the function, I found the following issues: >> > 1. It'll overflow into LargeIntegers during computation for some >> > SmallInteger input. That can and should be fixed by adding a bitAnd: >> > 16r3FFF. >> > 2. It will accept negative integers, but I'm not sure if it will work the >> > same way the primitive does. >> > >> > Levente >> > >> > [1] >> > http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024826.html >> > [2] >> > http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024831.html >> > >> > On Thu, 20 Apr 2017, Chris Muller wrote: >> > >> >> Okay, but it's a given that hash functions are desired to be fast, so >> >> one can always assume optimized code in them. I was hoping for a >> >> comment that would refer to the origin of this hash function, so one >> >> could research and possibly understand it... >> >> >> >> >> >> On Tue, Apr 18, 2017 at 10:59 AM, <[hidden email]> wrote: >> >>> >> >>> David T. Lewis uploaded a new version of Kernel to project The Trunk: >> >>> http://source.squeak.org/trunk/Kernel-dtl.1096.mcz >> >>> >> >>> ==================== Summary ==================== >> >>> >> >>> Name: Kernel-dtl.1096 >> >>> Author: dtl >> >>> Time: 18 April 2017, 11:59:08.257358 am >> >>> UUID: 877ab97f-9ebe-4405-af31-fe9caab25eb6 >> >>> Ancestors: Kernel-eem.1095 >> >>> >> >>> SmallInteger>>hashMultiply comment provided by Andres Valloud >> >>> >> >>> =============== Diff against Kernel-eem.1095 =============== >> >>> >> >>> Item was changed: >> >>> ----- Method: SmallInteger>>hashMultiply (in category 'bit >> >>> manipulation') ----- >> >>> hashMultiply >> >>> + "Multiply by 1664525 mod 2^28 without overflowing into large >> >>> integers." >> >>> | low | >> >>> - >> >>> low := self bitAnd: 16383. >> >>> ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * >> >>> low) bitAnd: 16383) * 16384)) >> >>> bitAnd: 16r0FFFFFFF! >> >>> >> >>> >> > >> > |
Re: The Trunk: Kernel-dtl.1096.mcz
|
|
In reply to this post by Eliot Miranda-2
Hi Eliot,
On Thu, 20 Apr 2017, Eliot Miranda wrote: > Hi Levente, > On Thu, Apr 20, 2017 at 2:08 PM, Levente Uzonyi <[hidden email]> wrote: > Hi Chris, > > The recent mails of Andres Valloud answer your questions[1][2]. > > > 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. > > > Now that I took a deeper look at the function, I found the following issues: > 1. It'll overflow into LargeIntegers during computation for some SmallInteger input. That can and should be fixed by adding a bitAnd: 16r3FFF. > > > I don't see that for SmallInteger maxVal. Try the following: > Debug: > | v low | > v := SmallInteger maxVal. > low := v bitAnd: 16383. > ^ 9741 * low + ((9741 > * (v bitShift: -14) + (101 * low) bitAnd: 16383) > * 16384) bitAnd: 268435455 > > and then do run until... ThisContext top class ~= SmallInteger > > When I try this it runs to the end. internal computation leaves the 30-bits range is 16r6B7B3FB7, which has 31-bits. It also works for 60-bits SmallIntegers for the same reason, the multiplier constant's low 14-bits part is small enough. > > 2. It will accept negative integers, but I'm not sure if it will work the same way the primitive does. > > > 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 :-) Right, but I'd rather not try the same in 64-bits. :) Levente > > > Levente > > [1] http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024826.html > [2] http://lists.squeakfoundation.org/pipermail/vm-dev/2017-April/024831.html > > On Thu, 20 Apr 2017, Chris Muller wrote: > > Okay, but it's a given that hash functions are desired to be fast, so > one can always assume optimized code in them. I was hoping for a > comment that would refer to the origin of this hash function, so one > could research and possibly understand it... > > > On Tue, Apr 18, 2017 at 10:59 AM, <[hidden email]> wrote: > David T. Lewis uploaded a new version of Kernel to project The Trunk: > http://source.squeak.org/trunk/Kernel-dtl.1096.mcz > > ==================== Summary ==================== > > Name: Kernel-dtl.1096 > Author: dtl > Time: 18 April 2017, 11:59:08.257358 am > UUID: 877ab97f-9ebe-4405-af31-fe9caab25eb6 > Ancestors: Kernel-eem.1095 > > SmallInteger>>hashMultiply comment provided by Andres Valloud > > =============== Diff against Kernel-eem.1095 =============== > > Item was changed: > ----- Method: SmallInteger>>hashMultiply (in category 'bit manipulation') ----- > hashMultiply > + "Multiply by 1664525 mod 2^28 without overflowing into large integers." > | low | > - > low := self bitAnd: 16383. > ^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * low) bitAnd: 16383) * 16384)) > bitAnd: 16r0FFFFFFF! > > > > > > > -- > _,,,^..^,,,_ > best, Eliot > > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |