Enhanced Primitive Support

292 views
Skip to first unread message

Rich Hickey

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

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

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

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

Rob

Mark Engelberg

unread,
Jun 17, 2010, 9:55:10 PM6/17/10
to clo...@googlegroups.com
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

unread,
Jun 17, 2010, 11:00:57 PM6/17/10
to clo...@googlegroups.com

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.

http://groups.google.com/group/jvm-languages/msg/0413ed05d1371907

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

unread,
Jun 17, 2010, 11:47:36 PM6/17/10
to clo...@googlegroups.com
On Thu, Jun 17, 2010 at 11:00 PM, Rich Hickey <richh...@gmail.com> 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

unread,
Jun 17, 2010, 11:57:28 PM6/17/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 12:20:00 AM6/18/10
to clo...@googlegroups.com
On Thu, Jun 17, 2010 at 11:57 PM, 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.

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

unread,
Jun 18, 2010, 12:22:27 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 12:24:55 AM6/18/10
to clo...@googlegroups.com

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
-------------
CTO, Linkuistics Pty Ltd
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

unread,
Jun 18, 2010, 12:56:59 AM6/18/10
to clo...@googlegroups.com
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:

(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

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

unread,
Jun 18, 2010, 1:22:39 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 1:23:35 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 1:33:17 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 1:43:44 AM6/18/10
to clo...@googlegroups.com
> ... 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

unread,
Jun 18, 2010, 1:44:33 AM6/18/10
to clo...@googlegroups.com

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


CTO, Linkuistics Pty Ltd
Ph: 0438 840 787

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

David Nolen

unread,
Jun 18, 2010, 2:01:08 AM6/18/10
to clo...@googlegroups.com
On Fri, Jun 18, 2010 at 1:44 AM, Antony Blakey <antony...@gmail.com> 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

unread,
Jun 18, 2010, 2:10:32 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 2:15:16 AM6/18/10
to clo...@googlegroups.com
On Fri, Jun 18, 2010 at 2:10 AM, Mark Engelberg <mark.en...@gmail.com> 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

unread,
Jun 18, 2010, 2:35:37 AM6/18/10
to clo...@googlegroups.com
On Fri, Jun 18, 2010 at 2:10 AM, Mark Engelberg <mark.en...@gmail.com> 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

unread,
Jun 18, 2010, 2:58:08 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 3:12:11 AM6/18/10
to clo...@googlegroups.com

+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
--------------------------
CTO, Linkuistics Pty Ltd
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

unread,
Jun 18, 2010, 3:36:39 AM6/18/10
to clo...@googlegroups.com
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
> seems like too much of a bad tradeoff,

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

unread,
Jun 18, 2010, 4:44:14 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 4:48:49 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 5:44:52 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 6:35:01 AM6/18/10
to clo...@googlegroups.com
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
about this, the new developments do seem attractive in many ways
(^: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

unread,
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
user=> (bad-twice-fact 5)
java.lang.ArithmeticException: integer overflow (NO_SOURCE_FILE:7)
user=> (bad-twice-fact 5N)
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

unread,
Jun 18, 2010, 7:22:21 AM6/18/10
to clo...@googlegroups.com
On Fri, Jun 18, 2010 at 11:47 AM, Carson <c.sci...@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".)

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

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

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

unread,
Jun 18, 2010, 8:10:46 AM6/18/10
to clo...@googlegroups.com
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
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

Laurent PETIT

unread,
Jun 18, 2010, 8:12:49 AM6/18/10
to clo...@googlegroups.com
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

unread,
Jun 18, 2010, 8:39:12 AM6/18/10
to clo...@googlegroups.com

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/

David Nolen

unread,
Jun 18, 2010, 8:45:45 AM6/18/10
to clo...@googlegroups.com
On Fri, Jun 18, 2010 at 6:47 AM, Carson <c.sci...@gmail.com> wrote:
(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))) 

Not only is it contrived, under the proposal, this implementation of fact is broken. It needs to be fixed to:

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

With that change bad-twice-fact is not actually bad.

As Christophe Grand has mentioned one of the main things that is be complained about from the BigInt supporters *is already a problem* in Clojure. Nothing new to see here.

Finally having actually tried out the new branches, this is a good change for me. I'd like to hear more from the BigInt crowd about whether getting their code to work with the new branches is actually causing problems.

So far it just seems like talk.

ajuc

unread,
Jun 18, 2010, 8:48:25 AM6/18/10
to Clojure
+1 to safe-by-default.

I use clojure for games, but if it will be possible to easily make
computations fast, safe-by-default is more important.

Rich Hickey

unread,
Jun 18, 2010, 8:49:41 AM6/18/10
to clo...@googlegroups.com

This L suffix idea is a non-starter. Here's why:

We're in a reader based language. The reader reads objects. When the
reader reads 42, it must return an object. It cannot return an int or
a long primitive. Right now, it returns an Integer. I've also
conducted experiments where it returned a Long. Certainly 42000000000
will be a Long. What different thing would the reader return given
42L, or 42000000000L? Given an int 42 what should the printer print?
And long 42, Long 42? Would (= 42L (read-string (pr-str 42L)))?

------
The second thing I don't see being acknowledged is that the real
problem here is the semantic difference. It's not a matter of getting
at a primitive operation when handed a boxed number - that already
happens, and pretty efficiently. It is the fact that the results have
to go somewhere, and the difference in 'where' creates a difference in
semantics. In master right now:

(+ x y)

and

(+ (identity x) y)

can produce different results. We already have bug reports around
this, and user confusion. Fixing it requires adopting a single
semantic for +. Choosing auto-promotion precludes the use of + on
primitives, a huge loss IMO. Choosing throw-on-overflow precludes auto-
promotion, but preserves polymorphism otherwise, and gives the
compiler free reign to optimize since it will never be altering the
semantics by doing so.

I don't see a way around this fundamental dichotomy. The semantics for
+ should be unified, and the operator that makes the other choice
needs to be called something else, or placed somewhere else.

Rich

Konrad Hinsen

unread,
Jun 18, 2010, 8:56:35 AM6/18/10
to clo...@googlegroups.com
On 18.06.2010, at 14:49, Rich Hickey wrote:

> I don't see a way around this fundamental dichotomy. The semantics for + should be unified, and the operator that makes the other choice needs to be called something else, or placed somewhere else.

My preference would be "placed somewhere else". We have namespaces, so why not profit from them?

My vote would be for:

1) clojure.core/+ doing bigint promotion and reduction under all circumstances (no optimizations that would break the semantics)

2) clojure.fastmath/+ doing type-specific and optimized addition.

This would retain the "safe by default" approach that I think fits Clojure best, and yet make it easy to use the "fast" version everywhere with nothing to change but the ns form at the top of a module.

Konrad.


Rich Hickey

unread,
Jun 18, 2010, 9:11:03 AM6/18/10
to clo...@googlegroups.com

------
While range could be written differently, this is tantamount to saying
- if I use a bigint to lookup another number in some mapping, it might
not be a bigint. Yes, ok, but not a real issue.

-------------
Note - I don't mean to single you out, as others are using the same
language, but I find this whole characterization of throw-on-overflow
being somehow 'unsafe' to be a bit specious.

I want it to be perfectly clear to everyone, this is not a choice
between good math and bad math, i.e. C/Java style truncating/wrapping
of results. That will never be the default. Such silent truncation/
wrap is truly unsafe, and often the proposed alternative. It was a
surprising result that optimizations of hot spot, combined with
pipelining and speculative execution on modern processors, makes the
overflow checking a very minor overhead above the raw operations, and,
in my mind, a third, new, viable and safe high-performance option.

Is a program that might throw an exception unsafe? If so, no Java
program is safe.

Is a vector that throws an exception when asked to store something at
an index out of range, rather than grow to accommodate it, unsafe?
This is in many ways similar - you are creating a result that doesn't
fit, and need to be using a bigger container.

So, let's go easy on the hyperbole. The behavior might not be what you
desire, but it is not unsafe.

Rich

Carson

unread,
Jun 18, 2010, 9:19:18 AM6/18/10
to Clojure
On Jun 18, 5:45 am, David Nolen <dnolen.li...@gmail.com> wrote:
> On Fri, Jun 18, 2010 at 6:47 AM, Carson <c.sci.b...@gmail.com> wrote:
> > (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)))
>
> Not only is it contrived, under the proposal, this implementation of fact is
> broken. It needs to be fixed to:
>
> (defn fact [n] (if (zero? n) 1N (* n (fact (dec n)))))
>
> With that change bad-twice-fact is not actually bad.

I appreciate what you're saying, and the example above is not broken.
Recall from here:

On Jun 17, 8:00 pm, Rich Hickey <richhic...@gmail.com> wrote:
...
> 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.

I believe the example (which I have tried on the num branch) shows
providing a BigInt argument does not always make things safe. That is
all.

Carson

Rich Hickey

unread,
Jun 18, 2010, 9:20:35 AM6/18/10
to clo...@googlegroups.com

Which then begs the questions:

- how will someone 'protect' themselves from libraries written using
fastmath?

- similar looking code will change semantics when the ns switch is
made - seems dangerous as it might violate the presumptions of the
original authors.

Rich


Nicolas Oury

unread,
Jun 18, 2010, 9:31:06 AM6/18/10
to clo...@googlegroups.com
In this situation, I would rather have some kind of toggle *use-bigints-by-default* (defaulted to false) used by the compiler.
Then, if someone needs big integers, he can switch the toggle and recompile everything.
You wouldn't have to change the libraries ns. 

As for being predictable, if you have numbers that can be bigger than 10^19, you would probably know it in advance.
(indices, counters and the like don't grow that big)

Laurent PETIT

unread,
Jun 18, 2010, 9:32:19 AM6/18/10
to clo...@googlegroups.com
2010/6/18 Rich Hickey <richh...@gmail.com>:

> I want it to be perfectly clear to everyone, this is not a choice between
> good math and bad math, i.e. C/Java style truncating/wrapping of results.
> That will never be the default. Such silent truncation/wrap is truly unsafe,

> and often the proposed alternative. It was a surprising result that
> optimizations of hot spot, combined with pipelining and speculative
> execution on modern processors, makes the overflow checking a very minor
> overhead above the raw operations, and, in my mind, a third, new, viable and
> safe high-performance option.
>
> Is a program that might throw an exception unsafe? If so, no Java program is
> safe.
>
> Is a vector that throws an exception when asked to store something at an
> index out of range, rather than grow to accommodate it, unsafe? This is in
> many ways similar - you are creating a result that doesn't fit, and need to
> be using a bigger container.
>
> So, let's go easy on the hyperbole. The behavior might not be what you
> desire, but it is not unsafe.
>

Fair enough.

Laurent PETIT

unread,
Jun 18, 2010, 9:35:53 AM6/18/10
to clo...@googlegroups.com
2010/6/18 Nicolas Oury <nicola...@gmail.com>:

No please, not even in my worst nightmares !
Semantic changing compilation flags ? So I use lib A which needs lib B
compiled with flags C and D, but I also use lib E which needs lib B
compiled with other values for the flags ... I think this just is a
recipe for disaster.

Carson

unread,
Jun 18, 2010, 9:39:49 AM6/18/10
to Clojure
hmm...didn't see this earlier.
You're right, it's not unsafe, it's undesired behaviour. My mistake
describing it that way.

Nicolas Oury

unread,
Jun 18, 2010, 9:41:12 AM6/18/10
to clo...@googlegroups.com


On Fri, Jun 18, 2010 at 2:35 PM, Laurent PETIT <lauren...@gmail.com> wrote:

No please, not even in my worst nightmares !
Semantic changing compilation flags ? So I use lib A which needs lib B
compiled with flags C and D, but I also use lib E which needs lib B
compiled with other values for the flags ... I think this just is a
recipe for disaster.

Seen like this, this does not look so great.

However, I would like to note that, in this specific situation, there is a flag that subsumes the other.
I can't see someone relying on overflow (as opposed to promotion) for its behavior...
It would be a bit sick.

Rich Hickey

unread,
Jun 18, 2010, 10:04:31 AM6/18/10
to clo...@googlegroups.com

On Jun 17, 2010, at 11:57 PM, Mark Engelberg wrote:

> 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 fully acknowledge this is a breaking change that doesn't suit your
preferences. But again, you are over- and misstating things.

The benefit does not only accrue to those annotating their arguments.

Because many functions and methods return primitives (and more will,
now that fns can return primitives), any operations on their results
and/or literals can be optimized. E.g. things like (if (< (dec (count
x)) 100) ...) can now be optimized into primitives.

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

Agreed that this equality bit is a separate issue.


Rich

Stuart Halloway

unread,
Jun 18, 2010, 10:08:25 AM6/18/10
to clo...@googlegroups.com
While I enjoy a theoretical debate as much as the next person, it
would be nice to see

(1) examples of real code that fail on reasonable inputs, if this
change were made. And how difficult it would be to fix them.

(2) examples of real code that get way faster, and the ease of making
those changes (if any).

WRT #1, we have tested a few dozen libs, and found only a single
trivial breakage in their test suites. But I would say tha is still
just plural anecdotes. More data welcome!

Christophe Grand

unread,
Jun 18, 2010, 10:09:02 AM6/18/10
to clo...@googlegroups.com
On Fri, Jun 18, 2010 at 2:49 PM, Rich Hickey <richh...@gmail.com> wrote:
> This L suffix idea is a non-starter. Here's why:
>
> We're in a reader based language. The reader reads objects. When the reader
> reads 42, it must return an object. It cannot return an int or a long
> primitive. Right now, it returns an Integer. I've also conducted experiments
> where it returned a Long. Certainly 42000000000 will be a Long. What
> different thing would the reader return given 42L, or 42000000000L? Given an
> int 42 what should the printer print? And long 42, Long 42? Would (= 42L
> (read-string (pr-str 42L)))?

But what if the reader reads 42 as a BigInteger (or an alternative
implementation) and 42L as a Long?
then you should be able to tell them apart.

I agree with the goals of the num branch, I'm just unconvinced by the
reader defaulting to Long for integer literals.

Christophe

Heinz N. Gies

unread,
Jun 18, 2010, 10:11:27 AM6/18/10
to clo...@googlegroups.com

On Jun 18, 2010, at 15:11 , Rich Hickey wrote:
> So, let's go easy on the hyperbole. The behavior might not be what you desire, but it is not unsafe.
I agree with both actually it isn't unsafe but in my eyes undesired, met me explain.

In generally it seems we have two options:

1) We make fast default and loose auto promotion in the number stack.

2) We make it more difficult to be fast (as in extra work) but keep promotion.

Lets hope that I got this right otherwise the following argumentation can be skipped since it's based on this understandings. (of cause there might be a way to accomplish both which would - without question the best way to go ;)

Now let see the auto promotion has one very nice effect, it just works. That simple and this is in my eyes hugely important, because it gives people a happy and fluffy feeling to be able to write normal code without special considerations and deep knowledge of types and hinting. Lets face it for 90% of people it does not matter that it is a long or bigint or even a double they expect math to just work, this is one of the reasons why people enjoy languages like Ruby or buy Apple hardware - because it just works (yes we don't play on the same ground but it was a good principle of it). If we go to the point where people need to know that they have to pass a 42N instead of 42 or get an exception it is just plain ugly, it is javaish and that things are not javaish is one thing poeple love about clojure, and just to not be tossed in the bucket, it is not insecure just horrible inconvenient and annoying.

But lets look at the other side of the coin, performance. We all want it - of cause otherwise we'd put a lot of (Thread/sleep 1000) in our code but, again lets face the reality, most of us don't need it. Most of the time we don't need to do fac or fib or very fast math, in 90% of the cases what clojure offers is just fast enough since the bottle necks isn't arithmetics. For the rest 10% of the cases, well if you are in that case you likely have a complex algorithm. This again means that you belong to the people who really know what they are doing, and know what your algorithm works, given that someone in this position should know where to put performance optimization so the fact that it needs to be explict isn't that horrible in my eyes usually the code that has to be made more complex is alway some kind of focus code where you do way more then just toss a few statics on it and hope that it is fast but try every trick to get it fast - so you'll have the work anyway.

Now what is my conclusion: lets keep the 'it just works' and sacrifice some out of the box performance gains which 90% of the users won't notice anyway and half of the people notice it will only do so because they benchmark for exactly this. Especially since number arithmetics are rarely the bottlenecks, database lookups, string manipulations, IO, network and object allocation those are things that eat much performacne in the most cases.

Just my two (european!) cent :)

That said I find the possible performance gain extraordinary and brilliant, and I'm all for it just not for the sacrifice of 'it just works'. I rather write (long 1) in 2 functions where it is really needed then making sure I write 42N or ^Bigint in every function where I'm not 100% certain (which will likely be all but the two functions where I'd write logn).


Regards,
Heinz

Stuart Halloway

unread,
Jun 18, 2010, 12:06:46 AM6/18/10
to clo...@googlegroups.com
> 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.

It will be much easier for people to write fast library code (including in Clojure and contrib). So if you ever use Clojure libraries, you will get a speed boost.


Nicolas Oury

unread,
Jun 18, 2010, 10:24:02 AM6/18/10
to clo...@googlegroups.com
Why this is marked as abuse? It has been marked as abuse.
Report not abuse


On Fri, Jun 18, 2010 at 3:11 PM, Heinz N. Gies <he...@licenser.net> wrote:

But lets look at the other side of the coin, performance. We all want it - of cause otherwise we'd put a lot of (Thread/sleep 1000) in our code but, again lets face the reality, most of us don't need it. Most of the time we don't need to do fac or fib or very fast math, in 90% of the cases what clojure offers is just fast enough since the bottle necks isn't arithmetics. For the rest 10% of the cases, well if you are in that case you likely have a complex algorithm. This again means that you belong to the people who really know what they are doing, and know what your algorithm works, given that someone in this position should know where to put performance  optimization so the fact that it needs to be explict isn't that horrible in my eyes usually the code that has to be made more complex is alway some kind of focus code where you do way more then just toss a few statics on it and hope that it is fast but try every trick to get it fast - so you'll have the work anyway.


I am not sure (= (* 20 not-a-bottleneck) not-a-bottleneck)

or more precisely:
 (= (* 20 not-a-bottleneck-1 ...  not-a-bottleneck-250) not-a-bottleneck)

Nicolas Oury

unread,
Jun 18, 2010, 10:24:56 AM6/18/10
to clo...@googlegroups.com
I meant:

 (= (* 20 (+ not-a-bottleneck-1 ...  not-a-bottleneck-250)) not-a-bottleneck)

Rich Hickey

unread,
Jun 18, 2010, 10:26:36 AM6/18/10
to clo...@googlegroups.com

On Jun 18, 2010, at 10:09 AM, Christophe Grand wrote:

> On Fri, Jun 18, 2010 at 2:49 PM, Rich Hickey <richh...@gmail.com>
> wrote:
>> This L suffix idea is a non-starter. Here's why:
>>
>> We're in a reader based language. The reader reads objects. When
>> the reader
>> reads 42, it must return an object. It cannot return an int or a long
>> primitive. Right now, it returns an Integer. I've also conducted
>> experiments
>> where it returned a Long. Certainly 42000000000 will be a Long. What
>> different thing would the reader return given 42L, or 42000000000L?
>> Given an
>> int 42 what should the printer print? And long 42, Long 42? Would
>> (= 42L
>> (read-string (pr-str 42L)))?
>
> But what if the reader reads 42 as a BigInteger (or an alternative
> implementation) and 42L as a Long?
> then you should be able to tell them apart.
>

And keeps them that way? Hrm. Then most programs, that currently have
no bigints, will now be full of them. And the boxed math will be
slower still, as it will be the (possibly improved, but still more
complex) logic of bigints. And the interop will be trickier. The
current boxing matches the boxing you will get from things from the
outside world. This wouldn't. And if this is just a 'way to
communicate with the compiler' thing, then read/print round-tripping
will break.

> I agree with the goals of the num branch, I'm just unconvinced by the
> reader defaulting to Long for integer literals.
>

It's important not to get focused on the literals. There are
primitives coming from other places as well. The semantic dichotomy is
the driver. The choice of the semantics of + can't be based upon the
boxed-ness of the argument, as it is now.

Rich

Heinz N. Gies

unread,
Jun 18, 2010, 10:47:17 AM6/18/10
to clo...@googlegroups.com

On Jun 18, 2010, at 16:24 , Nicolas Oury wrote:
> I am not sure (= (* 20 not-a-bottleneck) not-a-bottleneck)
>
> or more precisely:
> (= (* 20 not-a-bottleneck-1 ... not-a-bottleneck-250) not-a-bottleneck)

Point is, no one will write 250 variables even less so values by hand, it will be a map, reduce or whatever and then it's pretty easy to type hint it if the performance is an issue at this point and if you write this code you likely will know that this is a bottleneck. (I ignore the * there since you corrected it, otherwise it'd be a nice Palce to point out that it is likely becoming a overflow and an exception w/o automatic promotion :P)

Regards,
Heinz

Nicolas Oury

unread,
Jun 18, 2010, 10:50:00 AM6/18/10
to clo...@googlegroups.com

Point is, no one will write 250 variables even less so values by hand, it will be a map, reduce or whatever and then it's pretty easy to type hint it if the performance is an issue at this point and if you write this code you likely will know that this is a bottleneck. (I ignore the * there since you corrected it, otherwise it'd be a nice Palce to point out that it is likely becoming a overflow and an exception w/o automatic promotion :P)


That would have been really better to have an exception as it was a bug :-b. 

Nicolas Oury

unread,
Jun 18, 2010, 11:23:47 AM6/18/10
to clo...@googlegroups.com
Experiment results :

I switched a program to num.
It was quite straightforward. 
First I had to replace a few unchecked-add by +.
Has unchecked-add changed name? (I use it for indices when itering on a java array, if there is an overflow, you will know it beforehand)

The only funny event is that it was much much much slower at first.
Mainly doing reflection stuff.
I used *warn-on-reflection* and found:


( < val 0) where val is a double. Ugly, bad and wrong. I am not proud. 
(* some-int some-double), that I changed to (* (double some-int) some-double)

Then, I had some results on the benchmark I use to test my change. (I remove 14 seconds to each, because it is the compilation time. As this program is made to run for a long time and I want to test the stationary speed,I put a very low threshold for the jit. I don't know if it is a good idea or not.)
Initial program :                           92 seconds - 14 = 78s
Corrected program with master :  86 seconds - 14 = 72s
Corrected program with num :     80 seconds - 14 = 66s

Note that it is quite heavy on the GC, so there is 5s gc in that, which increase still more the difference.
Altogether, it is around 10% faster, without touching any annotation and static function.
Moreover, it might be difficult to believe if you read the beginning of my mail, but I spend a lot of time adding annotations where I thought it was useful. 
That's difficult, and still there is a nice speedup.
Most of all, I could start added annotations to function. The problem is I use a lot of protocols.
Are there plans for support of prim in protocols?

Last thing, there is no single bottleneck that I could rewrite easily. This 10% is spread over the program.
Result of profiling: 

  Interpreted + native   Method                        
  0.2%     2  +    10    clojure.core__init.load
  0.1%     8  +     0    distribution.FastProductWithinComp.non_local_draw
  0.1%     7  +     0    clojure.core$vector.invoke
  0.1%     7  +     0    java.util.WeakHashMap.get
...
2.8%   177  +    32    Total interpreted (including elided)

     Compiled + native   Method                        
  2.4%   183  +     0    clojure.lang.RT.seqFrom
  2.2%   164  +     1    distribution.FastProductWithinComp.non_local_draw
  1.9%    61  +    81    java.util.WeakHashMap.getTable
  1.4%   103  +     0    clojure.lang.RestFn.invoke
  0.8%    62  +     1    clojure.core.protocols$fn__5284.invoke
  0.7%    51  +     0    clojure.lang.RT.next
  0.4%    31  +     1    clojure.lang.Var.pushThreadBindings
....
14.8%  1019  +   100    Total compiled (including elided)

         Stub + native   Method                        
 81.3%     0  +  6154    java.lang.Object.hashCode

And yes, this 10% are obtained in a code that mainly use HashMaps to retrieve already computed values (81.3% seems spent there).
So I would expect far better speed-up in a more typical program.

(Game : guess what the program does from its profile...)




Hugo Duncan

unread,
Jun 18, 2010, 12:48:57 PM6/18/10
to clo...@googlegroups.com
On Fri, 18 Jun 2010 09:20:35 -0400, Rich Hickey <richh...@gmail.com>
wrote:

>
> On Jun 18, 2010, at 8:56 AM, Konrad Hinsen wrote:
>
>> On 18.06.2010, at 14:49, Rich Hickey wrote:
>>
>>> I don't see a way around this fundamental dichotomy. The semantics for
>>> + should be unified, and the operator that makes the other choice
>>> needs to be called something else, or placed somewhere else.

If you are doing a lot of work with whichever semantic requires decorated
use, then it is going to seem awkward. A namespace based solution would
allow "natural" use of whichever semantic was appropriate for the domain
you are coding. It would still require an explicit choice - pulling in a
different namespace.

> - how will someone 'protect' themselves from libraries written using
> fastmath?

If I understand correctly, that is still an issue, whatever syntax is
chosen.

> - similar looking code will change semantics when the ns switch is made

The switch is explicit.

> - seems dangerous as it might violate the presumptions of the original
> authors.

Not sure I understand this. Presumably if you change your selected
semantics within a namespace, you had better be sure of how that affects
all the functions in that namespace.


--
Hugo Duncan

Mark Engelberg

unread,
Jun 18, 2010, 1:51:51 PM6/18/10
to clo...@googlegroups.com
On Thu, Jun 17, 2010 at 9:06 PM, Stuart Halloway
<stuart....@gmail.com> wrote:
> It will be much easier for people to write fast library code (including in Clojure and contrib). So if you ever use Clojure lib