from:"Andy"

On Aug 5, 6:09 am, Rich Hickey  wrote:
> On Wed, Aug 5, 2009 at 8:29 AM, Johann Kraus wrote:
>
> >> Could it be that your CPU has a single floating-point unit shared by 4
> >> cores on a single die, and thus only 2 floating-point units total for
> >> all 8 of your cores?  If so, then that fact, plus the fact that each
> >> core has its own separate ALU for integer operations, would seem to
> >> explain the results you are seeing.
>
> > Exactly, this would explain the behaviour. But unfortunately it is not
> > the case. I implemented a small example using Java (Java Threads) and
> > C (PThreads) and both times I get a linear speedup. See the attached
> > code below. The cores only share 12 MB cache, but this should be
> > enough memory for my micro-benchmark. Seeing the linear speedup in
> > Java and C, I would negate a hardware limitation.
>
> > _
> > Johann
>
>
> I looked briefly at your problem and don't see anything right off the
> bat. Do you have a profiler and could you try that out? I'm
> interested.
> Rich

I ran these tests on my iMac with 2.16 GHz Intel Core 2 Duo (2 cores)
using latest Clojure and clojure-contrib from git as of some time on
Aug 4, 2009.  The Java implementation is from Apple, version 1.6.0_13.

--
For int, there are 64 "jobs" run, each of which consists of doing
(inc 0) 1,000,000,000 times.  See pmap-batch.sh and pmap-testing.clj
for details.

http://github.com/jafingerhut/clojure-benchmarks/blob/398688c71525964ba4c2d55d0e487b7618efdc8b/misc/pmap-batch.sh

http://github.com/jafingerhut/clojure-benchmarks/blob/398688c71525964ba4c2d55d0e487b7618efdc8b/misc/pmap-testing.clj

Yes, yes, I know.  I should really use a library for command line
argument parsing to avoid so much repetitive code.  I may do that some
day.

Results for int 1 thread - jobs run sequentially

"Elapsed time: 267547.789 msecs"
real   269.22
user   268.61
sys  1.79

int 2 threads - jobs run in 2 threads using modified-pmap, which
limits the number of futures causing threads to run jobs to be at most
2 at a time.

"Elapsed time: 177428.626 msecs"
real   179.14
user   330.30
sys 15.46

Comment: Elapsed time with 2 threads is about 2/3 of elapsed time with
1 thread.  Not as good as the 1/2 as we'd like with a 2 core machine,
but better than not being faster at all.

--
For double, there are 16 "jobs" run, each of which consists of doing
(inc 0.1) 1,000,000,000 times.

double 1 thread

"Elapsed time: 258659.424 msecs"
real   263.28
user   247.29
sys 12.17

double 2 threads

"Elapsed time: 229382.68 msecs"
Dumping CPU usage by sampling running threads ... done.
real   231.05
user   380.79
sys 11.49

Comment: Elapsed time with 2 threads is about 7/8 of elapsed time with
1 thread.  Hardly any improvement at all for something that should be
"embarrassingly parallel", and the user time reported by Mac OS X's
/usr/bin/time increased by a factor of about 1.5.  That seems like way
too much overhead for thread coordination.

Here are hprof output files for the "double 1 thread" and "double 2
threads" tests:

http://github.com/jafingerhut/clojure-benchmarks/blob/51d499c2679c2d5ed42a65adcef6d9e8bc3e1aad/misc/pmap-batch-output/pmap-double-1-hprof.txt

http://github.com/jafingerhut/clojure-benchmarks/blob/51d499c2679c2d5ed42a65adcef6d9e8bc3e1aad/misc/pmap-batch-output/pmap-double-2-hprof.txt

In both cases, over 98% of the time is spent in
java.lang.Double.valueOf(double d).  See the files for the full stack
backtraces if you are curious.

I don't see any reason why that method should have any kind of
contention or worse performance when running on 2 cores vs. 1 core,
but I don't know the guts of how it is implemented.  At least in
OpenJDK all it does is "return new Double(d)", where d is the double
arg to valueOf().  Is there any reason why "new" might exhibit
contention between parallel threads?

Andy

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

Re: Question about pmap




On Aug 6, 10:00 am, Bradbev  wrote:
> On Aug 6, 3:07 am, Andy Fingerhut 
> wrote:
>
>
>
> > On Aug 5, 6:09 am, Rich Hickey  wrote:
>
> > > On Wed, Aug 5, 2009 at 8:29 AM, Johann Kraus 
> > > wrote:
>
> > > >> Could it be that your CPU has a single floating-point unit shared by 4
> > > >> cores on a single die, and thus only 2 floating-point units total for
> > > >> all 8 of your cores?  If so, then that fact, plus the fact that each
> > > >> core has its own separate ALU for integer operations, would seem to
> > > >> explain the results you are seeing.
>
> > > > Exactly, this would explain the behaviour. But unfortunately it is not
> > > > the case. I implemented a small example using Java (Java Threads) and
> > > > C (PThreads) and both times I get a linear speedup. See the attached
> > > > code below. The cores only share 12 MB cache, but this should be
> > > > enough memory for my micro-benchmark. Seeing the linear speedup in
> > > > Java and C, I would negate a hardware limitation.
>
> > > > _
> > > > Johann
>
> > > I looked briefly at your problem and don't see anything right off the
> > > bat. Do you have a profiler and could you try that out? I'm
> > > interested.
> > > Rich
>
> > I ran these tests on my iMac with 2.16 GHz Intel Core 2 Duo (2 cores)
> > using latest Clojure and clojure-contrib from git as of some time on
> > Aug 4, 2009.  The Java implementation is from Apple, version 1.6.0_13.
>
> > --
> > For int, there are 64 "jobs" run, each of which consists of doing
> > (inc 0) 1,000,000,000 times.  See pmap-batch.sh and pmap-testing.clj
> > for details.
>
> >http://github.com/jafingerhut/clojure-benchmarks/blob/398688c71525964...
>
> >http://github.com/jafingerhut/clojure-benchmarks/blob/398688c71525964...
>
> > Yes, yes, I know.  I should really use a library for command line
> > argument parsing to avoid so much repetitive code.  I may do that some
> > day.
>
> > Results for int 1 thread - jobs run sequentially
>
> > "Elapsed time: 267547.789 msecs"
> > real       269.22
> > user       268.61
> > sys          1.79
>
> > int 2 threads - jobs run in 2 threads using modified-pmap, which
> > limits the number of futures causing threads to run jobs to be at most
> > 2 at a time.
>
> > "Elapsed time: 177428.626 msecs"
> > real       179.14
> > user       330.30
> > sys         15.46
>
> > Comment: Elapsed time with 2 threads is about 2/3 of elapsed time with
> > 1 thread.  Not as good as the 1/2 as we'd like with a 2 core machine,
> > but better than not being faster at all.
>
> > --
> > For double, there are 16 "jobs" run, each of which consists of doing
> > (inc 0.1) 1,000,000,000 times.
>
> > double 1 thread
>
> > "Elapsed time: 258659.424 msecs"
> > real       263.28
> > user       247.29
> > sys         12.17
>
> > double 2 threads
>
> > "Elapsed time: 229382.68 msecs"
> > Dumping CPU usage by sampling running threads ... done.
> > real       231.05
> > user       380.79
> > sys         11.49
>
> > Comment: Elapsed time with 2 threads is about 7/8 of elapsed time with
> > 1 thread.  Hardly any improvement at all for something that should be
> > "embarrassingly parallel", and the user time reported by Mac OS X's
> > /usr/bin/time increased by a factor of about 1.5.  That seems like way
> > too much overhead for thread coordination.
>
> > Here are hprof output files for the "double 1 thread" and "double 2
> > threads" tests:
>
> >http://github.com/jafingerhut/clojure-benchmarks/blob/51d499c2679c2d5...
>
> >http://github.com/jafingerhut/clojure-benchmarks/blob/51d499c2679c2d5...
>
> > In both cases, over 98% of the time is spent in
> > java.lang.Double.valueOf(double d).  See the files for the full stack
> > backtraces if you are curious.
>
> > I don't see any reason why that method should have any kind of
> > contention or worse performance when running on 2 cores vs. 1 core,
> > but I don't know the guts of how it is implemented.  At least in
> > OpenJDK all it does is "return new Double(d)", where d is the double
> > arg to valueOf().  Is there any reason why "

Re: Transient Data Structures

On Aug 6, 4:53 am, Rich Hickey  wrote:
> On Aug 5, 10:10 pm, Luc Prefontaine 
> wrote:
>
> > I like this very much... that's the kind of clever optimizations that
> > preserves Clojure principles and
> > can yield significant performance increases. This could also help
> > dealing with performance critics
> > in these small mutable languages "benchmarks" that newbies attempt to
> > clone in Clojure.
>
> > Thank's Rich !
>
> You're welcome!
>
> And special thanks to Christophe Grand, who (quickly!) applied the
> same technique to the hash maps and contributed that yesterday. So
> now, in the master branch, vectors and hash maps support transients.
> Everyone please try them out (where appropriate :).
>
> Rich

Thank you, Christophe!  I've been wanting to try those out.

I made changes to 3 lines of my Clojure program for the k-nucleotide
benchmark, which spends most of its time in a function tally-dna-subs-
with-len that creates a hash map counting the number of times that
each of a bunch of length k strings occurs in a long string.  Source
here, if you're curious:

http://github.com/jafingerhut/clojure-benchmarks/blob/38e1f592ca3befe94a0674a5f5a43d952cd369b3/knuc/knucleotide.clj-7.clj

It went from about 19 minutes down to about 12 minutes.  Excellent
improvement for a small change to the code.  That brings it down to
about 7.7 times the run time of the Java version from the language
shootout web site.

Andy

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

Re: Clojure performance tests and clojure a little slower than Java


On Aug 6, 3:28 pm, André Thieme  wrote:
> On 27 Jul., 23:26, AndyF  wrote:
>
> Hello Andy, could you please update the following table?
>
>
>
> >         |  sbcl  |  perl  |   ghc  |  java |   clj
> > -
> > mand-   | wrong  | out of |  32.7  |  28.6  | 340.4
> > elbrot  | output | mem    |  59.3  |  54.4  | 350.5
> >         |        | (?)    |   0.8  |   0.4  |   4.7
>
> > k-nuc-  | 190.9  | 306.0  |  90.5  |  52.4  | 1677.6 (27m 57.6s)
> > leotide | 187.9  | 302.7  | 130.8  |  89.6  | 2245.1 (37m 25.1s)
> >         |   2.4  |   1.9  |   4.6  |   1.8  |   24.2 (    24.2s)
>
> When I understand you correctly, you now use Transients
> in those benchmarks, which improved their runtime behaviour.

You are correct.  I've updated that file:

http://github.com/jafingerhut/clojure-benchmarks/blob/bb9755bdeeccae84a9b09fbf34e45f6d45d4b627/RESULTS

I've attempted to always put the best Clojure program results I've
found so far on the same line with the run times for the programs in
other languages, and then sometimes I will also include the second
best Clojure results on a separate group of lines after that.

Thanks,
Andy

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

Re: Question about pmap

On Aug 6, 11:51 am, John Harrop  wrote:
> Cache misses are a possibility; try the integer version with long, so the
> size of the data is the same as with double.
> The other possibility I'd consider likely is that the JDK you were using
> implements caching in Double.valueOf(double). This could be dealt with if
> Clojure boxing directly called new Double(double). Caching in valueOf
> methods has been known to cause trouble in other situations, involving Java,
> primitive boxing, and performance. Besides the caching wrecking memory
> access-pattern locality, causing CPU cache misses, it likely involves
> acquiring and releasing a global lock on the Double cache, which will kill
> multithreaded performance particularly.

Interesting how the caching can mess performance up, especially in
multi-threaded situations.  I don't know yet how to confirm whether my
implementation uses that caching, but I did see a mention of it in
some docs for Double.valueOf(double), and didn't think about the
possibility of that introducing locking.  In this particular test, I
doubt it would increase non-locality much if at all, since we are
always providing the same value (0.1) to the method, so the cache
should have exactly 1 element in it the whole time.  But if it were
synchronized, that would definitely bring down the performance of this
particular test, or in general any test with a significant number of
float or double operations, down closer to that of a single core.

If that is the performance bottleneck in this case, is there any way
around it?  Perhaps I could try locally changing my Clojure Java
source to use new Double instead of Double.valueOf(double) and it
might actually be faster.

I'll try out some variations with different types like long and float,
and report back when I've got them.

Thanks,
Andy

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

combining methods

2009-08-07 Thread Andy Chambers


Hey All,

Does clojure have an equivalent of either CLOS's `call-next-method' or
java's super?

For example, given the multi-method, and the interfaces ICDISCElement
and IODMDef, where IODMDef extends ICDISCElement

(defmulti validate class)

(defmethod validate ICDISCElement [elem]
  ;;generic validation of all elements)

(defmethod validate IODMDef [def]
  ;;how can I do stuff in here then pass control to the other validate
method)


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

Re: Clojure performance tests and clojure a little slower than Java

2009-08-07 Thread Andy Fingerhut

On Aug 6, 6:49 pm, John Harrop  wrote:
> On Thu, Aug 6, 2009 at 6:57 PM, Andy Fingerhut <
>
> andy_finger...@alum.wustl.edu> wrote:
> > You are correct.  I've updated that file:
>
> >http://github.com/jafingerhut/clojure-benchmarks/blob/bb9755bdeeccae8...
>
> Could you post the Mandelbrot code you use? Because I know for a fact that
> Clojure can do FP calcs as fast as native C code, given the -server vm and a
> loop/recur with unboxed doubles, and my understanding of Mandelbrot is that
> it's just FP calcs.

Here is the root of the clojure-benchmarks github directory tree.
They are all in there:

http://github.com/jafingerhut/clojure-benchmarks/tree/master

You can get specific files by browsing the directory tree on the web
site, or if you use git, you can git clone the whole thing and have a
local copy on your computer:

git clone git://github.com/jafingerhut/clojure-benchmarks.git

It is mandelbrot/mandelbrot.clj-1.clj.  There is a
mandelbrot.clj-2.clj that is the same, except it uses my modified-pmap
to compute separate rows in parallel.  I'm still investigating reasons
why parallelism isn't getting me much bang for the buck in the
"questions about pmap" thread before worrying performance turning more
complex programs using floats/doubles in parallel.

I did go back to the archives for a discussion in early April, 2009
when others on this list were discussing how to tweak the core of the
mandelbrot code (the function "dot" in my version), and I used the
fastest of those versions I could find, but I may have missed some
opportunities for speeding it up, and I definitely welcome any and all
improved versions.  I'd recommend comparing the speed on your machine
vs. the Java version that is in the same directory as the Clojure
source.

Andy

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

Re: Test a random function

2009-08-07 Thread Andy Fingerhut

On Aug 7, 6:17 pm, Sean Devlin  wrote:
> Ok, I need some help.  I'm writing some tests for c.c.seq-utils, and I
> ran into a problem defining a test for both shuffle and rand-elt.
>
> Does anyone here have any experience writing tests for random
> functions?  Am I going to need to use serious statistics the answer
> this?
>
> Ideas?

It depends upon what you want to test.  If you want to test that rand-
elt selects an item from the seq s independently on each run, and with
equal probability for all elements, then that is effectively like
testing rand-int for the same properties, and yes, you will have to
get into some statistics to do so.

However, if you back off from testing the random part of the function,
there are some "invariants" that are always true that you could test,
such as:

(1) the value x returned by rand-elt should always be a member of the
seq s

(2) the value returned by shuffle should always have the same number
of each item as the input seq s.  That is, if you evaluate the
function 'tally' below on the input seq s and on the returned seq t,
you should always find (= (tally s) (tally t)) is true.

(defn tally [s]
  (loop [s s
 t (transient {})]
(if-let [s (seq s)]
  (let [item (first s)]
(recur (next s) (assoc! t item (inc (get t item 0)
  (persistent! t

Andy

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

Re: Clojure performance tests and clojure a little slower than Java

2009-08-07 Thread Andy Fingerhut


On Aug 7, 5:14 pm, John Harrop  wrote:
> Your core loop seems to be:
> (loop [zr (double 0.0)
>          zi (double 0.0)
>          zr2 (double 0.0)
>          zi2 (double 0.0)
>          iterations-remaining iterations-remaining]
>     (if (and (not (neg? iterations-remaining))
>              (< (+ zr2 zi2) limit-square))
>       (let [new-zi (double (+ (* (* f2 zr) zi) pi))
>             new-zr (double (+ (- zr2 zi2) pr))
>             new-zr2 (double (* new-zr new-zr))
>             new-zi2 (double (* new-zi new-zi))]
>         (recur new-zr new-zi new-zr2 new-zi2 (dec iterations-remaining)))
>
> What I suggest is
>
> (loop [zr (double 0.0)
>        zi (double 0.0)
>        i (int (inc iterations-remaining))]
>   (let [zr2 (* zr zr)
>         zi2 (* zi zi)]
>     (if (and (not (= 0 i)) (< (+ zr2 zi2 limit-square)))
>        (recur (+ (- zr2 zi2) pr) (+ (* (* f2 zr) zi) pi) (unchecked-inc i))
>        (whatever...
>
> * Same calculations
> * Less items in recur rebind
> * Counter is also primitive
>
> (untested, may need slight tweakage)

Needed unchecked-dec in place of unchecked-inc, and I used (zero? i)
instead of (= 0 i) (not sure if that makes much difference), and the
results are much better -- the time went down to a little less than
half of what it was before.

http://github.com/jafingerhut/clojure-benchmarks/blob/fe10ef25ec17b77dd03f6d1ccff4f35273764f3b/RESULTS

I also tried it with 4 parallel threads on my 2-core machine, and this
problem parallelizes significantly better than the simpler problem in
the "questions about pmap" discussion thread -- nearly half the
elapsed time, and only 6% more total CPU time for the 4-thread version
vs. the sequential version.

Thanks!
Andy

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

Re: Question about pmap

2009-08-08 Thread Andy Fingerhut


Johann, if you are still following this thread, could you try running
this Clojure program on your 8 core machine?

http://github.com/jafingerhut/clojure-benchmarks/blob/3e45bd8f6c3eba47f982a0f6083493a9f076d0e9/misc/pmap-testing.clj

These first set of parameters below will do 8 jobs sequentially, each
doing 10^10 (inc c)'s, where c is a double primitive.  The second will
do the 8 jobs in parallel, hopefully finishing about 8 times faster on
your machine:

java -cp  clojure.main pmap-testing.clj double2 8
100 1
java -cp  clojure.main pmap-testing.clj double2 8
100 8

If you replace double2 with double1, it should reproduce your initial
test case with (inc 0.1) in the inner loop -- the one that started
this thread about why there wasn't much speedup.


I created some Clojure and Java functions that are as similar as I
know how to make them, but frankly I don't really know whether my JVM
implementation (Apple's java 1.6.0_13) is using 'new Double', or a
cache as mentioned by John Harrop earlier in this discussion, in its
implementation of Double.valueOf(double).  I've found that the
performance is very similar to a Java program that uses 'new Double'
explicitly in its inner loop.

In the results linked below, the 'sequential' runs are for calling the
function named twice in a row, whereas the 'parallel' runs are for
having two parallel threads, on my 2 core machine, each of which calls
the named function once.  The total amount of computation in each case
should be the same, so you'd hope that the parallel case would finish
in about half the time, with about the same amount of total CPU time
being utilized.

That isn't what happens for the Java code with 'new Double' (called
NewDoubleTest), or for the Clojure code that has (inc 0.1) and calls
Double.valueOf(double) down in its implementation (called spin-
double1).  The parallel case only saves about 14% of the elapsed time
with 2 cores, and takes about 50% more total CPU time.

The more typical code that takes a single double value, initializes
it, and then adds 1 to it each time through the inner loop (Java
DoubleTest, Clojure spin-double2), is significantly faster than the
versions mentioned above.  Plus they exhibit the expected speedup from
using 2 cores instead of 1.

http://github.com/jafingerhut/clojure-benchmarks/blob/3e45bd8f6c3eba47f982a0f6083493a9f076d0e9/misc/RESULTS

I'm not sure how to determine why calling 'new Double' each time
through NewDoubleTest's inner loop causes 2 threads to perform not
much better than 1.  The best possible explanation I've heard is from
Nicolas Oury -- perhaps we are measuring the bandwidth from cache to
main memory, not raw computational ability of the processor cores.

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

Re: Clojure performance tests and clojure a little slower than Java

2009-08-09 Thread Andy Fingerhut

On Aug 8, 2:16 pm, John Harrop  wrote:
> On Sat, Aug 8, 2009 at 5:23 AM, Mark Engelberg 
> wrote:
>
>
>
> > On Fri, Aug 7, 2009 at 5:14 PM, John Harrop wrote:
> > >     (if (and (not (= 0 i)) (< (+ zr2 zi2 limit-square)))
>
> > I believe that (zero? i) is faster than (= 0 i).
>
> On primitive ints? Have you tested it?

I have, now, at your suggestion.  Here are the results on my iMac,
2.16 GHz Intel Core 2 Duo, Mac OS X 10.5.8, Java version:

% java -version
java version "1.6.0_13"
Java(TM) SE Runtime Environment (build 1.6.0_13-b03-211)
Java HotSpot(TM) 64-Bit Server VM (build 11.3-b02-83, mixed mode)

All are for the mandelbrot.clj-3.clj program here:

http://github.com/jafingerhut/clojure-benchmarks/blob/3e45bd8f6c3eba47f982a0f6083493a9f076d0e9/mandelbrot/mandelbrot.clj-3.clj

(By the way, these links should not be to blank pages, as you
experienced earlier.  I can follow them when reading in the Clojure
group web page, or in my email client.  Perhaps the software you are
using to read these messages is truncating the URLs, and thus they are
not going to the intended place?  Sorry they are so long, which tends
to cause these kinds of issues.)

I did two runs for each version, with the only difference between them
being replacing the (zero? i) expression in function 'dot' with a
different expression, as indicated below.  (zero? i) is a clear winner
in reducing run time.

If it makes a difference, I'm also using latest github clojure and
clojure-contrib as of about August 6, 2009.  Here is what the REPL
says about the definition of zero?

% clj
Clojure 1.1.0-alpha-SNAPSHOT
user=> (use 'clojure.contrib.repl-utils)
nil
user=> (source zero?)
(defn zero?
  "Returns true if num is zero, else false"
  {:tag Boolean
   :inline (fn [x] `(. clojure.lang.Numbers (isZero ~x)))}
  [x] (. clojure.lang.Numbers (isZero x)))

using (zero? i) in dot:

real2m38.378s
user2m40.601s
sys 0m1.875s

real2m30.614s
user2m33.081s
sys 0m1.853s

using (= 0 i) in dot:

real3m18.556s
user3m20.334s
sys 0m2.060s

real3m20.425s
user3m23.392s
sys 0m1.734s

using (== 0 i) in dot:

real3m21.701s
user3m24.043s
sys 0m1.982s

real3m22.441s
user3m24.420s
sys 0m2.013s

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

Re: Pure-functional N-body benchmark implementation

On Aug 10, 11:35 am, fft1976  wrote:
> On Aug 10, 4:46 am, Jarkko Oranen  wrote:
>
> > I'm not going to start optimising,
>
> Somebody'd better!
>
> You always hear this dogma that one should write "elegant" code first
> and optimize later, and when you do that, a few little changes can
> make Clojure as fast as Java.
>
> Here's your chance to show it :-)
>
> > but somehow I doubt that is
> > the bottleneck
>
> The locality of changes is what I doubt.

I've got a functional version in my clojure-benchmarks git repository,
too, and it is currently 138 times slower on my machine than the Java
version.  I haven't looked in detail at your code, but at a high level
it appears to be similar to yours in structure -- i.e., it doesn't try
to go overboard with float/double declarations, and uses only Clojure
data structures.  I haven't tried optimizing it yet, just because I've
done more optimizing with some of the other benchmarks first.

It would be nice to have a Clojure version under 10 times Java's run
time here, without resorting to Java data structures and methods.
There may be better motivational techniques than using the word
"dogma" and daring people to do better :-)

Then again, perhaps this may be an example where the best thing for
someone working on a real project is to take the inner loop code and
write it in Java, the way some people take inner loops in C progams
and hand-code them in assembly -- because they are in a situation
where it is worth the time to optimize.  I would point out that some
of these benchmark programs in Haskell, for example, are not pure
functional implementations, and people have gone to (what seems to me)
great effort to optimize the heck out of their programs in ways that
most Haskell programmers would probably find excessive.  Even some of
the C and C++ implementations seem to pull out __builtin_memmove calls
and explicitly using SSE macros in order to tweak out a few more
milliseconds of lower run time.

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

Re: Pure-functional N-body benchmark implementation

On Aug 10, 2:19 pm, Jonathan Smith  wrote:
> 1.) use something mutable
> 2.) unroll all the loops (mapping is a loop)
> 3.) try not to coerce between seq/vec/hash-map too much.
>
> in real world, stuff like the shootout is pretty useless, as generally
> you'd reach for a better algorithm rather than implementing the
> shackled, crippled, naive algorithms that the benchmark forces you to
> implement.
>
> (Not that they aren't useful to some extent, just that language
> productivity and how fast you can iterate your software design in the
> language is, IMO, a much better indicator of a good language than
> micro benchmarking).

I agree that they are useful to some extent.  In the real world, you
would use a better algorithm, but those better algorithms can be
implemented in any language, too.  As you say, a higher level language
that lets you iterate more quickly on multiple implementations of
different algorithms has advantages.  At the end of the day, there is
something in the language implementations that can enable faster
execution times than others.  A micro-benchmark can be useful to tell
you that if your application needs to do lots of double number
crunching, you definitely shouldn't be implementing it in Perl, for
example -- at least not that part of your application.

By the way, fft1976, this Clojure version of the n-body benchmark
takes about half the time of your code on my machine (for a shorter
test than the one for the benchmark web site -- I haven't compared yet
on the full length test since it takes about an hour for my version).

http://github.com/jafingerhut/clojure-benchmarks/blob/3e45bd8f6c3eba47f982a0f6083493a9f076d0e9/n-body/nbody.clj-5.clj

It doesn't use any mutable data structures, but it does use vectors,
has some double declarations, and avoids using map for operations on
pairs of 3d vectors, so it has some optimizations.

Using the new transient vectors recently added by Rich, and also
either using transient maps, or changing the implementation of planet
data to use vectors instead of the maps that I use, would probably
speed things up some more.  I also still have a fair number of uses of
map that would probably be faster with loop/recur.

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

Re: Pure-functional N-body benchmark implementation

OK, I've got a new Clojure program for the n-body benchmark, and it is
significantly faster than my previous one -- down from 138 x Java run
time, to 37 x Java run time. Still room for improvement somewhere
there, I'm sure, including perhaps using Java arrays instead of
Clojure vectors.

http://github.com/jafingerhut/clojure-benchmarks/blob/2423c5ba7bcded349bc21cfa4204bb840fd75bfa/n-body/nbody.clj-6.clj

The main changes from the slower version are:

+ make separate vectors for each "attribute" of a body in motion, i.e.
a separate vector of positions, a vector of velocities, etc., instead
of using maps.
+ Use loop/recur almost everywhere it makes sense. I still have a few
map calls in the function 'energy' and the functions it calls, and
maybe in the init code, but that is only done twice and once during
the whole execution, versus advance which is called 50,000,000 times
in the long version of the benchmark.
+ It uses the new transient/assoc!/conj!/persistent! functions for
Clojure vectors, so you need a pretty new copy of Clojure if you want
to run it yourself.

Updates summary of results is here:

http://github.com/jafingerhut/clojure-benchmarks/blob/14c5df3ee28d418a938de584f6675860043dd0f5/RESULTS

And, as usual, improvements to the performance of these Clojure
programs are welcome.

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

Re: Pure-functional N-body benchmark implementation


On Aug 10, 5:57 pm, Mark Engelberg  wrote:
> Andy,
>
> My understanding is that any double that gets stored in a vector or
> map is boxed, and therefore, the vast majority of your double
> conversions aren't really doing anything, because when you pull them
> out of the vector or map, they'll just be Double objects again.
>
> I believe that the biggest reason for the performance difference
> between Clojure and Java on this benchmark is that if you use a
> Clojure data structure (e.g., a map) to represent each "body" object,
> you get a lot of boxing and unboxing of the doubles.
>
> So I hypothesize that the biggest bang for the buck is to find a way
> in Clojure to create body objects with primitive double fields.  Can
> the new new do that?  If not, your best bet may be to represent a body
> object as a Java array of several doubles, rather than using a Clojure
> map.  The first double could represent the mass, the second could
> represent vx, the second vy, and so on.  Make macros for the accessors
> that extract these values using aget.
>
> It's speculation on my part, but I think this will get you much closer
> to Java speed than your current approach.

I've tried an approach like you suggest, using mutable Java arrays of
doubles, macros using aget / aset-double for reading and writing these
arrays, and loop/recur everywhere iteration is needed in the inner
loop.  It is here:

http://github.com/jafingerhut/clojure-benchmarks/blob/173e68a52ca2e180f9d5f3ac4c81a737358d1491/n-body/nbody.clj-7.clj

I was surprised to find that it is significantly slower (about 3x)
than my best Clojure one so far, which uses the new transients, and
vectors of doubles to store the state of the bodies -- the one I
posted earlier today.

http://github.com/jafingerhut/clojure-benchmarks/blob/173e68a52ca2e180f9d5f3ac4c81a737358d1491/n-body/nbody.clj-6.clj

The updated summary of results is here:

http://github.com/jafingerhut/clojure-benchmarks/blob/173e68a52ca2e180f9d5f3ac4c81a737358d1491/RESULTS

I suspect I'm doing something wrong in my mutable Java array
implementation, but I don't see what it could be.

Thanks,
Andy
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

Re: Pure-functional N-body benchmark implementation


On Aug 10, 11:33 pm, Mark Engelberg  wrote:
> On Mon, Aug 10, 2009 at 11:15 PM, Andy
>
> Fingerhut wrote:
> > I suspect I'm doing something wrong in my mutable Java array
> > implementation, but I don't see what it could be.
>
> There still seems to be a lot of boxing and unboxing going on.  For example, 
> in:
> (let [[momx momy momz] (offset-momentum bodies)
> the call to offset-momentum returns a vector of the three doubles, so
> they would be boxed, so momx momy momz are not primitives.

That code is only run once during initialization, then never again.
It is well under 0.1% of the entire run time of the long benchmark.

The bulk of the computation is this call tree, where advance! is
called 50,000,000 times sequentially in the long benchmark:

advance!
bodies-update-velocities!
bodies-update-positions!

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

Re: Pure-functional N-body benchmark implementation

On Aug 10, 11:50 pm, Christophe Grand  wrote:
> Hi Andy,
>
> On Tue, Aug 11, 2009 at 8:15 AM, Andy Fingerhut <
>
> andy_finger...@alum.wustl.edu> wrote:
> > I've tried an approach like you suggest, using mutable Java arrays of
> > doubles, macros using aget / aset-double for reading and writing these
> > arrays, and loop/recur everywhere iteration is needed in the inner
> > loop.  It is here:
>
> aget-* and aset-* are slow, just use aget and aset with type hints.
>
> Christophe

Wow, you ain't kiddin.  I changed about 10 lines from my last version,
to avoid using aset-double, using aset and type hints until the
reflection warnings went away, and it sped up by a factor of 10.  I'm
leaving the previous version's source and results there just so I can
have a future reference to point to at the difference it makes.  New
results here:

http://github.com/jafingerhut/clojure-benchmarks/blob/9dc56d8ff53f0b8d363f213317587432bd8793de/RESULTS

Still almost 11 times slower than the Java version, but a lot more
respectable than my earlier attempts.

Should there be a similar warning like *warn-on-reflection* that tells
you to avoid using aset-* if you want better performance?  Or at least
put a loud warning in the doc strings for those functions about their
poor performance?  Or can they just be removed?

Thanks!

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

Re: Transient Data Structures


On Aug 10, 11:15 am, Christophe Grand  wrote:
> Hi Andy,
>
> On Thu, Aug 6, 2009 at 7:40 PM, Andy Fingerhut <
>
>
>
> andy_finger...@alum.wustl.edu> wrote:
> > Thank you, Christophe!  I've been wanting to try those out.
>
> > I made changes to 3 lines of my Clojure program for the k-nucleotide
> > benchmark, which spends most of its time in a function tally-dna-subs-
> > with-len that creates a hash map counting the number of times that
> > each of a bunch of length k strings occurs in a long string.  Source
> > here, if you're curious:
>
> >http://github.com/jafingerhut/clojure-benchmarks/blob/38e1f592ca3befe...
>
> > It went from about 19 minutes down to about 12 minutes.  Excellent
> > improvement for a small change to the code.  That brings it down to
> > about 7.7 times the run time of the Java version from the language
> > shootout web site.
>
> Could you try my "leafless" 
> branch;http://github.com/cgrand/clojure/tree/leafless?
>
> Thanks,
>
> Christophe

And Christophe's latest improvements to transient support for maps
improves the running time of my k-nucleotide benchmark program from
about 12 minutes to about 9.5 minutes.  Very nice stuff.  It isn't in
Rich's clojure repository yet, but you can get the changes from
Christophe's github repo if you want to try it out.

Thanks,
Andy
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

Re: Pure-functional N-body benchmark implementation

In case it matters to anyone, my intent in creating these Clojure
programs to compare their speed to others isn't to try to rip into
Clojure, or start arguments. It is for me to get my feet wet with
Clojure, and perhaps produce some examples that others can learn from
on what performs well in Clojure and what doesn't. So far, it has
even had the unexpected benefit of providing a ready-made test for
Christophe Grand to do a quick test of some improvements to his
implement of transients for Clojure maps. Cool beans.

Also, while it may appear I do benchmarks for a living, I don't :-)
I'd personally like to know before investing more time with Clojure
what kind of performance I can attain with it. Most of my commercial
software development to date has been in assembly and C, and the
expressiveness of Lisp is a breath of fresh air that helps me remember
why I love programming. Clojure's concurrency features, and keeping
around the power of Lisp macros, are a huge pull for me.

But there are those times that you want performance, and I'm curious
how much I can get out of Clojure code, vs. implementing certain inner
loops in Java, C, or what-have-you. Just because some part of your
code might lead you, for desire of better performance, to implement it
by hand in Java or C doesn't deter me from Clojure at all -- but I'd
like to know how likely that is.

OK, with that said, I've now got the n-body benchmark within 3.2 times
Java's run time on the same problem. The only change from my previous
version that sped things up was to replace 3-operand arithmetic
operations with 2-operand operations. Currently, this enables Clojure
to use primitive ops, instead of something slower.

Updated results here:

http://github.com/jafingerhut/clojure-benchmarks/blob/0f7fdd358086cb95c898d7c2656215408a8d0689/RESULTS

As always, suggestions or improved versions are welcome.

Thanks,
Andy
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---

Re: Can Clojure be as fast as Java?


On Aug 11, 4:27 pm, Stuart Halloway  wrote:
> If I am reading the README correctly, clj-8 is 10.8 times slower than  
> Java, but clj-9 does better: 3.2 times slower.
>
> Stu

You are reading that correctly.  My clj-9 wasn't created until after
fft1976's message starting this thread.

Andy

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

Re: Pure-functional N-body benchmark implementation