Clojure

pmap level of parallelism inconsistent for chunked vs non-chunked input

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: Release 1.1, Release 1.2, Release 1.3, Release 1.4
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test

Description

The code of pmap creates futures for the set of map operations it needs to perform with (map #(future %) coll), then acts on that sequence in a fashion obviously intended to keep only #CPUs+2 unfinished futures realized at any given time. It works exactly this way for non-chunked input seqs, but when pmap is passed a chunked seq, the seq of futures also becomes chunked. This causes an arbitrary number of futures to be realized as the #CPUs+2 window and chunk-size window interact.

The doc-string for pmap doesn't promise any particular level of parallelism, but I think the inconsistent parallelism for chunked vs non-chunked input comprises a bug.

Activity

Hide
Stuart Halloway added a comment -

Next person to take a deep look at pmap should probably also think through fork/join.

Show
Stuart Halloway added a comment - Next person to take a deep look at pmap should probably also think through fork/join.
Hide
Jim Blomo added a comment -

fork/join is a Java 7 feature. Would a proposed patch need to be able to fall back to Java 5 features?

Show
Jim Blomo added a comment - fork/join is a Java 7 feature. Would a proposed patch need to be able to fall back to Java 5 features?
Hide
Andy Fingerhut added a comment -

Clojure/core folks can say more authoritatively, but I believe with the recent reduce enhancements that rely on jsr166 code, Clojure 1.5 will most likely require Java 6 or later, and Java 5 will no longer be supported.

Show
Andy Fingerhut added a comment - Clojure/core folks can say more authoritatively, but I believe with the recent reduce enhancements that rely on jsr166 code, Clojure 1.5 will most likely require Java 6 or later, and Java 5 will no longer be supported.
Hide
Jim Blomo added a comment -

Spinning up more threads than CPU cores is not a good idea when the work is CPU bound. Currently (1.4) pmap uses an unbounded thread pool, so chunked sequences will create more threads than intended. The least invasive change is to use a fixed sized thread pool (ForkJoinPool being one example). pmap is differentiated from core.reducers by the fact that it is lazy. This implies a one-at-a-time ThreadPool.submit model, instead of the recursive fork/join model. Tradeoffs include:

Enforce look-ahead even on chunked sequences:

  • + no threadPool changes
  • - working against chunking, which is presumably being used for a reason

Move to a fixed size thread pool:

  • + reduce contention for cpu-bound functions on chunked sequences
  • - increase total realization time for io-bound functions

Use ForkJoinPool for fixed thread pool (instead of newFixedThreadPool):

  • + automatic and dynamic parallelism
  • - more complex setup (picking Java 6 vs 7 implementation, sharing pool with core.reducers)

I think using a traditional fixed size thread pool is the right option. Most of the time all of pmap's results will be realized, so I don't think it's worth saving work by being strict about the look-ahead size. This is also the decision map has made. Since we're not using ForkJoin's main strength (recursive work queuing), I don't think it is worth setting it up in clojure.core.

I'll use Agent/pooledExecutor as the fixed size thread.

Let me know if I forgot or misunderstood anything.

Show
Jim Blomo added a comment - Spinning up more threads than CPU cores is not a good idea when the work is CPU bound. Currently (1.4) pmap uses an unbounded thread pool, so chunked sequences will create more threads than intended. The least invasive change is to use a fixed sized thread pool (ForkJoinPool being one example). pmap is differentiated from core.reducers by the fact that it is lazy. This implies a one-at-a-time ThreadPool.submit model, instead of the recursive fork/join model. Tradeoffs include: Enforce look-ahead even on chunked sequences:
  • + no threadPool changes
  • - working against chunking, which is presumably being used for a reason
Move to a fixed size thread pool:
  • + reduce contention for cpu-bound functions on chunked sequences
  • - increase total realization time for io-bound functions
Use ForkJoinPool for fixed thread pool (instead of newFixedThreadPool):
  • + automatic and dynamic parallelism
  • - more complex setup (picking Java 6 vs 7 implementation, sharing pool with core.reducers)
I think using a traditional fixed size thread pool is the right option. Most of the time all of pmap's results will be realized, so I don't think it's worth saving work by being strict about the look-ahead size. This is also the decision map has made. Since we're not using ForkJoin's main strength (recursive work queuing), I don't think it is worth setting it up in clojure.core. I'll use Agent/pooledExecutor as the fixed size thread. Let me know if I forgot or misunderstood anything.
Hide
Jim Blomo added a comment -

2012-05-28 pmap-chunking-862.diff uses a fixed size thread pool for pmap functions.

Show
Jim Blomo added a comment - 2012-05-28 pmap-chunking-862.diff uses a fixed size thread pool for pmap functions.
Hide
Andy Fingerhut added a comment -

Patch pmap-chunking-862.diff dated May 28, 2012 no longer applies cleanly after latest commits to Clojure master on Jan 11, 2014. I think the only issue is that the tests added have changed context lines, so should be a quick fix if someone wants to update the patch.

Show
Andy Fingerhut added a comment - Patch pmap-chunking-862.diff dated May 28, 2012 no longer applies cleanly after latest commits to Clojure master on Jan 11, 2014. I think the only issue is that the tests added have changed context lines, so should be a quick fix if someone wants to update the patch.
Hide
Jim Blomo added a comment -

Thanks for the update, Andy. I'll take a crack at it this month.

Show
Jim Blomo added a comment - Thanks for the update, Andy. I'll take a crack at it this month.

People

Vote (0)
Watch (2)

Dates

  • Created:
    Updated: