Presentation 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.

Speakers


PDF: slides.pdf

Slides

ForkJoin

ForkJoin @Sander_Mak

About

About Coding at ( ) Writing Blog @ branchandbound.net Speaking

Agenda

Agenda ForkJoin Setting the scene ForkJoin API & Patterns Comparisons & Future break Akka Introduction Actors Async IO

Problem?

Problem?

Problem?

Problem?

Problem?

Problem?

Problem?

Problem?

Problem?

Problem? Architectural mismatch

Problem?

Problem? So let the compiler/runtime solve it!

Problem?

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?

Problem? So let the compiler/runtime solve it! Unfortunately not in , but feasible in pure functional languages like

First attempt

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); }

Demo

Threads

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

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

ForkJoin Introducing: ForkJoinPool java.util.concurrent.ForkJoinTask java.util.concurrent. ForkJoinTask RecursiveAction RecursiveTask ForkJoinPool: void T execute (ForkJoinTask) invoke (ForkJoinTask)

ForkJoin

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

Demo

ForkJoin

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

ForkJoinPool Implements ExecutorService Autosize workers (overridable) Work queue per worker Work-stealing between queues

Work stealing

Work stealing ForkJoinPool

Work stealing

Work stealing ForkJoinPool 1

Work stealing

Work stealing ForkJoinPool 2 3 1

Work stealing

Work stealing ForkJoinPool st ol en 3 2

Work stealing

Work stealing ForkJoinPool 4 5 3 6 7 2

Work stealing

Work stealing ForkJoinPool 4 sto len 5 7 6

Work stealing

Work stealing ForkJoinPool 4 8 9 5 10 11 12 13 sto len 7 6

Scalability

Scalability ForkJoinPool

Patterns

Patterns #1 Problem structure Acyclic CPU Bound - I/O upfront - No webcrawlers please...

Patterns

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

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

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

Demo 2.797.245 world cities (Maxmind.com) Demo 1: simple search Demo 2: lat/long bounded