Smalltalk › Squeak › Squeak VM

[OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

11 messages Options

David T Lewis

[OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

Comparison of SmallInteger and Float is simple in Spur32, we just have to convert the SmallInteger to a (double), which is an exact operation, and perform the comparison of (double).

But it's more tricky in Spur64 because SmallInteger has more precision (61 bits) than Float (53 bits) and thus conversion to (double) might be inexact...

Example:

si := 1<<(Float precision + 2)+1.
sf := si asFloat.
self deny: sf = si.
self deny: si = sf.

It's not obvious to find where the trick happens in the VM, because all code at upper level is equivalent to trivial asFloat conversion followed by comparison, and there are many possible path!

Let's concentrate on <=

SmallInteger receiver:

#primitiveLessOrEqual
#genPrimitiveLessOrEqual (JIT)
BoxedFloat64 receiver:
#primitiveFloatLessOrEqual
#genPrimitiveFloatLessOrEqual (JIT)
SmallFloat64 receiver:
#primitiveSmallFloatLessOrEqual
#genPrimitiveSmallFloatLessOrEqual (JIT)
All receivers (non jitted sender or stack VM only?):
#bytecodePrimLessOrEqual

For generated C code, the protection is programmed in lower level #loadFloatOrIntFrom:

To check that it does not exceed 53 bits, we shift the integer left << and forth >> and verify integrity. If not, we fail the primitive.
With shift length as programmed currently, the primitive will fail for 52 bits and above. It should fail for 54 bits and above, but that's a detail, the primitive will fail more often than necessary...

The problem is that there is no such exactness check for jitted primitives!

I have sketched a solution in Squeak inbox (See http://source.squeak.org/inbox/Kernel-nice.1260.diff), demonstrated here for SmallInteger <=

^(asFloat := self asFloat) = aNumber
     ifTrue: [self <= aNumber truncated]
     ifFalse: [asFloat <= aNumber]

In C code that is:

if ( (double) si == sf ) return si <= (int64) sf;
else return (double) si <= sf;

It works for all the comparisons (though = and ~= could be a bit simpler, no need to perform the comparison twice).

And it's simple enough to be jitted (I have prototyped it this evening).

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub, or mute the thread.

David T. Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

To check my understanding, the strategy can be summarized as:

When comparing an integer to a float, first check if the integer can be cast
to a float without loss of precision. If so, then treat both values as
floating point, and compare the two float values. Otherwise fall back to
existing comparison logic.

This sounds like a good optimization to me. As you have said, it can
be done in the VM because the VM already understands the word sizes
and object storage formats.

Dave

On Tue, Aug 20, 2019 at 05:19:47PM -0700, Nicolas Cellier wrote:

>
> Comparison of SmallInteger and Float is simple in Spur32, we just have to convert the SmallInteger to a (double), which is an exact operation, and perform the comparison of (double).
>
> But it's more tricky in Spur64 because SmallInteger has more precision (61 bits) than Float (53 bits) and thus conversion to (double) might be inexact...
>
> Example:
>
> si := 1<<(Float precision + 2)+1.
> sf := si asFloat.
> self deny: sf = si.
> self deny: si = sf.
>
> It's not obvious to find where the trick happens in the VM, because all code at upper level is equivalent to trivial asFloat conversion followed by comparison, and there are many possible path!
>
> Let's concentrate on <=
>
> SmallInteger receiver:
> - #primitiveLessOrEqual
> - #genPrimitiveLessOrEqual (JIT)
> BoxedFloat64 receiver:
> - #primitiveFloatLessOrEqual
> - #genPrimitiveFloatLessOrEqual (JIT)
> SmallFloat64 receiver:
> - #primitiveSmallFloatLessOrEqual
> - #genPrimitiveSmallFloatLessOrEqual (JIT)
> All receivers (non jitted sender or stack VM only?):
> - #bytecodePrimLessOrEqual
>
> For generated C code, the protection is programmed in lower level #loadFloatOrIntFrom:
>
> To check that it does not exceed 53 bits, we shift the integer left << and forth >> and verify integrity. If not, we fail the primitive.
> With shift length as programmed currently, the primitive will fail for 52 bits and above. It should fail for 54 bits and above, but that's a detail, the primitive will fail more often than necessary...
>
> The problem is that there is no such exactness check for jitted primitives!
>
> I have sketched a solution in Squeak inbox (See http://source.squeak.org/inbox/Kernel-nice.1260.diff), demonstrated here for SmallInteger <=
>
> ^(asFloat := self asFloat) = aNumber
> ifTrue: [self <= aNumber truncated]
> ifFalse: [asFloat <= aNumber]
>
> In C code that is:
>
> if ( (double) si == sf ) return si <= (int64) sf;
> else return (double) si <= sf;
>
> It works for all the comparisons (though = and ~= could be a bit simpler, no need to perform the comparison twice).
>
> And it's simple enough to be jitted (I have prototyped it this evening).
>
>
>
>
>
>
> --
> You are receiving this because you are subscribed to this thread.
> Reply to this email directly or view it on GitHub:
> https://github.com/OpenSmalltalk/opensmalltalk-vm/issues/417

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

In reply to this post by David T Lewis

Hi David,
sort of...

We know that smallInt asFloat may be inexact.
We could test whether it is exact or not with smallInt asFloat asInteger = smallInt like what is done in Squeak SmallInteger>>#isAnExactFloat check, but that's not what we do here.
What we do is to check if ever that rounding error could change the result of comparison. If it could not, then the rounding error is innocuous and we can proceed with float comparison.

So more exactly, the algorithm is:

check if there is a possible ambiguity
if yes, use exact comparison (the usual image side smallInt = smallFloat asTrueFraction)
if no, use inexact but innocuous comparison (the simple smallInt asFloat = smallFloat)
(strictly speaking, the comparison is exact, only the operands may not)

If smallInt asFloat > smallFloat we know for sure that smallInt > smallFloat.
If smallInt asFloat < smallFloat we know for sure that smallInt < smallFloat.
The only case where we could have ambiguity is when smallInt asFloat = smallFloat.

But in this case, we know that smallFloat value is integer. Indeed, either asFloat is exact, and smallInt = smallFloat, or inexact, but that means that smallInt > (2 raisedTo: Float precision) and then Float has not enough precision to have a fraction part. Thus smallFloat asTrueFraction = smallFloat asInteger in this ambiguous case, a nice thing for the VM to not deal with Fraction!

A potential remaining problem could be that smallFloat asInteger may be a LargeInteger, for example SmallInteger maxVal asInteger > SmallInteger maxVal in 64 bits image.
But we know that:
SmallInteger minVal <= smallFloat and: [smallFloat <= SmallInteger maxVal nextPowerOfTwo]
Thus in the VM, we are safe, SmallInteger span only 61 bits and we have 64 bits registers.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or mute the thread.

David T. Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

Nicolas,

Thank you for this explanation :-)

Dave

On Wed, Aug 21, 2019 at 12:03:42AM -0700, Nicolas Cellier wrote:

>
> Hi David,
> sort of...
>
> We know that `smallInt asFloat` may be inexact.
> We could test whether it is exact or not with `smallInt asFloat asInteger = smallInt` like what is done in Squeak `SmallInteger>>#isAnExactFloat` check, but that's not what we do here.
> What we do is to check if ever that rounding error could change the result of comparison. If it could not, then the rounding error is innocuous and we can proceed with float comparison.
>
> So more exactly, the algorithm is:
> - check if there is a possible ambiguity
> - if yes, use exact comparison (the usual image side `smallInt = smallFloat asTrueFraction`)
> - if no, use inexact but innocuous comparison (the simple `smallInt asFloat = smallFloat`)
> (strictly speaking, the comparison is exact, only the operands may not)
>
> If `smallInt asFloat > smallFloat` we know for sure that `smallInt > smallFloat`.
> If `smallInt asFloat < smallFloat` we know for sure that `smallInt < smallFloat`.
> The only case where we could have ambiguity is when `smallInt asFloat = smallFloat`.
>
> But in this case, we know that smallFloat value is integer. Indeed, either asFloat is exact, and `smallInt = smallFloat`, or inexact, but that means that `smallInt > (2 raisedTo: Float precision)` and then Float has not enough precision to have a fraction part. Thus `smallFloat asTrueFraction = smallFloat asInteger` in this ambiguous case, a nice thing for the VM to not deal with Fraction!
>
> A potential remaining problem could be that smallFloat asInteger may be a LargeInteger, for example `SmallInteger maxVal asInteger > SmallInteger maxVal` in 64 bits image.
> But we know that:
> `SmallInteger minVal <= smallFloat and: [smallFloat <= SmallInteger maxVal nextPowerOfTwo]`
> Thus in the VM, we are safe, SmallInteger span only 61 bits and we have 64 bits registers.
>
> --
> You are receiving this because you commented.
> Reply to this email directly or view it on GitHub:
> https://github.com/OpenSmalltalk/opensmalltalk-vm/issues/417#issuecomment-523326042

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

In reply to this post by David T Lewis

Closed #417.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

In reply to this post by David T Lewis

Solved, I added more exahaustive tests in Squeak and they now pass
Never mind the CI failures... We really fail at keeping something so complex stable... way too many configurations!!!

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

In reply to this post by David T Lewis

Just for archeology, the problem was foreseen in 2014 and fixed for non jitted code only
See thread
[Vm-dev] Potential problems with 64bit spur large SmallInteger comparison
http://lists.squeakfoundation.org/pipermail/vm-dev/2014-December/017401.html

Of course, it seems that google does not index that...

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

In reply to this post by David T Lewis

Hi Nicolas,

I apologize for not having noticed this issue until now.  As far as writing the tests so that the JIT code will be run, you can either write the test recursively, e.g.

fooTest
self fooTest: 0

fooTest: n
n < 2 ifTrue: [^self fooTest: n + 1]. "Make sure method is JITTED"
...

or run the tests in a block and make sure the block is repeated, say, 10 times. There is a secret primitive in the VM one can use to test for JITTED ness. See Context>>X-ray in Cog-Tests. If you need this in the KernelTests then you can add it as an extension.

xray
"Lift the veil from a context and answer an integer describing its interior state.
Used for e.g. VM tests so they can verify they're testing what they think they're testing.
0 implies a vanilla heap context.
Bit 0 = is or was married to a frame
Bit 1 = is still married to a frame
Bit 2 = frame is executing machine code
Bit 3 = has machine code pc (as opposed to nil or a bytecode pc)
Bit 4 = method is currently compiled to machine code"
<primitive: 213>
^0 "Can only fail if unimplemented; therefore simply answer 0"

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

In reply to this post by David T Lewis

also, in e.g. CogObjectRepresentationFor64BitSpur>>genFloatComparison:orIntegerComparison:invert:boxed: or anywhere else the issue comes up it would be good for non-experts to extend the comment, so that instead of just

"If floatRcvr == (double) intArg then use compareInt(intArg,(int64) floatRcvr)"

it says
"If floatRcvr == (double) intArg then use compareInt(intArg,(int64) floatRcvr).
see #417"
or
"If floatRcvr == (double) intArg then use compareInt(intArg,(int64) floatRcvr).
because in 64-bits SmallInteger has more significant bits (60) than Float (53)"

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or mute the thread.

David T Lewis

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

In reply to this post by David T Lewis

One last nit; there is no need to use
self cppIf: objectMemory wordSize > 4 ifTrue: [ ... ] ].
One can simply write
objectMemory wordSize > 4 ifTrue: [ ... ].

This is because VMMaker generates entirely different sources for 64-bit and 32-bit VMs, and so the objectMemory wordSize > 4 test is inlined at source generation time. Reserve cppIf:ifTrue: for things that really are VM-compile-time options, such as whether the VM is being compiled with IMMUTABILITY (read-only) support or not.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or mute the thread.

Juan Vuletich-3

Re: [OpenSmalltalk/opensmalltalk-vm] Mixed SmallInteger/Float comparison is inexact in Spur64 when jitted (#417)

In reply to this post by David T Lewis

Hi Folks,

In the case where the integer -> float conversion is inexact, I think we need to make the choice in the image and not in the VM.

For example, it is a valid use case to be able to mimic C. This is useful, for example, for code having various versions, in Smalltalk / C / OpenCL, etc. It is also useful for porting C libraries to Smalltalk and having the same behavior as with a standards compliant C compiler.

According to Recent draft of the ISO C18 standard: https://web.archive.org/web/20181230041359if_/http://www.open-std.org/jtc1/sc22/wg14/www/abq/c17_updated_proposed_fdis.pdf
6.3.1.8 Conversions -Usual arithmetic conversions
6.5.8 Relational operators
6.5.9 Equality operators
"...if the corresponding real type of either operand is double, the other operand is converted, without change of type domain, to a type whose corresponding real type is double."
(without any regard to the actual values being compared!)

I'm not saying that Squeak / Pharo / Cuis should change current behavior.

But I think that a Smalltalk developer should be able to tweak Smalltalk code to their requirements. The best way to do this is to make the primitive fail if one of the arguments is Float, the other is SmallInteger, and the two alteratives (float comparison and int comparison) would yield different results.

Making the primitive fail in those cases means the performance cost is only paid for very large values (hopefully rather infrequent as instances of SmallInteger). The alternative is that people wanting to mimic the C behavior adds a class check for every comparison (regardless of the values), at a much higher performance penalty.

Another reasonable alternative is to provide a new set of comparison primitives, and let the image choose which one to call.

Thanks,

-- 
Juan Vuletich
www.cuis-smalltalk.org
https://github.com/Cuis-Smalltalk/Cuis-Smalltalk-Dev
https://github.com/jvuletich
https://www.linkedin.com/in/juan-vuletich-75611b3
@JuanVuletich

On 8/21/2019 4:03 AM, Nicolas Cellier wrote:

Hi David,
sort of...

We know that smallInt asFloat may be inexact.
We could test whether it is exact or not with smallInt asFloat asInteger = smallInt like what is done in Squeak SmallInteger>>#isAnExactFloat check, but that's not what we do here.
What we do is to check if ever that rounding error could change the result of comparison. If it could not, then the rounding error is innocuous and we can proceed with float comparison.

So more exactly, the algorithm is:

check if there is a possible ambiguity

if yes, use exact comparison (the usual image side smallInt = smallFloat asTrueFraction)

if no, use inexact but innocuous comparison (the simple smallInt asFloat = smallFloat)
(strictly speaking, the comparison is exact, only the operands may not)

If smallInt asFloat > smallFloat we know for sure that smallInt > smallFloat.
If smallInt asFloat < smallFloat we know for sure that smallInt < smallFloat.
The only case where we could have ambiguity is when smallInt asFloat = smallFloat.

But in this case, we know that smallFloat value is integer. Indeed, either asFloat is exact, and smallInt = smallFloat, or inexact, but that means that smallInt > (2 raisedTo: Float precision) and then Float has not enough precision to have a fraction part. Thus smallFloat asTrueFraction = smallFloat asInteger in this ambiguous case, a nice thing for the VM to not deal with Fraction!

A potential remaining problem could be that smallFloat asInteger may be a LargeInteger, for example SmallInteger maxVal asInteger > SmallInteger maxVal in 64 bits image.
But we know that:
SmallInteger minVal <= smallFloat and: [smallFloat <= SmallInteger maxVal nextPowerOfTwo]
Thus in the VM, we are safe, SmallInteger span only 61 bits and we have 64 bits registers.

—
You are receiving this because you commented.
<script type="application/ld+json">[ { "@context": <a class="moz-txt-link-rfc2396E" href="http://schema.org">"http://schema.org"</a>, "@type": "EmailMessage", "potentialAction": { "@type": "ViewAction", "target": <a class="moz-txt-link-rfc2396E" href="https://github.com/OpenSmalltalk/opensmalltalk-vm/issues/417?email_source=notifications\u0026email_token=AIJPEW4JXZBE5VRRFDN42FDQFTSE5A5CNFSM4IN66INKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD4YVEWQ#issuecomment-523326042">"https://github.com/OpenSmalltalk/opensmalltalk-vm/issues/417?email_source=notifications\u0026email_token=AIJPEW4JXZBE5VRRFDN42FDQFTSE5A5CNFSM4IN66INKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD4YVEWQ#issuecomment-523326042"</a>, "url": <a class="moz-txt-link-rfc2396E" href="https://github.com/OpenSmalltalk/opensmalltalk-vm/issues/417?email_source=notifications\u0026email_token=AIJPEW4JXZBE5VRRFDN42FDQFTSE5A5CNFSM4IN66INKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD4YVEWQ#issuecomment-523326042">"https://github.com/OpenSmalltalk/opensmalltalk-vm/issues/417?email_source=notifications\u0026email_token=AIJPEW4JXZBE5VRRFDN42FDQFTSE5A5CNFSM4IN66INKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD4YVEWQ#issuecomment-523326042"</a>, "name": "View Issue" }, "description": "View this Issue on GitHub", "publisher": { "@type": "Organization", "name": "GitHub", "url": <a class="moz-txt-link-rfc2396E" href="https://github.com">"https://github.com"</a> } } ]</script>