Почему этот код не видит значительного прироста производительности, когда я использую несколько потоков на четырехъядерном компьютере?

Question

Я написал некоторый Java-код, чтобы узнать больше об инфраструктуре Executor.

В частности, я написал код для проверки гипотезы Коллатца - это говорит о том, что если вы итеративно применяете следующую функцию к любому целому числу, вы в конечном итоге получите 1:

f(n) = ((n% 2) == 0)?n / 2: 3 * n + 1

CH до сих пор не доказан, и я подумал, что это будет хороший способ узнать об Executor.Каждому потоку присваивается диапазон [l, u] целых чисел для проверки.

В частности, моя программа принимает 3 аргумента - N (число, на которое я хочу проверить CH), RANGESIZE (длина интервалачто поток должен обрабатывать), и NTHREAD, размер пула потоков.

Мой код работает нормально, но я увидел гораздо меньшее ускорение, чем я ожидал - порядка 30%, когда я перешел с 1 на4 темы.

Моя логика заключалась в том, что вычисления полностью связаны с процессором, и каждая подзадача (проверка CH на наличие фиксированного диапазона размеров) занимает примерно одно и то же время.

Есть ли у кого-нибудь идеи относительно того, почему яВы не видите увеличения скорости в 3–4 раза?

Если бы вы могли сообщить о времени выполнения при увеличении количества потоков (вместе с машиной, JVM и ОС), что также было бы здорово.

Особенности

Время выполнения:

java -d64 -server -cp.Collatz 10000000 1000000 4 => 4 потока, занимает 28412 миллисекунд

java -d64 -server -cp.Collatz 10000000 1000000 1 => 1 поток, занимает 38286 миллисекунд

Процессор:

Четырехъядерный процессор Intel Q6600 с тактовой частотой 2,4 ГГц, 4 ГБ.Машина выгружена.

Java:

java версия "1.6.0_15" Java (TM) SE Runtime Environment (сборка 1.6.0_15-b03) Java HotSpot (TM) 64-разрядный серверВМ (сборка 14.1-b02, смешанный режим)

ОС:

Linux quad0 2.6.26-2-amd64 # 1 SMP Вт 9 марта 22:29:32 UTC 2010 x86_64 GNU / Linux

Код: (Я не могу получить код для публикации, я думаю, он слишком длинный для требований SO, источник доступен в Google Docs

import java.math.BigInteger;
import java.util.Date;
import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

class MyRunnable implements Runnable {
  public int lower;
  public int upper;

  MyRunnable(int lower, int upper) {
    this.lower = lower;
    this.upper = upper;
  }

  @Override
  public void run() {
    for (int i = lower ; i <= upper; i++ ) {
      Collatz.check(i);
    }
    System.out.println("(" + lower + "," + upper + ")" );
  }
}


public class Collatz {

  public static boolean check( BigInteger X ) {
    if (X.equals( BigInteger.ONE ) ) {
      return true;
    } else if ( X.getLowestSetBit() == 1 ) { 
      // odd
      BigInteger Y = (new BigInteger("3")).multiply(X).add(BigInteger.ONE);
      return check(Y);
    } else {
      BigInteger Z = X.shiftRight(1); // fast divide by 2
      return check(Z);
    }
  }

  public static boolean check( int x ) {
    BigInteger X = new BigInteger( new Integer(x).toString() );
    return check(X);
  }

  static int N = 10000000;
  static int RANGESIZE = 1000000;
  static int NTHREADS = 4;

  static void parseArgs( String [] args ) {

    if ( args.length >= 1 ) {
      N = Integer.parseInt(args[0]);
    }
    if ( args.length >= 2 ) {
      RANGESIZE = Integer.parseInt(args[1]);
    }
    if ( args.length >= 3 ) {
      NTHREADS = Integer.parseInt(args[2]);
    }
  }

  public static void maintest(String [] args ) {
    System.out.println("check(1): " + check(1));
    System.out.println("check(3): " + check(3));
    System.out.println("check(8): " + check(8));
    parseArgs(args);
  }

  public static void main(String [] args) {
    long lDateTime = new Date().getTime();
    parseArgs( args );
    List<Thread> threads = new ArrayList<Thread>();
    ExecutorService executor = Executors.newFixedThreadPool( NTHREADS );
    for( int i = 0 ; i < (N/RANGESIZE); i++) {
      Runnable worker = new MyRunnable( i*RANGESIZE+1, (i+1)*RANGESIZE );
      executor.execute( worker );
    }
    executor.shutdown();
    while (!executor.isTerminated() ) {
    }
    System.out.println("Finished all threads");
    long fDateTime = new Date().getTime();
    System.out.println("time in milliseconds for checking to " + N + " is " + 
                            (fDateTime - lDateTime )  + 
                            " (" + N/(fDateTime - lDateTime ) + " per ms)" );
  }
}

Answer 1

Ожидание при занятости может быть проблемой:

while (!executor.isTerminated() ) { 
} 

Вместо него можно использовать awaitTermination():

while (!executor.awaitTermination(1, TimeUnit.SECONDS)) {}

Answer 2

Как ответил @axtavt, ожидание может быть проблемой. Вы должны сначала это исправить, так как это часть ответа, но не все. Это не поможет в вашем случае (на Q6600), потому что он кажется узким местом на 2 ядрах по какой-то причине, так что другой доступен для цикла занятости и поэтому нет никакого очевидного замедления, но на моем Core i5 это заметно ускоряет 4-х поточную версию.

Я подозреваю, что в случае Q6600 ваше конкретное приложение ограничено объемом доступного общего кэша или чем-то еще, специфичным для архитектуры этого ЦП. Q6600 имеет два 4-мегабайтных кэша L2, что означает, что процессоры используют их совместно, и кеш-памяти третьего уровня нет. На моем ядре i5 каждый ЦП имеет выделенный кэш L2 (256 КБ, а затем более широкий 8 МБ общий кэш L3. 256 КБ на каждый ЦП может иметь значение ... в противном случае это делает другая архитектура).

Вот сравнение Q6600 с вашим Collatz.java и Core i5 750.

На моем рабочем ПК, который также является Q6600 @ 2,4 ГГц, как ваш, но с 6 ГБ ОЗУ, Windows 7 64-битной и JDK 1.6.0_21 * (64-битной), вот некоторые основные результаты:

• 10000000 500000 1 (среднее из трех прогонов): 36982 мс
• 10000000 500000 4 (среднее из трех прогонов): 21252 мс

Конечно, быстрее - но не завершается в четверть времени, как вы ожидаете, или даже наполовину ... (хотя это примерно чуть больше половины, об этом чуть позже). Обратите внимание, что в моем случае я сократил размер рабочих блоков вдвое, а максимальная куча по умолчанию составляет 1500 м.

Дома у меня на Core i5 750 (4 ядра без гиперпоточности), 4 ГБ ОЗУ, 64-битная Windows 7, jdk 1.6.0_22 (64-битная):

• 10000000 500000 1 (среднее из 3 прогонов) 32677 мс
• 10000000 500000 4 (в среднем 3 пробега) 8825 мс
• 10000000 500000 4 (среднее из 3 запусков) 11475 мс (без исправления ожидания занятости, для справки)

версия с 4 потоками занимает 27% времени, которое занимает версия с 1 потоком, когда цикл занятости занят. Намного лучше. Очевидно, что код может эффективно использовать 4 ядра ...

• ПРИМЕЧАНИЕ. Java 1.6.0_18 и более поздние изменили настройки кучи по умолчанию, поэтому размер кучи по умолчанию на моем рабочем компьютере составляет почти 1500 м, а на домашнем ПК - около 1000 м.

Возможно, вы захотите увеличить кучу по умолчанию, на случай, если произойдет сборка мусора и немного замедлит работу вашей 4-поточной версии. Это может помочь, а может и нет.

По крайней мере, в вашем примере, есть вероятность, что ваш больший размер рабочей единицы слегка искажает ваши результаты ... вдвое это может помочь вам приблизиться по крайней мере к 2-кратной скорости, так как 4 потока будут заняты в течение большей части время. Я не думаю, что Q6600 будет лучше справляться с этой конкретной задачей ... будь то кеш или какая-то другая внутренняя архитектура.

Во всех случаях я просто запускаю "java Collatz 10000000 500000 X", где x = число указанных потоков.

Единственные изменения, которые я сделал в вашем java-файле, заключались в том, чтобы сделать один из отпечатков в распечатке, чтобы было меньше разрывов строк для моих прогонов с 500000 на единицу работы, чтобы я мог видеть больше результатов в консоли одновременно, и я отменил цикл ожидания занятости, который важен для i5 750, но не имеет значения для Q6600.

Answer 3

Вы используете BigInteger.Он занимает много места в реестре.Скорее всего, на уровне компилятора у вас есть разлив регистров, что делает ваш процесс связанным с памятью.

Также обратите внимание, что когда вы синхронизируете свои результаты, вы не учитываете дополнительное время, затрачиваемое JVM для выделения потокови работа с пулом потоков.

Вы также можете столкнуться с конфликтами памяти при использовании константных строк.Все строки хранятся в общем пуле строк, и поэтому это может стать узким местом, если только java не очень умен в этом.

В целом, я бы не советовал использовать Java для такого рода вещей.Использование pthreads было бы лучшим способом для вас.

Answer 4

Вы можете попробовать использовать функцию submit, а затем посмотреть, какие возвращающиеся Future проверяют их, чтобы увидеть, завершился ли поток.

Завершение не возвращается, пока не произойдет останов.

Отправка в будущем (задача Runnable) Отправляет задачу Runnable для выполнения и возвращает Future, представляющий эту задачу.

isTeridity () Возвращает значение true, если все задачи завершены после завершения работы.

Попробуйте...

public static void main(String[] args) {
    long lDateTime = new Date().getTime();
    parseArgs(args);
    List<Thread> threads = new ArrayList<Thread>();
    List<Future> futures = new ArrayList<Future>();

    ExecutorService executor = Executors.newFixedThreadPool(NTHREADS);
    for (int i = 0; i < (N / RANGESIZE); i++) {
        Runnable worker = new MyRunnable(i * RANGESIZE + 1, (i + 1) * RANGESIZE);
        futures.add(executor.submit(worker));
    }
    boolean done = false;
    while (!done) {
        for(Future future : futures) {
            done = true;
            if( !future.isDone() ) {
                done = false;
                break;
            }
        }
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    System.out.println("Finished all threads");
    long fDateTime = new Date().getTime();
    System.out.println("time in milliseconds for checking to " + N + " is " +
            (fDateTime - lDateTime) +
            " (" + N / (fDateTime - lDateTime) + " per ms)");
    System.exit(0);
}