Source
r/Clojure•
joinr

Any idea what's going on with resource scaling and futures in this case?

I have an embarrassingly parallel workload (a bunch of replications of a simulation). I'm currently working on scaling the work out to additional cores and getting surprising speedups, which I've replicated below with a small example.

The naive thought, is that if I can assign one replication (should be an identical workload and runtime) to one core, I should be able to farm out n runs to n cores and get close to a direct speedup (n runs in 1 replication's runtime). That is, if I have N runs, and N cores, and N isolated threads (one for each core), the total batch of runs should take as much time as a single run. In practice, I realize there's still a little coordination overhead and the like (e.g. submitting tasks to run), so maybe something like 1.2x of the runtime. Maintaining result order relative to input order is not important.

(ns paralelltest
  (:require [clojure.core.async :as async]))

(.availableProcessors (Runtime/getRuntime))
;;8

(defn work []
  (zipmap (range 500000) (range 500000)))

(time (dotimes [i 1] (work)))
;; "Elapsed time: 210.021199 msecs"

;;submit one job.
(time (dotimes [i 1] (mapv deref (for [i (range 1)] (future (work))))))
;;"Elapsed time: 210.06426 msecs"

(time (dotimes [i 1] (mapv deref (for [i (range 8)] (future (work))))))
;;"Elapsed time: 735.863726 msecs"

(/ 735.86 210.06)
;;3.503094353994097

;;alternate implementation using core.async threads.
(defn pmap!
  ([n f xs]
   (let [output-chan (async/chan)]
     (async/pipeline-blocking n
                              output-chan
                              (map f)
                              (async/to-chan xs))
     (async/<!! (async/into [] output-chan))))
  ([f xs] (pmap! (.availableProcessors (Runtime/getRuntime)) f  xs)))

(time (dotimes [i 1] (pmap! 8 (fn [_] (work)) (range 8))))
;;"Elapsed time: 768.104268 msecs"

;;an unordered attempt.
(defn work-n [n f]
  (let [result   (promise)
        xs       (atom [])
        _        (add-watch xs :done
                            (fn [_ _ old new]
                              (when (== (count new) n)
                                (deliver result new))))
        submit   (fn [x]
                  (swap! xs conj x))
        workers (dotimes [i n]
                  (future (submit (f))))]
    @result))

(time (dotimes [i 1] (work-n 1 work)))
;;"Elapsed time: 213.370527 msecs"

(time (dotimes [i 1] (work-n 8 work)))
;;"Elapsed time: 798.423232 msecs"

In this intentionally naive case, we aren't do anything requiring coordination (barring compiling the derefd results into a very small vector) so I don't see any obvious contention. Each thread is working on its own task to build a map. Yet we have (better than 8x the runtime), 3.5x the runtime where I would have expected close to 1-1.2x due to vague overhead....

I'm pretty well versed in optimizing single threaded code and digging into visualvm to get all sorts of measures, hotspots, etc. dug out. I am in unfamiliar water here with how to understand

  • if there's something causing contention from visual VM output,
  • whether there's an intrinsic overhead I'm missing in this use case.

My next stop would be to try java interop and directly use an executor service (also new ground for me) to see if that helps. Any insight would be welcome.

For reference, I'm running on 64 bit OpenJDK 1.8_222, 4GB max heap, intel I7 6700HQ @ 2.6 ghz, Windows 10. The phenomenon is reproducible on multiple systems though including Ubuntu. GC usage doesn't go above 1gb, there don't appear to be any collections being triggered in VisualVM.

Thanks in advance for any insight, even more so if you can point me toward a way to get better scaling here.

--Update--

On a 72-core AWS instance with 163gb max heap, the observed scaling for 72 replications is ~14x vs a single-rep batch.

So on the one hand, I'm pending 8x the effort for a ~2.28x speedup on the 8 core laptop, and on the big iron, about 72x the effort for around a 5.14x speedup.

Posted Jan 10, 2020, 10:47 PM UTC · edited

739
zerg000000•

Since the workload in the topic is pure object allocation, but not cpu work. You should not expect any boost from the number of cpu ;-).

Object is allocated in heap instead of stack which is shared across threads, so in nature, this work should be >!synchronised!<. But yes our gentle JVM did something great about multithread object allocation, every thread will preserved some heap memory. If the object allocation is within the size of this preserved heap memory, the object allocation is independent to other threads. the size is calculated as heap size / number of threads, so the speed up will depend on heap size '-Xmx' more than the number of cpu.

(TLAB)

https://blogs.oracle.com/jonthecollector/a-little-thread-privacy-please

3
joinrOP•

Fascinating, and makes sense. Wondering if -XX:TLABSize will help.....that or reducing allocation (which means going mutable) since almost all workloads are going to allocate on jvm, especially in clojure. Or spin up n separate jvm processes. Also consistent with u/jafingerhut conjecture.

Conundrum that going toward allocation heavy immutable style will clip your wings in parallel runs due to effectively becoming i/o bound allocation lol. This would explain many common scenarios where someone goes to use pmap or other parallel means, and ends up running into the common 2-3x improvement wall. Thanks.

resource here indicates that there's supposed to be some automatic TLAB resizing policy happening by default in response to allocation pressure.

2
zerg000000•

resource here

Wow. That article is really useful and detailed explanation of how TLAB works. Thanks a lot!

2
didibus•

Apparently you can disable TLAB with: -XX:-UseTLAB. Would allow you to test the impact it has on performance.

And a link again to one of my favorite series on the JVM: https://shipilev.net/jvm/anatomy-quarks/4-tlab-allocation/

1
jafingerhut•

This is a conjecture of mine, and while I have looked into it somewhat before, I do not have any great suggestions on what experiments to run or measurements to make that would determine if this is true or not. Well, maybe one suggestion.

I suspect that in some cases, the Java allocation of new objects and/or GC can be a common bottleneck between multiple threads. There are multiple GC implementations available in OpenJDK, and some proprietary Java VMs, with many tweakable parameters, so if this conjecture is true, there very well might be particular GC/parameter combinations that avoid this, and I would love to see an in-depth article demonstrating that this conjecture is true or false, with experiments to back it up.

The one suggestion I have that could help confirm this or refute it would be to run the N parallel workloads in N separate processes, each process a separate JVM with its own independent allocator and GC state. If you get closer to an N times speedup with that, versus a single JVM with N threads, that is at least evidence that there is _something_ about a single JVM process that is slowing things down.

2
jafingerhut•

Another possibility: if the code you are running has a memory working set that fits entirely in the L1 caches, and/or perhaps other caches very close to the CPU cores, then it is easier to see that an N times speedup should be possible, because the CPU cores should not interact with each other much, or at all.

However, read/write bandwidth to shared on-chip cache, and off-the-CPU-chip main DRAM of the computer, is a shared resource among all CPU cores in many multi-core CPU architectures, and it is likely in many multi-core CPUs that a process/thread whose limiting speed factor is read/write to DRAM, cannot achieve an N times speedup when using all N cores, because the read/write bandwidth is not designed to be N times faster than what one CPU core can access by itself.

2
joinrOP•

The one suggestion I have that could help confirm this or refute it would be to run the N parallel workloads in N separate processes, each process a separate JVM with its own independent allocator and GC state

Great idea, I'll explore this.

that avoid this, and I would love to see an in-depth article demonstrating that this conjecture is true or false, with experiments to back it up.

I think testing out different GC's and tuning would be a worthwhile effort as well. I may need to go troll Martin Thompson's articles to see if there's anything relevant...

if the code you are running has a memory working set that fits entirely in the L1 caches, and/or perhaps other caches very close to the CPU cores, then it is easier to see that an N times speedup should be possible, because the CPU cores should not interact with each other much, or at all.

The degree to which the workload is mechanically sympathetic to the underlying architecture is also an interesting question I hadn't gotten to, since there could undoubtedly be contention there.

Thanks for the ideas on independent variables to test.

1
jafingerhut•

Re-reading your message, you mention that perhaps GC is never triggering in your runs. Even if no collections are being triggered, though, it is possible that the Java `new` allocation of objects has internal locking when called from many parallel threads. Some JVMs have a "slab allocator" that tries to make allocations more independent between Java threads. It does not eliminate the locking, but makes it happen only when one thread allocates all of a larger "slab"/chunk of memory.

2
joinrOP•

Yea, there's definitely allocation, but not the patterns we see when the GC is under pressure (although I'm not digging very deep...), more like bulk allocation up front (peaking far less than 1/4 of the heap max). I'm running the default GC (parallel I think). Lots of magic probably happening there..

1
jafingerhut•

Another factor that can come into play here, although it might not be for tests as short as the ones measured so far: https://en.wikipedia.org/wiki/Dynamic_frequency_scaling

For long enough periods of heavy compute in a multi-core CPU, modern chips _cannot_ run all cores at the highest clock speed, because it would draw too much power, and/or produce too much heat, that the thermal design of the chip cannot get that heat off the chip surface fast enough if all cores are running at their highest clock speeds for too long.

There are options in modern Linux kernels to disable this feature of a CPU, and fix its clock speed to a constant value, that I have seen mentioned in a paper where someone was doing very carefully controller benchmarks, but I haven't used them myself. On a Mac, the utility program iStat Menus has a Sensors menu that can show the current CPU clocks speed (and many other measurements, e.g. temperatures taken at various places inside your computer) updated every 1 second or so.

I do not think this is the only factor at play here, nor even the dominant one, but wanted to mention it as another variable to consider.

2
jafingerhut•

And one more that I hope someone else can provide good articles/links to if they find more details: https://en.wikipedia.org/wiki/Hyper-threading

Hyper-threading of 2 logical cores into one physical CPU core is quite common on Intel multi-core processors, and I think in some cases, especially if the threads competing for CPU core resources are identical, as they are in these tests, might not be able to achieve a 2x speedup.

2
jafingerhut•

My Mac where I measured the following results has 4 physical CPU cores, determined by looking at iStat Menus output (4 separate temperature measurements, one per CPU core), but the JDK returns 8 from the `(.availableProcessors (Runtime/getRuntime))` call because hyper-threading is enabled, and there are 2 hyper-threads in each physical core.

When I run a numeric-work job with 10000000000 iterations instead of what is in the latest master (10^10), and do (submit numeric-work 1), (submit numeric-work 2), 3, etc, up to 8, I see these speedup values (speedup = # of threads executed, from 1 to 8, divided by the elapsed time):

2 1.95

3 2.79

4 3.72

5 3.71

6 3.73

7 3.75

8 3.79

Speedup is nearly linear up to 4 threads, equal to the number of physical CPU cores, and is pretty much flat after that point, probably because the multiple Java threads running concurrently on a single physical CPU core are competing for CPU core execution pipeline resources.

3
jafingerhut•

By the way, I would guess that numeric-work code, and things like it that do little or no memory access and everything fits in the L1 instruction/data caches, to be a kind of worst case for hyper-threading. Hyper-threading can give 2x speedup for 2 logical cores on a single physical CPU core, I believe, for more typical workloads where there are frequent cache misses, since the other thread can use CPU pipeline resources when one of the two threads is stuck waiting for cache misses.

2
joinrOP•

This is entirely consistent with my "numeric-work" runs, which appear to yield a nearly 4x speedup, vs. the reported 8 cores. I think I'm HT on an Intel I7 as well, will verify that I have 4 physical cores.

1
joinrOP•

Good catch (keep them coming, I'm actually collating these into a sort of lessons learned for broader reference...). I'd read about HT acting squirrely (indeed I'm on an I7, and I think I was testing the large cluster on I5 equivalents...), so definitely relevant.

1
jafingerhut•

u/joinr When you say "for broader reference", are you thinking of writing and publishing some kind of article that summarizes these lessons learned? If so, I'd be happy to review before you publish, and/or provide comments afterwards. I think having something like this, e.g. "Why N times speedup can be challenging to achieve with N processors" would be useful to point people at who are trying out experiments like this, if they are wondering what is going "wrong".

1
joinrOP•

For now, I'm maintaining a working reference for - more or less - expectation management. I actually have known about this phenomenon for years now, I just never dug into it too hard (since I hadn't needed to scale up too much, 2-3x improvement was good enough). I don't think there's a great story in the Clojure community around why this happens. "just drop in pmap for your stuff and everything will scale because immutability and no locks" seems to be kind of the wishful thinking conventional wisdom that floats around a lot (just like "allocations are cheap" vs. "allocations have a small cost you should avoid if you want performance...but clojure idioms encourage allocation...also this becomes even more of a bottleneck when you try to scale your idiomatic code..."). It's sort of like the cold shot of water you get when you learn about Ahmdal's law for the first time and realize that awesome set of uber parallel cores you're sitting won't get you as much bang as you'd wished in practice.

I'm very interested in actually doing some kind of study that examines JVM settings, memory, cores, and other independent variables that contribute to the apparent lack of scaling. Then actually providing solutions to address these issues and improve throughput, or being really straightforward about managing expectations based on observed results.

For the time being, I'm documenting what I learn as I go, in the hopes that I can leverage resources for the aforementioned work problem better, and then maybe spiral that out to lessons learned. I'd certainly be happy to collaborate on something like this (either for formal or informal publication). I do, however, feel extremely out of depth regarding the JVM side of things :)

1
joinrOP•

apropos popped up in my lit review, nice real world benchmarks too (albeit oldish).

1
WikiTextBot•

Dynamic frequency scaling

Dynamic frequency scaling (also known as CPU throttling) is a technique in computer architecture whereby the frequency of a microprocessor can be automatically adjusted "on the fly" depending on the actual needs, to conserve power and reduce the amount of heat generated by the chip. Dynamic frequency scaling helps preserve battery on mobile devices and decrease cooling cost and noise on quiet computing settings, or can be useful as a security measure for overheated systems (e.g. after poor overclocking). Dynamic frequency scaling is used in all ranges of computing systems, ranging from mobile systems to data centers to reduce the power at the times of low workload.

^[ ^PM ^| ^Exclude ^me ^| ^Exclude ^from ^subreddit ^| ^FAQ ^/ ^Information ^| ^Source ^] ^Downvote ^to ^remove ^| ^v0.28

1
joinrOP•

Thanks. I've been down this road with stochastic results due to hardware throttling and power consumption / heat balance (particularly on a laptop), it's definitely something to keep in mind. Even on the AWS stuff, unless you're paying for consistent availability of resources, you're still stuck with potential swings in available cycles. Hell, I learned a long time ago that even having browser tabs open in the background can seriously mess with your profiling/benchmarking results and cause seemingly weird regressions....until you close down your CPU hog in the background :) This (on a single threaded case) had a pretty substantial effect (like 10% speed hit) just for having the browser open at times.

Cracking open some research into "java scalability" has yielded quite a bit of interesting stuff, to include some performance optimizations they've made across Java 9 - 12, specifically targeting scalability. The old 2-4x scalability wall is not an unfamiliar problem in Java it seems (there are slides and presentations going back several years).

1
joinrOP•

u/zerg000000, u/jafingerhut :

After some additional research in light of feedback, I offer these additional experiments:

(ns paralleltest.core
  (:require [clojure.core.async :as async]))

(.availableProcessors (Runtime/getRuntime))
;;8

(defn submit [f n]
  (time (dotimes [i 1] (mapv deref (map (fn [_] (future (f))) (range n))))))

;;Our original massive object allocating workload...
(defn work []
  (zipmap (range 500000) (range 500000)))

;;Lighter allocation workloads...
(defn add-empty []
  (dotimes [i 10000000] (assoc {} :a 2)))

(defn add-map []
  (dotimes [i 10000000] (assoc {:a 2 :b 3} :a 2)))

(submit work 1)
;;"Elapsed time: 213.985636 msecs"
(submit work 8)
;;"Elapsed time: 740.427077 msecs"

;;Lol, wtf, why is this just like 3.73x faster? makes no sense!
(submit add-map 1)
;;"Elapsed time: 56.790034 msecs"

(submit add-map 8)
;;"Elapsed time: 123.411164 msecs"

(submit add-empty 1)
;;"Elapsed time: 199.970449 msecs"
(submit add-empty 8)
;;"Elapsed time: 390.509209 msecs"

(defn numeric-work []
  (dotimes [i 500000000] (unchecked-add 1 1)))

;;I figured we'd have our closes opportunity for
;;a proportional speedup, but nope!  Very strange...
;;since we shouldn't a allocating anything!
(submit numeric-work 1)
"Elapsed time: 156.91116 msecs"
(submit numeric-work 8)
"Elapsed time: 343.235013 msecs"

So whatever contention is happening on the heap seems significantly ameliorated in the face of small object workloads (which squares with the Thread Local Allocation Buffer stuff I've read about). What's very strange is the numeric workload; we have enough space per-core for each non-allocating loop to just go do arithmetic, yet our speedup is walled at about 4x instead of 8x. Very bizarre.

I'm still exploring messing with memory settings, TLAB sizing, switching GC's, and ultimately just running multiple JVM processes. I must admit this is a bit depressing, since the bumper stickers for Clojure include immutability, concurrency, parallelism. The price you're paying (at least naively) is you have to go down into the mine and meet the devil (GC/memory tuning) to actually leverage your processing resources. I mean, you get some benefit out of the box, which is useful, but it's underwhelming. The other option is to avoid allocation, which means going mutable or using object pools :(, or have completely separate heaps (coordinate multiple JVM processes).

Perhaps if the use-case is limited to allocation-less reads and similar operations, you can get more efficient use of resources (although even the simple numeric work example seems unreasonably clipped...).

1
jafingerhut•

I can double check, but I suspect that `(unchecked-add 1 1)` in your numeric-work function is still allocating at least 1 Java Long object on the heap for every iteration, then it immediately becomes garbage. I would recommend a Clojure `loop` that you verify uses primitive arithmetic to do something like sum up the value of the loop variable over all iterations, and return the sum. That should allocate only 1 Java Long object total.

2
joinrOP•

I put up a repo here where I include a loop version, also using primitive-math just to be sure. Look like same performance. I think the original dotimes expands to a loop, which is initialized with a primitive (long), and the unchecked-inc looks to be fully hinted as well (2 primitive local longs), so I think in this little case, we get the same runtime (although unchecked-inc does appear to go through clojure.lang.Numbers which is "usually" a warning sign, maybe not in this case).

Still very weird that this case in particular doesn't scale almost 1:1...

1
zerg000000•

use this for no alloc workload, you will feel the different.

(.availableProcessors (Runtime/getRuntime))
;;8

(defn work []
  (loop [acc 0
         i   1]
    (if (< i 1000000000)
      (recur (unchecked-add acc i) (unchecked-inc i))
      acc)))
;;// Decompiling class: user$work__1322
;;import clojure.lang.*;
;;
;;public final class user$work__1322 extends AFunction
;;{
;;    public static Object invokeStatic() {
;;        long acc = 0L;
;;        long n;
;;        for (long i = 1L; i < 100000000L; ++i, acc = n) {
;;            n = acc + i;
;;        }
;;        return Numbers.num(acc);
;;    }
    
;;    @Override
;;    public Object invoke() {
;;        return invokeStatic();
;;    }
;;}

(time (dotimes [i 1] (work)))
;; "Elapsed time: 671.52061 msecs"
(time (dotimes [i 1] (doall (pmap (fn [_] (work)) (range 8)))))
;; "Elapsed time: 1097.222202 msecs"

(/ (* 8 671.52061) 1097.222202)
;; 4.896150360617658
1
jafingerhut•

1 day

A speedup of 4.9x is a definitely noticeably better than what I saw, but it is also still quite a bit lower than the theoretical 8x speedup one would get if the 8 threads were executing completely independent of each other in their hardware resource usage. With your modified code, I suspect the 2 hyper-threads running on a single physical CPU core (assuming you have a 4 CPU core x 2 hyper-threads/CPU core machine, too) are still sharing enough resources that they are keeping you still fairly far from the desired 8x goal.

Nothing against your code, mind you -- this is most likely well known properties of the hardware at play.

1
didibus•

I read somewhere trying to use -XX:+UseParallelGC and increasing the size of the young generation could help with slowness due to multi-threading alloc.

1
joinrOP•

Fascinating. I thought (from recent research) parallelgc is on by default (at least in the JDK I run, 1.8), I think in later releases they moved to the G1GC....

So many arcane options to mess with :)

1
didibus•

These were the best JVM settings I could find:

$ clj -J-XX:+UseParallelGC -J-Xms2G -J-Xmx2G -J-XX:NewRatio=1 /tmp/paralelltest.clj
"Elapsed time: 730.709075 msecs"
"Elapsed time: 558.40982 msecs"
"Elapsed time: 867.221048 msecs"

I get the following alloc rates:

Starting single-threaded no future
Rate is: 524.583164 MB/sec
Rate is: 862.677548 MB/sec
Rate is: 909.380581 MB/sec
Rate is: 907.705686 MB/sec
Starting single-threaded
Rate is: 903.955616 MB/sec
Rate is: 861.487985 MB/sec
Rate is: 691.929134 MB/sec
Rate is: 698.600416 MB/sec
Starting multi-threaded
Rate is: 787.602328 MB/sec
Rate is: 455.739964 MB/sec
Rate is: 830.445487 MB/sec
Rate is: 252.008673 MB/sec

It does look to be alloc related. The alloc rate is slower in the multi-threaded case. But I'm a bit at lost if something can be done to speed it up.

I also checked, the map returned by (work) is 35MB in size.

1
joinrOP•

Thanks for trying these, I used them and had the same relative performance across the updated benchmarks posted in a repo.

1
didibus•

There also seem to be quite a lot more time spent in GC when I'm running the multi-core version. Which I'm not sure why, since it shouldn't be creating any more garbage. But I'm wondering if what happens is that because it is multi-core, it actually does go way faster, but that means more garbage more quickly, and as a result, more GC, which ends up resulting in an overall slower total time.

1
joinrOP•

Very interesting hypothesis. Perhaps it's churning...

I'm still learning up on memory profiling, I need to get something better than VisualVM on the case (e.g. JFR has a way to look at TLAB contents and other stuff). Do you have a preferred profiler?

1
didibus•

I normally use the clojure-goes-fast profiler or VisualVM.

clojure-goes-fast can profile allocs as well, and it has a alloc-rate-meter that measures allocation rates.

I've also used Zulu's Mission Control in the past: https://www.azul.com/products/zulu-mission-control/

1
didibus•

I actually checked with Zulu Mission Control, and if I understand correctly, it seems the threads almost always were using TLAB, and almost no allocation outside of TLAB was made. But, the multi-core version spent way more time in GC than the latter. And what happens is that the zipmap is like twice as slow, but they all happen in parallel. Haven't tried with the numeric one yet. With this, my best guess would be that throwing more heap space would help.

1