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

Eliot Miranda eliot.miranda at gmail.com
Sat Aug 8 16:47:56 UTC 2020


Hi Levente,


> On Aug 7, 2020, at 5:07 PM, Levente Uzonyi <leves at caesar.elte.hu> wrote:
> 
> Hi Eliot,
> 
> If performance matters, I've got two alternative implementations.

Performance isn’t that big a deal.  But something told me that the indexOf: approach sux :-)

> 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 ]

When I tested this it was slower.  I tested it on ByteArrays >= 256 bytes in length that were less than 50% zeros.  So let’s not go this way.

> 
> 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 ]

That’s neat, I’ll remember the technique.  But what we have is more straight forward.

> 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