Checked integral arithmetic V0.1

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/...

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
>

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

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@gmail.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@bacon.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
> >

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

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