# Enhanced Primitive Support

363 views

### Rich Hickey

Jun 17, 2010, 4:13:54 PM6/17/10
to Clojure
I've been doing some work to enhance the performance, and unify the
semantics, of primitives, in three branches. I've started to document
this work here:

https://www.assembla.com/wiki/show/clojure/Enhanced_Primitive_Support

Feedback welcome,

Rich

### Rob Lachlan

Jun 17, 2010, 5:10:15 PM6/17/10
to Clojure
I think the enhanced support for primitives is fantastic. I'm looking
forward to doing more numerical work in clojure.

Quibble: Using a multiple-recursive algorithm for calculating
fibonnaci values.

user> (defn fib-2 [n] (if (>= n 1)
(loop [i 0 f0 0 f1 1]
(if (== i n) f0 (recur (inc i)
f1
(+ f0 f1))))))
#'user/fib-2
user> (time (fib-2 38))
"Elapsed time: 0.12 msecs"
39088169

I understand that it's just for demonstration purposes, but
impressionable people (like me!) might not know better.
(Of course, we can calculate fibonacci values using the closed form
formula, but that's neither here nor there.)

Other than that, looks great.

Rob

### Rich Hickey

Jun 17, 2010, 5:15:57 PM6/17/10
to Clojure

On Jun 17, 5:10 pm, Rob Lachlan <robertlach...@gmail.com> wrote:
> I think the enhanced support for primitives is fantastic.  I'm looking
> forward to doing more numerical work in clojure.
>
> Quibble:  Using a multiple-recursive algorithm for calculating
> fibonnaci values.
>
> user> (defn fib-2 [n] (if (>= n 1)
>                   (loop [i 0 f0 0 f1 1]
>                     (if (== i n) f0 (recur (inc i)
>                                            f1
>                                            (+ f0 f1))))))

Naive fib is often used as a benchmark, the point being not to do a
fast fib, but comparative, 'what is the perf on naive fib'? Not being
tail-recursive, it tests function calling overhead, and thus here
demonstrates what we gain by not having to box on args and returns.

Rich

### Rob Lachlan

Jun 17, 2010, 5:20:08 PM6/17/10
to Clojure
Ah -- well that makes sense then. Bravo!

Rob

### Mark Engelberg

Jun 17, 2010, 9:55:10 PM6/17/10
It's great to be discussing the possibility of enhanced primitive support.

I like most of the proposals. But this part troubles me:

# For bigints, specify bigints
* new literal bigint format 42N
# bigints contagious, no more auto-reductions
* (\+ 0N 21 21) => 42N

One of the big reasons I prefer Clojure over languages like Scala/F#
is that in Clojure, numbers "just work". I don't have to worry about
overflow errors, and the use of numbers in sets/hash tables is
generally pretty intuitive (it gets a little wonky if you're using
numbers produced by Java methods, but at least you're good if you stay
within Clojure).

As a case in point, consider writing a naive recursive factorial function.

(defn fact [n]
(if (zero? n) 1 (* n (fact (dec n)))))

In Clojure, (fact 3) produces the Integer 6. (fact 40) produces the
BigInteger 815915283247897734345611269596115894272000000000. It just
works. The answers produced by fact can be used in collections,
compared for equality with other numbers.

In F#, Scala, if you want factorial to not break on something like an
input of 40, you have to essentially use the bigint literal syntax
like what you're proposing:
(defn fact [n]
(if (zero? n) 1N (* n (fact (dec n)))))

Now, the results of this function are "contaminating bigints" which
can't be used as effectively with other Clojure data structures. As
you pointed out, it causes problems when the same number can have two
different type representations depending on the sequence of
computations used to get to that number. This will always be somewhat
of a problem due to Java interop, but it's important to me that all
numbers arrived at through Clojure computations just work with respect
to equality and use in sets/hash tables. The lack of auto-reduction,
in conjunction with the proposal to make equality take numeric type
into account, will really cripple the utility of bigints.

Even more frustrating, in my experience with languages like F# and
Scala, functions written like this are way, way slower. The reason is
that Java's bigint arithmetic is sloooooow. To protect yourself from
overflow, you've forced the function to use bigint arithmetic on
1N*2N*3N*..., well before you even reach a bigint. For this
particular function, it reaches bigint status quite quickly, so the
performance degradation is fairly minimal. But I have found that in
general, requiring programmers to explicitly use bigint arithmetic for
small numbers in order to protect from overflow is an absolute
performance killer. Clojure's technique of auto-promotion to bigint
upon overflow, and then auto-reduction when appropriate, is way, way
faster than using bigints all the time.

In summary:
No auto-reduction would make bigints second-class citizens and make
them difficult to use in other functions and collections.
No auto-promotion to bigints means that programmers who want to
protect from overflow have to use bigints everywhere, which destroys
performance.

So what would be the downside of implementing most of these proposals
(e.g., 1 is a literal for long 1), but retain auto-promotion and
auto-reduction rather than throwing an error for primitive long math?
Seems to me like this would be the best of both worlds. What am I
missing?

### Rich Hickey

Jun 17, 2010, 11:00:57 PM6/17/10

You raise several points, I'll take them in turn. First, things are
not as dire as you state. Certainly one could write a version of fact
that hardwired bigints as you showed. But you need not - here's the
original naive definition:

(defn fact [n]
(if (zero? n) 1 (* n (fact (dec n)))))

Such logic that doesn't specify one of the components (in this case,
n) is still polymorphic, as are operations with mixed components. So
the power is in the hands of the supplier of n:

user=> (fact 10)
3628800

user=> (fact 40)
java.lang.ArithmeticException: integer overflow

user=> (fact 40N)
815915283247897734345611269596115894272000000000N

I think you can always write code in this way, such that it will work
with any of the numeric types, without dictating.

----
It is true that Java's BigIntegers are slow, especially for numbers
small enough to fit in Long or Integer, so using them for smaller
numbers has overhead. But there are other options, not yet pursued
here. For instance, Kawa has a higher performing biginteger that uses
an internal int component until it overflows. I'm sure no one has a
particular attachment to BigInteger should we find a better
alternative. It would be easy to create a big integer class based on
the Kawa concept, perhaps with a long or int basis overflowing to
BigInteger itself.

----------
As far as performance killer, that depends on your perspective. It is
my belief that overwhelming majority of code *never* uses numbers that
exceed long, And those people are suffering a 'performance killer' on
the order of 10-20x by having numbers be boxed all the time.

------
The interaction between equality and the BigInteger schism is
something I am still thinking about. That is why the branches are
staged. Only the 'equal' branch has the type-strict =

--------
The thing that you are missing is that there is no single
representation on the JVM* that can hold either a primitive or a
reference to an Object like a BigInteger. That is where the current
semantic difference creeps in - a primitive op sourced by a primitive
must have as its target a primitive - should it produce an object
there would be nowhere to put it. And any interface points (like the
math operations themselves) cannot dynamically take either a primitive
or an object. So the auto-promotion has an unavoidable cost of the use
of objects to hold all values, and the allocation thereof. Opting out
of the objects means a change in semantics. Auto-promotion cannot be
made a uniform semantic for both primitives and objects.

---------
Another alternative is to provide a second set of operations with auto-
promoting, object based semantics. These would never operate on
primitives. Since a key argument for auto-promotion is the poor
behavior of small bigints, making a better bigint seems preferable.

--------
In the end, this does put the interests of two sides of the community
at odds. Only one set of interests can be the default. Part of the
point of this discussion is to measure the sides (so speak up people!).

I think the current default doesn't serve the majority well, and has a
semantic rift. Making ordinary programs that use longs and doubles run
fast requires extensive and tedious annotation that is easy to get
wrong. This work proves it could be completely otherwise.

Rich

* There are proposals:

http://blogs.sun.com/jrose/entry/fixnums_in_the_vm

Note that even on mature platforms like CL with very good tagging and
fixnum systems, actually getting at full-width 32- and 64-bit hardware
operations requires extensive, tedious and error-prone annotation.
I.e. a tagged number is not a hardware number.

### David Nolen

Jun 17, 2010, 11:47:36 PM6/17/10
On Thu, Jun 17, 2010 at 11:00 PM, Rich Hickey wrote:
In the end, this does put the interests of two sides of the community at odds. Only one set of interests can be the default. Part of the point of this discussion is to measure the sides (so speak up people!).

I am squarely on the side of prim/num/equals. The number of questions on the ML, #clojure, StackOverflow, etc. for the past two years about proper type-hinting shows how much incidental complexity the current system brings to the table.

Look no further than:
vs.

The difference is startling.

In order to write decently fast numeric code in Clojure up until now you had to be Christophe Grand ;) or have a fairly good understanding of macros that walk code to tag primitive types. And even so, the inability to return primitives made many nested recursive algorithms perform poorly. The only way to work around this was to convert your functions to macros and inline everything resulting of course in a considerable loss of modularity. Dirty hacks.

For those that need BigInts (the majority of whom are solving Project Euler problems, god bless them), telling them to add a single N is so much simpler than explaining the current complexities to newcomers who don't understand why floating point arithmetic is so darn slow.

More importantly, I think that deftype/defrecord/protocols/static/prim/num/equals represent an astounding work of *unification*. You no longer need to resort to Java - all the tools for building fast code is right there.

My gut feeling is that many Clojure devs won't think to much about this work - they've got their hands full with the rest of the language or are working in domains where they are under the impression that this unification work does not affect them. But I think this kind of work is paving the way for the community to give more of a helping hand to converting core data structures from Java to Clojure, extending them, patching them, and contributing new ones - all in a language that (unlike Java) naturally guides you to "do the right thing".

So though I don't know how much of a stir this thread will create (because I think it's more of a large under the surface wave), I have no doubt it will pay off in a big, big way.

### Mark Engelberg

Jun 17, 2010, 11:57:28 PM6/17/10
Thanks for the responses.

Going back to the naive factorial function:

(defn fact [n]
(if (zero? n) 1 (* n (fact (dec n)))))

Right now,
user=> (fact 40)
815915283247897734345611269596115894272000000000

Under the proposed changes,

user=> (fact 40)
java.lang.ArithmeticException: integer overflow

So the same code now risks an arithmetic exception. What have I, the
programmer, gained from this new level of risk? The answer, if I'm
the kind of programmer who has no interest in putting in type
annotations into the header of the function, is nothing. There is no
speed improvement without the additional type annotations. So all
I've gained is the /potential/ for a speed improvement.

I assume that most Clojure users really like its dynamic nature. If
this is true, then for most of us, the common case is to NOT annotate
our code with types. Certainly I like the idea of making it as easy
as possible to write fast code in Clojure. I want my dynamically
typed code to be as fast as it can be, and it's nice to know that
there is a way to write statically typed code that is even faster.
But I really don't want to incur a penalty (i.e., possibility of
Arithmetic Exception) when I'm not using type annotations.

I agree that the burden on those who want to write type annotated code
is too high. I agree that this should be made easier. But
ultimately, I still want the burden to be on them (or me, the 1% time
I need it), not those of us who prefer unannotated code. I that some
of the changes you have proposed for moving the annotations into the
header, along with literal notation for long (i.e., 0L rather than
(long 0)) would be preferable to the bigint dichotomy.

I agree that an improved bigint type would address the performance
aspect of my argument. On the other hand, it wouldn't really address
the problem of using these things in sets and hash tables. I think
it's very important that Clojure have one unique canonical
representation for numbers arrived at through Clojure-based
computations. It is very difficult to use numbers sanely if that's
not the case.

I see your point that there are a couple of sides to this argument. I
hope I can persuade some more people to speak up for my side :)

### David Nolen

Jun 18, 2010, 12:20:00 AM6/18/10
On Thu, Jun 17, 2010 at 11:57 PM, Mark Engelberg wrote:
I assume that most Clojure users really like its dynamic nature.  If
this is true, then for most of us, the common case is to NOT annotate
our code with types.  Certainly I like the idea of making it as easy
as possible to write fast code in Clojure.

The problem is that it distinctly *not* easy to write fast numeric code in Clojure. It requires expert Clojure knowledge. On the other hand, the mental burden for someone who wants BigInts in the new system is very low - you'll get a trivial to track exception.

And the new system doesn't remove any of the lovely dynamic stuff. There's absolutely no compromise there. In fact in the new system you can write your code initially sans ^:static and fn type hints entirely, you work to get your algorithm right, play around at the REPL as usual, then you add ^:static, type hint only the arglist and return value ...

BOOM, you get raw JVM speed.

But of course I'm biased as you are :) In two years I've never once been interested in BigInts. I have however have mangled and munged my code since 2008 trying to get basic numeric algorithms to perform even remotely in the vicinity to their Java counterparts to no avail.

David

### Daniel Gagnon

Jun 18, 2010, 12:22:27 AM6/18/10
The problem is that it distinctly *not* easy to write fast numeric code in Clojure. It requires expert Clojure knowledge. On the other hand, the mental burden for someone who wants BigInts in the new system is very low - you'll get a trivial to track exception.

Also, when done, it doesn't look like clojure anymore.

+1 on the new behaviour.

### Antony Blakey

Jun 18, 2010, 12:24:55 AM6/18/10

On 18/06/2010, at 12:30 PM, Rich Hickey wrote:

> You raise several points, I'll take them in turn. First, things are not as dire as you state. Certainly one could write a version of fact that hardwired bigints as you showed. But you need not - here's the original naive definition:
>
> (defn fact [n]
> (if (zero? n) 1 (* n (fact (dec n)))))
>
> Such logic that doesn't specify one of the components (in this case, n) is still polymorphic, as are operations with mixed components. So the power is in the hands of the supplier of n:
>
> user=> (fact 10)
> 3628800
>
> user=> (fact 40)
> java.lang.ArithmeticException: integer overflow
>
> user=> (fact 40N)
> 815915283247897734345611269596115894272000000000N

That's fine for fact, but as a consumer of library functions, how do I know when I should pass in bigints? How do I know when an intermediate value, for my particular combination of parameter values, is going to overflow?

Should I just use 'N' on every number to every function? This proposal destroys the black-box nature of functions, and seems to me to be the easy solution rather than the best solution, which, I acknowledge, might be very hard work, possibly involving every such function having 2 polymorphic variants, one generic boxed form and one unboxed form, automatically selected and call-site-cached like OO dispatch.

Antony Blakey
-------------
Ph: 0438 840 787

If you pick up a starving dog and make him prosperous, he will not bite you. This is the principal difference between a man and a dog.
-- Mark Twain

### David Nolen

Jun 18, 2010, 12:56:59 AM6/18/10
On Fri, Jun 18, 2010 at 12:24 AM, Antony Blakey wrote:

That's fine for fact, but as a consumer of library functions, how do I know when I should pass in bigints? How do I know when an intermediate value, for my particular combination of parameter values, is going to overflow?

If the library isn't communicating that to you isn't that just a broken API that you don't want to participate in? Tag information on arglists is available:

(defn foo [^BigInteger a b ^BigInteger c]
(+ a b))
(print (map (fn [xs] (map meta xs)) (:arglists (meta #'foo))))

;(({:tag BigInteger} nil {:tag BigInteger}))

IDEs can easily (and should) expose this.

David

### Jason Wolfe

Jun 18, 2010, 1:03:59 AM6/18/10
to Clojure
At first read this all looks awesome to me, and I'd love to see prim/
num/equals in 1.2!

Type hinting math has been a pain, I rarely need bigints and would be
happy being explicit about them when I do, and I can't think of
obvious cases where I'd need (equals? [2.0] [2]), which I gather will
no longer be possible in the equals branch (for any value of
"equals?").

Moreover, the distinction between = and .equals (and, hence, = and set/
map lookups) was a significant source of complexity and confusion for
me learning Clojure, and I'd be happy to see that go away.

I guess it'll take some experience to see if similar difficulties
arise with collections & boxing in the new setting, but at first
glance the new design seems very well thought-out.

One minor question: with this change, will it still be possible to do
primitive math on floats and ints? On modern machines I suppose
there's little reason to want this (other than perhaps saving memory),
but for other hosts like 32-bit dalkvik or javascript I'd imagine this
might present a performance problem?

Thanks!

### Richard Newman

Jun 18, 2010, 1:22:39 AM6/18/10
I don't want to commit to a full-fledged response on this issue (yet), but:

On the other hand, the mental burden for someone who wants BigInts in the new system is very low - you'll get a trivial to track exception.

Assuming that I understand your implication (that ArithmeticExceptions are trivial to track): that might be true in Java, with checked exceptions, but it wouldn't be true in Clojure. If some operations overflow some of the time, you need thorough tests… and for all of the libraries you use to have thorough tests. It's not a small mental burden to constantly fear that any library call at all could suddenly overflow at any time. What are we, C programmers?

Automatic type promotion is a good thing, if not without its quirks (map behavior being one of them). One of the fantastic things about Common Lisp is its rich numeric tower.

That said, if we could have speed and safety…

### Mark Engelberg

Jun 18, 2010, 1:23:35 AM6/18/10
On Thu, Jun 17, 2010 at 9:20 PM, David Nolen <dnolen...@gmail.com> wrote:
> The problem is that it distinctly *not* easy to write fast numeric code in
> Clojure. It requires expert Clojure knowledge.

Right, but with just the prim branch and a shorthand for long literals, you get:
(defn ^:static fib ^long [^long n]
(if (<= n 1L)
1L
(+ (fib (dec n)) (fib (- n 2L)))))

which really isn't that bad. So my claim is that the prim branch gets
you far enough along the road to easy fast numeric code, without
screwing with the numeric tower.

### Mark Engelberg

Jun 18, 2010, 1:33:17 AM6/18/10
Hmmm, here's an idea:

How about inside of a static function with type annotations, all
literals are automatically converted into long and doubles, otherwise
behavior stays the same.

So:

(defn ^:static fib ^long [^long n]

(if (<= n 1)
1
(+ (fib (dec n)) (fib (- n 2)))))

is automatically converted to

(defn ^:static fib ^long [^long n]

(if (<= n (long 1))
(long 1)
(+ (fib (dec n)) (fib (- n (long 2))))))

whereas
(defn fib [n]
(if (<= n 1)
1
(+ (fib (dec n)) (fib (- n 2)))))
works the way it always did.

This behavior makes a lot of sense because (I think) the only time you
really gain from literals being primitives is when the variables
around it are also hinted. Otherwise, the polymorphic nature of the
variable will cause the literal to get boxed anyway.

### Richard Newman

Jun 18, 2010, 1:43:44 AM6/18/10
> ... which, I acknowledge, might be very hard work, possibly
> involving every such function having 2 polymorphic variants, one
> generic boxed form and one unboxed form, automatically selected and
> call-site-cached like OO dispatch.

That's pretty much what Common Lisp compilers do. The compiler (or
your own compiler macro, if you so choose) can examine the input forms
and the compiler environment to decide what code to produce.

The following is from Allegro Common Lisp, but all of the input is
ANSI CL -- part of the spec.

Observe how the compiler switches between different implementations of
trivial addition as it gets a progressively looser or tighter bound on
x. (I've elided some of the irrelevant preamble.)

What would be nice is if Clojure and/or the JVM could produce safe
code/bytecode that wouldn't overflow, but could also be JIT-optimized
into unboxed primitive arithmetic for known input ranges.

;; Range known, optimizing for speed: assembly add instruction.
cl-user(7): (disassemble
(compile nil
(lambda (x)
(declare (type (integer 0 255) x)
(optimize (speed 3)))
(+ x 2))))
...
15: 48 83 c7 10 add rdi,\$16
19: f8 clc
20: 4c 8b 74 24 10 movq r14,[rsp+16]
25: c3 ret

;; We know that x is a fixnum: the arithmetic doesn't need a
function call, but
;; the result will be a boxed bignum, because fixnum + 2 won't fit
in a fixnum.
;; If this function were inlined elsewhere, the compiler might
avoid that decision.
cl-user(8): (disassemble
(compile nil
(lambda (x)
(declare (type fixnum x)
(optimize (speed 3)))
(+ x 2))))
...
21: 74 01 jz 24
23: 17 (pop ss) ; sys::trap-signal-hit
24: 48 c1 ff 03 sar rdi,\$3
28: 49 c7 c5 02 00 movq r13,\$2
00 00
35: 49 03 fd addq rdi,r13
38: 4c 8b ef movq r13,rdi
41: 49 d1 e5 sall r13,\$1
44: 70 19 jo 71
46: 49 d1 e5 sall r13,\$1
49: 70 14 jo 71
51: 49 d1 e5 sall r13,\$1
54: 70 0f jo 71
56: 49 8b fd movq rdi,r13
59: f8 clc
60: 48 8d 64 24 78 leaq rsp,[rsp+120]
65: 4c 8b 74 24 10 movq r14,[rsp+16]
70: c3 ret
71: 41 ff 57 47 call *[r15+71] ; sys::box-to-new-bignum
75: eb ef jmp 60
77: 90 nop

;; Nothing known: call to excl::+_2op, the two-arg addition function.
cl-user(9): (disassemble
(compile nil
(lambda (x)
(declare (optimize (speed 3)))
(+ x 2))))
...
21: 74 01 jz 24
23: 17 (pop ss) ; sys::trap-signal-hit
24: 40 f6 c7 07 testb dil,\$7
28: 75 12 jnz 48
30: 48 83 c7 10 add rdi,\$16
34: f8 clc
35: 70 1e jo 67
37: 48 8d 64 24 78 leaq rsp,[rsp+120]
42: 4c 8b 74 24 10 movq r14,[rsp+16]
47: c3 ret
48: 49 8b af 2f ff movq rbp,[r15-209] ; excl::+_2op
ff ff
55: 48 c7 c6 10 00 movq rsi,\$16 ; 2
00 00
62: ff 53 d0 call *[rbx-48] ; sys::tramp-two
65: eb e2 jmp 37
67: 49 c7 c5 10 00 movq r13,\$16 ; 2
00 00
74: 49 2b fd subq rdi,r13
77: eb e1 jmp 48
79: 90 nop

### Antony Blakey

Jun 18, 2010, 1:44:33 AM6/18/10

On 18/06/2010, at 2:26 PM, David Nolen wrote:

> On Fri, Jun 18, 2010 at 12:24 AM, Antony Blakey <antony...@gmail.com> wrote:
>
> That's fine for fact, but as a consumer of library functions, how do I know when I should pass in bigints? How do I know when an intermediate value, for my particular combination of parameter values, is going to overflow?
>
> If the library isn't communicating that to you isn't that just a broken API that you don't want to participate in? Tag information on arglists is available:

No. How do I know whether I need to pass a bigint literal or not? For what possible input values will overflow be an issue? It's easy to see with fact, but that's because the function implementation is clearly visible, and has well known growth properties of a single argument. And it's not just literals - when functions are composed from other functions that have this same problem and return primitive types - hence using the static versions of functions - the question in general becomes impossible to answer, not only because there might be a number of parameters with interdependencies, but because the structure of intermediate results may not be visible to the consumer. And what if you don't have the source to the function? This proposal not only puts the burden of promotion and representation choice onto the user of a function, but it requires that promotion be done before the function is executed, in a precautionary way, rather than iff needed.

This proposal is IMO a very bad idea.

Antony Blakey
--------------------------

Ph: 0438 840 787

Lack of will power has caused more failure than lack of intelligence or ability.
-- Flower A. Newhouse

### David Nolen

Jun 18, 2010, 2:01:08 AM6/18/10
On Fri, Jun 18, 2010 at 1:44 AM, Antony Blakey wrote:
> On Fri, Jun 18, 2010 at 12:24 AM, Antony Blakey <antony...@gmail.com> wrote:
This proposal is IMO a very bad idea.

Why do you need know? You're assumption is built on someone writing a writing a bad library (one that doesn't handle long & BigInt that should). The tools are there for the library to behave correctly regardless of the input.

(defn fact [n]
(if (zero? n) 1N (* n (fact (dec n)))))

(fact 40)
(fact 40N)

both work. The burden is not on the consumer but the designer of the library. What's the problem?

David

### Mark Engelberg

Jun 18, 2010, 2:10:32 AM6/18/10
Why this is marked as abuse? It has been marked as abuse.
Report not abuse
On Thu, Jun 17, 2010 at 11:01 PM, David Nolen <dnolen...@gmail.com> wrote:
> What's the problem?
> David

It's a composability issue.
Elaborating on Anthony's explanation, let's say you call (fact (foo n)).

Do you know what values of n, when passed to foo, produce a value
large enough that fact will produce an exception? If you do know
this, do you know enough about the internals of foo to know the best
way to fix the problem? If you pass a bigint to foo, are you
guaranteed to get a bigint as an output, or do you need to explicitly
wrap a protective call to bigint between the two calls? In other
words, do you call (fact (foo 20N)) or (fact (bigint (foo 20))?

This imposes too high a burden on any programmer who cares about safety.

### David Nolen

Jun 18, 2010, 2:15:16 AM6/18/10
On Fri, Jun 18, 2010 at 2:10 AM, Mark Engelberg wrote:
This imposes too high a burden on any programmer who cares about safety.

Rich Hickey's branch work boil down to:

1) double/long crowd get to stop eating bark
2) BigInt crowd loses free lunch

I'd say this is a bona fide community compromise and Rich Hickey saw it coming :)

David

### David Nolen

Jun 18, 2010, 2:35:37 AM6/18/10
On Fri, Jun 18, 2010 at 2:10 AM, Mark Engelberg wrote:
Elaborating on Anthony's explanation, let's say you call (fact (foo n)).

This imposes too high a burden on any programmer who cares about safety.

Don't buy it. That's the whole point of BigInt contagion. If fact and foo are correctly written this will work.

(defn fact [n]
(if (zero? n) 1N (* n (fact (dec n)))))

(defn foo [n]
(inc n))

(fact (foo 40))
(fact (foo 40N))

Both work.

### Richard Newman

Jun 18, 2010, 2:58:08 AM6/18/10
This imposes too high a burden on any programmer who cares about safety.

Don't buy it. That's the whole point of BigInt contagion. If fact and foo are correctly written this will work.

It only takes one library to screw up, and the whole stack falls down.

Screwing up can occur because of omission (fact being written with a "1", not "1N", and not being tested with large inputs), or by design.

This whole debate arose because people care about the speed of their numeric functions! The safety bignums (which make things slower) will be omitted for performance reasons, or by accident, and people won't obey the contract of the function… or won't be able to because of the complex interactions between libraries. I can't control where every value in my program goes.

In Clojure as it stands now, those edge cases would see a small performance penalty as bignums occurred (and then it would go away if they got demoted!). After this change, a one-in-a-million collision of numbers and performance-oriented programming would throw an exception with no way to recover from higher up the stack.

A programmer who really cares about safety would thus indeed have to shoulder a massive burden: either review and get complete test coverage over every library in their dependency stack, or ensure that no non-bignum can ever enter a library function. I guess that also means no strings, no file sizes, no URLs, no values which might get recombined… because any of those values could produce a non-bignum and enter an unsafe Clojure library function, causing an overflow with no possibility of continuing. (This ain't Common Lisp.)

Having digested Rich's notes, pretty much the only thing that I disagree with is the lack of automatic bignum promotion/demotion. It seems like too much of a bad tradeoff, sacrificing one of Clojure's selling points for a little numeric performance. Thus far, Clojure has done pretty well in lexically scoping its "please make this fast and unsafe" bits — primitive calls, loop, transients. This would break that pattern.

I wonder: is there's a middle ground, where primitives are automatic almost everywhere, but bignum promotion on overflow is still possible?

### Antony Blakey

Jun 18, 2010, 3:12:11 AM6/18/10

+1, what I've been trying to say.

> I wonder: is there's a middle ground, where primitives are automatic almost everywhere, but bignum promotion on overflow is still possible?

That's what I was suggesting by having two versions of functions, one with primitives and one with boxed values. I did some investigation on this for a Smalltalk JIT using LLVM, in the form of partial specialisation e.g. dynamically generating type-specialised versions of functions (methods in ST) and using the types available at the call site to dispatch - which is more obvious in Clojure because we already have multi-method dispatch. For Clojure you wouldn't test all types, it could just be a binary choice of all primitives where expected or not Of course where a type-specialised function calls another type-specialised function you can avoid the dispatch entirely because you have the type information at the call site. This way, you can pay for the type-driven dispatch once at the start of a computation and end up doing minimal testing (basically dynamically checking that type invariants are maintained e.g. args haven't been promoted in the case under discussion). IMO this is speed + safety.

Antony Blakey
--------------------------
Ph: 0438 840 787

Reflecting on W.H. Auden's contemplation of 'necessary murders' in the Spanish Civil War, George Orwell wrote that such amorality was only really possible, 'if you are the kind of person who is always somewhere else when the trigger is pulled'.
-- John Birmingham, "Appeasing Jakarta"

### Chris Dean

Jun 18, 2010, 3:36:39 AM6/18/10
Richard Newman <holy...@gmail.com> writes:
> Having digested Rich's notes, pretty much the only thing that I
> disagree with is the lack of automatic bignum promotion/demotion. It

This nicely summarizes my thoughts. The other parts of Rich's notes
seem very elegant, but I can see lack of promotion leading to problem in
my own code. Some external input causing an intermediate result to
overflow would certainly happen. Probably at the least convenient time
possible.

(Have we discarded the concept of a set of non-promoting math functions
that are only used during optimization? prim-+ prim-/ etc.)

Cheers,
Chris Dean

### Nicolas Oury

Jun 18, 2010, 4:44:14 AM6/18/10
Dear all,

just finished to read the proposals.

- prim is great and would allow to keep performance in more idiomatic code
- I am pro-num.
It allows to get read of plenty of annotations or java methods.
Annotations are difficult for beginners, makes code hard to read, maintain and modify, even for experts.
Moreover, in those days of 64-bits integers, the need for bigint is quite rare, except for Fibonacci or factorial functions ;-b.
That's a bit provocative, but I think most code that needs bigints are "number-centric" code.
I mean code whose primary interest is the treatment of numbers.

Whereas every single program suffers from annotation or boxing.

Currently, all programs have to pay (annotations, speed, and/or java code).

I feel it is fairer that a few programs, that have high expectation on numbers, should pay.
I think, however, it is important we ensure they have a way to pay. And that it is not too expensive.

Maybe, it could be interesting to keep the old behaviour in safe-+, safe-* and the like?

Or, as Rich said, to make a good big numbers implementation that scales well to small integers.

Maybe, there should be a compiler option for default arithmetic :
* choose from long (the default default), int (for people wanting to run clojure on a mobile phone), FastAndCleverBigNums (for people caring about safety and having unusually big numbers)
* the same could be made for default decimal arithmetic.

One of the great benefit of num, is that it allows:

- equal, which is a big step forward.

Altogether, I like very much the fact that these proposals, together with protocols and datatypes, gives a way to obtain high performance Clojure code in a Java-agnostic way.
It seems a good thing for clojure in clojure and porting to other platforms.

Best regards,

Nicolas.

### Nicolas Oury

Jun 18, 2010, 4:48:49 AM6/18/10
On a totally different point:

is there a way of having he equivalent of #^final/#^static for defs?
Sometimes, you know a def won't be dynamically bound/redefined.
Would there be a benefit for the JITed code (less memory barriers or more asm reordering) to give a way to pass this information
to the JVM?

Best,

Nicolas.

### Christophe Grand

Jun 18, 2010, 5:44:52 AM6/18/10
On Fri, Jun 18, 2010 at 8:58 AM, Richard Newman <holy...@gmail.com> wrote:
> It only takes one library to screw up, and the whole stack falls down.
> Screwing up can occur because of omission (fact being written with a "1",
> not "1N", and not being tested with large inputs), or by design.

It can already happen: a library can screw you by design.

(defn fact [n] (loop [r (int 1) n (int n)] (recur (* r n) (dec n))))
user=> (fact 40)
java.lang.ArithmeticException: integer overflow (NO_SOURCE_FILE:0)

Actually people who want numerical perfs have to do very invasive type
hinting and other interfaces workaround because primitives are...
primitives (not objects).

With contagious bigints (let's nick name them "safeints" and assume
they are not BigInteger but something à la kawa) a single N on
literals or having all your inputs going through a safeint conversion
would trigger safe computations (unless you try to call a static
primitive-hinted fn but the compiler would then bark).

Of course a rogue fn can still internally convert to primitives and
overflow but you can't do anything to protect you from that.

As for mixing several numebr representations in a single collection, I
think it's a problem of normalizing data but most of the time your are
either in safeland or in fastland so your representations will be
homogeneous (safehints or (boxed) primitives).

A middleground may be to keep the semantics proposed by Rich but:
* integer literals default to safeint (unless suffixed by L for long)
* scientific notation and decimal literals default to double (unless
suffixed by M or N)
* implement a better bigint.

Christophe

--
European Clojure Training Session: Brussels, 23-25/6 http://conj-labs.eu/
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.cgrand.net/ (en)

### Michał Marczyk

Jun 18, 2010, 6:35:01 AM6/18/10
On 18 June 2010 05:57, Mark Engelberg <mark.en...@gmail.com> wrote:
> I assume that most Clojure users really like its dynamic nature.  If
> this is true, then for most of us, the common case is to NOT annotate
> our code with types.  Certainly I like the idea of making it as easy
> as possible to write fast code in Clojure.  I want my dynamically
> typed code to be as fast as it can be, and it's nice to know that
> there is a way to write statically typed code that is even faster.
> But I really don't want to incur a penalty (i.e., possibility of
> Arithmetic Exception) when I'm not using type annotations.
>
> I agree that the burden on those who want to write type annotated code
> is too high.  I agree that this should be made easier.  But
> ultimately, I still want the burden to be on them (or me, the 1% time
> I need it), not those of us who prefer unannotated code.  I that some
> of the changes you have proposed for moving the annotations into the
> header, along with literal notation for long (i.e., 0L rather than
> (long 0)) would be preferable to the bigint dichotomy.

QFT -- I'm in absolute agreement.

It seems to me that in its current shape, the new design -- actually
the "no automatic promotion/demotion" part -- would amount to
sacrificing correctness for performance *by default*; that doesn't
strike me as a good way to go. Not a single language I like using does
that... this of course includes my favourite language, Clojure, as it
currently stands on the master branch. :-)

Part of the reason why I think this is a bad idea is that while it is
all very well to say that people should know what they're doing,
libraries should be well-designed and have excellent test coverage
etc., this is not what happens in practice. (It's also perfectly
possible to write correct concurrent programmes with locks...). And
not necessarily through lack of dilligence; I know I have learned many
a gotcha by getting bitten by it (and rather expect to accumulate
plenty more "bites" in the years to come).

I suppose that's fine as long as one is learning something useful in
the process, but I should think that top numeric performance is
something required only by a certain part of the community -- a
sizeable one, no doubt, but hardly a majority share -- in fact
comprising the people most likely to know what they're doing when
dealing with numbers (why would someone *not* doing involved numeric
computations know what s/he's doing with numbers on a comparable level
to someone who is?). Making things significantly easier for them would
be welcome, of course, but perhaps not at the cost of making
*everyone* deal with entirely new kinds of complexity to support that.

I wouldn't know if the "good" solution Antony Blakey mentions is
feasible currently, but if it isn't, I'd prefer the language to err on
the side of caution, while perhaps offering a better system for
hand-annotating things for top performance (some people have been
using pretty ingenious macros to ease things a little -- perhaps these
could be improved upon to produce an acceptable close-to-universal
solution)?

Right, so these are my initial impressions. I'll continue thinking
(^:static is very cool indeed!) and I'm curious to see if I might be
able to bring myself to see more positive sides to the long/bigint
split (as well as come to an opinion on the equals issue).

All the best,
Michał

### Carson

Jun 18, 2010, 6:47:31 AM6/18/10
to Clojure
Just tried out num branch and I really like how easy it is to be
fast! However...

Consider:

(defn fact [n] (if (zero? n) 1 (* n (fact (dec n)))))
(defn twice-fact [n] (fact (fact n)))
(defn bad-twice-fact [n] (fact (-> n fact range last inc)))

user=> (fact (fact 5))
java.lang.ArithmeticException: integer overflow (NO_SOURCE_FILE:3)
user=> (fact (fact 5N))
6689502913449127057588118054090372586752746333138029810295671352301633557244962989366874165271984981308157637893214090552534408589408121859898481114389650005964960521256960000000000000000000000000000N
user=> (twice-fact 5)
java.lang.ArithmeticException: integer overflow (NO_SOURCE_FILE:5)
user=> (twice-fact 5N)
6689502913449127057588118054090372586752746333138029810295671352301633557244962989366874165271984981308157637893214090552534408589408121859898481114389650005964960521256960000000000000000000000000000N
java.lang.ArithmeticException: integer overflow (NO_SOURCE_FILE:7)
java.lang.ArithmeticException: integer overflow (NO_SOURCE_FILE:8)

> Don't buy it. That's the whole point of BigInt contagion. If fact and foo
> are correctly written this will work.

BigInt contagion doesn't help if in some convoluted manner a BigInt's
value is used to construct a primitive sufficiently large that later
causes an overflow.

It'd sure be nice if I could just write ((safe bad-twice-fact) 5) and
get back a BigInt. Maybe ((safe foo) x) can ensure all arguments and
return values of function foo are boxed, and recursively, ensures
boxing of arguments and return values for all functions called by foo,
etc. Is that possible? Would that guarantee safety?

Carson

On Jun 17, 11:35 pm, David Nolen <dnolen.li...@gmail.com> wrote:

### Nicolas Oury

Jun 18, 2010, 7:22:21 AM6/18/10
On Fri, Jun 18, 2010 at 11:47 AM, Carson wrote:

> Don't buy it. That's the whole point of BigInt contagion. If fact and foo
> are correctly written this will work.

BigInt contagion doesn't help if in some convoluted manner a BigInt's
value is used to construct a primitive sufficiently large that later
causes an overflow.

I would like to see that in real examples. And not in something that tend to be mainly a program that crunch numbers.
(I think a program "about numbers" could take a bit of complexity to handle numbers.
If you write a program to that generates web page, you agree to have an html library and not have "every structure in clojure is html".)

On the other hand, programs that have few number computations - mainly to handle a few stats and indices - but that are spread in a lot of code
(I think most program are like that) should benefit from good performance without annotating all the code.

### Carson

Jun 18, 2010, 7:54:41 AM6/18/10
to Clojure
On Jun 18, 2:44 am, Christophe Grand <christo...@cgrand.net> wrote:
> With contagious bigints (let's nick name them "safeints" and assume
> they are not BigInteger but something à la kawa) a single N on
> literals or having all your inputs going through a safeint conversion
> would trigger safe computations (unless you try to call a static
> primitive-hinted fn but the compiler would then bark).

I think the example
(defn bad-twice-fact [n] (fact (-> n fact range last inc)))
shows it takes more than safeint conversion of arguments to the
"surface" function to trigger safe computations. All functions called
by the "surface" function needs to have their arguments converted to
bigints too, and their return values probably, just in case. Although
I'm not sure if even that's enough without auto-promotion (if I
understand auto-promotion correctly...). But note the example doesn't
even use any type hints or explicit conversion to primitives (the
point is the conversion may occur as a legitimate side effect of doing
something else).

*Still*, I'm in favour of fast by default, with an *easy* way to make
things safe as an option.

### Carson

Jun 18, 2010, 8:10:01 AM6/18/10
to Clojure
On Jun 18, 4:22 am, Nicolas Oury <nicolas.o...@gmail.com> wrote:
> On Fri, Jun 18, 2010 at 11:47 AM, Carson <c.sci.b...@gmail.com> wrote:
> > Don't buy it. That's the whole point of BigInt contagion. If fact and foo
> > > are correctly written this will work.
>
> > BigInt contagion doesn't help if in some convoluted manner a BigInt's
> > value is used to construct a primitive sufficiently large that later
> > causes an overflow.
>
> > I would like to see that in real examples. And not in something that tend
>
> to be mainly a program that crunch numbers.
> (I think a program "about numbers" could take a bit of complexity to handle
> numbers.
>  If you write a program to that generates web page, you agree to have an
> html library and not have "every structure in clojure is html".)

I agree! Sorry I have no real examples, just my contrived example.
But note the example I used isn't *that* contrived, in the sense that
it doesn't use any type hints or explicit conversion to primitives to
cause an overflow on purpose. The point is that the overflow may occur
as a legitimate side effect of doing something else, whereas it
currently will not.

And *still*, I'm in favour of fast by default, with an *easy* way to
make things safe as an option. The key is to make the safe option
*easy*.

### Laurent PETIT

Jun 18, 2010, 8:10:46 AM6/18/10
I'm no expert in this field.

What I would like to avoid, is having to become expert in the field to
expect the prevention of more :

* nightmare debug sessions because of my own code or third party
libraries code
* crash in production code

which might derive from the choices.

I tend to think that it seems wrong to require more knowledge from
people wanting to write *more* correct code than from people wanting
to write faster/performant code. This is were I would place the
cursor.

2010/6/18 Carson <c.sci...@gmail.com>:

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> For more options, visit this group at

### Laurent PETIT

Jun 18, 2010, 8:12:49 AM6/18/10
2010/6/18 Carson <c.sci...@gmail.com>:

> And *still*, I'm in favour of fast by default, with an *easy* way to
> make things safe as an option. The key is to make the safe option
> *easy*.

The solution is easy: write java code by default, and clojure code
when you want to be safe :-p

### Lee Spector

Jun 18, 2010, 8:39:12 AM6/18/10

I too think that "correct by default" is a much better idea than "fast by default."

One way I think about this is that the meaning of +, for example, is the sum of its numeric arguments. The performance characteristics are not part of this core meaning, although of course everyone will be happier the better the performance is. Nonetheless, I think that the meaning should be correctly maintained as a first priority, and that means giving the right answer regardless of how many bits are needed.

I frequently produce BigIntegers, even in code that's not particularly math-heavy. It has always galled me that in most programming languages any such code breaks because of low-level implementation issues that I don't want to have to think about most of the time. I usually just want the right answer, and I certainly don't want to have to think about the binary representations every time I write code that handles numbers. If I find that my code is too slow then I'll have to think about it, and that's when it makes sense to have to deal with declarations or type hints or special faster unsafe arguments or whatever. Ideally this will take as little work as possible, but I think it'd be a bad approach to make fast free (default) at the cost of saying "but the meaning of + may not actually be numeric sum, and this depends on the number of bits required to represent your numbers, so you better always be thinking about low level representation stuff whenever you use numbers."

-Lee

--
Lee Spector, Professor of Computer Science
School of Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspe...@hampshire.edu, http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438

Check out Genetic Programming and Evolvable Machines:
http://www.springer.com/10710 - http://gpemjournal.blogspot.com/