Java Division and rounding

Question

I am looking to divide up an array to process in parallel, but am struggling to split up the array when the size does not divide nicely by the number of threads (since it rounds down). I think I am missing something obvious, but how could I handle this? I can't just round up, since then it would go past the index.

final int NUM_THREADS = Integer.parseInt(args[1]);
int size = g.nodes.length / NUM_THREADS;

for( int i = 0; i < NUM_THREADS; i++ ) {
    Runnable task = new GraphSortRunnable(i*size, (i+1)*size, g.nodes);
    // code continues
 }

Answer 1

Solution

Now, if your goal is 2 chunks, then 13 / 2 = 6.5, but 13 / 6 = 2 + 1/2, so still not good. You have to round up, which is called ceiling.

So, two ways to round up when doing int calculations.

1. Convert to double and use Math.ceiling(): chunkSize = (int)Math.ceiling((double)arraySize / (double)threadCount).

2. Rely of the fact that int / int is always rounded down (truncated), so ceiling(a/b) = truncate((a + b - 1) / b), or in your case: chunkSize = (arraySize + threadCount - 1) / threadCount.

Example

If you had 10 values and 4 threads, the above code would result in chunk size of 3, so your threads would likely get 3,3,3,1.

If you want 3,3,2,2, it gets more complicated. Basically, repeat the chunk size calculation after each chunk is calculated.

• First chunk is ceil(10/4) = 3, so that leaves 7 values and 3 threads.
• Second chunk is ceil(7/3) = 3, so that leaves 4 values and 2 threads.
• Third chunk is ceil(4/2) = 2, so that leaves 2 values and 1 thread.
• Fourth thunk is 2.

CODE

And finally to prove my point, here's the code:

public static void main(String[] args) {
    System.out.println(splitEvenly(10, 2));
    System.out.println(splitEvenly(10, 3));
    System.out.println(splitEvenly(10, 4));
    System.out.println(splitEvenly(500, 13));
    System.out.println(splitEvenly(5, 10));
}
public static List<Integer> splitEvenly(int valueCount, int threadCount) {
    List<Integer> chunks = new ArrayList<>();
    int valuesLeft = valueCount;
    for (int threadsLeft = threadCount; threadsLeft > 0; threadsLeft--) {
        int chunk = (valuesLeft + threadsLeft - 1) / threadsLeft;
        chunks.add(chunk);
        valuesLeft -= chunk;
    }
    return chunks;
}

Output:

[5, 5]
[4, 3, 3]
[3, 3, 2, 2]
[39, 39, 39, 39, 39, 39, 38, 38, 38, 38, 38, 38, 38]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

Answer 2

You can use Java8 stream API. It is simpler than custom splitting:

public class Main {

   public static void main(String[] args) throws Exception {
      Object[] gnode = new Object[10];
      Arrays.stream(gnode).parallel().forEach(Main::processOneNode);
   }

   public static void processOneNode(Object node){
       System.out.println(Thread.currentThread().getName());
   }
}

You can customize it. See Custom thread pool in Java 8 parallel stream

ForkJoinPool forkJoinPool = new ForkJoinPool(20);
forkJoinPool.submit(() -> Arrays.stream(gnode).parallel().forEach(Main::processOneNode)).get();