6
\$\begingroup\$

I am playing around with parallelization in Java and am trying to see how to squeeze out more performance on my multi-core box. My machine has 6 physical cores, 12 with hyperthreading.

However, with this code, I only see performance improvements up to about 3-4 threads, after which the improvements top off and then decline. I would expect performance to decline beyond, let's say, 6-8 threads, but not before. What, if anything, could I do to improve the code, especially with respect to improving speed?

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class AddStuff 
{
   private static final int FIFTY_MILLION = 50000000;

   public static void main(String[] args) 
   {
      final int numRecords = FIFTY_MILLION;
      final int numIterations = 100;
      final int maxThreads = 20;

      double[] numbers = new double[numRecords];
      Random r = new Random(1);

      for (int i = 0; i < numbers.length; i++)
         numbers[i] = r.nextDouble();

      System.out.println(String.format("Running aggregation of %d times %d iterations...", numRecords, numIterations));

      for (int numThreads = 1; numThreads <= maxThreads; numThreads++)
         runExperiment(numRecords, numIterations, numThreads, numbers);

      System.out.println("Done");      
   }

   private static void runExperiment(final int numRecords, final int numIterations, final int numThreads, double[] numbers) {

      long start = System.nanoTime();

      double total = 0;
      for (int iteration = 0; iteration < numIterations; iteration++)
         total +=computeTotal(numbers, numThreads);

      double duration = ((double) (System.nanoTime() - start)) / 1000000000;


      System.out.println(String.format("Threads: %d,  Time: %.4fs,  Total: %f ", numThreads, duration, total));
   }

   private static double computeTotal(double[] numbers, int numThreads) 
   {
      Map<Thread, Calculator> map = new HashMap<Thread, Calculator>();

      for (int i = 0; i < numThreads; i++)
      {
         final Calculator c = new Calculator(numbers, i, numThreads);

         Thread t = new Thread(new Runnable() {
            @Override
            public void run() {
               c.calculate();
            }
         });

         map.put(t, c);
         t.start();
      }

      for (Thread t : map.keySet())
      {
         try {
            t.join();
         } catch (InterruptedException e) {
            e.printStackTrace();
         }
      }

      double total = 0;
      for (Calculator c : map.values())
         total += c.total;

      return total;
   }

   private static class Calculator
   {
      private final double[] numbers;
      private final int start;
      private final int step;
      private volatile double total;

      public Calculator(double[] numbers, int start, int step)
      {
         this.numbers = numbers;
         this.start = start;
         this.step = step;
      }

      void calculate()
      {
         double myTotal = 0;
         int myStep = step;
         for (int i = start; i < numbers.length; i += myStep)
            myTotal += numbers[i];

         total = myTotal;
      }
   }
}

Output:

Running aggregation of 50000000 times 100 iterations...
Threads: 1,  Time: 6.6146s,  Total: 2500279036.887666 
Threads: 2,  Time: 4.1568s,  Total: 2500279036.888092 
Threads: 3,  Time: 3.7190s,  Total: 2500279036.887598 
Threads: 4,  Time: 3.5688s,  Total: 2500279036.887534 
Threads: 5,  Time: 3.5660s,  Total: 2500279036.887787 
Threads: 6,  Time: 4.0408s,  Total: 2500279036.887868 
Threads: 7,  Time: 4.3832s,  Total: 2500279036.887928 
Threads: 8,  Time: 4.4459s,  Total: 2500279036.887951 
Threads: 9,  Time: 4.6616s,  Total: 2500279036.887927 
Threads: 10,  Time: 4.1727s,  Total: 2500279036.887934 
Threads: 11,  Time: 4.5164s,  Total: 2500279036.887979 
Threads: 12,  Time: 5.4117s,  Total: 2500279036.887936 
Threads: 13,  Time: 6.8391s,  Total: 2500279036.887914 
Threads: 14,  Time: 7.1266s,  Total: 2500279036.887913 
Threads: 15,  Time: 7.6294s,  Total: 2500279036.887928 
Threads: 16,  Time: 7.3882s,  Total: 2500279036.887915 
Threads: 17,  Time: 7.7739s,  Total: 2500279036.887911 
Threads: 18,  Time: 7.7469s,  Total: 2500279036.887903 
Threads: 19,  Time: 8.6564s,  Total: 2500279036.887903 
Threads: 20,  Time: 9.2766s,  Total: 2500279036.887903 
Done
\$\endgroup\$
5
  • 2
    \$\begingroup\$ 5 cores for java, 1 core for the OS / IDE. \$\endgroup\$
    – Pimgd
    Oct 28, 2015 at 13:53
  • \$\begingroup\$ @Pimgd In general, fine, but my box is completely idle otherwise. When my program is not running, CPU utilization shows 0-1% pretty consistently. \$\endgroup\$
    – MrCodeMnky
    Oct 28, 2015 at 14:07
  • \$\begingroup\$ And don't forget you have 1 thread whose responsibility is making other threads. \$\endgroup\$
    – Pimgd
    Oct 28, 2015 at 14:14
  • \$\begingroup\$ @MrCodeMnky You're not taking into account context switching. For something computationally heavy like this, hyper-threading has no benefit, as it cannot actually process two instructions at a time on the same "core." \$\endgroup\$ Oct 28, 2015 at 14:15
  • \$\begingroup\$ @EBrown I agree that beyond a certain point the context switching will cause performance to degrade significantly. But I would still expect a near-linear speedup up to 6 cores. Perhaps there is something wrong with the code itself that is causing an unnecessary bottleneck. \$\endgroup\$
    – MrCodeMnky
    Oct 28, 2015 at 14:18

2 Answers 2

4
\$\begingroup\$

You have volatile on your total of the Calculator, but you don't actually read from it until the thread has finished. You could remove it, that way the synchronization on the variable would be removed.


Since one of your threads is responsible for starting new threads, that can be the first thread, saving you 1 more thread:

  for (int i = 1; i < numThreads; i++)
  {
     final Calculator c = new Calculator(numbers, i, numThreads);

     Thread t = new Thread(new Runnable() {
        @Override
        public void run() {
           c.calculate();
        }
     });

     map.put(t, c);
     t.start();
  }
  final Calculator c = new Calculator(numbers, 0, numThreads);
  c.calculate();

  double total = c.total;
  ...

That saves you an extra idle thread. You can only use this in example code like yours though, as real tasks will probably be better off with having a division between "worker threads" and "manager threads".

On that note, maybe you should use a thread pool of sorts - get the overhead of creating threads down.

  void calculate()
  {
     double myTotal = 0;
     int myStep = step;
     for (int i = start; i < numbers.length; i += myStep)
        myTotal += numbers[i];

     total = myTotal;
  }

Here you load step and total into a local for some reason, but not numbers.length. Why not?

\$\endgroup\$
2
  • \$\begingroup\$ Appreciate the comments! The one suggestion that improved performance was removing volatile from total on the Calculator. Made things faster about by 5%. \$\endgroup\$
    – MrCodeMnky
    Oct 28, 2015 at 14:57
  • \$\begingroup\$ "ThreadPool of sorts" ForkJoinPool comes to mind \$\endgroup\$
    – Vogel612
    Oct 28, 2015 at 23:23
5
\$\begingroup\$

Bad order for cache

Your calculation routine is adding up every nth number, where n is the number of threads. This is very bad for cache utilization. If you split the list so that each thread had a contiguous chunk instead, that would be a lot better for cache utilization and make everything faster.

Modified code

I made the following changes to your code:

First, I modified your Calculator class to take a start and end argument instead of a start and step argument:

private static class Calculator
{
    private final double[] numbers;
    private final int start;
    private final int end;
    private double total;

    public Calculator(double[] numbers, int start, int end)
    {
        this.numbers = numbers;
        this.start = start;
        this.end = end;
    }

    void calculate()
    {
        double myTotal = 0;
        for (int i = start; i < end; i++)
            myTotal += numbers[i];

        total = myTotal;
    }
}

Then I modified the computeTotal() function to split the numbers into evenly sized contiguous chunks:

private static double computeTotal(double[] numbers, int numThreads)
{
    Map<Thread, Calculator> map = new HashMap<Thread, Calculator>();
    int chunkSize = (numbers.length / numThreads);

    for (int i = 0; i < numThreads; i++)
    {
        int start = i * chunkSize;
        int end   = (i == numThreads - 1) ? numbers.length :
                                            (i+1) * chunkSize;
        final Calculator c = new Calculator(numbers, start, end);

The results

These are the results on my machine before the change (4 cores, no hyperthreads, only 10 million doubles instead of 50 million):

Running aggregation of 10000000 times 100 iterations...
Threads: 1,  Time: 1.2901s,  Total: 499890086.941070
Threads: 2,  Time: 0.7689s,  Total: 499890086.941129
Threads: 3,  Time: 0.6693s,  Total: 499890086.941116
Threads: 4,  Time: 0.6586s,  Total: 499890086.941095
Threads: 5,  Time: 1.1863s,  Total: 499890086.941099
Threads: 6,  Time: 1.1560s,  Total: 499890086.941105
Threads: 7,  Time: 1.1590s,  Total: 499890086.941105
Threads: 8,  Time: 1.1804s,  Total: 499890086.941100
Threads: 9,  Time: 1.6860s,  Total: 499890086.941106
Threads: 10,  Time: 1.7471s,  Total: 499890086.941105

And these are the results after the cache friendly modifications:

Running aggregation of 10000000 times 100 iterations...
Threads: 1,  Time: 1.2738s,  Total: 499890086.941070
Threads: 2,  Time: 0.6965s,  Total: 499890086.941110
Threads: 3,  Time: 0.4985s,  Total: 499890086.941099
Threads: 4,  Time: 0.4814s,  Total: 499890086.941099
Threads: 5,  Time: 0.6425s,  Total: 499890086.941099
Threads: 6,  Time: 0.5468s,  Total: 499890086.941105
Threads: 7,  Time: 0.5108s,  Total: 499890086.941106
Threads: 8,  Time: 0.5244s,  Total: 499890086.941099
Threads: 9,  Time: 0.5870s,  Total: 499890086.941105
Threads: 10,  Time: 0.5293s,  Total: 499890086.941099
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.