Actually, more like Numbers did a number on me. But we’re good friends now. Numbers is ready to go. This is a long post; Numbers is big.

In the previous post, A numbers game, I talked about how I might approach implementing clojure.lang.Numbers, the heart of the implementation of arithmetic in Clojure. At the end of that post was a section called “What we’ll do”:

  • Implement enough of Ops and its subclasses to get equiv, compare, and hasheq
  • Maybe contemplate whether there is a better way to accomplish the two-parameter arg dispatch in F#.
  • Definitely contemplate how to get the remaining operations, mostly arithmetic operations, working with this when we have the other pieces to make that possible. (But mostly kicking this can down the road.)

I ended up implementing all of it except for one tiny piece that won’t be needed until much later. I did end up changing the type-dispatch based on some benchmarking And the third point is now moot.

Here’s how it went down, including a quick look at the internals of Numbers.

The whole enchilada

I had contemplated porting just enough of Numbers to enable continued work on the collections implementation. Two reasons for this: (1) some concerns about how entangled Numbers was with other parts of Clojure; and (2) Numbers is big. For (1), further analysis showed that the entanglement was not too bad. For (2), to give you an idea, my port of just the code in Numbers itself has around 650 member methods. That does not include some of the supporting classes, such as Ratio and BigInt. But I finally decided to do it all just to make sure I was not missing something that would be a bigger problem down the road.

Dispatching dispatch

In the previous post, we discussed the need to take objects and map them to a numerical category, and take pairs of objects and map them to a common category.

Our categories are L = Long, D = Double, R = Ratio, BI = BigInteger and BD = BigDouble, UL = Unsigned long and CD = decimal (CLR built-in). Our mapping table is this:

* L D R BI BD UL CD
L > L D R BI BD BI CD
D > D D D D D D D
R > R D R R BD R BD
BI > BI D R BI BD BI BD
BD > BD D BD BD BD BD BD
UL > BI D R BI BD UL CD
CD > CD D BD BD BD CD CD

I couldn’t think of anything simpler than just using an enum to represent the categories, and 2D array to represent the table.

Mapping an object to its category is a simple match on type. The code, leaving out some of the table initialization–that gets boring quickly– is here:

type OpsType =
    | Long = 0 | Double = 1 | Ratio = 2 | BigInteger = 3
    | BigDecimal = 4 | ULong = 5  | ClrDecimal = 6

module OpsSelector =

    let selectorTable =
        array2D
            [|  // first row of table
                [| OpsType.Long; OpsType.Double; OpsType.Ratio; OpsType.BigInteger;
                  OpsType.BigDecimal; OpsType.BigInteger OpsType.ClrDecimal |]

                // etc

             |]

    let ops (x: obj) : OpsType =
        match Type.GetTypeCode(x.GetType()) with
        | TypeCode.SByte
        | TypeCode.Int16
        | TypeCode.Int32
        | TypeCode.Int64 -> OpsType.Long


        | TypeCode.Byte
        | TypeCode.UInt16
        | TypeCode.UInt32
        | TypeCode.UInt64 -> OpsType.ULong

        | TypeCode.Single
        | TypeCode.Double -> OpsType.Double

        | TypeCode.Decimal -> OpsType.ClrDecimal

        | _ ->
            match x with
            | :? BigInt
            | :? BigInteger -> OpsType.BigInteger
            | :? Ratio -> OpsType.Ratio
            | :? BigDecimal -> OpsType.BigDecimal
            | _ -> OpsType.Long

    let combine (t1: OpsType, t2: OpsType) = selectorTable[int (t1), int (t2)]

(I’ll back to that placement of Byte later on.)

Yes, you have to set your enum values and arrange the table properly. I have a unit test that explicitly lists and checks for all 49 entries. But we now can see the interactions all in one place; that beats chasing around a 4000-line file hunting down the connections.

Unsurprisingly, array lookup is faster than working through virtual methods as the current implementation does. More than twice as fast.

The benchmark results are:

Method Mean Error StdDev Ratio RatioSD
TypeCombine 349.9 us 6.98 us 10.23 us 1.00 0.00
LookupCombine 178.9 us 2.81 us 2.63 us 0.51 0.02
LookupCombine2D 168.9 us 2.04 us 1.91 us 0.48 0.02

TypeCombine is the virtual method approach. LookupCombine2D is the 2D table lookup. The LookupCombine was a version of table lookup that used an array of arrays rather than a 2D array. That requires an extra array lookup. Just thought I’d check. Not least because in the virtual method approach, the combine operation hands back the implementation object for the category. In my 2D approach, combine hands back an enum which I then use to index into an array of objects. So I end up with two array lookups. I’m pretty confident from this test that that is still a win.

The benchmark code can be found here.

Clojure arithmetic

Check out the Clojure cheatsheet for a handy list of Clojure functions. For our purposes, look under the heading Primitives/Numbers; the functions listed as Arithmetic, Compare, Bitwise, and Unchecked, as well as a few others such as zero? all rely on the class clojure.lang.Numbers.

Much of the complexity of Numbers comes from the implementation of the arithmetic operators. The functions +, -, *, inc, and dec are all quite similar. And they come in quoted versions: +', =', etc. The functions unchecked-add and the other unchecked- functions will come into play, too.

Here again is the Clojure source for +:

(defn +
  "Returns the sum of nums. (+) returns 0. Does not auto-promote
  longs, will throw on overflow. See also: +'"
  {:inline (nary-inline 'add 'unchecked_add)
   :inline-arities >1?
   :added "1.2"}
  ([] 0)
  ([x] (cast Number x))
  ([x y] (. clojure.lang.Numbers (add x y)))
  ([x y & more]
     (reduce1 + (+ x y) more)))

You need to look at the :inline. The nary-inline call makes + expand into a call to Numbers.add or Numbers.unchecked_add depending on the value of *unchecked-math*. By comparison, here is the source for +':

(defn +'
  "Returns the sum of nums. (+') returns 0. Supports arbitrary precision.
  See also: +"
  {:inline (nary-inline 'addP)
   :inline-arities >1?
   :added "1.0"}
  ([] 0)
  ([x] (cast Number x))
  ([x y] (. clojure.lang.Numbers (addP x y)))
  ([x y & more]
   (reduce1 +' (+' x y) more)))

Unchecked math no longer comes into play. We just call Numbers.addP

Finally, unchecked-add is:

(defn unchecked-add
  "Returns the sum of x and y, both long.
  Note - uses a primitive operator subject to overflow."
  {:inline (fn [x y] `(. clojure.lang.Numbers (unchecked_add ~x ~y)))
   :added "1.0"}
  [x y] (. clojure.lang.Numbers (unchecked_add x y)))

It just uses Numbers.unchecked_add, so it is the same as + in an unchecked context. Note the slight variations in the comments:

  • +: “Does not auto-promote longs, will throw on overflow.”
  • +': “Supports arbitrary precision.”
  • unchecked-add: “uses a primitive operator subject to overflow.”

(The comment on + is incorrect – it will throw if *unchecked-math* is false, else it will “[use] a primitive operator subject to overflow.”)

Note that “auto-promote” and “supports arbitrary precision”. are the same: if the result of an operation cannot be represented in the type in question, promote to a wider type and do the computation there. As an example, add 1 to the maximum long value with each flavor of addition:

user=> (+ Int64/MaxValue 1)
...
integer overflow                          <---- BOOOOMMM!
user=>
user=> (+' Int64/MaxValue 1)
9223372036854775808N                      <-  BigInteger, our of Int64 range
user=> (unchecked-add Int64/MaxValue 1)
-9223372036854775808                      <- overflow, wrap around to negative
user=> (class *1)
System.Int64
user=> (== *2 Int64/MinValue)
true
user=>

We will dig into Numbers.add, Numbers.addP, and Numbers.unchecked_add. The other arithmetic operators are similar. Numbers.add has a lot of overloads:

add(x: obj, y: obj)
add(x: double, y: double)
add(x: int64, y: int64)
add(x: uint64, y: uint64)
add(x: decimal, y: decimal)
add(x: double, y: obj)
add(x: obj, y: double)
add(x: double, y: int64)
add(x: int64, y: double)
add(x: double, y: uint64)
add(x: uint64, y: double)
add(x: int64, y: obj)
add(x: obj, y: int64)
add(x: uint64, y: obj)
add(x: obj, y: uint64)
add(x: int64, y: uint64)
add(x: uint64, y: int64)

And the same for addP and unchecked_add. (Starting to get an idea why there are 650 methods in Numbers?)

Why so many overloads? Why these in particular?

Leaving out decimal for the moment, the types mentioned are the three primitive numeric types you are likely to run into–double, int64 and uint64–plus obj, which covers everthing else. The sixteen entries cover all pairs. The ones with specific numeric primitive type will be called if there is an inferred type at the point of invocation. Depending on the particulars, we might be able to avoid boxing, both at the call site and inside the method itself.

Take the double overloads in all their glory:

    static member add(x: double, y: double) = x + y
    static member add(x: double, y: obj) = x + y
    static member add(x: obj, y: double) = x + y
    static member add(x: double, y: int64) = x + double (y)
    static member add(x: int64, y: double) = double (x) + y
    static member add(x: double, y: uint64) = x + double (y)
    static member add(x: uint64, y: double) = double (x) + y

Because double is contagious – if there is a double in your computation, the other argument will be converted to double.– in the overloads of double with the primitive numeric types, we just convert and do the addition – not boxing.

(For some reason the double/obj and obj/double methods on the JVM are written the equivalent of static member add(x: double, y: obj) = Numbers.add (x, convertToDouble (y)) I have no idea why. If you do, let me know.)

As a bonus, the return type for each is double, providing typing for the result that might avoid boxing at the call site.

The situation is more complicated when overflow is involved. (double arithmetic does not overflow – +/-Inf take care of that.) Let’s look at int64. We cannot just define

    static member add(x: int64, y: int64) = x + y

because the + operator is unchecked. In C#, one could wrap this in checked context. In F#, there are checked versions of the arithmetic operators, but I’ve not found a good way to use them locally; see [this StackOverflow entry] https://stackoverflow.com/questions/2271198/f-checked-arithmetics-scope) for an example. (The JVM version uses java.util.math.addExact(long,long)) here.) So we’ll do it ourselves.

How can we tell if an overflow has occurred?

Overflow occurs when the result of the addition cannot be represented in the type in question. With unchecked addition, you still get a result, its just not the arithemetically correct answer: 9223372036854775807L + 1L = -9223372036854775808L. Overflow in addition cannot happen when the operands are of differing sign (+/-). The symptom of overflow is that operands have the same sign and the result has the opposite sign. One could write a complicated condition to test for this. Or one could use some bit-twiddling magic to do it more efficiently.

In 2’s-complement arithmetic, the sign is carried in the most-signifiant bit (MSB). If you XOR two integers, the result will have 0 in the MSB if their MSBs agree (i.e., they have the same sign) and 1 if they disagree. Thus a negative XOR result indicates differing sign. Our overflow test is that the sum differs in sign from both operands. Thus:

static member add(x: int64, y: int64) =
    let ret = x + y

    if (ret ^^^ x) < 0 && (ret ^^^ y) < 0 then
        raise <| OverflowException("integer overflow")
    else
        ret

You are going to have do this kind of analysis for each of int64 , uint64, and decimal for each arithmetic operation. If your’re thinking those unchecked operators are looking better, well, they won’t help in the long run. addP is going to have to check for overflow, so you’re still going to have to put in the work. (Or you could try checked and catch overflow exceptions, but that just seems wrong.)

The other overloads of add for int64 pretty much have to throw in the towel. For example,

static member add(x: int64, y: obj) = Numbers.add (x :> obj, y)

In other words, just defer to add(obj,obj) and let it do its magic. This the default approach when you can’t figure out something more bespoke to do.

And thus we arrive at the most general case:

static member add(x: obj, y: obj) = Numbers.getOps(x, y).add (x, y)

We discussed this operation in detail in the previous post. We dispatch to an appropriate handler depending the types of the arguments, per the table given above.

This is not circular. The method we are defining above is Numbers.add. The add we calling there is on a class specialized for operations of a particular category, the category selected by the getOps.

Let’s continue with addition and look at addP. This is the promoting version of the operation. It has the same overloads as add. Promoting happens when the result of the operation is not representable in the type in question. That can’t happen with double, so the addP overloads involving double are identical to their add counterparts. For int64, the result not being representable is just the condition of overflow. Promotion here means to move to a type that can represent the result. Thus

static member addP(x: int64, y: int64) =
    let ret = x + y

    if (ret ^^^ x) < 0 && (ret ^^^ y) < 0 then
        Numbers.addP (x :> obj, y :> obj)
    else
        ret :> obj

When overflow is detected, rather than throwing an OverflowException as we did in add, we default to the double-obj case, which is just as you might expect:

static member addP(x: obj, y: obj) = Numbers.getOps(x, y).addP (x, y)

And I’ve never understood why this is coded this way. Because here’s what’s going to happen. The getOps is going to hand us a LongOps object because both arguments are int64 and our combination table says L x L -> L. In LongOps.addP we are going to do the exact same thing as here: do the addition and the check for overflow. The difference is what we do on this overflow. We call Numbers.BIGINT_OPS.add (x, y). WHy didn’t we just do that directly? Are we afraid that somewhere down the line int64 overflows are going to be handled by something other than BigInt? We incur a cost here of an extra method call, to conversions of the boxed integers, and the extra addition/overflow check. (I’ll probably be changing to a direct call and just leave note in the code.)

After all that, unchecked_add is marvelously uncomplicated. Just unchecked addition using the built-in operation.

static member unchecked_add(x: int64, y: int64) = x + y

And the general case is handled in the usual way:

static member unchecked_add(x: obj, y: obj) =
    Numbers.getOps(x, y).unchecked_add (x, y)

The general case

The static class Numbers itself provides the entry points that Clojure code calls into. Where possible, as you’ve seen, it will try to do the operation. But the general case always comes down to: take the operands, determine what category of number we should be working in–L, D, R, BI, BD, UL, or CD, as above– and hand it off to a specialized object. These objects implement the Ops inteface:

type Ops =
    abstract isZero: x: obj -> bool
    abstract isPos: x: obj -> bool
    abstract isNeg: x: obj -> bool

    abstract add: x: obj * y: obj -> obj
    abstract addP: x: obj * y: obj -> obj
    abstract unchecked_add: x: obj * y: obj -> 

    ...

There is class for each numeric category: LongOps, DoubleOps, etc. When a method on one of these is invoked, say BigDecimalOps, you know that you are working in a context where the arguments can be converted to the type in question, namely BigDecimal. Do that, compute your result accordingly.

A few examples will give the general idea. For DoubleOps,

member this.add(x, y) : obj =
    convertToDouble (x) + convertToDouble (y) :> obj

while for LongOps:

member this.add(x, y) : obj =
    Numbers.add (convertToULong (x), convertToULong (y))

Here is why it hard to decouple Numbers from the Ops classes. They call back and forth.

There are some other tricks used in the code. For example, for types that do not involve promotion (D, R, BI, and BD), the P versions of the operations can just call the regular versions:

member this.addP(x, y) = (this :> Ops).add (x, y)

Given that these things are true for four classes, we capture those commonalities in an abstract base class for those specific classes.

With this background, you should be able to work through the rest of the code. It all comes down to the peculiarities of the individual categories.

The problem with Byte

In Java, the primitive type byte is signed. The CLR has both Byte and SByte, unsigned and signed, respectively. Byte is used when you are doing byte-level work for I/O, etc. I don’ think I’ve every used SBtye.

When I created the signed and unsigned hierarchies, I assigned Byte to the unsigned side.

      sbyte <  int16 <  int32 <  int64 
       byte < uint16 < uint32 < uint64

Though that is technically pure, the result is that (+ b 1), where b is byte, ends up involving BigInt because we are mixing signed and unsigned integers, which takes us into int64 and uint64 by promotion, and those two combine to BigIntOps. I’m not sure that’s what people would expect.

When I first thought about adding proper handling of unsigned, I debated just promoting all the unsigned type other than uint64 into int64–their values are all representable in int64. Only uint64 has values not representable in int64 (and vice versa). The fact is that is almost impossible to stay working with any primitive numeric type other than int64 and double in Clojure.

I have a dream of someday adding a compiler mode that allows all the primitive types to be handled efficiently. It certainly would be non-portable and hence need to be a switched feature. But I’m thinking here of someone like a person using Clojure in Unity where efficiency in handling those numeric types is important.

Status

As I write this, I have completed porting the Numbers code. I’m writing tests like crazy. In an upcoming post I’ll provide a link to a snapshot of the code at this point.

In the process of writing tests, I found bugs that I traced back to the original code. (My code, not the JVM code.) These are all edge cases in the handling of decimal and uint64. Code to handle those types are a very recent addition. I will be doing bug fixes in the current code.