Quick arithmetic timing

[Brian Watkins]

Java -- 3.5 s

double out=0;
for(int i=0;i<100000000;i++)
out+= Math.sqrt(i);

returns 6.66666661666567E11
-----

SBCL -- 9 s

(time (let ((r 0)) (dotimes (i 100000000 r) (setf r (+ r (sqrt i))))))

returns 2.748779e11 WRONG

-----

SBCL -- 6 s

(time (let ((r 0d0)) (declare (type double-float r)) (dotimes (i
100000000 r) (declare (type fixnum i)) (setf r (+ r (sqrt i))))))

returns 6.666666616665508d11

-----

Clojure (current -- March was a little slower) -- 14 s

(time (loop [ acc 0 ind 0] (if (= ind 100000000) acc (recur (+ acc (.
java.lang.Math (sqrt ind))) (+ 1 ind)))))w

returns 6.66666661666567E11

-----

Kawa -- 51 s

(time (let loop ((acc 0) (ind 0)) (if (= ind 100000000) acc (loop (+
acc (sqrt ind)) (+ 1 ind)))))

returns 6.66666661666567E11

-----

CRuby 1.8 -- 200 s

out=0
(0..100000000).each do |i|
out+= i**(0.5)
end

returns 666666671666.612

[Chouser]

On Wed, Jun 4, 2008 at 6:01 PM, Brian Watkins <Wild...@gmail.com> wrote:
> Clojure (current -- March was a little slower) -- 14 s
>
> (time (loop [ acc 0 ind 0] (if (= ind 100000000) acc (recur (+ acc (.
> java.lang.Math (sqrt ind))) (+ 1 ind)))))w

On my machine that's 17 seconds.
With a couple minor changes, it can run in 3.4 seconds:

(time
(loop [acc (double 0) ind 0]
(if (< ind 100000000)
(recur (+ acc (. java.lang.Math (sqrt ind))) (inc ind))
acc)))

--Chouser

[Rich Hickey]

This should be much faster:

(time
(loop [acc (double 0) ind (int 0)]
(if (== ind (int 100000000))

acc
(recur (+ acc (. java.lang.Math (sqrt ind)))

(unchecked-inc ind)))))

Rich

[Brian Watkins]

On my machine this runs in 4s on the latest Clojure, roughly the same
speed as the pure Java version. Note that the pure Java version
didn't include time to compile from source, so this is actually faster
than the 3.5s pure Java run.

The type hints don't seem to help on the March alpha download.

It's a little more complicated than the SBCL type hint declarations,
but works very nicely. This makes a nice example for the type hinting
also.

-Brian

[Rich Hickey]

On Jun 4, 7:35 pm, Brian Watkins <WildU...@gmail.com> wrote:
> On my machine this runs in 4s on the latest Clojure, roughly the same
> speed as the pure Java version. Note that the pure Java version
> didn't include time to compile from source, so this is actually faster
> than the 3.5s pure Java run.
>
> The type hints don't seem to help on the March alpha download.
>
> It's a little more complicated than the SBCL type hint declarations,
> but works very nicely.

I guess that's subjective. I find (declare (type double-float r)) more
cumbersome than (double r). 0d0 brings up a question I have for
everyone - is it worth it to add d/i/f/L suffixes for numeric literal
type hints? That could make the example:

(time
(loop [acc 0d ind 0i]
(if (== ind 100000000i)
acc
(recur (+ acc (. Math (sqrt ind)))
(inc ind)))))

Also, it ends up unchecked-inc didn't make any difference in this
case.

Rich

[Stephen C. Gilardi]

> 0d0 brings up a question I have for
> everyone - is it worth it to add d/i/f/L suffixes for numeric literal
> type hints? That could make the example:
>
> (time
> (loop [acc 0d ind 0i]
> (if (== ind 100000000i)
> acc
> (recur (+ acc (. Math (sqrt ind)))
> (inc ind)))))
>
> Also, it ends up unchecked-inc didn't make any difference in this
> case.

I think that would be a nice convenience. I see that BigDecimal
already uses the M suffix on read and prn.

The precedent in other languages seems to be to make the suffixes case
insensitive.

Should there be a suffix for BigInt? (My current thought is that it's
not necessary.)

While looking at this, I noticed this which surprised me:

user=> (bigdec 1)
java.lang.IllegalArgumentException: No matching method found: valueOf

--Steve

[Raoul Duke]

> The precedent in other languages seems to be to make the suffixes case
> insensitive.

if not, please make it required as upper case to avoid the "1" vs. "l" problems.

[Brian Watkins]

> > 0d0 brings up a question I have for
> > everyone - is it worth it to add d/i/f/L suffixes for numeric literal
> > type hints?

It's quite convenient for writing numerical code in java to have the d/
L/i suffixes. I imagine that it will be even more useful in Clojure
now that I'm trying the type hinting.

+1

-Brian

[Randall R Schulz]

Accept upper or lower, sure, but why forbid the lower-case, even
for 'l'? Most programmers use fonts that clearly distinguish O / and
1 / l and there's no reason they should be forced to use the upper-case
if they don't want to.

Randall Schulz

[brad clawsie]

On Jun 4, 3:01 pm, Brian Watkins <WildU...@gmail.com> wrote:
> Java -- 3.5 s
>
> double out=0;
> for(int i=0;i<100000000;i++)
> out+= Math.sqrt(i);

> returns 666666671666.612

in case anyone is moderately interested in haskell:

module Main where
import Data.List
main = print $ foldl' (\x y -> x + (sqrt(y))) 0 [1..100000000]

$ time ./t
6.66666671666567e11

real 0m34.997s
user 0m32.487s
sys 0m0.097s

[Graham Fawcett]

On Jun 6, 11:59 am, brad clawsie <claw...@fastmail.fm> wrote:
> On Jun 4, 3:01 pm, Brian Watkins <WildU...@gmail.com> wrote:
>
> > Java -- 3.5 s
>
> > double out=0;
> > for(int i=0;i<100000000;i++)
> >    out+= Math.sqrt(i);
> > returns  666666671666.612
>
> in case anyone is moderately interested in haskell:
>
> module Main where
> import Data.List
> main = print $ foldl' (\x y -> x + (sqrt(y))) 0 [1..100000000]

I wonder, is there a way to hint a higher-order Clojure equivalent,
perhaps

(time (reduce + 0 (map #(. java.lang.Math (sqrt %)) (range
100000000))))

so that it performs as well as the loop/recur version? Or could 'pure'
versions of the HOFs rewrite the expression into an efficient loop?
(I'm thinking of deforestation rules like those in the Glasgow Haskell
compiler, though they didn't seem to help much in Brad's example.)
Clojure seems to qualify as a mostly-lazy, mostly-functional language,
so it would be nice if higher-order operations were mostly-
efficient. ;-)

Is there a way to profile Clojure code, and get Clojure-friendly
results? As a newbie, I can only guess at where the hotspots in my
example would be.

Graham

[laurentvaucher]

OCaml?

let sum_sqrt =
let rec aux_ss acc i =
if i = 100000000
then acc
else aux_ss (acc +. sqrt (float i)) (i + 1)
in
aux_ss 0.0 0;;

print_float sum_sqrt;;
print_newline ();;


-> compiled to bytecode : ~5x slower than latest Clojure version
(compilation time included)
-> compiled to native code : ~35% slower (compilation time excluded)

Anyway, on my old AMD, I've got results that are not totally coherent
with what others have reported.
java : 1.5s
java -server : 2.4s
clojure typed code : 6.8s
clojure typed code -server : 5.3s
clojure untyped code -server : 16s

Even the best latest clojure is still far from Java (not that it
bothers me that much, mind you).

(My java is Sun 1.6.0_03 on Linux, Clojure is SVN revision 898)

Ah, the joy of microbenchmarks! :o)

[Rich Hickey]

I would say the higher-order operations _are_ mostly efficient, and
most applications shouldn't bother with these lower-level operations
unless they are processing a lot of data.

As far as profiling, I would imagine Clojure code could be profiled
with Java profiling tools that don't presume the bytecode came from
Java source, as it emits the needed debug info.

As far as your code - the hotspots vs. a direct loop will most
definitely be laziness, as it introduces allocations. Don't expect any
optimization to eliminate that soon.

A little tweak gives much better performance:

;primitive loop, best possible performance

(time
(loop [acc (double 0) ind (int 0)]
(if (== ind (int 100000000))

acc
(recur (+ acc (. Math sqrt ind))
(inc ind)))))
"Elapsed time: 2577.373 msecs"
6.66666661666567E11

;avoiding lazy map and using a type hint, very good performance from
higher-level code:
(time (reduce #(+ (double %1) (. Math sqrt %2)) 0 (range 100000000)))
"Elapsed time: 4597.319 msecs"
6.66666661666567E11

This makes me think it might be useful to have a reduce that
takes :map and :filter options, like parallel/par does....

Rich

[Graham Fawcett]

On Jun 6, 5:20 pm, Rich Hickey <richhic...@gmail.com> wrote:
> A little tweak gives much better performance:
>
> ;primitive loop, best possible performance
> (time
> (loop [acc (double 0) ind (int 0)]
> (if (== ind (int 100000000))
> acc
> (recur (+ acc (. Math sqrt ind))
> (inc ind)))))
> "Elapsed time: 2577.373 msecs"
> 6.66666661666567E11
>
> ;avoiding lazy map and using a type hint, very good performance from
> higher-level code:
> (time (reduce #(+ (double %1) (. Math sqrt %2)) 0 (range 100000000)))
> "Elapsed time: 4597.319 msecs"
> 6.66666661666567E11

Brilliant, thanks -- that's what I was hoping to see.

> This makes me think it might be useful to have a reduce that
> takes :map and :filter options, like parallel/par does....

That would look something like this?

(reduce #(+ (double %1) (double %2)) (range 100000000) :map #(. Math
sqrt %)))

I like it. Having the :map on the end seems a little funky, but it
separates concerns better than a complicated reduce/fold function, and
it would be easy to rewrite a sluggish (reduce ... (map ...)) to this
form.

Best,
Graham