title: Understanding the work stealing algorithm
body: <p>I have read a lot on this algorithem. When explaining this algorithem , the words :
  <a href="https://stackoverflow.com/questions/9081382/work-stealing-algorithm">work stealing algorithm [closed]</a></p>
  
  <blockquote>
    <p>Those forked subtasks can recursively
    create more subtasks themself and thus fill up the working queues of
    the parallely working threads. If one thread finished and has nothing
    more to do, he can "steal" the work from the queue of another thread.</p>
  </blockquote>
  
  <p>I understand that this algorithem is new and does not exists in Executors.newCachedThreadPool / Executors.newFixedThreadPool
  <BR>I would like to see that one thread handles only work from it's queue.
  I created a small program that creates threads recursively. see below.
  How can I see that it doesn't use the work stealing algorithem ?</p>
  
  <pre><code>public static void main(String[] args) throws Exception {
      int[] myArray = IntStream.rangeClosed(1, 10).toArray();
  
          ExecutorService executorService = Executors.newFixedThreadPool(5);
          CustomCallable customCallable = new CustomCallable(myArray, executorService);
          customCallable.call();
          executorService.shutdownNow();
  }
  public class CustomCallable implements Callable&lt;Integer&gt; {
      private static final int THRESHOLD = 2;
      private int[] array;
      private ExecutorService executorService;
  
      public CustomCallable(int[] array, ExecutorService executorService) {
          this.array = array;
          this.executorService = executorService;
      }
  
      @Override
      public Integer call() throws Exception {
          int sum = 0;
          log.debug(" start [{}] ", Arrays.toString(array) );
          if (array.length &gt; THRESHOLD) {
              List&lt;Callable&lt;Integer&gt;&gt; dividedTasks = createSubtasks(array, executorService);
              sum = executorService.invokeAll(dividedTasks).stream()
                      .mapToInt(feature -&gt; {
                          try {
                              return feature.get();
                          } catch (InterruptedException e) {
                              e.printStackTrace();
                          } catch (ExecutionException e) {
                              e.printStackTrace();
                          }
                          return 0;
                      })
                      .sum();
         } else {
              sum = processing(array);
          }
          log.debug(" sum[{}]={} ", Arrays.toString(array) ,sum);
          return sum;
      }
  
      private List&lt;Callable&lt;Integer&gt;&gt; createSubtasks(int[] array, ExecutorService executorService) {
          int[] arr1 = Arrays.copyOfRange(array, 0, array.length / 2);
          int[] arr2 = Arrays.copyOfRange(array, array.length / 2, array.length);
          List&lt;Callable&lt;Integer&gt;&gt; dividedTasks = new ArrayList&lt;&gt;();
          dividedTasks.add(new CustomCallable(arr1, executorService));
          dividedTasks.add(new CustomCallable(arr2, executorService));
          return dividedTasks;
      }
  
      private Integer processing(int[] array) {
          int result = Arrays.stream(array)
                  .sum();
          return result;
      }
  }
  </code></pre>
  
  <p>This is the output :</p>
  
  <pre><code>[main] DEBUG com.example.CustomCallable -  start [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]  
  [pool-2-thread-1] DEBUG com.example.CustomCallable -  start [[1, 2, 3, 4, 5]]  
  **[pool-2-thread-3] DEBUG com.example.CustomCallable -  start [[1, 2]]**  
  [pool-2-thread-2] DEBUG com.example.CustomCallable -  start [[6, 7, 8, 9, 10]]  
  [pool-2-thread-4] DEBUG com.example.CustomCallable -  start [[3, 4, 5]]  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  start [[6, 7]]  
  **[pool-2-thread-3] DEBUG com.example.CustomCallable -  sum[[1, 2]]=3**  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  sum[[6, 7]]=13  
  **[pool-2-thread-3] DEBUG com.example.CustomCallable -  start [[8, 9, 10]]**  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  start [[3]]  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  sum[[3]]=3  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  start [[4, 5]]  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  sum[[4, 5]]=9  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  start [[8]]  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  sum[[8]]=8  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  start [[9, 10]]  
  [pool-2-thread-5] DEBUG com.example.CustomCallable -  sum[[9, 10]]=19  
  **[pool-2-thread-3] DEBUG com.example.CustomCallable -  sum[[8, 9, 10]]=27**  
  [pool-2-thread-4] DEBUG com.example.CustomCallable -  sum[[3, 4, 5]]=12  
  [pool-2-thread-2] DEBUG com.example.CustomCallable -  sum[[6, 7, 8, 9, 10]]=40  
  [pool-2-thread-1] DEBUG com.example.CustomCallable -  sum[[1, 2, 3, 4, 5]]=15  
  [main] DEBUG com.example.CustomCallable -  sum[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]=55 
  </code></pre>
  
  <p><BR>As you can see :
  <BR>main triggered thread-2 and thread-1
  <BR>thread-1 triggered <strong>thread-3(calculating [1,2])</strong> and thread-4
  <BR>thread-2 triggered thread-5 and <strong>thread-3(calculating [1,2] after finishing calculating[8,9,10])</strong><br>
  As I understand thread-3 handles work from thread-1 and thread-2.<br>
  Looks like thread-3 <em>work steal</em><br>
  If I change it to </p>
  
  <pre><code> ExecutorService executorService = Executors.newWorkStealingPool();
  </code></pre>
  
  <p>which supports workstealing algorithem, what do I see differently ?</p>
  
  <pre><code>[main] DEBUG com.example.CustomCallable -  start [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]  
  [ForkJoinPool-1-worker-1] DEBUG com.example.CustomCallable -  start [[1, 2, 3, 4, 5]]  
  [ForkJoinPool-1-worker-2] DEBUG com.example.CustomCallable -  start [[1, 2]]  
  [ForkJoinPool-1-worker-2] DEBUG com.example.CustomCallable -  sum[[1, 2]]=3  
  [ForkJoinPool-1-worker-2] DEBUG com.example.CustomCallable -  start [[3, 4, 5]]  
  [ForkJoinPool-1-worker-3] DEBUG com.example.CustomCallable -  start [[6, 7, 8, 9, 10]]  
  [ForkJoinPool-1-worker-0] DEBUG com.example.CustomCallable -  start [[6, 7]]  
  [ForkJoinPool-1-worker-0] DEBUG com.example.CustomCallable -  sum[[6, 7]]=13  
  [ForkJoinPool-1-worker-0] DEBUG com.example.CustomCallable -  start [[8, 9, 10]]  
  **[ForkJoinPool-1-worker-4] DEBUG com.example.CustomCallable -  start [[3]]**  
  **[ForkJoinPool-1-worker-4] DEBUG com.example.CustomCallable -  sum[[3]]=3**  
  [ForkJoinPool-1-worker-4] DEBUG com.example.CustomCallable -  start [[4, 5]]  
  [ForkJoinPool-1-worker-4] DEBUG com.example.CustomCallable -  sum[[4, 5]]=9  
  **[ForkJoinPool-1-worker-4] DEBUG com.example.CustomCallable -  start [[8]]**  
  **[ForkJoinPool-1-worker-4] DEBUG com.example.CustomCallable -  sum[[8]]=8**  
  [ForkJoinPool-1-worker-4] DEBUG com.example.CustomCallable -  start [[9, 10]]  
  [ForkJoinPool-1-worker-4] DEBUG com.example.CustomCallable -  sum[[9, 10]]=19  
  [ForkJoinPool-1-worker-2] DEBUG com.example.CustomCallable -  sum[[3, 4, 5]]=12  
  [ForkJoinPool-1-worker-0] DEBUG com.example.CustomCallable -  sum[[8, 9, 10]]=27  
  [ForkJoinPool-1-worker-1] DEBUG com.example.CustomCallable -  sum[[1, 2, 3, 4, 5]]=15  
  [ForkJoinPool-1-worker-3] DEBUG com.example.CustomCallable -  sum[[6, 7, 8, 9, 10]]=40  
  [main] DEBUG com.example.CustomCallable -  sum[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]=55
  </code></pre>
  
  <p><BR>As you can see we have 5 workers and worker-4 handles work triggered by worker-3 as well as worker-1. In what way this is different from the previous execution ?</p>
  
  <p>You can download the code from <a href="https://github.com/idaamit/trigger-threads-examples/tree/master/recursive-opening-threads" rel="nofollow noreferrer">github</a></p>