Статьи

Влияние программирования на Java 8 Streams на производительность алгоритма

Январь 21, 2019

Многопарадигмальное программирование на Java стало возможным в течение многих лет благодаря поддержке сочетания сервис-ориентированного, объектно-ориентированного и аспектно-ориентированного программирования. Java 8 с классами lambdas и java.util.stream.Stream — это хорошая новость, потому что она позволяет нам добавить в смесь парадигму функционального программирования. Действительно, было много ажиотажа вокруг лямбд. Но разумно ли менять наши привычки и то, как мы пишем наш код, не зная сначала опасностей, которые могут скрываться?

Класс Stream Java 8 является изящным, поскольку он позволяет собирать данные и объединять несколько функциональных вызовов в эти данные, создавая аккуратный код. Алгоритмы сопоставления / сокращения являются хорошим примером, когда вы берете коллекцию данных и агрегируете их, сначала выбирая или изменяя данные из сложной области и упрощая ее (часть «карты»), а затем сводя ее к одному полезному значению. ,

Возьмем, к примеру, следующие классы данных (написанные на Groovy, чтобы я получил генерацию кода конструкторов, методов доступа, методов hash / equals и toString!):

01
02
03
04
05
06
07
08
09
10
11
//Groovy
@Immutable
class City {
    String name
    List<Temperature> temperatures
}
@Immutable
class Temperature {
    Date date
    BigDecimal reading
}

Я могу использовать эти классы для построения случайных данных о погоде в списке объектов City , например:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private static final long ONE_DAY_MS = 1000*60*60*24;
private static final Random RANDOM = new Random();
 
public static List<City> prepareData(
                      int numCities, int numTemps) {
    List<City> cities = new ArrayList<>();
    IntStream.range(0, numCities).forEach( i ->
        cities.add(
            new City(
                generateName(),
                generateTemperatures(numTemps)
            )
        )
    );
    return cities;
}
 
private static List<Temperature> generateTemperatures(
                                         int numTemps) {
    List<Temperature> temps = new ArrayList<>();
    for(int i = 0; i < numTemps; i++){
        long when = System.currentTimeMillis();
        when += ONE_DAY_MS*RANDOM.nextInt(365);
        Date d = new Date(when);
        Temperature t = new Temperature(
                             d,
                             new BigDecimal(
                                RANDOM.nextDouble()
                             )
                         );
        temps.add(t);
    }
    return temps;
}
 
private static String generateName() {
    char[] chars = new char[RANDOM.nextInt(5)+5];
    for(int i = 0; i < chars.length; i++){
        chars[i] = (char)(RANDOM.nextInt(26) + 65);
    }
    return new String(chars);
}

Строка 7 использует класс IntStream , также из Java 8, для построения диапазона, по которому IntStream строки 8-13, добавляя новые города в список, построенный в строке 6. Строки 22-30 генерируют случайные температуры в случайные дни.

Если бы я хотел затем рассчитать среднюю температуру, зарегистрированную в августе, по всем городам, я мог бы написать следующий функциональный алгоритм:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Instant start = Instant.now();
Double averageTemperature = cities.stream().flatMap(c ->
    c.getTemperatures().stream()
).filter(t -> {
    LocalDate ld = LocalDateTime.ofEpochSecond(
                       t.getDate().getTime(),
                       0,
                       ZoneOffset.UTC
                    ).toLocalDate();
    return ld.getMonth() == Month.AUGUST;
}).map(t ->
    t.getReading()
).collect(
    Collectors.averagingDouble(
        TestFilterMapReducePerformance::toDouble
    )
);
 
Instant end = Instant.now();
System.out.println(
    "functional calculated in " +
    Duration.between(start, end) +
    ": " + averageTemperature);

Линия 1 используется для запуска часов. Затем код создает поток из списка городов в строке 2. Затем я выравниваю данные, создавая один длинный список всех температур, используя метод flatMap (также строка 2), передавая ему лямбду в строке 3, которая возвращает каждое список температур в виде потока, который метод flatMap может добавлять вместе. Как только это будет сделано, я использую метод filter в строке 4, чтобы выбросить любые данные, которые не относятся к августу. Затем я вызываю метод map в строке 11, чтобы преобразовать каждый объект Temperature в
BigDecimal и с полученным потоком я использую метод collect в строке 13 вместе со сборщиком, который вычисляет среднее значение. Строка 15 нуждается в вспомогательной функции для преобразования экземпляров BigDecimal в double s, поскольку строка 14 работает с double s, а не с
BigDecimal s:

1
2
3
4
/** method to convert to double */
public static Double toDouble(BigDecimal a) {
    return a.doubleValue();
}

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
BigDecimal total = BigDecimal.ZERO;
int count = 0;
for(City c : cities){
    for(Temperature t : c.getTemperatures()){
        LocalDate ld = LocalDateTime.ofEpochSecond(
                          t.getDate().getTime(),
                          0,
                          ZoneOffset.UTC).toLocalDate();
        if(ld.getMonth() == Month.AUGUST){
            total = total.add(t.getReading());
            count++;
        }
    }
}
double averageTemperature = total.doubleValue() / count;

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

Для более точного считывания данных о производительности мне нужно многократно запускать алгоритмы, чтобы у компилятора горячей точки было время для прогрева. Запустив алгоритмы несколько раз в псевдослучайном порядке, я смог измерить, что код, написанный в функциональном стиле, занимает в среднем около 0,93 секунды (при использовании тысячи городов, каждый с тысячей температур; рассчитывается на ноутбуке с Intel 64-разрядный процессор i5 2,40 ГГц с 4 ядрами). Код, написанный в императивном стиле, занял 0,70 секунды, что на 25% быстрее.

Поэтому я спросил себя, всегда ли императивный код быстрее функционального кода. Давайте попробуем просто посчитать количество температур, зарегистрированных в августе. Функциональный код может выглядеть так:

1
2
3
4
5
6
7
8
9
long count = cities.stream().flatMap(c ->
    c.getTemperatures().stream()
).filter(t -> {
    LocalDate ld = LocalDateTime.ofEpochSecond(
                       t.getDate().getTime(),
                       0,
                       ZoneOffset.UTC).toLocalDate();
    return ld.getMonth() == Month.AUGUST;
}).count();

Функциональный код включает в себя фильтрацию и затем вызов метода count . В качестве альтернативы эквивалентный императивный код может выглядеть следующим образом:

01
02
03
04
05
06
07
08
09
10
11
12
long count = 0;
for(City c : cities){
    for(Temperature t : c.getTemperatures()){
        LocalDate ld = LocalDateTime.ofEpochSecond(
                       t.getDate().getTime(),
                       0,
                       ZoneOffset.UTC).toLocalDate();
        if(ld.getMonth() == Month.AUGUST){
            count++;
        }
    }
}

В этом примере при работе с набором данных, отличным от того, который использовался для расчета средних температур за август, императивный код в среднем составлял 1,80 секунды, а функциональный код — чуть меньше. Поэтому мы не можем сделать вывод, что функциональный код работает быстрее или медленнее, чем императивный код. Это действительно зависит от варианта использования. Что интересно, мы можем заставить вычисления выполняться параллельно, используя метод parallelStream() вместо метода stream() . В случае вычисления средней температуры использование параллельного потока означает, что среднее значение вычисляется за 0,46 секунды, а не 0,93 секунды. Параллельный подсчет температур занял 0,90 секунд, а не 1,80 секунд. Попробуйте написать императивный код, который разделяет данные, распределяет вычисления по ядрам и объединяет результаты в единую среднюю температуру — это займет много работы! Именно это является одной из главных причин желания добавить функциональное программирование в Java 8. Как это работает? Spliterators и Completers используются для распределения работы в ForkJoinPool по умолчанию, который по умолчанию оптимизирован для использования столько потоков, сколько имеется ядер. Теория гласит, что использование только столько потоков, сколько имеется ядер, означает, что с переключением контекста не тратится время, но это зависит от того, содержит ли выполняемая работа какой-либо блокирующий ввод / вывод — это то, что я обсуждаю в своей книге о Scala .

Порождение потоков — интересная тема при работе с серверами приложений Java EE, так как строго говоря, вы не можете порождать потоки. Но поскольку создание параллельного потока не порождает никаких потоков, не нужно беспокоиться об этом! Использование параллельных потоков вполне допустимо в среде Java EE!

Вы можете использовать алгоритм карты / уменьшения, чтобы рассчитать общее количество температур в августе:

1
2
3
4
5
int count = cities.stream().map(c ->
    c.getTemperatures().size()
).reduce(
    Integer::sum
).get();

Строка 1 создает поток из списка и отображает (преобразует) города в число температур для города, используя лямбду в строке 2. Строка 3 уменьшает поток «количества температур» в одно значение, используя сумму метод класса Integer в строке 4. Поскольку потоки могут не содержать элементов, метод Reduce возвращает Optional , и мы вызываем метод get, чтобы получить общее количество. Мы можем сделать это безопасно, потому что мы знаем, что города содержат данные. Если вы работаете с данными, которые могут быть пустыми, вы можете вызвать метод orElse(T) который позволяет вам указать значение по умолчанию, которое будет использоваться, если результат недоступен.

С точки зрения написания функционального кода есть еще один способ написания этого алгоритма:

1
2
3
4
5
long count = cities.stream().map(c ->
    c.getTemperatures().stream().count()
).reduce(
    Long::sum
).get();

Используя вышеупомянутый метод, лямбда в строке 2 подсчитывает размер списка температур, преобразовывая его в пар и вызывая метод count . С точки зрения производительности, это плохой способ получить размер списка. С тысячей городов и тысячей температур в каждом, общее количество было рассчитано за 160 мсек с использованием первого алгоритма. Второй алгоритм увеличивает это время до 280 мс! Причина в том, что ArrayList знает его размер, так как он отслеживает его, когда элементы добавляются или удаляются. Поток, с другой стороны, вычисляет размер, сначала отображая каждый элемент на значение 1L а затем уменьшая поток на 1L используя метод Long::sum . Для длинных списков данных, которые являются значительными накладными расходами по сравнению с простым поиском размера по атрибуту в списке.

Сравнение времени, требуемого функциональным кодом, со временем, требуемым следующим императивным кодом, показывает, что функциональный код работает в два раза медленнее — императивный код вычисляет общее количество температур в среднем всего за 80 мс.

1
2
3
4
long count = 0;
for(City c : cities){
    count += c.getTemperatures().size();
}

Использование параллельного потока вместо последовательного потока, опять же, просто вызывая метод parallelStream() вместо метода stream() в строке 1 тремя перечисленными выше списками, приводит к алгоритму, требующему в среднем 90 мс, т.е. немного больше, чем императивный код ,

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

1
2
3
4
5
int count = cities.stream().collect(
    Collectors.summingInt(c ->
        c.getTemperatures().size()
    )
);

Эквивалентный императивный код:

1
2
3
4
long count = 0;
for(City c : cities){
    count += c.getTemperatures().size();
}

В среднем, функциональный листинг занимал 100 мс, что было в то же время, что и императивный листинг. Использование параллельного потока, с другой стороны, сократило время расчета вдвое, до 50 мс.

Следующий вопрос, который я задавал себе, состоял в том, можно ли определить, сколько данных необходимо обработать, чтобы использование параллельного потока стало целесообразным? Разделение данных, отправка их в ExecutorService например, ForkJoinPool и сбор результатов вместе после расчета не бесплатны — они стоят с точки зрения производительности. Конечно, возможно работать, когда это окупается, для параллельной обработки данных, и ответ, как правило, зависит от варианта использования.

В этом эксперименте я вычисляю среднее из списка чисел. Я повторяю работу снова и снова (раз NUM_RUNS ) просто для получения измеримых значений, поскольку вычисление среднего из трех чисел слишком быстро для надежного измерения. Я изменяю размер списка от 3 до трех миллионов, чтобы определить, насколько большим должен быть список, прежде чем он окупится, используя параллельный поток для вычисления среднего.

Использованный алгоритм был:

1
2
3
4
5
6
double avg = -1.0;
for(int i = 0; i < NUM_RUNS; i++){
    avg = numbers.stream().collect(
        Collectors.averagingInt(n->n)
    );
}

Просто для удовольствия, вот еще один способ сделать расчет:

1
2
3
4
5
6
7
double avg = -1.0;
for(int i = 0; i < NUM_RUNS; i++){
    avg = numbers.stream().
            mapToInt(n->n).
            average().
            getAsDouble();
}

Результаты были следующими. Имея всего три числа в списке, я провел расчет 100 000 раз. Многократное выполнение теста показало, что в среднем последовательный расчет занимал 20 мс по сравнению с параллельным вычислением, который занимал 370 мс. Так что с небольшой выборкой данных в этом случае не стоит использовать параллельный поток.

С другой стороны, при наличии трех миллионов чисел в списке последовательный расчет занял 1,58 секунды по сравнению с 0,93 секундами для параллельного вычисления. Так что с большой выборкой данных в этом случае стоит использовать параллельный поток. Обратите внимание, что количество прогонов было уменьшено по мере увеличения размера набора данных, поэтому мне не пришлось долго ждать результатов (я не пью кофе!).

Количество номеров в списке Avg. время SERIAL Avg. ПАРАЛЛЕЛЬНОЕ время NUM_RUNS
3 0.02s 0.37s 100000
30 0.02s 0.46s 100000
300 0.07s 0.53s 100000
3000 1.98s 2.76s 100000
30000 0.67s 1.90s 10000
300000 1.71s 1.98s 1000
3000000 1.58s 0.93s 100

Означает ли это, что параллельные потоки полезны только для больших наборов данных? Нет! Это полностью зависит от интенсивности расчетов под рукой. Следующий бесполезный алгоритм просто нагревает процессор, но демонстрирует сложный расчет.

01
02
03
04
05
06
07
08
09
10
11
12
private void doIntensiveWork() {
    double a = Math.PI;
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 1000; j++){
            for(int k = 0; k < 100; k++){
                a = Math.sqrt(a+1);
                a *= a;
            }
        }
    }
    System.out.println(a);
}

Мы можем создать список из двух исполняемых файлов, которые выполняют эту интенсивную работу, используя следующий список:

1
2
3
4
5
6
private List<Runnable> generateRunnables() {
    Runnable r = () -> {
        doIntensiveWork();
    };
    return Arrays.asList(r, r);
}

Наконец, мы можем измерить время, необходимое для запуска двух исполняемых таблиц, например, параллельно (см. Вызов метода parallelStream() в строке 3):

1
2
3
4
5
6
7
List<Runnable> runnables = generateRunnables();
Instant start = Instant.now();
runnables.parallelStream().forEach(r -> r.run());
Instant end = Instant.now();
System.out.println(
    "functional parallel calculated in " +
    Duration.between(start, end));

В параллельном потоке для выполнения интенсивной работы дважды требовалось в среднем 260 мс. При использовании последовательного потока это заняло в среднем 460 мс, т.е. почти вдвое больше времени.

Что мы можем сделать из всех этих экспериментов? Что ж, невозможно окончательно сказать, что функциональный код медленнее, чем императивный код, и невозможно также сказать, что использование параллельных потоков быстрее, чем использование последовательного потока. Мы можем заключить, что программистам необходимо экспериментировать с различными решениями и измерять влияние стиля кодирования на производительность, когда они пишут критичный к производительности код. Но давайте будем честными, в этом нет ничего нового! Для меня, что вы должны забрать с собой после прочтения этого поста, это то, что всегда есть много способов написать алгоритмы, и выбор правильного пути важен. Знание того, какой путь правильный, — это сочетание опыта, но, что более важно, игра с кодом и пробование различных решений. Наконец, как всегда, не оптимизируйте преждевременно!

Ссылка: Влияние программирования на Java 8 Streams на производительность алгоритма от нашего партнера по JCG Антона Кучера из блога The Kitchen in the Zoo .
51
Share: