On Fri, Jul 29, 2011 at 10:09 AM, abedra <aaron.be...@gmail.com> wrote:
> Can you provide a couple of concrete examples for this? I will make
> the ticket in JIRA and start working on it, but I am spread thin on
> quite a few things at the moment and these examples will help a lot.
>
> Cheers,
>
> Aaron Bedra
Sure, let me elaborate on what I mean with a short but somewhat
contrived example.
Consider the following definition of factorial:
(defn fact [n]
(loop [n n result 1]
(if (zero? n) result
(recur (dec n) (* result n)))))
factorial overflows as soon as you get to (fact 21). Now, let's say
you don't know exactly at what point factorial overflows. So to be on
the safe side, the recommended procedure is to pass a bigint to the
factorial function and rely on contagion to make this work, i.e.:
(fact 21N)
The problem is that (fact 21N) in 1.3 is slower than (fact 21) in 1.2.
We're paying a big performance by relying on contagion.
Here's why:
In Clojure 1.2, the first 20 multiplications are done with longs, and
only when it overflows then the last multiplication is done with
bigints.
In Clojure 1.3, all the multiplications are done with bigints which are slow.
When this issue was first raised back when Rich floated the idea of
primitive ops with bigint contagion, he created the stub class saying
that eventually the plan would be to come up with a better version of
bigint than Java's BigInteger class in the sense that it would reduce
and compute with longs (and maybe ints) when in that range.
Now, factorial is contrived because overflow happens fairly early in
the process, yet the difference is still measurable. For many of the
statistics I compute in my work project, a substantial number of the
computations happen within the long range, but sometimes they
overflow. 1.3 kills performance for me if I try to leverage
contagion; I must convert everything to the overflow ' operators.
I was thinking about this recently because I was rewriting my
clojure.contrib.math to support 1.3. One of the things I had to think
about was how the expt function should behave. It would be most
compatible with 1.3's "outlook" if
(expt primitive-long primitive-long) returned a primitive-long or
generated an overflow error. But to implement expt in this way, I
also have to think about the fact that for many cases, exponentiation
will overflow. So what should users do? One option is I could also
provide a expt' function. But I ruled this out because then I get
caught up in a proliferation of two versions (regular and ') of nearly
every math function. It might be feasible to provide a single version
of expt that supports primitive math and then allow users to use
contagion (e.g., (expt 2N 100)), but this contagion will hurt
performance. So the only viable option I see is to implement expt
with boxed numbers and the *' operator, maintaining the same
performance profile as 1.2, but missing out on the possibility of
making the primitive math people happy.
Does this explanation help?
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
