Распараллеливание занимает больше времени, чем непараллельное задание

Question

Мне нужно сделать задание по программированию для университета.Задача состоит в том, чтобы реализовать программу, которая возвращает все решения уравнения q² + 3qp + p² = r² (q, p, r простых чисел).Впоследствии программа должна быть ускорена распараллеливанием.К сожалению, мы должны использовать BigInteger, так что не удивляйтесь.

Это мой класс, который я написал, который вычисляет именно это уравнение.

    public boolean calculateEquation() {
    //Equation: p² + 3pq + q² = r²
    if (calculatePSquare().add(calculate3TimesPQ()).add(calculateQSquare()).equals(calculateRSquare())) {
        System.out.println("p: " + p + " q: " + q + " r: " + r);
    }
    return calculatePSquare().add(calculate3TimesPQ()).add(calculateQSquare()).equals(calculateRSquare());
}
@Override
public void run() {
    calculateEquation();
}

Полный код для этого класса: https://pastebin.com/wwrDurUT

Следующим моим шагом было проверить коди остановите время, чтобы увидеть, работает ли распараллеливание позже.Чтобы реализовать распараллеливание, я рассмотрел различные потоки, в том числе и ту, которая связана здесь: Какой самый простой способ распараллелить задачу в Java?

И это был мойрезультат:

ExecutorService executorService = Executors.newFixedThreadPool(Configuration.instance.maximumNumberOfCores);
        ExecutorCompletionService executorCompletionService = new ExecutorCompletionService(executorService);

        for (BigInteger pValue : possiblePValues) {
            for (BigInteger qValue : possibleQValues) {
                for (BigInteger rValue : possibleRValues) {
                    executorCompletionService.submit(new Thirteen(pValue, qValue, rValue), null);
                }
            }
        }
        executorCompletionService.take();

Полный код: https://pastebin.com/kviEnnFH

Теперь, что забавно, распараллеленная версия работает быстрее только при небольшом количестве задач.Для всех простых чисел от 0 до 500 параллельная версия работает быстрее.Если я возьму все простые числа от 0 до 2000, результаты будут выглядеть совсем иначе:

Все простые числа от 0 до 100:

Не распараллелено: Задача заняла: 110ms

Распараллелено: Задача заняла: 64мс

Все простые числа от 0 до 2000:

Не распараллелено: Задача заняла: 7797ms

Распараллелено: Задача заняла: 25799мс

Поскольку по этому вопросу так мало легко понятных ресурсов, и я, честно говоря, не совсем понимаю, что именно делает мой код,Я очень удивлен, почему он ведет себя так, как он делает.

Answer 1

Прежде всего, нет смысла реализовывать это уравнение p² + 3pq + q² = r² с использованием тройки, встроенной для циклов, что приводит к сложности O(n) = n^3.Это можно сделать, используя только два цикла for, поскольку, если мы знаем, что значения p и q, r могут быть вычислены с использованием уравнения.

for (BigInteger p: possiblePValues) {
    for (BigInteger q: possibleQValues) {
        BigInteger r = p.pow(2).add(q.pow(2)).add(p.multiply(q).multiply(new BigInteger("3")))
        // decide if sqrt(r) is prime
     }
 }

Теперь, если мы сохранили предварительно-вычисленные простые числа внутри Hashmap, например, мы можем определить, является ли r простым числом с помощью поиска.

О параллализации: Ваш подход неверен, поскольку вы просто порождаете потоки для некоторых операцийкоторые занимают относительно короткое время для завершения.Вероятно, накладные расходы на управление потоками занимают больше времени, чем операция по вычислению самого уравнения.Я предполагаю, что именно поэтому вы получаете более длительный период для многопоточной версии.Не существует золотого правила о том, как распараллеливать два встроенных цикла for.Мой подход состоит в том, чтобы разбить первый цикл на более мелкие куски в зависимости от того, сколько у вас ядер, и создать несколько интервалов.Например, если у нас 100 простых чисел и 4 потока, первый поток примет значения p, имеющие индекс от 0 до 24, второй от 25 до 49 и т. Д.Второй цикл for должен выполняться от 0 до 100 в каждом потоке.Используя этот подход, вы можете вычислить все возможные значения r.