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

Question

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

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

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

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

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

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

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

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

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

Особенности

Runtimes:

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

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

Процессор:

Quadcore Intel Q6600 на частоте 2,4 ГГц, 4 Гб. Машина выгружена.

Java:

ява версия "1.6.0_15" Java (TM) SE Runtime Environment (сборка 1.6.0_15-B03) Java HotSpot (TM) 64-разрядного сервера VM (сборка 14.1-B02, смешанный режим)

OS:

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

Busy ожидания может быть проблема:

while (!executor.isTerminated()) { 
} 

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

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

Answer 2

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

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

У вас также могут быть конфликты памяти, когда вы используете постоянные строки. Все строки хранятся в объединенном пуле строк, и поэтому это может стать узким местом, если только Java не очень умный.

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

Answer 3

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

Терминал не возвращается до завершения работы.

Future submit (Runnable task) Представляет задачу Runnable для выполнения и возвращает будущее, представляющее эту задачу.

isTerminated() Возвращает 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); 
} 

Answer 4

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

Я подозреваю, что в случае с Q6600 ваше конкретное приложение ограничено объемом доступного общего кеша или чем-то другим, специфичным для архитектуры этого ЦП. Q6600 имеет два 4 МБ кэша L2, что означает, что ЦП их делят, а не кеш-память L3. На моем ядре 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 ядра не HyperThreading), 4 Гб RAM, Windows 7 64-бит, JDK 1.6.0_22 (64-битный):

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

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

• Примечание: Java 1.6.0_18 и позже были изменены настройки кучи по умолчанию - так что мой по умолчанию размер кучи почти 1500м на моем рабочем компьютере, и около 1000 м на мой домашний компьютер.

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

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

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

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