- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers

# Checked integral arithmetic V0.1

Tue, 2011-11-15, 22:27

Hi scalaists,

inspired by a recent discussion I implemented a "toy version" of checked

integral arithmetic for scala.

I think it has grown enough that it might be useful for somebody to play with

it. It uses enrichment pattern to provide new operators for the integral types

(+?, -?, *?, /?) which check for overflow. The performance penalty is a

slowdown of a factor of ~2-3. However Long multiplication check is far worse.

Repo is there:

http://github.com/bjohanns2002/scalax-checkedarithmetic

Of course - feedback is welcome :-)

Greetings

Bernd

Tue, 2011-11-15, 23:17

#2
Re: Checked integral arithmetic V0.1

Just wondering... could arithmetic with overflow checking be

implemented as a Numeric[Either[Int, Overflow]] typeclass?

(alternately Numeric[Option[Int]] if you dont need to capture data

about the overflow)

That would potentially allow you to sub in and out checking. Such as

using checking in Development, and Unchecked in Production for speed.

-Ben

On Wed, Nov 16, 2011 at 8:26 AM, Bernd Johannes wrote:

> Hi scalaists,

>

> inspired by a recent discussion I implemented a "toy version" of checked

> integral arithmetic for scala.

>

> I think it has grown enough that it might be useful for somebody to play with

> it. It uses enrichment pattern to provide new operators for the integral types

> (+?, -?, *?, /?) which check for overflow. The performance penalty is a

> slowdown of a factor of ~2-3. However Long multiplication check is far worse.

>

> Repo is there:

> http://github.com/bjohanns2002/scalax-checkedarithmetic

>

> Of course - feedback is welcome :-)

>

> Greetings

> Bernd

>

Tue, 2011-11-15, 23:27

#3
Re: Checked integral arithmetic V0.1

On Wed, Nov 16, 2011 at 09:00:13AM +1100, Ben Hutchison wrote:

> Just wondering... could arithmetic with overflow checking be

> implemented as a Numeric[Either[Int, Overflow]] typeclass?

> (alternately Numeric[Option[Int]] if you dont need to capture data

> about the overflow)

This is an interesting idea but I don't think it would work.

A lot of important methods in Numeric (e.g. comparison methods) don't

return T but instead return a Boolean, or an Int. Code using those

methods with your Option[Int] class would crash at runtime if you tried

to do comparisons (for instance comparing a T to zero) using any of

those other methods, since otherwise it'd have to return true or false

(either of which would be wrong).

I don't think you would buy yourself much over just crashing like

Bernd's implementation does.

Tue, 2011-11-15, 23:37

#4
Re: Checked integral arithmetic V0.1

On Wed, Nov 16, 2011 at 9:07 AM, Erik Osheim wrote:

> On Wed, Nov 16, 2011 at 09:00:13AM +1100, Ben Hutchison wrote:

>> Just wondering... could arithmetic with overflow checking be

>> implemented as a Numeric[Either[Int, Overflow]] typeclass?

>> (alternately Numeric[Option[Int]] if you dont need to capture data

>> about the overflow)

>

> This is an interesting idea but I don't think it would work.

>

> A lot of important methods in Numeric (e.g. comparison methods) don't

> return T but instead return a Boolean, or an Int. Code using those

> methods with your Option[Int] class would crash at runtime if you tried

> to do comparisons (for instance comparing a T to zero) using any of

> those other methods, since otherwise it'd have to return true or false

> (either of which would be wrong).

You have a point. The state the issue another way, Option[Int] is

difficult to define an Ordering for.

Its not an insurmountable obstacle however. Either decouple Ordering

from the Arithmetic operators by splitting Numeric into finer grained

traits (the correct long term solution IMO), or simply assume that

None (ie an overflow result) is always less (or greater) than

Some(Int).

-Ben

Wed, 2011-11-16, 00:57

#5
Re: Checked integral arithmetic V0.1

When I first started writing SafeLong, it was actually a typeclass for Either[Long,BigInt], but i ended up just creating a class for it. Polymorphism seemed like a better fit and had speed benefits. But Either was a nice fit.

On Nov 15, 2011 5:00 PM, "Ben Hutchison" <brhutchison [at] gmail [dot] com> wrote:

>

> Just wondering... could arithmetic with overflow checking be

> implemented as a Numeric[Either[Int, Overflow]] typeclass?

> (alternately Numeric[Option[Int]] if you dont need to capture data

> about the overflow)

>

> That would potentially allow you to sub in and out checking. Such as

> using checking in Development, and Unchecked in Production for speed.

>

> -Ben

>

> On Wed, Nov 16, 2011 at 8:26 AM, Bernd Johannes <bjohanns [at] bacon [dot] de> wrote:

> > Hi scalaists,

> >

> > inspired by a recent discussion I implemented a "toy version" of checked

> > integral arithmetic for scala.

> >

> > I think it has grown enough that it might be useful for somebody to play with

> > it. It uses enrichment pattern to provide new operators for the integral types

> > (+?, -?, *?, /?) which check for overflow. The performance penalty is a

> > slowdown of a factor of ~2-3. However Long multiplication check is far worse.

> >

> > Repo is there:

> > http://github.com/bjohanns2002/scalax-checkedarithmetic

> >

> > Of course - feedback is welcome :-)

> >

> > Greetings

> > Bernd

> >

Wed, 2011-11-16, 07:27

#6
Re: Checked integral arithmetic V0.1

Am Dienstag, 15. November 2011, 22:56:54 schrieb Erik Osheim:

> On Tue, Nov 15, 2011 at 10:26:01PM +0100, Bernd Johannes wrote:

> > inspired by a recent discussion I implemented a "toy version" of checked

> > integral arithmetic for scala.

>

> Hi Bernd,

>

> Looks promising!

>

> I haven't actually had time to read your code yet (still at work) but

> if you want to compare approaches, this is some code Tom Switzer wrote

> for a rational class we're working on. While the action taken when

> overflow occurs is different (in our case we increase precision, in

> your case you throw an error), the overflow check should be similar.

>

I was thinking along this line also - why not promote to a wider type to

capture the "required" precision? But I dropped it again because I fear the

effort to get this done / right is more than I can provide at the moment.

You have to do all the wiring and plumbing yourself effectively replacing all

the Numeric stuff from the standard (just gut feeling).

> You might find it useful to read, it's at:

>

> https://github.com/non/scala-numerics-refactor/blob/master/src/main/scala/n

> umerics/math/Rat.scala

I will have a look at it - for sure.

> Ultimately I think the problem of overflow (for code that isn't

> performance critical) could be solved in Scala through a well-written

> boxed number type, which could wrap the existing numeric types and

> promote itself through the numeric tower as needed to maintain

> precision when combined with other numbers, e.g.:

>

> /-> Float -*-> Double -------\

> Byte -> Short * / * -> BigDecimal -> Rational

> \-> Int -*-> Long -> BigInt -/

>

A good idea. The goal should be that it provides faster arithmetic and / or

less memory consumption than the existing Big* types (if none of these goals

could be met one would use the Big* type directly).

> One other suggestion... if you're seeing a x2-3 slowdown it may be due

> to the boxing you're doing. You could probably write a compiler plugin

I'm not sure. I would expect the slowdown to be far more dramatic if boxing

would occur.

E.g. two Int additions, a fetch and store to an array and a while predicate

take ~1,4 ns on my system. The same with one addition replaced by a checked

addition takes ~3,9 ns.

So the overhead for one checked addition is around ~2,5 ns. Internally I

perform a Long addition to capture overflows. A "raw" Long addition cycle

takes rougly twice the time of a "raw" Int addition cycle. So the remaining

overhead is somewhere ~1 ns. I would be flabbergasted if the VM / scala could

sponsor the creation and destruction of a complete object within 1 ns!

I rather think escape analyses (or whatever magic the JVM / the compiler

applies) has completely erased the object creation already.

> (along the lines of what I did for Numeric) if you wanted to be sure to

> eliminate the object allocations and boxing. You can see the plugin

> here:

>

> https://github.com/azavea/numeric/blob/master/plugin/src/main/scala/com/aza

> vea/math/plugin/OptimizedNumeric.scala

I suppose this will make for a tough reading. Somehow I feel not prepared yet

for compiler plugin writing ;-)

Greetings

Bernd

Wed, 2011-11-16, 08:07

#7
Re: Checked integral arithmetic V0.1

Am Dienstag, 15. November 2011, 23:07:05 schrieb Erik Osheim:

> On Wed, Nov 16, 2011 at 09:00:13AM +1100, Ben Hutchison wrote:

> > Just wondering... could arithmetic with overflow checking be

> > implemented as a Numeric[Either[Int, Overflow]] typeclass?

> > (alternately Numeric[Option[Int]] if you dont need to capture data

> > about the overflow)

>

> This is an interesting idea but I don't think it would work.

>

> A lot of important methods in Numeric (e.g. comparison methods) don't

> return T but instead return a Boolean, or an Int. Code using those

> methods with your Option[Int] class would crash at runtime if you tried

> to do comparisons (for instance comparing a T to zero) using any of

> those other methods, since otherwise it'd have to return true or false

> (either of which would be wrong).

>

> I don't think you would buy yourself much over just crashing like

> Bernd's implementation does.

>

On Tue, Nov 15, 2011 at 10:26:01PM +0100, Bernd Johannes wrote:

> inspired by a recent discussion I implemented a "toy version" of checked

> integral arithmetic for scala.

Hi Bernd,

Looks promising!

I haven't actually had time to read your code yet (still at work) but

if you want to compare approaches, this is some code Tom Switzer wrote

for a rational class we're working on. While the action taken when

overflow occurs is different (in our case we increase precision, in

your case you throw an error), the overflow check should be similar.

You might find it useful to read, it's at:

https://github.com/non/scala-numerics-refactor/blob/master/src/main/scal...

Ultimately I think the problem of overflow (for code that isn't

performance critical) could be solved in Scala through a well-written

boxed number type, which could wrap the existing numeric types and

promote itself through the numeric tower as needed to maintain

precision when combined with other numbers, e.g.:

/-> Float -*-> Double -------\

Byte -> Short * / * -> BigDecimal -> Rational

\-> Int -*-> Long -> BigInt -/

One other suggestion... if you're seeing a x2-3 slowdown it may be due

to the boxing you're doing. You could probably write a compiler plugin

(along the lines of what I did for Numeric) if you wanted to be sure to

eliminate the object allocations and boxing. You can see the plugin

here:

https://github.com/azavea/numeric/blob/master/plugin/src/main/scala/com/...