Search in:

You're watching a preview of this video, click the button on the left to puchase the full version from JavaPolis'06.

0:00:00 / 0:52:49

- Force Flash slides
- Force Flash video
- Playback speed
- Slow
- Normal
- Fast
- Cheetha
- View Mode
- Slides And Video
- Slides Focused
- Slides Maxed
- Video Focused
- Video Maxed

- About
- Downloads
- Related

Fork/Join is no silver bullet when it comes to scaling computation, and it is somewhat low-level. Therefore we will also look at how it compares to other techniques such as Map-Reduce and of course good-old threads.

Published on May 7th 2012

- 1.587
- 20
- 0
- 5
- 0

- ForkJoin @Sander_Mak
- About Coding at ( ) Writing Blog @ branchandbound.net Speaking
- Agenda ForkJoin Setting the scene ForkJoin API & Patterns Comparisons & Future break Akka Introduction Actors Async IO
- Problem?
- Problem?
- Problem?
- Problem?
- Problem? Architectural mismatch
- Problem? So let the compiler/runtime solve it!
- Problem? So let the compiler/runtime solve it! n < 2 n if (n < 2) { return n; } else { return fib(n - 1) + fib(n - 2); }
- Problem? So let the compiler/runtime solve it! Unfortunately not in , but feasible in pure functional languages like
- First attempt public static int fib(final int n) { if (n < 2) { return n; } else { final int[] t1 = {0}, t2 = {0}; Thread thread1 = new Thread() { public void run() { t1[0] = fib(n - 1); } }; Thread thread2 = new Thread() { public void run() { t2[0] = fib(n - 2); } }; thread1.start(); thread2.start(); thread1.join(); thread2.join(); return t1[0] + t2[0]; } } if (n < 2) { return n; } else { return fib(n - 1) + fib(n - 2); }
- Threads Threads are mostly waiting Improve with threadpooling but not by much starvation What if we sum in a new thread? synchronization visibility issues (Java Memory Model)
- ForkJoin Fork: Recursively decompose large task into subtasks Result = 3 Fib(4) Join: Await results of recursive tasks and combine Fib(1) Fib(3) Fib(2) Fib(2) Fib(1) Fib(1) Fib(0) Fib(0)
- ForkJoin Introducing: ForkJoinPool java.util.concurrent.ForkJoinTask java.util.concurrent. ForkJoinTask RecursiveAction RecursiveTask ForkJoinPool: void T execute (ForkJoinTask<?>) invoke (ForkJoinTask<T>)
- ForkJoin compute(problem) { if (problem.size < threshold) directlySolve(problem) else { do-forked { leftResult = compute(left(problem)) rightResult = compute(right(problem)) } join(leftResult, rightResult) return combine(leftResult, rightResult) } } Keep overhead down: sequential cutoff
- ForkJoin compute(problem) { if (problem.size < threshold) directlySolve(problem) else { do-forked { leftResult = compute(left(problem)) rightResult = compute(right(problem)) } join(leftResult, rightResult) return combine(leftResult, rightResult) } } Keep overhead down: sequential cutoff
- ForkJoinPool Implements ExecutorService Autosize workers (overridable) Work queue per worker Work-stealing between queues
- Work stealing ForkJoinPool
- Work stealing ForkJoinPool 1
- Work stealing ForkJoinPool 2 3 1
- Work stealing ForkJoinPool st ol en 3 2
- Work stealing ForkJoinPool 4 5 3 6 7 2
- Work stealing ForkJoinPool 4 sto len 5 7 6
- Work stealing ForkJoinPool 4 8 9 5 10 11 12 13 sto len 7 6
- Scalability ForkJoinPool
- Patterns #1 Problem structure Acyclic CPU Bound - I/O upfront - No webcrawlers please...
- Patterns #2 Sequential cutoff Guidelines > 100 and < 10.000 `basic computational steps' Experiment and tune Never lock/synchronize compute(problem) { if (problem.size < threshold) directlySolve(problem) else { do-forked { ... } join ... } }
- Patterns #3 Fork once, fool me twice Why? Implementation specific Avoids overhead Especially on smallish tasks left.fork() rightResult = right.compute() leftResult = left.join() return leftResult + rightResult left.fork() leftResult = left.join() rightResult = right.compute() return leftResult + rightResult
- Patterns #4 Use convenience methods invoke fjTask.invoke(); // Equivalent to fjTask.fork(); fjTask.join(); // But always tries execution // in current thread first! invokeAll invokeAll(fjTask1, fjTask2, fjTaskN); // Or: invokeAll(collectionOfTasks);
- Demo 2.797.245 world cities (Maxmind.com) Demo 1: simple search Demo 2: lat/long bounded

## Be the first one to add a comment