Want to dive even deeper?

Take the course Java Spring Part: 2 by Bruce E. Hilton and become an expert!
Java Spring Part: 2
by Bruce E. Hilton

Check it out!
You're watching a preview of this video, click the button on the left to puchase the full version from GeeCON.

Fork/Join and Akka (part 1/2)

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
  • 1.606
  • 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

Comments

Be the first one to add a comment