[bug] Integer>>hash
Locked
[bug] Integer>>hash
 
|
Re: [bug] Integer>>hash
|
|
RE: [bug] Integer>>hash
|
|
Re: [bug] Integer>>hash
|
|
Re: [bug] Integer>>hash
|
|
RE: [bug] Integer>>hash
|
|
Re: [bug] Integer>>hash
|
|
In reply to this post by Paul Baumann
I looked at using self bitAnd: (SmallInteger maxVal bitShift: -1) + (self lastDigit bitShift: 8) as a hash function and it looks ok. here are some timings.
hash is the current nteger>>hash. speedOldHash is the current Integer has implemented as fast as I can see in vanilla Smalltalk; essentially digitlength is made a primitive and lastDigit is inlined. newHash is (SmallInteger maxVal bitShift: -1) + (self lastDigit bitShift: 8) with lastDigit inlined, i.e. (self bitAnd: (SmallInteger maxVal bitShift: -1)) + ((self digitAt: self basicSize) bitShift: 8) The timing script collects all large integers, sees how many different values are prodeuced and tomes the various hash functions. A send of #class is used as the overhead measurement case and its time s subtraced when ratios are computed. (| insts r times | insts := LargeInteger allGeneralInstances asArray. times := Dictionary with: #class -> 0 with: #hash -> 0 with: #speedOldHash -> 0 with: #newHash -> 0. r := 1000. (1 to: 10) do: [:n| times at: #class put: (times at: #class) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) class]]]). times at: #hash put: (times at: #hash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) hash]]]). times at: #speedOldHash put: (times at: #speedOldHash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) speedOldHash]]]). times at: #newHash put: (times at: #newHash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) newHash]]])]. insts size -> times -> (#(hash speedOldHash newHash) collect: [:sym| (times at: sym) asDouble - (times at: #class) / ((times at: #hash) - (times at: #class))]) -> (insts collect: [:li| li hash]) asSet size -> (insts collect: [:li| li speedOldHash]) asSet size -> (insts collect: [:li| li newHash]) asSet size -> ((insts collect: [:li| li newHash]) asSet size asDouble / (insts collect: [:li| li hash]) asSet size)) The results in my mal imager on our mondo Opteron server are: 14164 ->Dictionary (#class->2880200 #speedOldHash->7130494 #hash->11650808 #newHash->25181745 ) ->#(1.0d 0.48460654039036d 2.5427592933124d) ->1203 ->1203 ->14055 ->11.683291770574d i.e. the base case of looping sending lass takes 2.88 seconds. The original hash takes 11.65 seconds, the new hash 25.18 seconds. The original hash produces only 1203 values from 14164 integers whereas the new hash provides 14055. The bottom line is that the new hash is two and a half times slower (5 times slower than a sped-up implementation) but (albeit with a small sample size) it collapses the space of hash values by (14164-14055)/141.64 = 0.77% whereas the current hash function collapses it by (14164-1203)/141.64 = 91.51%. Paul, what was your new hash function and what realistic measurements do you have? If yours differs markedly from mine could you compare the two in a realistic setting? I'll reply to your message tmorow. The missus is banging on the ceiling; its time for me to go upstairs and help with the kids :) --- Eliot Miranda ,,,^..^,,, mailto:[hidden email] VisualWorks Engineering, Cincom Smalltalk: scene not herd Tel +1 408 216 4581 3350 Scott Blvd, Bldg 36 Suite B, Santa Clara, CA 95054 USA Fax +1 408 216 4500 |
Integer-newHash.st (884 bytes)
RE: [bug] Integer>>hash
|
|
In reply to this post by Paul Baumann
Hi Eliot,
The "newHash" had a low distribution in a dispersed GS oop range to 1.5M: VW 7.4.1 default: 10356 large integers. Rate 37 per ms Added to growing bag of 39 per ms. Matching add of 931 per ms. Hash ranges: 10356 hash values ranging 8192 to 23038 with 0 repeats. LPI>>hash ^(SmallInteger maxVal bitShift: -1) + (self lastDigit bitShift: 8) 10356 large integers. Rate 19 per ms Added to growing bag of 32 per ms. Matching add of 49 per ms. Hash ranges: 58 hash values ranging 268443647 to 268458239 with 10298 repeats. Martin's LPI>>hash 10356 large integers. Rate 54 per ms Added to growing bag of 57 per ms. "Why so low?" Matching add of 1235 per ms. Hash ranges: 10356 hash values ranging 0 to 16775947 with 0 repeats. LPI>>hash ^self 10356 large integers. Rate 326 per ms Added to growing bag of 693 per ms. Matching add of 617 per ms. Hash ranges: 10356 hash values ranging 536870912 to 1499916977 with 0 repeats. Returning "self" is winner here, but now look at the first 10000 values above maxValue: VW 7.4.1 default: 10000 large integers. Rate 0 per ms Added to growing bag of 1 per ms. Matching add of 1 per ms. Hash ranges: 256 hash values ranging 8192 to 8447 with 9744 repeats. LPI>>hash ^(SmallInteger maxVal bitShift: -1) + (self lastDigit bitShift: 8) 10000 large integers. Rate 0 per ms Added to growing bag of 0 per ms. Matching add of 0 per ms. Hash ranges: 1 hash values ranging 268443647 to 268443647 with 9999 repeats. Martin's LPI>>hash 10000 large integers. Rate 531 per ms Added to growing bag of 1150 per ms. Matching add of 989 per ms. Hash ranges: 10000 hash values ranging 0 to 9999 with 0 repeats. LPI>>hash ^self 10000 large integers. Rate 329 per ms Added to growing bag of 672 per ms. Matching add of 645 per ms. Hash ranges: 10000 hash values ranging 536870912 to 536880911 with 0 repeats. Martin's implementation performs best in the lower range of LargePositiveInteger. Returning the LPI itself performs best in a broader GS range of LPI. So far: Martin's implementation is best so far if there is a need to constrain the value returned from #hash. Returning the LPI itself is best general approach if no reason can be found to constrain the value. It comes down to the questions: Is there a need to constrain the value returned from #hash? Are there even more efficient ways to return constrained values? Paul Baumann IntercontinentalExchange | ICE 2100 RiverEdge Pkwy | 5th Floor | Atlanta, GA 30328 Tel: 770.738.2137 | Fax: 770.951.1307 | Cel: 505.780.1470 [hidden email] -----Original Message----- From: [hidden email] [mailto:[hidden email]] Sent: Thursday, September 14, 2006 8:46 PM To: [hidden email] Cc: [hidden email]; Paul Baumann Subject: Re: [bug] Integer>>hash I looked at using self bitAnd: (SmallInteger maxVal bitShift: -1) + (self lastDigit bitShift: 8) as a hash function and it looks ok. here are some timings. hash is the current nteger>>hash. speedOldHash is the current Integer has implemented as fast as I can see in vanilla Smalltalk; essentially digitlength is made a primitive and lastDigit is inlined. newHash is (SmallInteger maxVal bitShift: -1) + (self lastDigit bitShift: 8) with lastDigit inlined, i.e. (self bitAnd: (SmallInteger maxVal bitShift: -1)) + ((self digitAt: self basicSize) bitShift: 8) The timing script collects all large integers, sees how many different values are prodeuced and tomes the various hash functions. A send of #class is used as the overhead measurement case and its time s subtraced when ratios are computed. (| insts r times | insts := LargeInteger allGeneralInstances asArray. times := Dictionary with: #class -> 0 with: #hash -> 0 with: #speedOldHash -> 0 with: #newHash -> 0. r := 1000. (1 to: 10) do: [:n| times at: #class put: (times at: #class) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) class]]]). times at: #hash put: (times at: #hash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) hash]]]). times at: #speedOldHash put: (times at: #speedOldHash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) speedOldHash]]]). times at: #newHash put: (times at: #newHash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) newHash]]])]. insts size -> times -> (#(hash speedOldHash newHash) collect: [:sym| (times at: sym) -> asDouble - (times at: #class) / ((times at: #hash) - (times at: -> #class))]) (insts collect: [:li| li hash]) asSet size (insts collect: -> [:li| li speedOldHash]) asSet size (insts collect: [:li| li newHash]) -> asSet size ((insts collect: [:li| li newHash]) asSet size asDouble / -> (insts collect: [:li| li hash]) asSet size)) The results in my mal imager on our mondo Opteron server are: 14164 ->Dictionary (#class->2880200 #speedOldHash->7130494 #hash->11650808 ->#newHash->25181745 ) #(1.0d 0.48460654039036d 2.5427592933124d) ->1203 ->1203 ->14055 ->11.683291770574d i.e. the base case of looping sending lass takes 2.88 seconds. The original hash takes 11.65 seconds, the new hash 25.18 seconds. The original hash produces only 1203 values from 14164 integers whereas the new hash provides 14055. The bottom line is that the new hash is two and a half times slower (5 times slower than a sped-up implementation) but (albeit with a small sample size) it collapses the space of hash values by (14164-14055)/141.64 = 0.77% whereas the current hash function collapses it by (14164-1203)/141.64 = 91.51%. Paul, what was your new hash function and what realistic measurements do you have? If yours differs markedly from mine could you compare the two in a realistic setting? I'll reply to your message tmorow. The missus is banging on the ceiling; its time for me to go upstairs and help with the kids :) --- Eliot Miranda ,,,^..^,,, mailto:[hidden email] VisualWorks Engineering, Cincom Smalltalk: scene not herd Tel +1 408 216 4581 3350 Scott Blvd, Bldg 36 Suite B, Santa Clara, CA 95054 USA Fax +1 408 216 4500 -------------------------------------------------------- This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired. |
Re: [bug] Integer>>hash
|
|
RE: [bug] Integer>>hash
|
|
RE: [bug] Integer>>hash
|
|
Re: [bug] Integer>>hash
|
|
Re: [bug] Integer>>hash
|
|
Re: [bug] Integer>>hash
|
|
In reply to this post by Paul Baumann
Dennis Smith <[hidden email]> wrote:
| I pulled in the attached patch -- should there not be an override of | "newHash" | in SmallInteger (if anyone is going to use the message "newHash") -- so | it can just return "self"?? (for speed). No, Dennis. newHash is simply for testing purposes. One wuld use newHash to compare the performance of the new algorithm wth the current one. Once convinced one wanted to migrate one would rename newHash to hash, relacing the old definition. You'll also need o rehash the system. So you could use teh attached, which is an as-et-unreviewed patch and hence unofficial and not guaranteed to get ito the product at all. Use at your own risk... | [hidden email] wrote: | > I looked at using self bitAnd: (SmallInteger maxVal bitShift: -1) + (self lastDigit bitShift: 8) as a hash function and it looks ok. here are some timings. | > | > hash is the current nteger>>hash. | > | > speedOldHash is the current Integer has implemented as fast as I can see in vanilla Smalltalk; essentially digitlength is made a primitive and lastDigit is inlined. | > | > newHash is (SmallInteger maxVal bitShift: -1) + (self lastDigit bitShift: 8) with lastDigit inlined, i.e. | > (self bitAnd: (SmallInteger maxVal bitShift: -1)) + ((self digitAt: self basicSize) bitShift: 8) | > | > The timing script collects all large integers, sees how many different values are prodeuced and tomes the various hash functions. A send of #class is used as the overhead measurement case and its time s subtraced when ratios are computed. | > | > (| insts r times | | > insts := LargeInteger allGeneralInstances asArray. | > times := Dictionary with: #class -> 0 with: #hash -> 0 with: #speedOldHash -> 0 with: #newHash -> 0. | > r := 1000. | > (1 to: 10) do: | > [:n| | > times at: #class put: (times at: #class) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) class]]]). | > times at: #hash put: (times at: #hash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) hash]]]). | > times at: #speedOldHash put: (times at: #speedOldHash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) speedOldHash]]]). | > times at: #newHash put: (times at: #newHash) + (Time microsecondsToRun: [r timesRepeat: [1 to: insts size do: [:i| (insts at: i) newHash]]])]. | > insts size | > -> times | > -> (#(hash speedOldHash newHash) collect: [:sym| (times at: sym) asDouble - (times at: #class) / ((times at: #hash) - (times at: #class))]) | > -> (insts collect: [:li| li hash]) asSet size | > -> (insts collect: [:li| li speedOldHash]) asSet size | > -> (insts collect: [:li| li newHash]) asSet size | > -> ((insts collect: [:li| li newHash]) asSet size asDouble / (insts collect: [:li| li hash]) asSet size)) | > | > The results in my mal imager on our mondo Opteron server are: | > | > 14164 | > ->Dictionary (#class->2880200 #speedOldHash->7130494 #hash->11650808 #newHash->25181745 ) | > ->#(1.0d 0.48460654039036d 2.5427592933124d) | > ->1203 | > ->1203 | > ->14055 | > ->11.683291770574d | > | > i.e. the base case of looping sending lass takes 2.88 seconds. The original hash takes 11.65 seconds, the new hash 25.18 seconds. The original hash produces only 1203 values from 14164 integers whereas the new hash provides 14055. | > | > The bottom line is that the new hash is two and a half times slower (5 times slower than a sped-up implementation) but (albeit with a small sample size) it collapses the space of hash values by (14164-14055)/141.64 = 0.77% whereas the current hash function collapses it by (14164-1203)/141.64 = 91.51%. | > | > Paul, what was your new hash function and what realistic measurements do you have? If yours differs markedly from mine could you compare the two in a realistic setting? | > | > I'll reply to your message tmorow. The missus is banging on the ceiling; its time for me to go upstairs and help with the kids :) | > --- | > Eliot Miranda ,,,^..^,,, mailto:[hidden email] | > VisualWorks Engineering, Cincom Smalltalk: scene not herd Tel +1 408 216 4581 | > 3350 Scott Blvd, Bldg 36 Suite B, Santa Clara, CA 95054 USA Fax +1 408 216 4500 | > | > | -- | Dennis Smith [hidden email] | Cherniak Software Development Corporation +1 905.771.7011 | 400-10 Commerce Valley Dr E Fax: +1 905.771.6288 | Thornhill, ON Canada L3T 7N7 http://www.CherniakSoftware.com --- Eliot Miranda ,,,^..^,,, mailto:[hidden email] VisualWorks Engineering, Cincom Smalltalk: scene not herd Tel +1 408 216 4581 3350 Scott Blvd, Bldg 36 Suite B, Santa Clara, CA 95054 USA Fax +1 408 216 4500 |
Re: [bug] Integer>>hash
|
|
Re: [bug] Integer>>hash
|
|
Re: [bug] Integer>>hash
|
|
| Free forum by Nabble | Edit this page |