[squeak-dev] The Trunk: Collections-eem.907.mcz

Levente Uzonyi leves at caesar.elte.hu
Sat Aug 8 00:07:10 UTC 2020


Hi Eliot,

If performance matters, I've got two alternative implementations.
Both are about 1.2x faster than yours and are based on lookup tables.
The first one uses #digitValue which uses Character's "built-in" 
DigitValues table:

readHexFrom: aStream
 	"Initialize the receiver from a hexadecimal string representation"

 	1 to: self size do: [ :i |
 		| c v1 v2 |
 		((c := aStream next) asInteger > 102 "$f asInteger"
 			or: [ (v1 := c digitValue) < 0
 			or: [ v1 > 15
 			or: [ (c := aStream next) asInteger > 102 "$f asInteger"
 			or: [ (v2 := c digitValue) < 0
 			or: [ v2 > 15 ] ] ] ] ])
 			ifTrue: [ ^self error: 'Hex digit expected' ].
 		self at: i put: (v1 bitShift: 4) + v2 ]

The second one uses a non-minimal perfect hash table with an extremely 
simple hash function:

readHexFrom: aStream
 	"Initialize the receiver from a hexadecimal string representation"

 	| keys values |
 	keys :=  #[0 65 66 67 68 69 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 97 98 99 100 101 102 0 0 0 0 0 0 0 0 0 48 49 50 51 52 53 54 55 56 57 0 0 0 0 0 0].
 	values :=  #[0 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0].
 	1 to: self size do: [ :i |
 		| c index v1 v2 |
 		c := aStream next asInteger.
 		index := (c bitAnd: 63) + 1.
 		(keys at: index) = c ifFalse: [ ^self error: 'Hex digit expected' ].
 		v1 := values at: index.
 		c := aStream next asInteger.
 		index := (c bitAnd: 63) + 1.
 		(keys at: index) = c ifFalse: [ ^self error: 'Hex digit expected' ].
 		v2 := values at: index.
 		self at: i put: (v1 bitShift: 4) + v2 ]


Levente

On Thu, 6 Aug 2020, commits at source.squeak.org wrote:

> Eliot Miranda uploaded a new version of Collections to project The Trunk:
> http://source.squeak.org/trunk/Collections-eem.907.mcz
>
> ==================== Summary ====================
>
> Name: Collections-eem.907
> Author: eem
> Time: 6 August 2020, 12:51:46.481296 pm
> UUID: 4ea594f7-b7bf-4d48-9e7e-2e7cb3af5e70
> Ancestors: Collections-mt.906
>
> 2.7x faster ByteArray>>readHexFrom:
>
> =============== Diff against Collections-mt.906 ===============
>
> Item was changed:
>  ----- Method: ByteArray>>readHexFrom: (in category 'initialize') -----
>  readHexFrom: aStream
>  	"Initialize the receiver from a hexadecimal string representation"
> + 
> + 	1 to: self size do:
> + 		[:i| | n v1 v2 |
> + 		 n := aStream next asInteger.
> + 		 v1 := n > 57						"$9 asInteger = 57"
> + 				ifTrue:
> + 					[n > 96					"$a asInteger 97"
> + 						ifTrue: [n - 87]
> + 						ifFalse: [n > 64		"$A asInteger = 65"
> + 								ifTrue: [n - 55]
> + 								ifFalse: [-1]]] 
> + 			 	ifFalse: [n - 48].				"$0 asInteger = 48"
> + 		 (v1 between: 0 and: 15) ifFalse: [^self error: 'Hex digit expected'].
> + 		 n := aStream next asInteger.
> + 		 v2 := n > 57						"$9 asInteger = 57"
> + 				ifTrue:
> + 					[n > 96					"$a asInteger 97"
> + 						ifTrue: [n - 87]
> + 						ifFalse: [n > 64		"$A asInteger = 65"
> + 								ifTrue: [n - 55]
> + 								ifFalse: [-1]]]
> + 			 	ifFalse: [n - 48].				"$0 asInteger = 48"
> + 		(v2 between: 0 and: 15) ifFalse: [^self error: 'Hex digit expected'].
> + 		self at: i put: (v1 bitShift: 4) + v2]
> + 
> + 	"Proof that our filter selects only hexadecimal characters:
> + 	(0 to: 255)
> + 		select:
> + 			[:n|
> + 			(n > 57
> + 				ifTrue:
> + 					[n > 96 
> + 						ifTrue: [n - 87]
> + 						ifFalse: [n > 64
> + 								ifTrue: [n - 55]
> + 								ifFalse: [-1]]]
> + 			 	ifFalse: [n - 48]) between: 0 and: 15]
> + 		thenCollect:
> + 			[:n| Character value: n]"!
> - 	| map v ch value |
> - 	map := '0123456789abcdefABCDEF'.
> - 	1 to: self size do:[:i|
> - 		ch := aStream next.
> - 		v := (map indexOf: ch) - 1.
> - 		((v between: 0 and: 15) or: [((v:= v - 6) between: 0 and: 15)]) ifFalse:[^self error: 'Hex digit expected'].
> - 		value := v bitShift: 4.
> - 		ch := aStream next.
> - 		v := (map indexOf: ch) - 1.
> - 		((v between: 0 and: 15) or: [((v:= v - 6) between: 0 and: 15)]) ifFalse:[^self error: 'Hex digit expected'].
> - 		value := value + v.
> - 		self at: i put: value.
> - 	].
> - !


More information about the Squeak-dev mailing list