FloatConstants?
Locked
12
12
 
|
Implementing isFinite by looking at the exponent field would avoid the
creation of a transient floating point number. On 12/21/14 13:11 , Eliot Miranda wrote: > Hi Levente, > > please rewrite using a temp to hold the raw bits, a class var to hold the float array and hexadecimal. Then one can understand much easier. Also is inlining isFinite that important for performance? > > rawBits := FloatArrayBuffer at: 1 put: self; basicAt: 1 > etc... > > > Eliot (phone hence not writing the full method) > > On Dec 20, 2014, at 7:27 PM, Levente Uzonyi <[hidden email]> wrote: > >> On Sat, 20 Dec 2014, Chris Muller wrote: >> >>> On Fri, Dec 19, 2014 at 4:01 PM, Louis LaBrunda >>> <[hidden email]> wrote: >>>> Hi Chris, >>>> >>>> Is this any faster? >>>> >>>> Float>>#hashKey32 >>>> >>>> ^self isFinite ifTrue: [ >>>> self negative ifTrue: [4286578688 - self asIEEE32BitWord] ifFalse: [self >>>> asIEEE32BitWord + 2147483651] >>>> ] ifFalse: [self negative ifTrue: [0] ifFalse: [4294967294]]. >>> >>> About the same, but I think I like your code better. Thanks. >> >> Dave has already suggested to use a FloatArray for conversion instead of #asIEEE32BitWord. We use this technique in various network protocol implementations, and it works great. >> >> Here's a significantly faster, optimized version: >> >> hashKey32: aFloatArray >> >> self - self = 0.0 ifTrue: [ >> self < 0.0 ifTrue: [ ^4286578688 - (aFloatArray at: 1 put: self; basicAt: 1) ]. >> ^2147483651 + (aFloatArray at: 1 put: self; basicAt: 1) ]. >> self < 0.0 ifTrue: [ ^0 ]. >> ^4294967294 >> >> The argument is any FloatArray instance with at least one slot. >> >> >> Levente >> >> > > |
|
|
In reply to this post by Levente Uzonyi-2
On 22.12.2014, at 00:13, Levente Uzonyi <[hidden email]> wrote:
> > ConverterFloatArray at: 1 put: self; basicAt: 1. Any reason not to use this in #asIEEE32BitWord? Endianness? Arch-dependency? I see, it's not thread-safe. This would be: (FloatArray new: 1) at: 1 put: self; basicAt: 1. Might still be faster? - Bert - |
smime.p7s (5K) |
|
On Mon, Dec 22, 2014 at 3:59 AM, Bert Freudenberg <[hidden email]> wrote:
> On 22.12.2014, at 00:13, Levente Uzonyi <[hidden email]> wrote: >> >> ConverterFloatArray at: 1 put: self; basicAt: 1. > > Any reason not to use this in #asIEEE32BitWord? Endianness? Arch-dependency? > > I see, it's not thread-safe. This would be: > > (FloatArray new: 1) at: 1 put: self; basicAt: 1. > > Might still be faster? Yes. Since creation of a one-element FloatArray every time did not adversely affect performance of Levente's too significantly (only 3.7X instead of 4.0X faster), I decided it was worth the cost of the allocation than to worry about concurrency. So I ended up with Levente's latest except I cannot risk a calculation ending up -0.0, so I have to account for it too. And, NaN too. Thus: hashKey32 | bits | self = NegativeInfinity ifTrue: [ ^ 0 ]. self = Infinity ifTrue: [ ^ 4294967294 ]. self = NaN ifTrue: [ ^ 4294967295 ]. self = NegativeZero ifTrue: [ ^ 2147483651 ]. bits := (FloatArray new: 1) at: 1 put: self; basicAt: 1. self < 0.0 ifTrue: [ ^ 4286578688 - bits ]. ^ 2147483651 + bits Since there are not a full 32-bits worth of IEEE 32-bit floats (e.g., several thousand convert to NaN), it might be wise to move +Infinity and NaN _down_ a bit from the very maximum, for better continuity between the float and integer number lines, or for potential future special-case needs..? In any case, I wanted to at least see if what we have, above, works for every 32-bit IEEE float. To verify that, I enumerated all Floats in numerical order from -Infinity to +Infinity by creating them via #fromIEEE32BitFloat: from the appropriate ranges. It hit a snag at 2151677948. Check this out: | this next | this := Float fromIEEE32Bit: 2151677949. next := Float fromIEEE32Bit: 2151677948. self assert: next > this ; assert: ((FloatArray new: 1) at: 1 put: (next); basicAt: 1) > ((FloatArray new: 1) at: 1 put: (this); basicAt: 1) As I thought, the representations between IEEE floats and FloatArray floats are different-enough that their precisions align differently onto the 32-bit map for these two floats. IEEE's are precise-enough to distinguish these two floats, FloatArray representations are not. That these guys are considered "equal" by the FloatArray is actually good enough for my indexing requirement, but now I'm looking at the prim-fail code for FloatArray: at: index <primitive: 'primitiveAt' module: 'FloatArrayPlugin'> ^Float fromIEEE32Bit: (self basicAt: index) If this or the #at:put: primitive were to ever fail on the storage (at:put:) exclusive-or the access (at:) side, then it appears FloatArray itself would retrieve a value different than was stored..! |
|
|
Hi Chris,
On Tue, Dec 23, 2014 at 12:50 PM, Chris Muller <[hidden email]> wrote:
FloatArray basicNew: 1 will be a little bit faster. Please use hex to make the layout clear. Since there are not a full 32-bits worth of IEEE 32-bit floats (e.g., Chris, FloatArray stores 32-bit ieee 754 single-precision floats, Float represents 64-bit ieee 754 double-precision floats. They look like this: single-precision: sign, 8-bit exponent, 23 bit mantissa double-precision: sign, 11-bit exponent, 52 bit mantissa So if you assign a large Float to a Float array it will map to Infinity: ((FloatArray new: 1) at: 1 put: 1.0e238; at: 1) => Infinity and if you assign a small one it will map to zero: ((FloatArray new: 1) at: 1 put: 1.0e-238; at: 1) => 0.0 That these guys are considered "equal" by the FloatArray is actually But that happens whenever you store a double that cannot be represented as a 32-bit float. That;s exactly what we're doing here is mapping 64-bit floats to 32-bit floats so we expect to retrieve different values than those stored most of the time, on average 2^32-1/(2^32). Only 1/(2^32) of the double precision floats are exactly representable in 32-bits. best,
Eliot |
|
|
In reply to this post by Chris Muller-3
Chris, this is a case of gradual underflow, and it seems like it is not handled correctly in Float class>>fromIEEE32Bit: . Since the method has my initials, I'll try to sort out what the mess is...2014-12-23 21:50 GMT+01:00 Chris Muller <[hidden email]>:
|
|
|
OK, I got it, the mantissa was not shifted correctly in case of underflow... I'll publish as soon as I can get an updated trunk. 2014-12-23 22:58 GMT+01:00 Nicolas Cellier <[hidden email]>:
|
|
|
OK Chris, it should be corrected now, but your assertion is false... Your floats are negative, but FloatArray basicAt: is considering unsigned 32 bit ints... So the inequality must be swapped in this case...2014-12-23 23:10 GMT+01:00 Nicolas Cellier <[hidden email]>:
|
|
|
In reply to this post by Chris Muller-3
I don't know how you measured the speedup, but I got 8-12x improvement for
finite numbers. By creating a new FloatArray, the speedup decreases to 6-9x. Levente On Tue, 23 Dec 2014, Chris Muller wrote: > On Mon, Dec 22, 2014 at 3:59 AM, Bert Freudenberg <[hidden email]> wrote: >> On 22.12.2014, at 00:13, Levente Uzonyi <[hidden email]> wrote: >>> >>> ConverterFloatArray at: 1 put: self; basicAt: 1. >> >> Any reason not to use this in #asIEEE32BitWord? Endianness? Arch-dependency? >> >> I see, it's not thread-safe. This would be: >> >> (FloatArray new: 1) at: 1 put: self; basicAt: 1. >> >> Might still be faster? > > Yes. Since creation of a one-element FloatArray every time did not > adversely affect performance of Levente's too significantly (only 3.7X > instead of 4.0X faster), I decided it was worth the cost of the > allocation than to worry about concurrency. So I ended up with > Levente's latest except I cannot risk a calculation ending up -0.0, so > I have to account for it too. And, NaN too. Thus: > > hashKey32 > | bits | > self = NegativeInfinity ifTrue: [ ^ 0 ]. > self = Infinity ifTrue: [ ^ 4294967294 ]. > self = NaN ifTrue: [ ^ 4294967295 ]. > self = NegativeZero ifTrue: [ ^ 2147483651 ]. > bits := (FloatArray new: 1) at: 1 put: self; basicAt: 1. > self < 0.0 ifTrue: [ ^ 4286578688 - bits ]. > ^ 2147483651 + bits > > Since there are not a full 32-bits worth of IEEE 32-bit floats (e.g., > several thousand convert to NaN), it might be wise to move +Infinity > and NaN _down_ a bit from the very maximum, for better continuity > between the float and integer number lines, or for potential future > special-case needs..? > > In any case, I wanted to at least see if what we have, above, works > for every 32-bit IEEE float. To verify that, I enumerated all Floats > in numerical order from -Infinity to +Infinity by creating them via > #fromIEEE32BitFloat: from the appropriate ranges. > > It hit a snag at 2151677948. Check this out: > > | this next | > this := Float fromIEEE32Bit: 2151677949. > next := Float fromIEEE32Bit: 2151677948. > self > assert: next > this ; > assert: ((FloatArray new: 1) at: 1 put: (next); basicAt: 1) >> ((FloatArray new: 1) at: 1 put: (this); basicAt: 1) > > As I thought, the representations between IEEE floats and FloatArray > floats are different-enough that their precisions align differently > onto the 32-bit map for these two floats. IEEE's are precise-enough > to distinguish these two floats, FloatArray representations are not. > > That these guys are considered "equal" by the FloatArray is actually > good enough for my indexing requirement, but now I'm looking at the > prim-fail code for FloatArray: > > at: index > <primitive: 'primitiveAt' module: 'FloatArrayPlugin'> > ^Float fromIEEE32Bit: (self basicAt: index) > > If this or the #at:put: primitive were to ever fail on the storage > (at:put:) exclusive-or the access (at:) side, then it appears > FloatArray itself would retrieve a value different than was stored..! > > |
|
|
Here is what I used to measure:
| rand | rand := Random seed: 12345. [ (rand next ) hashKey32 ] bench This baseline version reports '902,000 per second.' hashKey32 self = NegativeInfinity ifTrue: [ ^ 0 ]. self = Infinity ifTrue: [ ^ 4294967294 ]. self = NaN ifTrue: [ ^ 4294967295 ]. "Identity check to allow a distinction between -0.0 and +0.0." self == NegativeZero ifTrue: [ ^ 2147483650 ]. "Smallest to largest negative IEEE 32-bit floats range from (2147483649 to: 4286578687), so invert that range." self negative ifTrue: [ ^ ("4286578687" 4286578688 - self asIEEE32BitWord) "+ 1" ]. "We're positive. IEEE 32-bit positives range from (0 to: 2139095039)." ^ self asIEEE32BitWord + 2147483651 Switching it to use FloatArray reports '3,530,000 per second.' hashKey32 | bits | self = NegativeInfinity ifTrue: [ ^ 0 ]. self = Infinity ifTrue: [ ^ 4294967294 ]. self = NaN ifTrue: [ ^ 4294967295 ]. self = NegativeZero ifTrue: [ ^ 2147483651 ]. bits := (FloatArray basicNew: 1) at: 1 put: self; basicAt: 1. self < 0.0 ifTrue: [ ^ 4286578688 - bits ]. ^ 2147483651 + bits Do you think the difference is less pronounced than yours due to my going through Random #next? On Tue, Dec 23, 2014 at 5:52 PM, Levente Uzonyi <[hidden email]> wrote: > I don't know how you measured the speedup, but I got 8-12x improvement for > finite numbers. By creating a new FloatArray, the speedup decreases to 6-9x. > > Levente > > > On Tue, 23 Dec 2014, Chris Muller wrote: > >> On Mon, Dec 22, 2014 at 3:59 AM, Bert Freudenberg <[hidden email]> >> wrote: >>> >>> On 22.12.2014, at 00:13, Levente Uzonyi <[hidden email]> wrote: >>>> >>>> >>>> ConverterFloatArray at: 1 put: self; basicAt: 1. >>> >>> >>> Any reason not to use this in #asIEEE32BitWord? Endianness? >>> Arch-dependency? >>> >>> I see, it's not thread-safe. This would be: >>> >>> (FloatArray new: 1) at: 1 put: self; basicAt: 1. >>> >>> Might still be faster? >> >> >> Yes. Since creation of a one-element FloatArray every time did not >> adversely affect performance of Levente's too significantly (only 3.7X >> instead of 4.0X faster), I decided it was worth the cost of the >> allocation than to worry about concurrency. So I ended up with >> Levente's latest except I cannot risk a calculation ending up -0.0, so >> I have to account for it too. And, NaN too. Thus: >> >> hashKey32 >> | bits | >> self = NegativeInfinity ifTrue: [ ^ 0 ]. >> self = Infinity ifTrue: [ ^ 4294967294 ]. >> self = NaN ifTrue: [ ^ 4294967295 ]. >> self = NegativeZero ifTrue: [ ^ 2147483651 ]. >> bits := (FloatArray new: 1) at: 1 put: self; basicAt: 1. >> self < 0.0 ifTrue: [ ^ 4286578688 - bits ]. >> ^ 2147483651 + bits >> >> Since there are not a full 32-bits worth of IEEE 32-bit floats (e.g., >> several thousand convert to NaN), it might be wise to move +Infinity >> and NaN _down_ a bit from the very maximum, for better continuity >> between the float and integer number lines, or for potential future >> special-case needs..? >> >> In any case, I wanted to at least see if what we have, above, works >> for every 32-bit IEEE float. To verify that, I enumerated all Floats >> in numerical order from -Infinity to +Infinity by creating them via >> #fromIEEE32BitFloat: from the appropriate ranges. >> >> It hit a snag at 2151677948. Check this out: >> >> | this next | >> this := Float fromIEEE32Bit: 2151677949. >> next := Float fromIEEE32Bit: 2151677948. >> self >> assert: next > this ; >> assert: ((FloatArray new: 1) at: 1 put: (next); basicAt: 1) >>> >>> ((FloatArray new: 1) at: 1 put: (this); basicAt: 1) >> >> >> As I thought, the representations between IEEE floats and FloatArray >> floats are different-enough that their precisions align differently >> onto the 32-bit map for these two floats. IEEE's are precise-enough >> to distinguish these two floats, FloatArray representations are not. >> >> That these guys are considered "equal" by the FloatArray is actually >> good enough for my indexing requirement, but now I'm looking at the >> prim-fail code for FloatArray: >> >> at: index >> <primitive: 'primitiveAt' module: 'FloatArrayPlugin'> >> ^Float fromIEEE32Bit: (self basicAt: index) >> >> If this or the #at:put: primitive were to ever fail on the storage >> (at:put:) exclusive-or the access (at:) side, then it appears >> FloatArray itself would retrieve a value different than was stored..! >> >> > |
|
|
In reply to this post by Nicolas Cellier
On Tue, Dec 23, 2014 at 5:08 PM, Nicolas Cellier
<[hidden email]> wrote: > OK Chris, it should be corrected now, This time it worked! #hashKey32 passed for all 32-bit Floats. Thank you!! > but your assertion is false... > Your floats are negative, but FloatArray basicAt: is considering unsigned 32 > bit ints... So the inequality must be swapped in this case... Indeed. As you know I was actually testing #hashKey32 and so that's what I get for cut-n-pasting-n-tweaking. Thanks again. |
|
|
> Thanks again.
.. and to everyone in this thread too. :) |
|
|
In reply to this post by Chris Muller-3
I see many reasons why the difference is smaller:
- you're also measuring the generation of the input - this creates new numbers and triggers GC more often - you're only benchmarking numbers between 0 and 1. #asIEEE32BitWord is a lot slower for negative values - you're using #bench, which has high overhead - you are comparing different versions than I did About your modifications: self = NaN will always return false, so that comparison is wrong. self == NegativeZero will almost never be true (try -0.0 == Float negativeZero). Use #= instead. After trying to understand what the code is about to do, I came to the conclusion that there's no reason to treat negative infinity and infinity separately. hashKey32 self > 0.0 ifTrue: [ ^16r80000003 + ((FloatArray basicNew: 1) at: 1 put: self; basicAt: 1) ]. self < 0.0 ifTrue: [ ^16rFF800000 - ((FloatArray basicNew: 1) at: 1 put: self; basicAt: 1) ]. self = self ifFalse: [ ^16rFFFFFFFF "NaN" ]. (self at: 1) = 0 ifTrue: [ ^16r80000003 "Zero" ]. ^16r7F800000 "Negative zero" Levente On Tue, 23 Dec 2014, Chris Muller wrote: > Here is what I used to measure: > > | rand | rand := Random seed: 12345. > [ (rand next ) hashKey32 ] bench > > This baseline version reports '902,000 per second.' > > hashKey32 > self = NegativeInfinity ifTrue: [ ^ 0 ]. > self = Infinity ifTrue: [ ^ 4294967294 ]. > self = NaN ifTrue: [ ^ 4294967295 ]. > "Identity check to allow a distinction between -0.0 and +0.0." > self == NegativeZero ifTrue: [ ^ 2147483650 ]. > "Smallest to largest negative IEEE 32-bit floats range from > (2147483649 to: 4286578687), so invert that range." > self negative ifTrue: [ ^ ("4286578687" 4286578688 - self > asIEEE32BitWord) "+ 1" ]. > "We're positive. IEEE 32-bit positives range from (0 to: > 2139095039)." > ^ self asIEEE32BitWord + 2147483651 > > Switching it to use FloatArray reports '3,530,000 per second.' > > hashKey32 > | bits | > self = NegativeInfinity ifTrue: [ ^ 0 ]. > self = Infinity ifTrue: [ ^ 4294967294 ]. > self = NaN ifTrue: [ ^ 4294967295 ]. > self = NegativeZero ifTrue: [ ^ 2147483651 ]. > bits := (FloatArray basicNew: 1) at: 1 put: self; basicAt: 1. > self < 0.0 ifTrue: [ ^ 4286578688 - bits ]. > ^ 2147483651 + bits > > Do you think the difference is less pronounced than yours due to my > going through Random #next? > > > On Tue, Dec 23, 2014 at 5:52 PM, Levente Uzonyi <[hidden email]> wrote: >> I don't know how you measured the speedup, but I got 8-12x improvement for >> finite numbers. By creating a new FloatArray, the speedup decreases to 6-9x. >> >> Levente >> >> >> On Tue, 23 Dec 2014, Chris Muller wrote: >> >>> On Mon, Dec 22, 2014 at 3:59 AM, Bert Freudenberg <[hidden email]> >>> wrote: >>>> >>>> On 22.12.2014, at 00:13, Levente Uzonyi <[hidden email]> wrote: >>>>> >>>>> >>>>> ConverterFloatArray at: 1 put: self; basicAt: 1. >>>> >>>> >>>> Any reason not to use this in #asIEEE32BitWord? Endianness? >>>> Arch-dependency? >>>> >>>> I see, it's not thread-safe. This would be: >>>> >>>> (FloatArray new: 1) at: 1 put: self; basicAt: 1. >>>> >>>> Might still be faster? >>> >>> >>> Yes. Since creation of a one-element FloatArray every time did not >>> adversely affect performance of Levente's too significantly (only 3.7X >>> instead of 4.0X faster), I decided it was worth the cost of the >>> allocation than to worry about concurrency. So I ended up with >>> Levente's latest except I cannot risk a calculation ending up -0.0, so >>> I have to account for it too. And, NaN too. Thus: >>> >>> hashKey32 >>> | bits | >>> self = NegativeInfinity ifTrue: [ ^ 0 ]. >>> self = Infinity ifTrue: [ ^ 4294967294 ]. >>> self = NaN ifTrue: [ ^ 4294967295 ]. >>> self = NegativeZero ifTrue: [ ^ 2147483651 ]. >>> bits := (FloatArray new: 1) at: 1 put: self; basicAt: 1. >>> self < 0.0 ifTrue: [ ^ 4286578688 - bits ]. >>> ^ 2147483651 + bits >>> >>> Since there are not a full 32-bits worth of IEEE 32-bit floats (e.g., >>> several thousand convert to NaN), it might be wise to move +Infinity >>> and NaN _down_ a bit from the very maximum, for better continuity >>> between the float and integer number lines, or for potential future >>> special-case needs..? >>> >>> In any case, I wanted to at least see if what we have, above, works >>> for every 32-bit IEEE float. To verify that, I enumerated all Floats >>> in numerical order from -Infinity to +Infinity by creating them via >>> #fromIEEE32BitFloat: from the appropriate ranges. >>> >>> It hit a snag at 2151677948. Check this out: >>> >>> | this next | >>> this := Float fromIEEE32Bit: 2151677949. >>> next := Float fromIEEE32Bit: 2151677948. >>> self >>> assert: next > this ; >>> assert: ((FloatArray new: 1) at: 1 put: (next); basicAt: 1) >>>> >>>> ((FloatArray new: 1) at: 1 put: (this); basicAt: 1) >>> >>> >>> As I thought, the representations between IEEE floats and FloatArray >>> floats are different-enough that their precisions align differently >>> onto the 32-bit map for these two floats. IEEE's are precise-enough >>> to distinguish these two floats, FloatArray representations are not. >>> >>> That these guys are considered "equal" by the FloatArray is actually >>> good enough for my indexing requirement, but now I'm looking at the >>> prim-fail code for FloatArray: >>> >>> at: index >>> <primitive: 'primitiveAt' module: 'FloatArrayPlugin'> >>> ^Float fromIEEE32Bit: (self basicAt: index) >>> >>> If this or the #at:put: primitive were to ever fail on the storage >>> (at:put:) exclusive-or the access (at:) side, then it appears >>> FloatArray itself would retrieve a value different than was stored..! >>> >>> >> > > |
|
|
On Wed, Dec 24, 2014 at 9:38 AM, Levente Uzonyi <[hidden email]> wrote:
> I see many reasons why the difference is smaller: > - you're also measuring the generation of the input > - this creates new numbers and triggers GC more often > - you're only benchmarking numbers between 0 and 1. #asIEEE32BitWord is a > lot slower for negative values > - you're using #bench, which has high overhead > - you are comparing different versions than I did > > About your modifications: > self = NaN will always return false, so that comparison is wrong. Doh! Thanks. I guess I burned myself again by that "invariant" that two identical objects can be considered equal.. I see you used self = self; is that better than an identity check against NaN? I guess its safer just in case some other NaN instance would be generated in the system? I've just always had an aversion to send #= to a Float and expect to get back true, but I guess if the arg is itself, it should be okay.. > self == NegativeZero will almost never be true (try -0.0 == Float > negativeZero). Oh wow. I had changed it to #== to avoid a different issue, but introduced this one..! > Use #= instead. > > After trying to understand what the code is about to do, I came to the > conclusion that there's no reason to treat negative infinity and > infinity separately. Yes! Something bugged me about putting +Infinity all the way up at (2^32)-2 because of the non-symmetry with the negative side. I like yours better! > hashKey32 > > self > 0.0 ifTrue: [ > ^16r80000003 + ((FloatArray basicNew: 1) at: 1 put: self; > basicAt: 1) ]. > self < 0.0 ifTrue: [ > ^16rFF800000 - ((FloatArray basicNew: 1) at: 1 put: self; > basicAt: 1) ]. > self = self ifFalse: [ ^16rFFFFFFFF "NaN" ]. > (self at: 1) = 0 ifTrue: [ ^16r80000003 "Zero" ]. > ^16r7F800000 "Negative zero" I'm going with the above (testing 32-bit range on it now), and I even remembered to avoid using the code-formatter to preserve the hex representations for Eliot. Levente, that you can do such positive critical review of this one method makes me shiver to wonder how many improvements you could discover for Ma-Object-Serializer! ;) Mucho thanks. |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |