How is the fork/join framework better than a thread pool?

by

I think the basic misunderstanding is, that the Fork/Join examples do NOT show work stealing but only some kind of standard divide and conquer.

Work stealing would be like this: Worker B has finished his work. He is a kind one, so he looks around and sees Worker A still working very hard. He strolls over and asks: “Hey lad, I could give you a hand.” A replies. “Cool, I have this task of 1000 units. So far I have finished 345 leaving 655. Could you please work on number 673 to 1000, I’ll do the 346 to 672.” B says “OK, let’s start so we can go to the pub earlier.”

You see – the workers must communicate between each other even when they started the real work. This is the missing part in the examples.

The examples on the other hand show only something like “use subcontractors”:

Worker A: “Dang, I have 1000 units of work. Too much for me. I’ll do 500 myself and subcontract 500 to someone else.” This goes on until the big task is broken down into small packets of 10 units each. These will be executed by the available workers. But if one packet is a kind of poison pill and takes considerably longer than other packets — bad luck, the divide phase is over.

The only remaining difference between Fork/Join and splitting the task upfront is this: When splitting upfront you have the work queue full right from start. Example: 1000 units, the threshold is 10, so the queue has 100 entries. These packets are distributed to the threadpool members.

Fork/Join is more complex and tries to keep the number of packets in the queue smaller:

  • Step 1: Put one packet containing (1…1000) into queue
  • Step 2: One worker pops the packet(1…1000) and replaces it with two packets: (1…500) and (501…1000).
  • Step 3: One worker pops packet (500…1000) and pushes (500…750) and (751…1000).
  • Step n: The stack contains these packets: (1..500), (500…750), (750…875)… (991..1000)
  • Step n+1: Packet (991..1000) is popped and executed
  • Step n+2: Packet (981..990) is popped and executed
  • Step n+3: Packet (961..980) is popped and split into (961…970) and (971..980).
    ….

You see: in Fork/Join the queue is smaller (6 in the example) and the “split” and “work” phases are interleaved.

When multiple workers are popping and pushing simultaneously the interactions are not so clear of course.

More Related Contents:

  1. Why does parallel stream with lambda in static initializer cause a deadlock?
  2. Java’s Fork/Join vs ExecutorService – when to use which?
  3. What determines the number of threads a Java ForkJoinPool creates?
  4. I confused with the error when i wrote the code like short a = 1;a=a (short)1; [closed]
  5. Set color of JTable row at runtime
  6. Android with Intent and Custom Listview
  7. Scanner and validating answers like a dictionary in Java
  8. How to use an existing database with an Android application [duplicate]
  9. How do I set the default locale in the JVM?
  10. Convert Date/Time for given Timezone – java
  11. how to read System environment variable in Spring applicationContext
  12. Custom ListView click issue on items in Android
  13. How to allow introducing only digits in jTextField?
  14. Access private field of another object in same class
  15. How to convert float to int with Java
  16. Functional style of Java 8’s Optional.ifPresent and if-not-Present?
  17. Is volatile expensive?
  18. Why implementing a Singleton pattern in Java code is (sometimes) considered an anti-pattern in Java world?
  19. UTF-8 byte[] to String
  20. Could not serialize object cause of HibernateProxy
  21. What is the JSON View class in Jackson and how does it work?
  22. Using JavaMail with TLS
  23. How is Java’s ThreadLocal implemented under the hood?
  24. How do I delete files programmatically on Android?
  25. How to print Two-Dimensional Array like table
  26. Change remote repository credentials (authentication) on Intellij IDEA 14
  27. Creating the ServerSocket in a separate thread?
  28. Java Class.forName() from distant directory
  29. what is Ljava.lang.String;@
  30. Why can’t OffsetDateTime parse ‘2016-08-24T18:38:05.507+0000’ in Java 8

Leave a Comment