2010/8/4 David Nolen <dnolen.li...@gmail.com>
> Have you considered that you're realizing very large lazy sequences and
> might be thrashing around in GC ? The parallel versions needs X times the
> available memory of the sequential version, where X is the number of
> concurrent threads right?
David, I don't think so, the burn function does not seem to hold onto the
head.
There's indeed a "potential" problem in the pmap version since it holds onto
the head of n-sized sequence, but since n ranges from 4 to 32 it hardly can
be the problem.
Lee, I don't have the general answer, but as a related note, I think there
may be a problem with the "with futures" version:
a. you quickly "bootstrap" all futures in the inner call to map
b. you collect the results of the futures in parallel in the outer call to
pmap
as a reminder:
(defn burn-via-futures [n]
(print n " burns via futures: ")
(time (doall (pmap deref (map (fn [_] (future (burn)))
(range n))))))
problem #1: since map is lazy, the bootstrapping of the futures will follow
the consumption of the seq by pmap (modulo chunked seq behavior). So to
quickly bootstrap all your futures before passing the seq to pmap, you
should wrap the (map) inside a doall
problem #2: maybe deref is a quick enough operation that using pmap with
deref does not make sense (or would make sense if the number of cores were
realllly big, e.g. if the coll would be of size 1.000.000 and the number of
core of the same magnitude order.
> David
>
>
> On Wed, Aug 4, 2010 at 10:36 AM, Lee Spector <lspec...@hampshire.edu>wrote:
>
>>
>> Apologies for the length of this message -- I'm hoping to be complete, but
>> that made the message pretty long.
>>
>> Also BTW most of the tests below were run using Clojure 1.1. If part of
>> the answer to my questions is "use 1.2" then I'll upgrade ASAP (but I
>> haven't done so yet because I'd prefer to be confused by one thing at a time
>> :-). I don't think that can be the full answer, though, since the last batch
>> of runs below WERE run under 1.2 and they're also problematic...
>>
>> Also, for most of the runs described here (with the one exception noted
>> below) I am running under Linux:
>>
>> [lspec...@fly ~]$ cat /proc/version
>> Linux version 2.6.18-164.6.1.el5 (mockbu...@builder10.centos.org) (gcc
>> version 4.1.2 20080704 (Red Hat 4.1.2-46)) #1 SMP Tue Nov 3 16:12:36 EST
>> 2009
>>
>> with this Java version:
>>
>> [lspec...@fly ~]$ java -version
>> java version "1.6.0_16"
>> Java(TM) SE Runtime Environment (build 1.6.0_16-b01)
>> Java HotSpot(TM) 64-Bit Server VM (build 14.2-b01, mixed mode)
>>
>> SO: Most of the documentation and discussion about clojure concurrency is
>> about managing state that may be shared between concurrent processes, but I
>> have what I guess are more basic questions about how concurrent processes
>> can/should be started even in the absence of shared state (or when all
>> that's shared is immutable) and about how to get the most out of concurrency
>> on multiple cores.
>>
>> I often have large numbers of relatively long, independent processes and I
>> want to farm them out to multiple cores. (For those who care this is often
>> in the context of evolutionary computation systems, with each of the
>> processes being a fitness test.) I had thought that I was farming these out
>> in the right way to multiple cores, using agents or sometimes just pmap, but
>> then I noticed that my runtimes weren't scaling in the way that I expected
>> across machines with different numbers of cores (even though I usually saw
>> near total utilization of all cores in "top").
>>
>> This led me to do some more systematic testing and I'm confused/concerned
>> about what I'm seeing, so I'm going to present my tests and results here in
>> the hope that someone can clear things up for me. I know that timing things
>> in clojure can be complicated both on account of laziness and on account of
>> optimizations that happen on the Java side, but I think I've done the right
>> things to avoid getting tripped up too much by these issues. Still, it's
>> quite possible that I've coded some things incorrectly and/or that I'm
>> misunderstanding some basic concepts, and I'd appreciate any help that
>> anyone can provide.
>>
>> First I defined a function that would take a non-trivial amount of time to
>> execute, as follows:
>>
>> (defn burn
>> ([] (count
>> (take 1E6
>> (repeatedly
>> #(* 9999999999 9999999999)))))
>> ([_] (burn)))
>>
>> The implementation with an ignored argument just serves to make some of my
>> later calls neater -- I suppose I might incur a tiny additional cost when
>> calling it that way but this will be swamped by the things I'm timing.
>>
>> Then I defined functions for calling this multiple times either
>> sequentially or concurrently, using three different techniques for starting
>> the concurrent processes:
>>
>> (defn burn-sequentially [n]
>> (print n " sequential burns: ")
>> (time (dotimes [i n] (burn))))
>>
>> (defn burn-via-pmap [n]
>> (print n " burns via pmap: ")
>> (time (doall (pmap burn (range n)))))
>>
>> (defn burn-via-futures [n]
>> (print n " burns via futures: ")
>> (time (doall (pmap deref (map (fn [_] (future (burn)))
>> (range n))))))
>>
>> (defn burn-via-agents [n]
>> (print n " burns via agents: ")
>> (time (let [agents (map #(agent %) (range n))]
>> (dorun (map #(send % burn) agents))
>> (apply await agents))))
>>
>> Finally, since there's often quite a bit of variability in the run time of
>> these things (maybe because of garbage collection? Optimization? I'm not
>> sure), I define a simple macro to execute a call three times:
>>
>> (defmacro thrice [expression]
>> `(do ~expression ~expression ~expression))
>>
>> Now I can do some timings, and I'll first show you what happens in one of
>> the cases where everything performs as expected.
>>
>> On a 16-core machine (details at
>> http://fly.hampshire.edu/ganglia/?p=2&c=Rocks-Cluster&h=compute-4-1.local),
>> running four burns thrice, with the code:
>>
>> (thrice (burn-sequentially 4))
>> (thrice (burn-via-pmap 4))
>> (thrice (burn-via-futures 4))
>> (thrice (burn-via-agents 4))
>>
>> I get:
>>
>> 4 sequential burns: "Elapsed time: 2308.616 msecs"
>> 4 sequential burns: "Elapsed time: 1510.207 msecs"
>> 4 sequential burns: "Elapsed time: 1182.743 msecs"
>> 4 burns via pmap: "Elapsed time: 470.988 msecs"
>> 4 burns via pmap: "Elapsed time: 457.015 msecs"
>> 4 burns via pmap: "Elapsed time: 446.84 msecs"
>> 4 burns via futures: "Elapsed time: 417.368 msecs"
>> 4 burns via futures: "Elapsed time: 401.444 msecs"
>> 4 burns via futures: "Elapsed time: 398.786 msecs"
>> 4 burns via agents: "Elapsed time: 421.103 msecs"
>> 4 burns via agents: "Elapsed time: 426.775 msecs"
>> 4 burns via agents: "Elapsed time: 408.416 msecs"
>>
>> The improvement from the first line to the second is something I always
>> see (along with frequent improvements across the three calls in a "thrice"),
>> and I assume this is due to optimizations talking place in the JVM. Then we
>> see that all of the ways of starting concurrent burns perform about the
>> same, and all produce a speedup over the sequential burns of somewhere in
>> the neighborhood of 3x-4x. Pretty much exactly what I would expect and want.
>> So far so good.
>>
>> However, in the same JVM launch I then went on to do the same thing but
>> with 16 and then 48 burns in each call:
>>
>> (thrice (burn-sequentially 16))
>> (thrice (burn-via-pmap 16))
>> (thrice (burn-via-futures 16))
>> (thrice (burn-via-agents 16))
>>
>> (thrice (burn-sequentially 48))
>> (thrice (burn-via-pmap 48))
>> (thrice (burn-via-futures 48))
>> (thrice (burn-via-agents 48))
>>
>> This produced:
>>
>> 16 sequential burns: "Elapsed time: 5821.574 msecs"
>> 16 sequential burns: "Elapsed time: 6580.684 msecs"
>> 16 sequential burns: "Elapsed time: 6648.013 msecs"
>> 16 burns via pmap: "Elapsed time: 5953.194 msecs"
>> 16 burns via pmap: "Elapsed time: 7517.196 msecs"
>> 16 burns via pmap: "Elapsed time: 7380.047 msecs"
>> 16 burns via futures: "Elapsed time: 1168.827 msecs"
>> 16 burns via futures: "Elapsed time: 1068.98 msecs"
>> 16 burns via futures: "Elapsed time: 1048.745 msecs"
>> 16 burns via agents: "Elapsed time: 1041.05 msecs"
>> 16 burns via agents: "Elapsed time: 1030.712 msecs"
>> 16 burns via agents: "Elapsed time: 1041.139 msecs"
>> 48 sequential burns: "Elapsed time: 15909.333 msecs"
>> 48 sequential burns: "Elapsed time: 14825.631 msecs"
>> 48 sequential burns: "Elapsed time: 15232.646 msecs"
>> 48 burns via pmap: "Elapsed time: 13586.897 msecs"
>> 48 burns via pmap: "Elapsed time: 3106.56 msecs"
>> 48 burns via pmap: "Elapsed time: 3041.272 msecs"
>> 48 burns via futures: "Elapsed time: 2968.991 msecs"
>> 48 burns via futures: "Elapsed time: 2895.506 msecs"
>> 48 burns via futures: "Elapsed time: 2818.724 msecs"
>> 48 burns via agents: "Elapsed time: 2802.906 msecs"
>> 48 burns via agents: "Elapsed time: 2754.364 msecs"
>> 48 burns via agents: "Elapsed time: 2743.038 msecs"
>>
>> Looking first at the 16-burn runs, we see that concurrency via pmap is
>> actually generally WORSE than sequential. I cannot understand why this
>> should be the case. I guess if I were running on a single core I would
>> expect to see a slight loss when going to pmap because there would be some
>> cost for managing the 16 threads that wouldn't be compensated for by actual
>> concurrency. But I'm running on 16 cores and I should be getting a major
>> speedup, not a slowdown. There are only 16 threads, so there shouldn't be a
>> lot of time lost to overhead.
>>
>> Also interesting, in this case when I start the processes using futures or
>> agents I DO see a speedup. It's on the order of 6x-7x, not close to the 16x
>> that I would hope for, but at least it's a speedup. Why is this so different
>> from the case with pmap? (Recall that my pmap-based method DID produce about
>> the same speedup as my other methods when doing only 4 burns.)
>>
>> For the calls with 48 burns we again see nearly the expected, reasonably
>> good pattern with all concurrent calls performing nearly equivalently (I
>> suppose that the steady improvement over all of the calls is again some kind
>> of JVM optimization), with a speedup in the concurrent calls over the
>> sequential calls in the neighborhood of 5x-6x. Again, not the ~16x that I
>> might hope for, but at least it's in the right direction. The very first of
>> the pmap calls with 48 burns is an anomaly, with only a slight improvement
>> over the sequential calls, so I suppose that's another small mystery.
>>
>> The big mystery so far, however, is in the case of the 16 burns via pmap,
>> which is bizarrely slow on this 16-core machine.
>>
>> Next I tried the same thing on a 48 core machine (
>> http://fly.hampshire.edu/ganglia/?p=2&c=Rocks-Cluster&h=compute-4-2.local).
>> Here I got:
>>
>> 4 sequential burns: "Elapsed time: 3062.871 msecs"
>> 4 sequential burns: "Elapsed time: 2249.048 msecs"
>> 4 sequential burns: "Elapsed time: 2417.677 msecs"
>> 4 burns via pmap: "Elapsed time: 705.968 msecs"
>> 4 burns via pmap: "Elapsed time: 679.865 msecs"
>> 4 burns via pmap: "Elapsed time: 685.017 msecs"
>> 4 burns via futures: "Elapsed time: 687.097 msecs"
>> 4 burns via futures: "Elapsed time: 636.543 msecs"
>> 4 burns via futures: "Elapsed time: 660.116 msecs"
>> 4 burns via agents: "Elapsed time: 708.163 msecs"
>> 4 burns via agents: "Elapsed time: 709.433 msecs"
>> 4 burns via agents: "Elapsed time: 713.536 msecs"
>> 16 sequential burns: "Elapsed time: 8065.446 msecs"
>> 16 sequential burns: "Elapsed time: 8069.239 msecs"
>> 16 sequential burns: "Elapsed time: 8102.791 msecs"
>> 16 burns via pmap: "Elapsed time: 11288.757 msecs"
>> 16 burns via pmap: "Elapsed time: 12182.506 msecs"
>> 16 burns via pmap: "Elapsed time: 14609.397 msecs"
>> 16 burns via futures: "Elapsed time: 2519.603 msecs"
>> 16 burns via futures: "Elapsed time: 2436.699 msecs"
>> 16 burns via futures: "Elapsed time: 2776.869 msecs"
>> 16 burns via agents: "Elapsed time: 2178.028 msecs"
>> 16 burns via agents: "Elapsed time: 2871.38 msecs"
>> 16 burns via agents: "Elapsed time: 2244.687 msecs"
>> 48 sequential burns: "Elapsed time: 24118.218 msecs"
>> 48 sequential burns: "Elapsed time: 24096.667 msecs"
>> 48 sequential burns: "Elapsed time: 24057.327 msecs"
>> 48 burns via pmap: "Elapsed time: 10369.224 msecs"
>> 48 burns via pmap: "Elapsed time: 6837.071 msecs"
>> 48 burns via pmap: "Elapsed time: 4163.926 msecs"
>> 48 burns via futures: "Elapsed time: 3980.298 msecs"
>> 48 burns via futures: "Elapsed time: 4066.35 msecs"
>> 48 burns via futures: "Elapsed time: 4068.199 msecs"
>> 48 burns via agents: "Elapsed time: 4012.069 msecs"
>> 48 burns via agents: "Elapsed time: 4052.759 msecs"
>> 48 burns via agents: "Elapsed time: 4085.018 msecs"
>>
>> Essentially this is the same picture that I got on the 16-core machine:
>> decent (but less than I would like -- only something like 3x-4x) speedups
>> with most concurrent methods in most cases but a bizarre anomaly with 16
>> burns started with pmap, which is again considerably slower than the
>> sequential runs. Why should this be? When I run only 4 burns or a full 48
>> burns the pmap method performs decently (that is, at least things get faster
>> than the sequential calls), but with 16 burns something very odd happens.
>>
>> Finally, I ran the same thing on my MacBook Pro 3.06 GHz Intel Core 2 Duo,
>> Mac OS X 10.6.4, with Clojure 1.2.0-master-SNAPSHOT under
>> Eclipse/Counterclockwise, with a bunch of applications running, so probably
>> this is acting more or less like a single core machine, and got:
>>
>> 4 sequential burns: "Elapsed time: 3487.224 msecs"
>> 4 sequential burns: "Elapsed time: 2327.569 msecs"
>> 4 sequential burns: "Elapsed time: 2137.697 msecs"
>> 4 burns via pmap: "Elapsed time: 12478.725 msecs"
>> 4 burns via pmap: "Elapsed time: 12815.75 msecs"
>> 4 burns via pmap: "Elapsed time: 8464.909 msecs"
>> 4 burns via futures: "Elapsed time: 11494.17 msecs"
>> 4 burns via futures: "Elapsed time: 12365.537 msecs"
>> 4 burns via futures: "Elapsed time: 12098.571 msecs"
>> 4 burns via agents: "Elapsed time: 10361.749 msecs"
>> 4 burns via agents: "Elapsed time: 12458.174 msecs"
>> 4 burns via agents: "Elapsed time: 9016.093 msecs"
>> 16 sequential burns: "Elapsed time: 8706.674 msecs"
>> 16 sequential burns: "Elapsed time: 8748.006 msecs"
>> 16 sequential burns: "Elapsed time: 8729.54 msecs"
>> 16 burns via pmap: "Elapsed time: 46022.281 msecs"
>> 16 burns via pmap: "Elapsed time: 44845.725 msecs"
>> 16 burns via pmap: "Elapsed time: 45393.156 msecs"
>> 16 burns via futures: "Elapsed time: 52822.863 msecs"
>> 16 burns via futures: "Elapsed time: 50647.708 msecs"
>> 16 burns via futures: "Elapsed time: 50337.916 msecs"
>> 16 burns via agents: "Elapsed time: 48615.905 msecs"
>> 16 burns via agents: "Elapsed time: 56703.723 msecs"
>> 16 burns via agents: "Elapsed time: 69765.913 msecs"
>> 48 sequential burns: "Elapsed time: 38885.616 msecs"
>> 48 sequential burns: "Elapsed time: 38651.573 msecs"
>> 48 sequential burns: "Elapsed time: 36669.02 msecs"
>> 48 burns via pmap: "Elapsed time: 169108.022 msecs"
>> 48 burns via pmap: "Elapsed time: 176656.455 msecs"
>> 48 burns via pmap: "Elapsed time: 182119.986 msecs"
>> 48 burns via futures: "Elapsed time: 176764.722 msecs"
>> 48 burns via futures: "Elapsed time: 169257.577 msecs"
>> 48 burns via futures: "Elapsed time: 157205.693 msecs"
>> 48 burns via agents: "Elapsed time: 140618.333 msecs"
>> 48 burns via agents: "Elapsed time: 137992.773 msecs"
>> 48 burns via agents: "Elapsed time: 143153.696 msecs"
>>
>> Here we have a very depressing picture. Although I wouldn't expect to get
>> any speedup from concurrency the concurrency-related slowdowns have now
>> spread to all of my concurrency-starting methods with all numbers of burns.
>> It is way way way worse to be using the concurrency methods than the
>> straightforward sequential method in every circumstance. Again, I understand
>> why one should expect a small loss in a case like this, but these are huge
>> losses and the number of threads that have to be coordinated (with no
>> shared) is quite small -- just 4-48.
>>
>> My guess is that all of this is stemming from some confusion on my part
>> about how I should be starting and managing concurrent processes, and my
>> greatest hope is that one of you will show me an alternative to my
>> burn-via-* functions that provides a speedup nearly linear with the number
>> of cores and only a negligible loss when there's only one core available...
>>
>> But any help of any kind would be appreciated.
>>
>> Thanks,
>>
>> -Lee
>>
>> --
>> Lee Spector, Professor of Computer Science
>> School of Cognitive Science, Hampshire College
>> 893 West Street, Amherst, MA 01002-3359
>> lspec...@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/
>>
>> --
>> 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<clojure%2bunsubscr...@googlegroups.com>
>> For more options, visit this group at
>> http://groups.google.com/group/clojure?hl=en
>
>
> --
> 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<clojure%2bunsubscr...@googlegroups.com>
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
>
--
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
