Написано в сотрудничестве с Питером Лоури .
Несколько дней назад у меня возникла серьезная проблема с производительностью сортировки с использованием нового декларативного стиля Java8. Смотрите блог пост здесь . В этом посте я только указал на проблему, но в этом посте я собираюсь углубиться в понимание и объяснение причин проблемы. Это будет сделано путем воспроизведения проблемы с использованием декларативного стиля и постепенного изменения кода до тех пор, пока мы не удалим проблему производительности и не останемся с производительностью, которую мы ожидаем, используя сравнение старого стиля.
Напомним, мы сортируем экземпляры этого класса:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
|
private static class MyComparableInt{ private int a,b,c,d; public MyComparableInt(int i) { a = i%2; b = i%10; c = i%1000; d = i; } public int getA() return a; public int getB() return b; public int getC() return c; public int getD() return d;} |
Используя декларативный стиль Java 8 (ниже), потребовалось ~ 6 секунд для сортировки 10-метровых экземпляров:
|
1
2
3
4
5
6
|
List mySortedList = myComparableList.stream() .sorted(Comparator.comparing(MyComparableInt::getA) .thenComparing(MyComparableInt::getB) .thenComparing(MyComparableInt::getC) .thenComparing(MyComparableInt::getD)) .collect(Collectors.toList()); |
Использование сортировщика (см. Ниже) заняло ~ 1,6 с для сортировки 10 млн экземпляров.
Это код вызова для сортировки:
|
1
2
3
|
List mySortedList = myComparableList.stream() .sorted(MyComparableIntSorter.INSTANCE) .collect(Collectors.toList()); |
Используя этот собственный компаратор:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
|
public enum MyComparableIntSorter implements Comparator<MyComparableInt>{ INSTANCE; @Override public int compare(MyComparableInt o1, MyComparableInt o2) { int comp = Integer.compare(o1.getA(), o2.getA()); if(comp==0){ comp = Integer.compare(o1.getB(), o2.getB()); if(comp==0){ comp = Integer.compare(o1.getC(), o2.getC()); if(comp==0){ comp = Integer.compare(o1.getD(), o2.getD()); } } } return comp; } } |
Давайте создадим метод comparing в нашем классе, чтобы мы могли более тщательно анализировать код. Причина метода comparing заключается в том, что мы можем легко менять реализации, но оставить вызывающий код прежним.
Во всех случаях так будет вызываться метод comparing :
|
1
2
3
4
5
6
7
|
List mySortedList = myComparableList.stream() .sorted(comparing( MyComparableInt::getA, MyComparableInt::getB, MyComparableInt::getC, MyComparableInt::getD)) .collect(Collectors.toList()); |
Первая реализация сравнения в значительной степени является копией в jdk.
|
01
02
03
04
05
06
07
08
09
10
|
public static <T, U extends Comparable<? super U>> Comparator<T> comparing( Function<? super T, ? extends U> ke1, Function<? super T, ? extends U> ke2, Function<? super T, ? extends U> ke3, Function<? super T, ? extends U> ke4) { return Comparator.comparing(ke1).thenComparing(ke2) .thenComparing(ke3).thenComparing(ke4); } |
Неудивительно, что для прохождения теста потребовалось ~ 6 секунд, но, по крайней мере, мы воспроизвели проблему и создали основу для продвижения вперед.
Давайте посмотрим на запись полета для этого теста:
Как видно, есть две большие проблемы:
- Проблема производительности в методе
lambda$comparing - Повторный вызов
Integer.valueOf(Integer.valueOf)
Давайте попробуем разобраться с первым, который находится в методе сравнения. На первый взгляд это кажется странным, потому что когда вы смотрите на код, в этом методе ничего особенного не происходит. Одна вещь, которая здесь происходит в основном, это поиск виртуальных таблиц, так как код находит правильную реализацию функции. Виртуальные таблицы используются, когда из одной строки кода вызывается несколько методов. Мы можем устранить этот источник задержки с помощью следующей реализации comparing . Расширяя все применения интерфейса Function каждая строка может вызывать только одну реализацию, и, следовательно, метод является встроенным.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
public static <T, U extends Comparable<? super U>> Comparator<T> comparing( Function<? super T, ? extends U> ke1, Function<? super T, ? extends U> ke2, Function<? super T, ? extends U> ke3, Function<? super T, ? extends U> ke4) { return (c1, c2) -> { int comp = compare(ke1.apply(c1), ke1.apply(c2)); if (comp == 0) { comp = compare(ke2.apply(c1), ke2.apply(c2)); if (comp == 0) { comp = compare(ke3.apply(c1), ke3.apply(c2)); if (comp == 0) { comp = compare(ke4.apply(c1), ke4.apply(c2)); } } } return comp; }; } |
Размотав метод, JIT должен иметь возможность встроить поиск метода.
Действительно, время почти вдвое сокращается до 3,5 с, давайте посмотрим на запись полета для этого прогона:
Когда я впервые увидел это, я был очень удивлен, потому что пока мы не сделали никаких изменений, чтобы уменьшить количество вызовов Integer.valueOf но этот процент упал! На самом деле здесь произошло то, что из-за изменений, которые мы внесли, чтобы разрешить встраивание, Integer.valueOf был встроен, а время, Integer.valueOf на Integer.valueOf , обвиняется в вызывающем ( lambda$comparing ), который встроил вызываемый ( Integer.valueOf ). Это распространенная проблема в профилировщиках, так как они могут ошибаться в отношении того, какой метод винить, особенно когда происходит встраивание.
Но мы знаем, что в предыдущей записи полета Integer.valueOf
было выделено, поэтому давайте удалим это с помощью этой реализации comparing и посмотрим, сможем ли мы сократить время еще больше.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
return (c1, c2) -> { int comp = compare(ke1.applyAsInt(c1), ke1.applyAsInt(c2)); if (comp == 0) { comp = compare(ke2.applyAsInt(c1), ke2.applyAsInt(c2)); if (comp == 0) { comp = compare(ke3.applyAsInt(c1), ke3.applyAsInt(c2)); if (comp == 0) { comp = compare(ke4.applyAsInt(c1), ke4.applyAsInt(c2)); } } } return comp;}; |
С этой реализацией время сокращается до 1,6 с, чего мы могли бы достичь с помощью специального компаратора.
Давайте снова посмотрим на запись полета для этого запуска:
Сейчас все время идет в реальных методах сортировки, а не в накладных.
В заключение мы узнали несколько интересных вещей из этого исследования:
- Использование новой декларативной сортировки Java8 в некоторых случаях будет в 4 раза медленнее, чем написание собственного компаратора, из-за стоимости автобоксирования и поиска виртуальных таблиц.
- Хотя FlightRecorder лучше других профилировщиков (см. Мой первый пост в блоге по этому вопросу), он все равно будет приписывать время неправильным методам, особенно когда происходит встраивание.
| Ссылка: | Java8 Lambdas: ошибка в сортировке производительности ОБЪЯСНЕНО от нашего партнера по JCG Дэниела Шая в блоге Rational Java . |