Увидеть что-нибудь. Скажите что-то. Докажи что-нибудь. Сделай что-нибудь.
Начиная с идеи
В мае 2013 года я был в командировке в Лондоне. Библиотека GS Collections была выпущена в открытый доступ на GitHub полтора года назад (январь 2012 г.). Я был членом экспертной группы JSR 335 и отправлял сообщения в список рассылки lambda-lib-spec-experts, когда хотел поделиться мнением по обсуждаемой теме.
Увидеть что-нибудь
Пока я был в Лондоне, я активно тестировал GS Collections с библиотекой Java Stream, используя бинарный снимок версии до Java 8. Я помню, как провел несколько часов в своем гостиничном номере напротив собора Святого Павла, ломая голову над своеобразной разницей в производительности, которую я наблюдал между stream и parallelStream при использовании с классом FastList GS Collections.
В то время проект Java Microbenchmark Harness (JMH) еще не существовал с открытым исходным кодом. Первая общедоступная версия JMH, которую я смог увидеть на GitHub, была помечена как релиз в ноябре 2013 года. Я написал и использовал свою собственную систему микротестирования на Java в течение нескольких лет. Инструмент был довольно простым, но я часто сомневался в точности результатов. Различия, которые я наблюдал между stream и parallelStream для FastList, были настолько резкими и неожиданными, что я решил, что обнаружил что-то, что нужно было решить.
Я знал, что доступ к Stream будет представлен в Java как методы по умолчанию с именами stream() и parallelStream() в интерфейсе java.util.Collection. Любой интерфейс или класс, расширяющий или реализующий java.util.Collection, наследует реализацию по умолчанию методов stream() и parallelStream(). И stream, и parallelStream зависели от другого метода по умолчанию с именем spliterator. Я знал, что FastList и другие изменяемые контейнеры в GS Collections сразу же смогут использовать Java Streams, поскольку они унаследованы от Collection.
Я провел несколько тестов, сравнивая stream и parallelStream с нетерпеливыми методами итерации, предоставленными GS Collections для FastList и ArrayList. Тесты измеряли среднее время в миллисекундах для каждой операции, поэтому на диаграммах чем меньше, тем лучше.
Вот цифры производительности, которые я видел для GS Collections FastList.
Вот цифры производительности, которые я видел для ArrayList.
Нетерпеливая фильтрация в коллекциях GS (зеленые столбцы) работала лучше, чем фильтрация stream/parallelStream (синие столбцы) во всех случаях. Это оправдало мои ожидания, так как нетерпеливые методы почти всегда будут лучше для одной операции, такой как фильтр. Разница в производительности между фильтрацией parallelStream с FastList и фильтрацией parallelStream с ArrayList меня смутила и обеспокоила. Я ожидал, что производительность FastList будет очень похожа на ArrayList.
Тесты проводились с использованием предварительных двоичных файлов Java 8 на двухъядерном компьютере с Windows. Увидеть увеличение производительности почти в 2 раза для параллельных случаев — это то, на что я надеялся с фильтрацией. Случай parallelStream для FastList работал медленнее, чем случай stream (последовательный). Это не имело для меня никакого смысла, поэтому я пошел и посмотрел код для stream и parallelStream, чтобы попытаться понять, почему я вижу эту неожиданную разницу.
Скажите что-то
Проблема, похоже, была связана с реализацией по умолчанию spliterator на Collection, которая возвращала IteratorSpliterator. ArrayList возвращает специализированную реализацию spliterator под названием ArrayListSpliterator. Не было spliterator для реализаций RandomAccess List, отличных от JDK, таких как FastList. В следующей теме я бы предложил добавить RandomAccessSpliterator в JDK, чтобы реализации RandomAccess List, отличные от JDK, не подвергались значительным потерям производительности при использовании parallelStream. Я сообщил о своих выводах в список рассылки группы lambda-lib-spec-experts. До Java 8 это была группа, которая сообщала обо всем, что связано с Java Streams. Следующая ссылка показывает ветку, которую я начал в списке рассылки на неделе, когда я был в Лондоне, проводя свои тесты.
Ответ на мое предложение RandomAccessSpliterator был весьма восприимчивым. Однако то, что я поделился идеей, не означает, что у меня не было МНОГО дополнительной работы. Я планировал посетить Языковой саммит JVM (JVMLS) в июле 2013 года и лично обсудить свои выводы с Брайаном Гетцем и другими членами экспертной группы JSR 335. К сожалению, через месяц после того, как я впервые сообщил о своих открытиях, моя жизнь погрузилась в полнейший хаос, и в итоге я отказался от этой идеи на несколько лет.
Неожиданный обход и очень продуманный подарок
За неделю до того, как я собирался поехать на JVMLS 2013, мою жену положили в больницу с диагнозом ОМЛ (лейкемия). Впервые я написал об этой истории пару лет назад.
Поскольку моя жена месяцами лежала в больнице, получая инвазивную химиотерапию, а в конечном итоге — трансплантацию стволовых клеток, я был переведен в режим автопилота, просто пытаясь помочь семье выжить. Любые выводы, которыми я поделился за пару месяцев до этого, были забыты (но не потеряны) в бурные времена, через которые я сейчас проходил.
Мой друг и коллега Влад посетил JVMLS в 2013 году без меня и вернулся с особым подарком в виде кофейного термоса JVMLS 2013.
Я держу этот невероятно продуманный подарок на полке в офисе передо мной, где я могу видеть его каждый день.
Еще один обходной путь — Eclipse Collections
После того, как в марте 2014 года была выпущена Java 8, после долгих дискуссий я решил, что лучшим путем для GS Collections будет переход в Eclipse Foundation, где он станет называться Eclipse Collections. Фактическую работу по миграции для коллекций Eclipse выполнил Хироши, который стал первым руководителем проекта коллекций Eclipse. Хироши Ито также является одним из героев этой истории RandomAccessSpliterator.
Докажи что-нибудь
После того, как в конце 2015 года Eclipse Collections была перенесена в Eclipse Foundation, я, наконец, вернулся к своей идее двухлетней давности. Я решил еще раз подтвердить свои опасения по поводу параллельной производительности Java Streams с помощью FastList. Первоначальный выпуск Eclipse Collections 7.0 был по функциям идентичен GS Collections 7.0. Eclipse Collections 7.0 и GS Collections 7.0 были скомпилированы с Java 7. Это означало бы, что ни одна из библиотек не будет иметь переопределений для stream(), parallelStream() или spliterator() и не будет наследовать реализации по умолчанию от Collection и List. Реализация spliterator() по умолчанию по-прежнему была IteratorSpliterator в Java 8. IteratorSpliterator была ужасно неоптимальной для parallelStream для List реализаций, которые были RandomAccess.
Я написал несколько тестов, используя JMH (теперь он был доступен), и работал с Хироши Ито, который написал первую реализацию RandomAccessSpliterator, которую я использовал для тестирования. IIRC, я провел тесты на четырехъядерном компьютере с Windows (извините, я не могу вспомнить точные характеристики компьютера / программного обеспечения и не записал их). Ниже приведены результаты фильтрации событий из списка от 1 до 1 000 000 с реализацией по умолчанию IteratorSpliterator, используемой для FastList. Результаты выражены в операциях в секунду, поэтому чем больше, тем лучше.
Когда мы подключили кастомную реализацию RandomAccessSpliterator, над которой работал Хироши, мы увидели изменение производительности.
Это именно то, что мы надеялись увидеть. Как только мы убедились, что различия в производительности, которые мы наблюдали между IteratorSpliterator и RandomAccessSpliterator, убедительны и воспроизводимы, Хироши начал общение с почтовой группой core-libs-dev.
Вперед к OpenJDK
Сделай что-нибудь
Это было первое электронное письмо с патчем, отправленное в почтовую группу core-libs-dev Хироши Ито. Письмо было датировано 11 мая 2016 года, то есть через три года и два дня после того, как я впервые поделился идеей с почтовой группой lambda-lib-spec-experts.
Работа над RandomAccessSpliterator была совместной работой Хироши Ито и Пола Сандоса. Я был просто автором идеи и специалистом по тестированию производительности. Хироши и Пол сделали всю тяжелую работу и модульное тестирование для реализации RandomAccessSpliterator. Я чрезвычайно благодарен за усилия обоих из них.
Следующая ошибка существует в качестве ссылки в системе ошибок OpenJDK для этой функции.
Теперь, когда OpenJDK находится на GitHub, исходный код RandomAccessSpliterator можно просмотреть в исходном коде AbstractList, где он находится как статический класс.
Java 9 и RandomAccessSpliterator
Код RandomAccessSpliterator был доставлен вовремя, чтобы быть выпущенным с Java 9 (сентябрь 2017 г.). RandomAccessSpliterator станет spliterator по умолчанию для FastList и любых других не-JDK RandomAccess List в любой другой библиотеке, которая не предоставляет свою собственную реализацию spliterator.
Долгое ожидание
В то время как RandomAccessSpliterator успела выйти на Java 9, многие компании ждали Java 11, прежде чем увидели какие-либо преимущества оптимизации. Совсем недавно большое количество приложений предприняли попытку перехода с Java 8 на Java 11 или Java 17.
К моменту выпуска Java 9 Eclipse Collections обновили FastList (начиная с EC 8.1) и ImmutableArrayList (начиная с EC 9.0), чтобы иметь пользовательские переопределения spliterator. Однако сегодня в Eclipse Collections все еще есть классы, которые будут использовать реализацию по умолчанию spliterator, которая возвращает RandomAccessSpliterator, включая класс с именем ArrayListAdapter.
Я решил запустить те же тесты, что и более 6 лет назад, только на этот раз с использованием Java 17 с java.util.ArrayList и ArrayListAdapter из Eclipse Collections, чтобы увидеть, имеет ли parallelStream достаточно схожие характеристики производительности.
Результаты оказались примерно такими, как я и ожидал. ArrayListAdapter является оболочкой для экземпляра ArrayList, поэтому я ожидал, что это потребует дополнительных затрат из-за необходимости делегировать все вызовы базовому экземпляру ArrayList. Тем не менее, RandomAccessSpliterator, похоже, неплохо справляется со своей задачей. ArrayList имеет специализированное переопределение spliterator, которое возвращает ArrayListSpliterator, и оно не сильно отличается от RandomAccessSpliterator в этом тесте.
Я провел эти тесты на четырехъядерном процессоре Intel Core I7 MacBook Pro с тактовой частотой 2,7 ГГц (начало 2013 г.), работающем со следующими JDK и версией JMH.
# Версия JMH: 1.35
# Версия VM: JDK 17, 64-разрядная виртуальная машина OpenJDK Server, 17+35–2724
Исходный код тестов находится здесь.
Размышления о дороге менее путешествовали
Будь готов
Предложение и внесение изменений в OpenJDK требует серьезного терпения, времени и усилий. Эта история демонстрирует, что вполне возможно внести свой вклад в OpenJDK, но это может быть не в те сроки, которые вы ожидаете. У меня также несколько раз были отвергнутые идеи. Это не личное. JDK используется миллионами разработчиков уже более четверти века для написания и запуска миллионов приложений. Разработчики, поддерживающие эту удивительную кодовую базу, являются экспертами, и мы должны быть осторожны, чтобы не тратить их время попусту.
Вы должны отправить свои идеи в качестве предложения в список рассылки core-libs-dev. Сначала поищите, чтобы увидеть, была ли ваша идея уже предложена и/или реализована.
Возможно, у вас есть отличная идея, и она все равно может быть отвергнута. Разработчики OpenJDK должны понять и взвесить компромисс между затратами и выгодами. Ваша потрясающая идея может быть признана не практичной и слишком дорогой.
Многие идеи не реализуются, и это совершенно нормально
Вот пример предложенной мной идеи, которая еще не реализована и, возможно, никогда не будет реализована, так как может быть просто непрактичной или не окупающей затрат. Разработчик, который ответил на мое первоначальное предложение, Claes Redestad, был чрезвычайно вдумчивым и полезным в своих ответах в списке рассылки. Он даже построил доказательство концепции метода в запросе на включение с некоторыми тестами. Я очень благодарен ему за время, которое он потратил на изучение моей идеи.
Есть мнение, что люди, которые постоянно работают с кодовой базой OpenJDK, имеют то, что обычные разработчики, кодирующие Java, могут не полностью понять или оценить. Будьте готовы к тому, что ваша идея будет оспорена, и, возможно, вы узнаете, что в этом простом примере кода, который вы предоставили, скрывается что-то более сложное или запутанное.
В случае String.join я узнал, что код, который я рассматривал в выпуске JDK 17, на самом деле не был кодом, который в настоящее время находится в репозитории OpenJDK, готовящимся для JDK 18. Теперь вы можете увидеть разницу для String.join между JDK 18 и JDK. 17».
Начните с малого и оставайтесь сосредоточенными
Я рекомендую предлагать изменения, улучшения и исправления ошибок в JDK: начинайте с малого и сосредоточьтесь. Если вы что-то увидели, а затем набрались смелости, чтобы что-то сказать, будьте готовы что-то доказать, а если вы преодолеете этот момент, будьте готовы взять на себя обязательство что-то сделать. Как только вы добьетесь успеха в нескольких небольших победах, вы сможете перейти к более крупным изменениям.
Дорога может занять больше времени, чем вы ожидаете, но конечный пункт может стоить того. Я могу сказать вам, что после девяти лет ожидания и, наконец, экспериментов с производительностью RandomAccessSpliterator в Java 17 и просмотра ожидаемых результатов время, которое я потратил и ждал, того стоило.
Спасибо, Хироши, Пол, Брайан, Дуг, Клас, вся команда OpenJDK и все члены экспертной группы JSR 335.
Я являюсь создателем и участником проекта OSS Eclipse Collections, которым управляет Eclipse Foundation. Коллекция Eclipse открыта для пожертвований.
