Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Java: Общие вопросы > Возведение в степень Fork/Join Framework'ом


Автор: Pawl 2.7.2012, 12:15
Уважаемые форумчане,
Исследую возможности Fork-Join фрэймворка. Написал программку возведения в степень числа.
Код

import java.util.concurrent.*;

public class ForkJoinPow extends RecursiveTask<Double> {
    private Double x;
    private int y;
    
    public ForkJoinPow(Double x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public Double compute() {
        System.out.println(Thread.currentThread().getName() + " pow is: " + y);            
        if (y > 0) {
            ForkJoinPow pow = new ForkJoinPow(x, y - 1);            
            pow.fork();                
            return pow.join() * x;                        
        }

        return 1d;            
    }
    
    public static void main(String[] args) {     
     ForkJoinPow task = new ForkJoinPow(2d, 100);
        ForkJoinPool pool = new ForkJoinPool();
        System.out.println(pool.invoke(task));
        System.out.println(pool.getPoolSize());
        System.out.println(pool.getParallelism());
    }
}

и вот какой вопрос у меня возник: этой строкой
Код

System.out.println(Thread.currentThread().getName() + " pow is: " + y);
 я определяю в частности, какой поток сейчас производит вычисление. Так вот, вычисления производят у меня всего 2 потока, хотя пул создается по умолчанию на 3 потока (т. к. на компе 3 проца), и методы
Код

        System.out.println(pool.getPoolSize());
        System.out.println(pool.getParallelism());
 возвращают 3.
Более того, если написать, к примеру,
Код

ForkJoinPool pool = new ForkJoinPool(10);

все равно количество работающих потоков получается меньшим, чем размер пула. Был бы благодарен, если кто-нибудь объяснит мне, в чем тут дело, и насколько корректно я тут вообще реализовал Fork/Join framework.
Спасибо!

Автор: jk1 2.7.2012, 13:07
Имхо проблема в декомпозиции. Надо бы делить работу пополам и правильно мержить:

Код

public class ForkJoinPow extends RecursiveTask<Double> {
    private Double x;
    private int y;

    public ForkJoinPow(Double x, int y) {
        this.x = x;
        this.y = y;
    }

    public Double compute() {
        System.out.println(Thread.currentThread().getName() + " pow is: " + y);
        if (y > 1) {
            ForkJoinPow pow1 = new ForkJoinPow(x, y / 2);
            pow1.fork();
            ForkJoinPow pow2 = new ForkJoinPow(x, y - y / 2);
            return pow2.compute() * pow1.join();
        } else {
            return x * y;
        }
    }


    public static void main(String[] args) {
        ForkJoinPow task = new ForkJoinPow(2d, 100);
        ForkJoinPool pool = new ForkJoinPool(5);
        System.out.println(pool.invoke(task));
        System.out.println(pool.getPoolSize());
        System.out.println(pool.getParallelism());
    }
}


Писал в браузере, так что мог не учесть какой-нибудь +- 1 или граничный случай. Но в целом идея должна быть понятна 

Автор: Pawl 2.7.2012, 13:40
Цитата(jk1 @  2.7.2012,  13:07 Найти цитируемый пост)
Но в целом идея должна быть понятна 

Идея понятна, подобный способ я, собственно, в начале и применял, но меня смущает то, что в этом случае появляются "лишние" шаги рекурсии. Например, при у = 10 получается такой вывод:
Код

ForkJoinPool-1-worker-1 pow is: 10
ForkJoinPool-1-worker-1 pow is: 5
ForkJoinPool-1-worker-2 pow is: 5
ForkJoinPool-1-worker-1 pow is: 3
ForkJoinPool-1-worker-2 pow is: 3
ForkJoinPool-1-worker-1 pow is: 2
ForkJoinPool-1-worker-3 pow is: 2
ForkJoinPool-1-worker-1 pow is: 1
ForkJoinPool-1-worker-2 pow is: 2
ForkJoinPool-1-worker-1 pow is: 1
ForkJoinPool-1-worker-3 pow is: 1
ForkJoinPool-1-worker-1 pow is: 1
ForkJoinPool-1-worker-2 pow is: 1
ForkJoinPool-1-worker-3 pow is: 1
ForkJoinPool-1-worker-2 pow is: 1
ForkJoinPool-1-worker-3 pow is: 2
ForkJoinPool-1-worker-1 pow is: 1
ForkJoinPool-1-worker-3 pow is: 1
ForkJoinPool-1-worker-2 pow is: 1
1024.0
3
3

т. е. всего 19 шагов, в то время, как минимально необходимое - 11 (от 10 до 0 вкл.).

Автор: jk1 2.7.2012, 14:00
Цитата

т. е. всего 19 шагов, в то время, как минимально необходимое - 11 (от 10 до 0 вкл.). 


Тут будет 10 считающих шагов, а остальные делают декомпозицию и вычислений не производят.
Вот этот код
Код

 public Double compute() {
        if (y > 1) {
            System.out.println(Thread.currentThread().getName() + " decomposing, pow is: " + y);
            ForkJoinPow pow1 = new ForkJoinPow(x, y / 2);
            pow1.fork();
            ForkJoinPow pow2 = new ForkJoinPow(x, y - y / 2);
            return pow2.compute() * pow1.join();
        } else {
            System.out.println(Thread.currentThread().getName() + " computing, pow is: " + y);
            return x * y;
        }
    }



показывает, какие шаги что делают.

Вообще говоря это логично, Fork/Join - это всегда дерево задач, а не линейная последовательность, как в вашем первом посте.

Автор: Pawl 2.7.2012, 14:21
Ок, будем разбираться. Кстати, ИМХО, писать 
Код

return x * y;
 ненужно. Ведь в ветке else y все-равно будет = 1, так что достаточно написать 
Код

return x;

и еще я в самом начале compute() дописал
Код

     if (y == 0) {
         return 1d;
     }
 чтобы корректно получить число в степени 0.

Автор: jk1 2.7.2012, 14:44
Цитата

Ок, будем разбираться. Кстати, ИМХО, писать 
код Java

return x * y;

 ненужно. Ведь в ветке else y все-равно будет = 1, так что достаточно написать 


Как уже писал выше - это черновик для иллюстрации концептуальных вещей. Так-то Вы конечно правы

Автор: Pawl 2.7.2012, 14:58
Спасибо!
Вообще, наверное, данный фреймворк не очень подходит для вычисления степени. Ветвления тут явно лишние. Может быть Вы знаете более подходящие и наглядные примеры?

Автор: jk1 2.7.2012, 15:32
Я когда-то писал merge sort сначала на потоках с ручной синхронизацией, затем - на fork/join, для иллюстрации.
Эта задача разветвляется гораздо лучше. Хорошо должна также пойти обработка любых древовидных структур, например файловых систем.

Важно только понимать, что реальный прирост производительности начинается при достаточной вычислительной емкости подзадач.

Автор: Stolzen 2.7.2012, 15:38
Цитата(Pawl @  2.7.2012,  15:58 Найти цитируемый пост)
Вообще, наверное, данный фреймворк не очень подходит для вычисления степени. Ветвления тут явно лишние. Может быть Вы знаете более подходящие и наглядные примеры?

Может mergesort?

Добавлено через 3 минуты и 22 секунды
Упс, пардон, меня уже опередили с советом про mergesort

Автор: Pawl 2.7.2012, 15:47
Цитата(jk1 @  2.7.2012,  15:32 Найти цитируемый пост)
Я когда-то писал merge sort сначала на потоках с ручной синхронизацией, затем - на fork/join, для иллюстрации.

Ок, я тоже попробую - для иллюстрации. smile Эту тему я закрываю, но если появятся вопросы по применению fork/join в сортировке - открою новую!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)