The Trunk: Collections-eem.746.mcz

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

The Trunk: Collections-eem.746.mcz

commits-2
Eliot Miranda uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-eem.746.mcz

==================== Summary ====================

Name: Collections-eem.746
Author: eem
Time: 18 April 2017, 2:10:45.148995 pm
UUID: 8d9adaca-1401-4323-974f-1aed16ae3688
Ancestors: Collections-eem.745

Nuke the pointless override of ByteSString class>>stringHash:initialHash: in ByteSymbol class.  Rewrite the non-byte version to use the hashMultiply primitive.

=============== Diff against Collections-eem.745 ===============

Item was removed:
- ----- Method: ByteSymbol class>>stringHash:initialHash: (in category 'primitives') -----
- stringHash: aString initialHash: speciesHash
- ^ByteString stringHash: aString initialHash: speciesHash!

Item was changed:
  ----- Method: String class>>stringHash:initialHash: (in category 'primitives') -----
  stringHash: aString initialHash: speciesHash
+ "Answer the hash of a byte-indexed string, using speciesHash as the initial value.
+ See SmallInteger>>hashMultiply."
+ | hash |
-
- | stringSize hash low |
- stringSize := aString size.
  hash := speciesHash bitAnd: 16r0FFFFFFF.
+ 1 to: aString size do:
+ [:pos |
+ hash := (hash + (aString basicAt: pos)) hashMultiply].
+ ^hash!
- 1 to: stringSize do: [ :pos |
- hash := hash + (aString basicAt: pos).
- "Begin hashMultiply"
- low := hash bitAnd: 16383.
- hash := (16r260D * low + ((16r260D * (hash // 16384) + (16r0065 * low) bitAnd: 16383) * 16384)) bitAnd: 16r0FFFFFFF ].
- ^hash.
-
-
- !


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: The Trunk: Collections-eem.746.mcz

Levente Uzonyi
On Tue, 18 Apr 2017, [hidden email] wrote:

> Eliot Miranda uploaded a new version of Collections to project The Trunk:
> http://source.squeak.org/trunk/Collections-eem.746.mcz
>
> ==================== Summary ====================
>
> Name: Collections-eem.746
> Author: eem
> Time: 18 April 2017, 2:10:45.148995 pm
> UUID: 8d9adaca-1401-4323-974f-1aed16ae3688
> Ancestors: Collections-eem.745
>
> Nuke the pointless override of ByteSString class>>stringHash:initialHash: in ByteSymbol class.  Rewrite the non-byte version to use the hashMultiply primitive.

Do you mean that the Smalltalk code is as quick as the primitive?
Because without the VM changes, the primitive is 3-4 times quicker than

  hash := speciesHash bitAnd: 16rFFFFFFF.
  1 to: aString size do: [:pos |
  hash := hash + (aString basicAt: pos) * 1664525 bitAnd: 16rFFFFFFF ].
  ^ hash

So, I presume such loop will still be slower even with the primitive for
#hashMultiply.

Levente

>
> =============== Diff against Collections-eem.745 ===============
>
> Item was removed:
> - ----- Method: ByteSymbol class>>stringHash:initialHash: (in category 'primitives') -----
> - stringHash: aString initialHash: speciesHash
> - ^ByteString stringHash: aString initialHash: speciesHash!
>
> Item was changed:
>  ----- Method: String class>>stringHash:initialHash: (in category 'primitives') -----
>  stringHash: aString initialHash: speciesHash
> + "Answer the hash of a byte-indexed string, using speciesHash as the initial value.
> + See SmallInteger>>hashMultiply."
> + | hash |
> -
> - | stringSize hash low |
> - stringSize := aString size.
>   hash := speciesHash bitAnd: 16r0FFFFFFF.
> + 1 to: aString size do:
> + [:pos |
> + hash := (hash + (aString basicAt: pos)) hashMultiply].
> + ^hash!
> - 1 to: stringSize do: [ :pos |
> - hash := hash + (aString basicAt: pos).
> - "Begin hashMultiply"
> - low := hash bitAnd: 16383.
> - hash := (16r260D * low + ((16r260D * (hash // 16384) + (16r0065 * low) bitAnd: 16383) * 16384)) bitAnd: 16r0FFFFFFF ].
> - ^hash.
> -
> -
> - !

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: The Trunk: Collections-eem.746.mcz

Eliot Miranda-2
Hi Levente,

On Tue, Apr 18, 2017 at 3:13 PM, Levente Uzonyi <[hidden email]> wrote:
On Tue, 18 Apr 2017, [hidden email] wrote:

Eliot Miranda uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-eem.746.mcz

==================== Summary ====================

Name: Collections-eem.746
Author: eem
Time: 18 April 2017, 2:10:45.148995 pm
UUID: 8d9adaca-1401-4323-974f-1aed16ae3688
Ancestors: Collections-eem.745

Nuke the pointless override of ByteSString class>>stringHash:initialHash: in ByteSymbol class.  Rewrite the non-byte version to use the hashMultiply primitive.

Do you mean that the Smalltalk code is as quick as the primitive?

No.  I mean that the non-primitive version for WideString should use the hashMultiply primitive, not the decomposed non-primitive hashMultiply.
 
Because without the VM changes, the primitive is 3-4 times quicker than

        hash := speciesHash bitAnd: 16rFFFFFFF.
        1 to: aString size do: [:pos |
                hash := hash + (aString basicAt: pos) * 1664525 bitAnd: 16rFFFFFFF ].
        ^ hash

So, I presume such loop will still be slower even with the primitive for #hashMultiply.

That's right.  But
hash := (hash + (aString basicAt: pos)) hashMultiply
is much faster than
hash := hash + (aString basicAt: pos).
"Begin hashMultiply"
low := hash bitAnd: 16383.
hash := (16r260D * low + ((16r260D * (hash bitShift: -14) + (16r0065 * low) bitAnd: 16383) * 16384)) bitAnd: 16r0FFFFFFF.

in the latest VMs which have a machine code primitive for hashMultiply.  Im the measurements I posted yesterday they're twice as fast.
 


Levente



=============== Diff against Collections-eem.745 ===============

Item was removed:
- ----- Method: ByteSymbol class>>stringHash:initialHash: (in category 'primitives') -----
- stringHash: aString initialHash: speciesHash
-       ^ByteString stringHash: aString initialHash: speciesHash!

Item was changed:
 ----- Method: String class>>stringHash:initialHash: (in category 'primitives') -----
 stringHash: aString initialHash: speciesHash
+       "Answer the hash of a byte-indexed string, using speciesHash as the initial value.
+        See SmallInteger>>hashMultiply."
+       | hash |
- -     | stringSize hash low |
-       stringSize := aString size.
        hash := speciesHash bitAnd: 16r0FFFFFFF.
+       1 to: aString size do:
+               [:pos |
+               hash := (hash + (aString basicAt: pos)) hashMultiply].
+       ^hash!
-       1 to: stringSize do: [ :pos |
-               hash := hash + (aString basicAt: pos).
-               "Begin hashMultiply"
-               low := hash bitAnd: 16383.
-               hash := (16r260D * low + ((16r260D * (hash // 16384) + (16r0065 * low) bitAnd: 16383) * 16384)) bitAnd: 16r0FFFFFFF ].
-       ^hash.
- - - !




--
_,,,^..^,,,_
best, Eliot


Loading...