Devoxx 2012: Java 8 Лямбда и параллелизм, часть 2

обзор

В Devoxx 2012: Java 8 Лямбда и параллелизм, часть 1 , я рассмотрел основы лямбда и параллелизма в Java 8, представленные на Devoxx в сессии. По дороге к JDK 8: лямбда, параллельные библиотеки и многое другое Джо Дарси. В этом посте я хотел бы осветить еще две сессии Devoxx на эту тему:

• Закрытия и коллекции — мир после восьми Мориса Нафталина
• Fork / Join, лямбда и параллель (): параллельные вычисления упрощены (тоже?) Хосе Паумардом

Эти два сеанса, как и первый, проходили в один и тот же день, в одной и той же комнате, один за другим, и вместе давали три разных взгляда на лямбды, параллельные коллекции и параллелизм в целом в Java 8.

Закрытия и коллекции — мир после восьми

На этой сессии Морис Нафталин , архитектор программного обеспечения с Incept5 и соавтор Java Generics and Collections , рассказал о другом мире после Java 8, уделив особое внимание влиянию лямбд на способы обработки коллекций с введением новых такие функции, как потоковая обработка, параллельные представления и многое другое.

Вступление

Морис начал с того, что немного рассказал о своей истории, своей книге и своем текущем проекте Lambda FAQ , который призван стать основным учебным онлайн-ресурсом для Project Lambda и который также является подготовкой ко второму изданию его книги, в какую часть коллекций необходимо будет тщательно пересмотреть.

Почему все так грубы о нас?

Вам не нужно было бы слишком далеко заглядывать в Интернет, чтобы найти ресурсы, которые относятся к Java с иронией и сарказмом, и идея о том, что «Java — это новый Cobol», получила широкое распространение. По словам докладчика, это может быть связано с тем, что мы пишем такой код:

// check each deadlined Plan. If it can't be done in time for its deadline, return the Plan
// that caused the problem; otherwise, return null.
private Plan checkPlans(List<Plan> deadlinedPlans) {
    Plan problemPlan = null;
    Iterator<Plan> planItr = deadlinedPlans.iterator();
    while (planItr.hasNext() && problemPlan == null) {
        Plan plan = planItr.next();
        problemPlan = checkPlan(plan);
    }
    return problemPlan
}

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

Не было бы здорово, если бы мы могли вместо этого написать это:

private Optional<Plan> checkPlans(List<Plan> deadlinedPlans) {
    return deadlinedPlans.stream().
        map(p -> checkPlan(p)).
        filter(p -> p != null).
        findFirst();
}

Приведенный выше код написан в функциональном стиле . Список планов помещается в поток , каждый из которых сопоставляется с результатом вызова checkPlan, результирующий поток фильтруется по ненулевым планам, и, наконец, первый из них обнаруживается. Как только вы научитесь читать, второй код станет намного лучше первого. И это может быть выполнено параллельно с небольшим дополнительным усилием.

Волшебный ингредиент

Магический ингредиент — это то, что позволяет нам повышать ценность. Вместо того , чтобы поставлять значения для конкретных библиотечных методов, мы будем предложения поведения для общих методов библиотеки. Здесь, как обычно в функциональном программировании, поведение рассматривается как значение более высокого порядка. Например, давайте сравним следующие Collection<E>методы:

boolean remove(Object o);
...
boolean removeIf(Predicate<? super E> p);

Вторая версия явно более общая, потому что мы задаем поведение вместо значения. Predicateинтерфейс с единственным абстрактным логическим методом test, который выполняется для removeIfкаждого элемента. Здесь Predicateесть функциональный интерфейс , и добавление нового метода removeIfк Collectionвозможно благодаря умолчанию методов , концепций , которые уже были охвачены в моем предыдущем посте .

В прошлом, чтобы создать экземпляр интерфейса для использования с приведенным выше кодом, мы использовали анонимный внутренний класс. Однако это не очень приятно. Если мы уберем шаблон, у нас останется только имя аргумента и тело метода, которые мы могли бы предоставить через лямбда-выражение :

plans.removeIf(p -> p.equals(problemPlan));

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

Лучшие API — трубы и фильтры

Лямбда, по существу простая вещь, может иметь действительно большое значение. В коллекциях мы увидим паттерн, известный как Pipes and Filters, который используется гораздо чаще. Это почтенный шаблон построения инструментов Unix, который также получил широкое распространение в других областях:

ps -ef | grep login | cut -c 50- | head

Этот шаблон имеет много преимуществ, которые также распространяются на коллекции Java:

• нет промежуточных переменных
• меньше (или нет) промежуточного хранения
• ленивая оценка, которая обеспечивает большой прирост эффективности
• гибкое создание инструментов, следуя философии Unix программ Write, которые хорошо выполняют одну задачу. Напишите программы для совместной работы .

В Java конвейер такой:

plans.stream().map(p -> checkPlan(p)).filter(p -> p != null).findFirst();

имеет источник , ряд промежуточных операций ( map, filter) и терминальную операцию ( findFirst), а средство, которое переносит значения из источника по конвейеру, называется потоком ( Stream). Операция map использует экземпляр нового функционального интерфейса Mapper, операция фильтрации использует уже упомянутые Predicate, и в операции терминала также могут быть встроены лямбда-выражения. Здесь идея «написания программ, которые делают что-то хорошо» хорошо представлена ​​обоими Mapperи Predicate, которые являются функциональными интерфейсами с одним методом.

Что именно Stream? Это последовательность значений, которая может быть частично оценена . В отличие от коллекций, вы на самом деле не знаете, что они содержат, потому что они еще не были сгенерированы. Выполнение отложенных операций, таких как mapи filterустанавливает конвейер:

Stream<Plan> planStream = plans.stream().map(p -> checkPlan(p)).filter(p -> p != null);

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

planStream.findFirst(); // stop after the first element

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

Вот еще несколько примеров операций, которые можно выполнять на потоках:

// get the plans longer than 15 minutes
planStream.filter(p -> p.getDuration().isLognerThan(minutes(15)));
// get the total duration of all the plans in a list
planStream.map(p -> p.getDuration()).reduce(Duration.ZERO, (d1, d2) -> d1.plus(d2));
// each plan belongs to a task; map each task to a collection of its plans
planStream.groupBy(p -> p.getTask());
// get the first five plans
planStream.limit(5);
// get all but the first five plans
planStream.skip(5);

Эти и другие методы сбора приведены в таблице ниже:

Здесь мы получаем большой объем знаний, в основном из функционального программирования. Это дает нам другой стиль программирования, который очень применим, поэтому код коллекций будет выглядеть по-другому. Ценность предложения заключается в том, что мы получим гораздо лучшие API, и наш код будет легче читать и писать, и он станет более понятным, когда мы к нему привыкнем. И более параллельный, потому что мы будем меньше полагаться на изменчивость.

Лучшие API — более тонкие API

Lambdas также предлагает еще один способ улучшить API. С методами, которые принимают и возвращают поведение, например, гораздо проще создавать собственные компараторы:

// method in class Comparators
Comparator<T> comparing(Mapper<T, U> m);
// usage
Comparator<Plan> byTask = Comparators.comparing(p -> getTask());
Comparator<Plan> byDuration = Comparators.comparing(p -> getDuration());

Приведенный выше код изолирует ключ сортировки в вызове comparing, а не извлекает его из самого кода сравнения, что намного приятнее, а также значительно упрощает составление детализированных методов:

plans.sort(byTask.compose(byDuration));

Составление компараторов позволяет использовать первый ключ сортировки как первичный, а второй как вторичный, очень аккуратно. Мы могли бы сделать это еще лучше, распределяя пользовательские компараторы в пользу ссылок на методы , Plan::getTaskи Plan::getDurationв этом случае.

Больше параллелизма

Существует два вида итераций: внешняя и внутренняя . Они, а также их преимущества и недостатки, уже были объяснены в моем предыдущем посте . Таким образом, нам действительно нужна внутренняя итерация, в которой мы снова задаем поведение для общих библиотечных методов:

plans.forEach(p -> p.setSection(null));

Здесь важно то, что библиотека, контролируя итерацию, может выполнять действительно сложные вещи, такие как параллелизм, выполнение не по порядку, лень и т. Д.

С помощью потоков вы можете получить параллельный поток, вызвав parallel:

plans.parallel().filter(...).map(...).reduce(...);

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

Мантра заключается в том, что параллелизм должен быть «явным, но не навязчивым». Вы должны попросить об этом, но тогда это сработает, и вам не придется больше ничего делать.

Вывод

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

В заключение, хотя лямбды могут показаться небольшим синтаксическим изменением, они сильно повлияют на стиль нашего кода и позволят авторам библиотек свободно вводить новшества. Они также будут поощрять стиль функционального кодирования, который, в свою очередь, будет стимулировать меньшую изменчивость, что приведет к более дружественному к параллельному коду. И, как отметил докладчик, после Java 8 наш Java-код станет более «стильным и утонченным», чем популярный бренд After Eight .

Fork / Join, лямбда и параллель (): параллельные вычисления сделали (тоже?) Легким

На заключительном занятии по этой теме Хосе Паумард , доцент в Институте Галилеи (Universite Paris 13) и давний блогер на Java le soir, рассказал о предостережениях о лямбде и параллельных вычислениях. Слайды этой сессии доступны здесь .

Вступление

В Java 8 у нас будут удивительные инструменты, позволяющие использовать всю мощь параллельного программирования. Тем не менее, есть также определенные предостережения и подводные камни, о которых мы должны знать.

Java Toolbox для параллелизма

Набор инструментов Java для параллелизма развился из ничего в JDK 5, через параллельные массивы в JDK 6 и, наконец, в среду Fork / Join в JDK 7.

The Fork / Join framework handles tasks. A task is a chunk of data which is able to spawn two or more subtasks, with the division strategy coded in the task itself. The main task can later join is subtasks. There are two main approaches:

• With dyadic recursive division, the task divides itself in two if it’s too big, and each of the subtasks can in turn divide itself in two, thus spawning a number of tasks of a suitable size, which are then also recursively joined.
• The task could be sliced by a for loop directly into a number of tasks of the right size, which are then joined all at once.

According to the speaker, the second strategy has proven to be much more efficient than the first one for the set of problems he has worked on, even though the Javadoc and many of the available resources are only describing the first one.

A very important caveat of Fork / Join is the Javadoc sentence «Computations should avoid synchronized methods or blocks». The consequence of this is that the task can’t share its state, instead it must transmit part of that state to the subtask while spawning it. When working on arrays, often the portion of the array transmitted has to be copied, which means additional memory consumption and degraded performance.

The Parallel Arrays API didn’t make it to the JDK, but is available as a special package, which is Java 6 compatible. Essentially, it brings the power of Fork / Join to Java 6.

Finally, Java 8 introduces the powerful new family of tools around lambdas already described in the previous two sessions. The mentioned method Collection.parallel() essentially implements in a nicer way the familiar concept of a task that can split itself.

Parallel Computing Caveats

Unfortunately, going parallel is not just a matter of calling parallel(). There are at least the following three problems which remain to be solved:

• Ensuring that the computation is correct
• Ensuring that parallelism actually brings performance gains
• Using algorithms that are parallelizable

An example of the first caveat mentioned in a presentation from Guy Steele is that a reduce operation has to be associative, or the result of the computation will not be correct:

reduce(a, reduce(b, c)) = reduce(reduce(a, b), c)

For example, the operation a + b is associative, but (a + b)² is not. If it’s supplied as a lambda expression in a reduce operation, it will produce wrong results, and neither the compiler nor the JVM could help us detect that.

The second caveat is about performance, and one example to illustrate it is sorting. Sorting in parallel is tricky, since one should first divide the list in 2 or more sublists, then sort each list using quicksort, and finally merge the sorted lists with mergesort. With this approach, the comparison itself is not computationally intensive, but there is lots of data moving between the cores.

The following two tables contain the times for sorting an array of 16M and 32M elements with different packet sizes, using the two division strategies mentioned above, on a 8 core CPU.

Based on the above results, we could make the following conclusions:

• The size of the packet should be «right», which depends on the total size and the number of processors.
• The division strategy matters.

Interestingly, if we just do quicksort on the original array with no parallelism at all, the results are:

The above results prove the second caveat: writing parallel code can be tricky, and does not always lead to performance improvements.

The third caveat is an even worse case. To illustrate it, Jose used the travelling salesman problem. This problem is known to be NP-complete, so instead of using an exact algorithm, we would use a heuristic approach such as simulated annealing to solve it. Since it’s quite computationally intensive, one could think that going parallel would increase the performance.

However, as the speaker demoed and explained, the simulated annealing algorithm that is guaranteed to find the right solution if executed sequentially either finds a wrong solution or doesn’t finish at all when executed in parallel. The reason is very simple — the used algorithm is not parallelizable at all, as the theorems on which it is based don’t hold in this case.

This brings us to the third caveat: some algorithms don’t work anymore if they are parallelized. In the case of simulated annealing, it loses its convergence properties if computed in parallel.

Conclusion

In Java 8, parallelization is going to be easier than ever, and this is really great. But we would still need to ask ourselves the following 3 questions, and we are all alone to answer them:

• Will the result be correct?
• Will it make my computations faster?
• Will it even work?

To be able to answer these questions, the speaker advised to spend more time learning how the CPUs work, how to program complex algorithms on them, and finally the parallel versions of the existing algorithms.

Finale

As I already mentioned in my previous post, from what I learned so far I find lambdas, the functional style, and the easier parallelism in Java 8 to be really wonderful. However, also the performance tests in Wordcounter confirmed that we should not take all the benefits for granted. Instead, as developers we should learn how to properly take advantage of these new opportunities. As usual in our craft, this means simply that more interesting challenges are yet to come.

Published on DZone by Stoyan Rachev (source).