This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Arithmetic Overflows - was Unsigned Arithmetic

18 replies
Bernd Johannes
Joined: 2011-01-28,
User offline. Last seen 42 years 45 weeks ago.

Just my opinion to overflows...

Am Samstag, 5. November 2011, 18:56:29 schrieb Peter C. Chapin:
> Overflow checking may result in a slower program but I tend to agree with
> you… I’d rather have it than not.
>

The silent overflowing inherited from Java (so no Scala invention here :-) is
one of the nastier things. I've been chasing quite some bugs routed in this
very unfortunate design decision.

I simply consider it a fundamental design flaw (in Java / the JVM -don't know
exactly where it stems from).
Well - apart from that the platform is still too tempting to leave it just
because of that... :-)

Anyway: if Scala should ever have the chance of setting this right without or
with JVM support or even just for .net I would higly recommend it. But I see
that the JVM may be a lost cause here, sadly enough.

Backward compatibility: Code that is relying on silent overflows is simply
using an antipattern (and even more often is using it not correct anyway). But
I agree that this could cause issues.

The intriguing question underneath is: what to do with cases where .net/CLR
will be acting fundamentally differently to the JVM? Discard the correct or
beneficial behaviour in favour of cross platform compatibility?
Looking forward to the "Joint Platform Future" - It will be quite an
adventure... ;-)

Just my 5 cents.
Bernd

Jesper Nordenberg
Joined: 2008-12-27,
User offline. Last seen 42 years 45 weeks ago.
Re: Arithmetic Overflows - was Unsigned Arithmetic

Bernd Johannes skrev 2011-11-07 08:18:
> I simply consider it a fundamental design flaw (in Java / the JVM -don't know
> exactly where it stems from).

It's the way most CPU's today are designed. To implement overflow
detection efficiently would require hardware support.

> Anyway: if Scala should ever have the chance of setting this right without or
> with JVM support or even just for .net I would higly recommend it. But I see
> that the JVM may be a lost cause here, sadly enough.

Nothing is stopping you from implementing your own integer type with
overflow detection in Scala. I don't see why this should be a feature in
the language.

/Jesper Nordenberg

Rüdiger Klaehn
Joined: 2009-06-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Arithmetic Overflows - was Unsigned Arithmetic

Overflow checking without CPU support will lead to unacceptable
performance in many cases. If yours is one of the cases where
performance is not as important, just use BigInt. It is easy to use in
scala (operators etc.)

That said, I think it might be worthwhile to have a library that
provides integers with overflow checking as well as unsigned integers
for those people that need them. Maybe in the new scalax namespace? It
is obviously possible to write your own wrapper with the appropriate
checks, but it is not completely trivial to get correct and fast.

On Mon, Nov 7, 2011 at 8:18 AM, Bernd Johannes wrote:
> Just my opinion to overflows...
>
> Am Samstag, 5. November 2011, 18:56:29 schrieb Peter C. Chapin:
>> Overflow checking may result in a slower program but I tend to agree with
>> you… I’d rather have it than not.
>>
>
> The silent overflowing inherited from Java (so no Scala invention here :-) is
> one of the nastier things. I've been chasing quite some bugs routed in this
> very unfortunate design decision.
>
> I simply consider it a fundamental design flaw (in Java / the JVM -don't know
> exactly where it stems from).
> Well - apart from that the platform is still too tempting to leave it just
> because of that... :-)
>
> Anyway: if Scala should ever have the chance of setting this right without or
> with JVM support or even just for .net  I would higly recommend it. But I see
> that the JVM may be a lost cause here, sadly enough.
>
> Backward compatibility: Code that is relying on silent overflows is simply
> using an antipattern (and even more often is using it not correct anyway). But
> I agree that this could cause issues.
>
> The intriguing question underneath is: what to do with cases where .net/CLR
> will be acting fundamentally differently to the JVM? Discard the correct or
> beneficial behaviour in favour of cross platform compatibility?
> Looking forward to the "Joint Platform Future" - It will be quite an
> adventure... ;-)
>
> Just my 5 cents.
> Bernd
>

Sciss
Joined: 2008-12-17,
User offline. Last seen 28 weeks 5 days ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

...or write a compiler plugin, one of the other things one mustn't forget about scala's extendability:

val i : @checkoverflow = 0x40000000
i * 4

that way you could also use it just for testing and fall back to 'normal' integers with full performance in deployment. like disabling assertions or removing @elidable.

best, -sciss-

On 7 Nov 2011, at 07:53, Rüdiger Klaehn wrote:

> Overflow checking without CPU support will lead to unacceptable
> performance in many cases. If yours is one of the cases where
> performance is not as important, just use BigInt. It is easy to use in
> scala (operators etc.)
>
> That said, I think it might be worthwhile to have a library that
> provides integers with overflow checking as well as unsigned integers
> for those people that need them. Maybe in the new scalax namespace? It
> is obviously possible to write your own wrapper with the appropriate
> checks, but it is not completely trivial to get correct and fast.
>
> On Mon, Nov 7, 2011 at 8:18 AM, Bernd Johannes wrote:
>> Just my opinion to overflows...
>>
>> Am Samstag, 5. November 2011, 18:56:29 schrieb Peter C. Chapin:
>>> Overflow checking may result in a slower program but I tend to agree with
>>> you… I’d rather have it than not.
>>>
>>
>> The silent overflowing inherited from Java (so no Scala invention here :-) is
>> one of the nastier things. I've been chasing quite some bugs routed in this
>> very unfortunate design decision.
>>
>> I simply consider it a fundamental design flaw (in Java / the JVM -don't know
>> exactly where it stems from).
>> Well - apart from that the platform is still too tempting to leave it just
>> because of that... :-)
>>
>> Anyway: if Scala should ever have the chance of setting this right without or
>> with JVM support or even just for .net I would higly recommend it. But I see
>> that the JVM may be a lost cause here, sadly enough.
>>
>> Backward compatibility: Code that is relying on silent overflows is simply
>> using an antipattern (and even more often is using it not correct anyway). But
>> I agree that this could cause issues.
>>
>> The intriguing question underneath is: what to do with cases where .net/CLR
>> will be acting fundamentally differently to the JVM? Discard the correct or
>> beneficial behaviour in favour of cross platform compatibility?
>> Looking forward to the "Joint Platform Future" - It will be quite an
>> adventure... ;-)
>>
>> Just my 5 cents.
>> Bernd
>>

Rüdiger Klaehn
Joined: 2009-06-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

I think unsigned integers and overflow-checking integers should be
different types.

Wrappers are OK, since escape analysis and scalar replacement (I used
to think that this was called stack allocation, but victor klang
corrected me) will remove most of the overhead in most situations.

And frankly, if somebody wants every integer operation to be able to
throw an exception he can't be that concerned with performance anyway.
A factor of 2 reduction in performance would still be enough for such
situations.

On Mon, Nov 7, 2011 at 11:42 AM, Sciss wrote:
> ...or write a compiler plugin, one of the other things one mustn't forget about scala's extendability:
>
> val i : @checkoverflow = 0x40000000
> i * 4
>
> that way you could also use it just for testing and fall back to 'normal' integers with full performance in deployment. like disabling assertions or removing @elidable.
>
What if somebody uses the overflow check (e.g. to do input
validation)? I think having a different type is preferable.

Viktor Klang
Joined: 2008-12-17,
User offline. Last seen 1 year 27 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic


On Mon, Nov 7, 2011 at 11:57 AM, Rüdiger Klaehn <rklaehn [at] googlemail [dot] com> wrote:
I think unsigned integers and overflow-checking integers should be
different types.

Wrappers are OK, since escape analysis and scalar replacement (I used
to think that this was called stack allocation, but victor klang
corrected me) will remove most of the overhead in most situations.

And frankly, if somebody wants every integer operation to be able to
throw an exception he can't be that concerned with performance anyway.
A factor of 2 reduction in performance would still be enough for such
situations.

But if you don't want overflow, and don't care about performance, why not just use BigInt/BigDecimal?
 

On Mon, Nov 7, 2011 at 11:42 AM, Sciss <contact [at] sciss [dot] de> wrote:
> ...or write a compiler plugin, one of the other things one mustn't forget about scala's extendability:
>
> val i : @checkoverflow = 0x40000000
> i * 4
>
> that way you could also use it just for testing and fall back to 'normal' integers with full performance in deployment. like disabling assertions or removing @elidable.
>
What if somebody uses the overflow check (e.g. to do input
validation)? I think having a different type is preferable.



--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang
Rüdiger Klaehn
Joined: 2009-06-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

2011/11/7 √iktor Ҡlang :
>
>
> On Mon, Nov 7, 2011 at 11:57 AM, Rüdiger Klaehn
> wrote:
>>
>> I think unsigned integers and overflow-checking integers should be
>> different types.
>>
>> Wrappers are OK, since escape analysis and scalar replacement (I used
>> to think that this was called stack allocation, but victor klang
>> corrected me) will remove most of the overhead in most situations.
>>
>> And frankly, if somebody wants every integer operation to be able to
>> throw an exception he can't be that concerned with performance anyway.
>> A factor of 2 reduction in performance would still be enough for such
>> situations.
>
> But if you don't want overflow, and don't care about performance, why not
> just use BigInt/BigDecimal?
>
It seems that quite often people want unsigned arithmetic or overflow
checking, and it would not be a big deal to provide this as a library.

I can see that somebody might want an unsigned data type to port an
algorithm from a language with unsigned arithmetic such as C++. And
people coming from VB or C# might want integer arithmetic with
overflow checks. I would be opposed to changing anything about scala
itself for something like this because IMHO it's not worth it, but if
you can do it as a library, why not?

Wrapping a primitive and defining some operations like compare
slightly differently will still be much faster than using BigInt, even
though it will be slower than using a primitive.

d_m
Joined: 2010-11-11,
User offline. Last seen 35 weeks 2 days ago.
Re: Arithmetic Overflows - was Unsigned Arithmetic

On Mon, Nov 07, 2011 at 08:18:07AM +0100, Bernd Johannes wrote:
> Anyway: if Scala should ever have the chance of setting this right without or
> with JVM support or even just for .net I would higly recommend it. But I see
> that the JVM may be a lost cause here, sadly enough.

I have been thinking about (and working on) a boxed Number type which
will promote its underlying types (when necessary) to avoid overflow
and to avoid loss of precision. I'm not sure if it will end up being
faster than just using BigInt/BigDecimal from the start but it might
be.

Unfortunately getting this right on the JVM will probably result in
slower code. For most applications the slowdown might not be a big
deal, but for some it certainly will be. Even without any boxing the
overflow check will take some time.

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

On Mon, Nov 7, 2011 at 05:39, Jesper Nordenberg wrote:
> Bernd Johannes skrev 2011-11-07 08:18:
>>
>> I simply consider it a fundamental design flaw (in Java / the JVM -don't
>> know
>> exactly where it stems from).
>
> It's the way most CPU's today are designed. To implement overflow detection
> efficiently would require hardware support.

Err, what? The x86 architecture seems to have both Overflow and Carry
flag (http://en.wikipedia.org/wiki/FLAGS_register_(computing)). Do you
mean to imply they are not used?

Peter C. Chapin 2
Joined: 2011-01-07,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

On Mon, 2011-11-07 at 13:32 -0500, Daniel Sobral wrote:

> > It's the way most CPU's today are designed. To implement overflow detection
> > efficiently would require hardware support.
>
> Err, what? The x86 architecture seems to have both Overflow and Carry
> flag (http://en.wikipedia.org/wiki/FLAGS_register_(computing)). Do you
> mean to imply they are not used?

Just setting a flag in the flag register isn't necessarily efficient. It
requires a conditional branch after every arithmetic instruction to
check that flag. The kind of hardware support the earlier poster is
talking about is when the processor automatically invokes an exception
routine when the overflow flag is set. That way no additional
instructions are needed to check for the overflow condition.

Some processors do have this kind of support but I suppose the JVM
doesn't use it since it's not universally available. I'm not sure.

Peter

Bernd Johannes
Joined: 2011-01-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

Am Montag, 7. November 2011, 08:39:10 schrieb Jesper Nordenberg:
> Bernd Johannes skrev 2011-11-07 08:18:
> > I simply consider it a fundamental design flaw (in Java / the JVM -don't
> > know exactly where it stems from).
>
> It's the way most CPU's today are designed. To implement overflow
> detection efficiently would require hardware support.
>

I am not intimate with the dot.net ways and if it is using hardware support to
detect overflows (which it can if instructed to do so) - but I am tempted to
bet that "our" mainstream cpus come along with hardware overflow detection.
It's been there in the very old 6510 days - I don't think it went away because
carry- and overflow detection was always quite low level stuff...

> > Anyway: if Scala should ever have the chance of setting this right
> > without or with JVM support or even just for .net I would higly
> > recommend it. But I see that the JVM may be a lost cause here, sadly
> > enough.
>
> Nothing is stopping you from implementing your own integer type with
> overflow detection in Scala. I don't see why this should be a feature in
> the language.

Thats true - in this case I could simulate at a higher level what's missing in
the lower levels. But I would prefer to spend the calculation cost where it is
spent most efficiently. Exposing (hardware?) overflow detection in scala.net
similarly to C# could enable scala to run its calculations at the same speed
with the same confidence as "native" dot.net (assuming quite a lot "best
cases" here).

On the other hand I just don't see how I would implement this "high level" in
scala without paying a terrible performance tax. But ok - it's a valid
argument that there is always C to the rescue when it comes to number
crunching - so agreed its not really necessary... ;-)

Greetings
Bernd

Bernd Johannes
Joined: 2011-01-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

Am Montag, 7. November 2011, 20:05:42 schrieb Peter C. Chapin:
> On Mon, 2011-11-07 at 13:32 -0500, Daniel Sobral wrote:
> > > It's the way most CPU's today are designed. To implement overflow
> > > detection efficiently would require hardware support.
> >
> > Err, what? The x86 architecture seems to have both Overflow and Carry
> > flag (http://en.wikipedia.org/wiki/FLAGS_register_(computing)). Do you
> > mean to imply they are not used?
>
> Just setting a flag in the flag register isn't necessarily efficient. It
> requires a conditional branch after every arithmetic instruction to
> check that flag. The kind of hardware support the earlier poster is
> talking about is when the processor automatically invokes an exception
> routine when the overflow flag is set. That way no additional
> instructions are needed to check for the overflow condition.
>
> Some processors do have this kind of support but I suppose the JVM
> doesn't use it since it's not universally available. I'm not sure.
>
> Peter

Ok, when Jesper referred to arithmetic overflow traps when he said "efficient"
then I have to agree. That's really not as ubiquitous as overflow detection
per se.

But gut feeling tells me that implementing overflow detection high level in
scala would cost much more than branch instructions after arithmetic
operations. But I would love to stand corrected :-)

Greetings
Bernd

Rüdiger Klaehn
Joined: 2009-06-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

On Mon, Nov 7, 2011 at 9:36 PM, Bernd Johannes wrote:
> Am Montag, 7. November 2011, 08:39:10 schrieb Jesper Nordenberg:
>> Bernd Johannes skrev 2011-11-07 08:18:
>> > I simply consider it a fundamental design flaw (in Java / the JVM -don't
>> > know exactly where it stems from).
>>
>> It's the way most CPU's today are designed. To implement overflow
>> detection efficiently would require hardware support.
>>
>
> I am not intimate with the dot.net ways and if it is using hardware support to
> detect overflows (which it can if instructed to do so) - but I am tempted to
> bet that "our" mainstream cpus come along with hardware overflow detection.
> It's been there in the very old 6510 days - I don't think it went away because
> carry- and overflow detection was always quite low level stuff...
>
>> > Anyway: if Scala should ever have the chance of setting this right
>> > without or with JVM support or even just for .net  I would higly
>> > recommend it. But I see that the JVM may be a lost cause here, sadly
>> > enough.
>>
>> Nothing is stopping you from implementing your own integer type with
>> overflow detection in Scala. I don't see why this should be a feature in
>> the language.
>
> Thats true - in this case I could simulate at a higher level what's missing in
> the lower levels. But I would prefer to spend the calculation cost where it is
> spent most efficiently. Exposing (hardware?) overflow detection in scala.net
> similarly to C# could enable scala to run its calculations at the same speed
> with the same confidence as "native" dot.net (assuming quite a lot "best
> cases" here).
>
> On the other hand I just don't see how I would implement this "high level" in
> scala without paying a terrible performance tax. But ok - it's a valid
> argument that there is always C to the rescue when it comes to number
> crunching - so agreed its not really necessary... ;-)
>
I have yet to see somebody with a real problem, like some brilliant
algorithm that he would like to implement in scala but can't because
there is no ultra high performance unsigned implementation. Most
hardcore bit twiddling algorithms can be adjusted to work just as well
with signed integers. It used to be that image manipulation was where
unsigned bytes were really needed. But nowadays you are better off
just using floats for each color component, and use the GPU if you
need some serious performance.

I can understand that someone would like to have unsigned integers or
integers with overflow detection with reasonable performance, but that
can be accomplished with a plain library wrapping primitives. Such a
library should also be able to handle odd bit counts (basically
anything between 1 and 64 bit, signed or unsigned, checked or
unchecked).

hossein_haeri
Joined: 2011-09-25,
User offline. Last seen 1 year 2 weeks ago.
Re: Re: Re: Arithmetic Overflows - was Unsigned Arithmetic
Dear Rüdiger,

I am currently working on a paper that would be happy to share once published. In that paper, my running example is a class which would be much more cleanly implemented using unsigned arithmetic. Letting the signed arithmetic in would simply make everything unreasonably nasty. Maybe I should emphasise thus that, there, unsigned arithmetic is chosen for correctness as opposed to efficiency.
TTFN,--Hossein
On 7 November 2011 22:08, Rüdiger Klaehn <rklaehn [at] googlemail [dot] com> wrote:
On Mon, Nov 7, 2011 at 9:36 PM, Bernd Johannes <bjohanns [at] bacon [dot] de> wrote:
> Am Montag, 7. November 2011, 08:39:10 schrieb Jesper Nordenberg:
>> Bernd Johannes skrev 2011-11-07 08:18:
>> > I simply consider it a fundamental design flaw (in Java / the JVM -don't
>> > know exactly where it stems from).
>>
>> It's the way most CPU's today are designed. To implement overflow
>> detection efficiently would require hardware support.
>>
>
> I am not intimate with the dot.net ways and if it is using hardware support to
> detect overflows (which it can if instructed to do so) - but I am tempted to
> bet that "our" mainstream cpus come along with hardware overflow detection.
> It's been there in the very old 6510 days - I don't think it went away because
> carry- and overflow detection was always quite low level stuff...
>
>> > Anyway: if Scala should ever have the chance of setting this right
>> > without or with JVM support or even just for .net  I would higly
>> > recommend it. But I see that the JVM may be a lost cause here, sadly
>> > enough.
>>
>> Nothing is stopping you from implementing your own integer type with
>> overflow detection in Scala. I don't see why this should be a feature in
>> the language.
>
> Thats true - in this case I could simulate at a higher level what's missing in
> the lower levels. But I would prefer to spend the calculation cost where it is
> spent most efficiently. Exposing (hardware?) overflow detection in scala.net
> similarly to C# could enable scala to run its calculations at the same speed
> with the same confidence as "native" dot.net (assuming quite a lot "best
> cases" here).
>
> On the other hand I just don't see how I would implement this "high level" in
> scala without paying a terrible performance tax. But ok - it's a valid
> argument that there is always C to the rescue when it comes to number
> crunching - so agreed its not really necessary... ;-)
>
I have yet to see somebody with a real problem, like some brilliant
algorithm that he would like to implement in scala but can't because
there is no ultra high performance unsigned implementation. Most
hardcore bit twiddling algorithms can be adjusted to work just as well
with signed integers. It used to be that image manipulation was where
unsigned bytes were really needed. But nowadays you are better off
just using floats for each color component, and use the GPU if you
need some serious performance.

I can understand that someone would like to have unsigned integers or
integers with overflow detection with reasonable performance, but that
can be accomplished with a plain library wrapping primitives. Such a
library should also be able to handle odd bit counts (basically
anything between 1 and 64 bit, signed or unsigned, checked or
unchecked).



--
--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------
Jesper Nordenberg
Joined: 2008-12-27,
User offline. Last seen 42 years 45 weeks ago.
Re: Arithmetic Overflows - was Unsigned Arithmetic

Bernd Johannes skrev 2011-11-07 21:47:
> Ok, when Jesper referred to arithmetic overflow traps when he said "efficient"
> then I have to agree. That's really not as ubiquitous as overflow detection
> per se.

Yes, as Peter wrote, it's not sufficient to have a flag in the CPU to
indicate overflow. The overflow must somehow be "translated" into an
exception in the JVM.

> But gut feeling tells me that implementing overflow detection high level in
> scala would cost much more than branch instructions after arithmetic
> operations. But I would love to stand corrected :-)

Depends on the backend I would say. If you have an LLVM, .NET or C/C++
backend, an unboxed integer type with overflow detection could be
relatively efficiently implemented. In the JVM you have the usual boxing
problem.

/Jesper Nordenberg

Bernd Johannes
Joined: 2011-01-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

Am Montag, 7. November 2011, 23:50:44 schrieb Jesper Nordenberg:
> Bernd Johannes skrev 2011-11-07 21:47:
> > Ok, when Jesper referred to arithmetic overflow traps when he said
> > "efficient" then I have to agree. That's really not as ubiquitous as
> > overflow detection per se.
>
> Yes, as Peter wrote, it's not sufficient to have a flag in the CPU to
> indicate overflow. The overflow must somehow be "translated" into an
> exception in the JVM.
>
> > But gut feeling tells me that implementing overflow detection high level
> > in scala would cost much more than branch instructions after arithmetic
> > operations. But I would love to stand corrected :-)
>
> Depends on the backend I would say. If you have an LLVM, .NET or C/C++
> backend, an unboxed integer type with overflow detection could be
> relatively efficiently implemented. In the JVM you have the usual boxing
> problem.

Ok - I got curious, just wrote a very naive version of integer & long checking
(just "+" and "*" for Int, "+" for Long) and I am quite impressed with scala.
I expected the result to be worse that that:

benchmark ms linear runtime
IntPlus 2,55 =========
IntPlusCheck 5,77 ======================
IntMul 1,53 =====
IntMulCheck 4,78 ==================
LongPlus 4,71 ==================
LongPlusCheck 7,72 ==============================

At least this gives me a feeling for the magnitude of performance impact.
Roughly a factor of 2 for the + case is acceptable (for me). And I chose "+?"
as operator for checked addition - so I can select which addition is worth the
cost.

So my conclusion: Indeed no need for low level support. I can live without...
and I have won a new pet project :-)

Greetings
Bernd

Bernd Johannes
Joined: 2011-01-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

Am Montag, 7. November 2011, 22:08:45 schrieb Rüdiger Klaehn:

>>> Nothing is stopping you from implementing your own integer type with
>>> overflow detection in Scala. I don't see why this should be a feature in
>>> the language.
>>
>> Thats true - in this case I could simulate at a higher level what's missing
>> in the lower levels. But I would prefer to spend the calculation cost where
>> it is spent most efficiently. Exposing (hardware?) overflow detection in
>> scala.net
>> similarly to C# could enable scala to run its calculations at the same
>> speed
>> with the same confidence as "native" dot.net (assuming quite a lot "best
>> cases" here).
> I have yet to see somebody with a real problem, like some brilliant
> algorithm that he would like to implement in scala but can't because
> there is no ultra high performance unsigned implementation. Most
> hardcore bit twiddling algorithms can be adjusted to work just as well
> with signed integers. It used to be that image manipulation was where
> unsigned bytes were really needed. But nowadays you are better off
> just using floats for each color component, and use the GPU if you
> need some serious performance.

I was referring just to the "silent overflow" problem. It has been a reason
for quite some subtle bugs I encountered.

The signed / unsigned problem is something different. When I need unsigned
arithmetic I think about it. I adjust my algorithm, test it with "unsigned" in
mind and most of the time that's it.

The overflow problem often hits people (including me) unprepared. You do some
calculation - confident that the result still fits into the target type. But
unfortunately an intermediate result doesn't. Or an input value is an order of
magnitude higher as you had expected - and because of [fill in whatever excuse
might exist - most often "performance"] there are no prechecks in place.

> I can understand that someone would like to have unsigned integers or
> integers with overflow detection with reasonable performance, but that
> can be accomplished with a plain library wrapping primitives. Such a
> library should also be able to handle odd bit counts (basically
> anything between 1 and 64 bit, signed or unsigned, checked or
> unchecked).

I was wrong thinking that a checking wrapper would consume a large amount of
performance. It turned out (in a naive test) that it "just" doubles the time
needed for Int addition. That's good enough for me.
However my approach was not "generic" - it was exactly for Int and nothing
else.

Greetings
Bernd

Rüdiger Klaehn
Joined: 2009-06-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

On Tue, Nov 8, 2011 at 12:02 AM, Bernd Johannes wrote:
> Am Montag, 7. November 2011, 23:50:44 schrieb Jesper Nordenberg:
>> Bernd Johannes skrev 2011-11-07 21:47:
>> > Ok, when Jesper referred to arithmetic overflow traps when he said
>> > "efficient" then I have to agree. That's really not as ubiquitous as
>> > overflow detection per se.
>>
>> Yes, as Peter wrote, it's not sufficient to have a flag in the CPU to
>> indicate overflow. The overflow must somehow be "translated" into an
>> exception in the JVM.
>>
>> > But gut feeling tells me that implementing overflow detection high level
>> > in scala would cost much more than branch instructions after arithmetic
>> > operations. But I would love to stand corrected :-)
>>
>> Depends on the backend I would say. If you have an LLVM, .NET or C/C++
>> backend, an unboxed integer type with overflow detection could be
>> relatively efficiently implemented. In the JVM you have the usual boxing
>> problem.
>
> Ok - I got curious, just wrote a very naive version of integer & long checking
> (just "+" and "*" for Int, "+" for Long) and I am quite impressed with scala.
> I expected the result to be worse that that:
>
> benchmark   ms linear runtime
> IntPlus 2,55 =========
> IntPlusCheck 5,77 ======================
> IntMul 1,53 =====
> IntMulCheck 4,78 ==================
> LongPlus 4,71 ==================
> LongPlusCheck 7,72 ==============================
>
> At least this gives me a feeling for the magnitude of performance impact.
> Roughly a factor of 2 for the + case is acceptable (for me). And I chose "+?"
> as operator for checked addition - so I can select which addition is worth the
> cost.
>
> So my conclusion: Indeed no need for low level support. I can live without...
> and I have won a new pet project :-)
>
Those numbers are better than I expected. The escape analysis and
scalar replacement must have completely eliminated the object
allocation for the wrapper. But don't expect to get such a low
overhead in real world situations. The worst case is maybe a
long-lived array of these new wrappers: instead of using a native
array, it will use an array of pointers and one object per element, so
the memory overhead will be huge.

But as long as you remain aware that these are just wrappers and need
to be casted to/from the underlying primitive for long-term storage
you should be OK.

Bernd Johannes
Joined: 2011-01-28,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: Arithmetic Overflows - was Unsigned Arithmetic

Am Dienstag, 8. November 2011, 07:20:27 schrieb Rüdiger Klaehn:
> On Tue, Nov 8, 2011 at 12:02 AM, Bernd Johannes wrote:
> > Am Montag, 7. November 2011, 23:50:44 schrieb Jesper Nordenberg:
> >> Bernd Johannes skrev 2011-11-07 21:47:
> >> > Ok, when Jesper referred to arithmetic overflow traps when he said
> >> > "efficient" then I have to agree. That's really not as ubiquitous as
> >> > overflow detection per se.
> >>
> >> Yes, as Peter wrote, it's not sufficient to have a flag in the CPU to
> >> indicate overflow. The overflow must somehow be "translated" into an
> >> exception in the JVM.
> >>
> >> > But gut feeling tells me that implementing overflow detection high
> >> > level in scala would cost much more than branch instructions after
> >> > arithmetic operations. But I would love to stand corrected :-)
> >>
> >> Depends on the backend I would say. If you have an LLVM, .NET or C/C++
> >> backend, an unboxed integer type with overflow detection could be
> >> relatively efficiently implemented. In the JVM you have the usual boxing
> >> problem.
> >
> > Ok - I got curious, just wrote a very naive version of integer & long
> > checking (just "+" and "*" for Int, "+" for Long) and I am quite
> > impressed with scala. I expected the result to be worse that that:
> >
> > benchmark ms linear runtime
> > IntPlus 2,55 =========
> > IntPlusCheck 5,77 ======================
> > IntMul 1,53 =====
> > IntMulCheck 4,78 ==================
> > LongPlus 4,71 ==================
> > LongPlusCheck 7,72 ==============================
> >
> > At least this gives me a feeling for the magnitude of performance impact.
> > Roughly a factor of 2 for the + case is acceptable (for me). And I chose
> > "+?" as operator for checked addition - so I can select which addition
> > is worth the cost.
> >
> > So my conclusion: Indeed no need for low level support. I can live
> > without... and I have won a new pet project :-)
>
> Those numbers are better than I expected. The escape analysis and
> scalar replacement must have completely eliminated the object
> allocation for the wrapper. But don't expect to get such a low
> overhead in real world situations. The worst case is maybe a
> long-lived array of these new wrappers: instead of using a native
> array, it will use an array of pointers and one object per element, so
> the memory overhead will be huge.
>
> But as long as you remain aware that these are just wrappers and need
> to be casted to/from the underlying primitive for long-term storage
> you should be OK.

I tried to design it that way that the calculation kicking in with an implicit
conversion returns the raw type (Int) again. So I hope that the intermediate
wrapper object never gets really "stored".
The test was run repeatedly (how often just caliper knows) on an array of 1.5
Mio Ints which where subject to a check addition / multiplication with the
result stored in a target array.
However did not "reuse" the result array - I will expand my test to see, if
this greatly degrades performance if I go on calculating on the checked
addition result.

Greetings
Bernd

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland