Влияние потоков Java на производительность при обходе матрицы
У меня есть две версии кода для диагонального перемещения матрицы MxN. По-видимому, даже с той же (плохой) логикой обхода версия, использующая Java Streams, работает в 5 раз медленнее, чем та, которая этого не делает.
Ограничения:
- 1 <= М, Н <= 10^4
- 1 <= М * Н <= 10^4
Версия 1: Использование циклов for:
public int[] findDiagonalOrder(int[][] mat) {
int M = mat.length;
int N = mat[0].length;
int[] traversal = new int[M * N];
int s = 0;
for(int sum=0; sum < M+N; sum++) {
for(int k=0; k<=sum; k++) {
int row = (sum%2 == 0) ? sum - k : k;
if (row < M && (sum-row < N))
traversal[s++] = mat[row][sum-row];
}
}
return traversal;
}
Версия 2: Использование потоков Java:
public int[] findDiagonalOrder(int[][] matrix) {
int M = matrix.length;
int N = matrix[0].length;
return IntStream.range(0, M+N)
.flatMap(sum -> IntStream.rangeClosed(0, sum)
.filter(i -> {
int row = (sum%2 == 0) ? (sum-i) : i;
return row < M && (sum - row) < N;
})
.map(i -> (sum%2 == 0) ? matrix[sum-i][i] : matrix[i][sum-i]))
.toArray();
}
Версия №1 выполняется примерно за 353 мс, а версия №2 — за 1500 мс. Я хотел понять, что вызывает такое ухудшение производительности? Я даже не использую Boxing/Unboxing, что могло повлиять.
PS: Я понимаю, что есть лучший способ обхода матрицы в O(M*N), но мой вопрос касается потоков.
Потоки имеют огромные накладные расходы, и всякий раз, когда вы можете избежать этого и должны следить за производительностью, избегайте. Есть веские причины полагаться на потоки, например, для обработки большого количества постоянных данных или использовать параллелизм (также разумный только для тысяч элементов данных), но в целом, просто обрабатывая небольшие наборы данных, потоки только удобны, но ничего не дают. все исполнительно.
Кроме того, как видите, вы делаете sum%2 == 0 дважды. Возможно, компилятор сможет это решить в определенной степени, для этого вам придется более глубоко изучить байт-код, но в конечном итоге при матричных вычислениях все сводится к минимизации операций и обеспечению максимальной работы кэша.
@Slevin - Вам нужно будет посмотреть собственный код. JIT-компилятор берет на себя всю тяжелую работу по оптимизации кода.
@StephenC Значит, байт-код не говорит правду об окончательной оптимизации? Я думал, что такие простые вещи, как двойное обнаружение операции, будут выполняться во время компиляции в байт-код, а оптимизацию под процессор, конечно, может сделать только JIT-компилятор. Спасибо. В любом случае, поскольку автор вопроса пытается снизить производительность, следует отметить, что в его случае правильное расположение примитивов Java в массиве для правильной выборки кэша является обязательным не только в C, но и в Java. (Вы не можете выполнить такую подготовку на языках сценариев, таких как JS или Python)
«Значит, байт-код не говорит правду об окончательной оптимизации?» - Правильный!!
@Слевин, глядя на байт-код, ты можешь узнать одну вещь. Дело в том, что в данной конкретной ситуации невозможно устранить избыточность двух sum%2 в байт-коде. Причина в том, что две ссылки на sum будут относиться к разным переменным на уровне байт-кода (поскольку это два случая захвата одного и того же значения, но в разных лямбда-выражениях).
Ответы 1
Я хотел понять, что вызывает такое ухудшение производительности?
Короткий ответ, вероятно, заключается в накладных расходах потока.
Производительность не является основной целью потоков Java. В текущих версиях Java компиляторы (пока) не способны преобразовывать потоковый код в собственный код, который работает так же хорошо, как классические циклы. В будущем это может измениться. Однако для того, чтобы это произошло, потребуются значительные усилия в области исследований и разработок, и (AFAIK) в настоящее время это не является приоритетом для команды Java.
Таким образом, упрощенное «следствие» заключается в том, что если производительность1 является наиболее важным требованием для данного фрагмента кода2, вам не следует использовать потоки в решении.
Я даже не использую Boxing/Unboxing, что могло повлиять.
Не явно. Но это могло происходить под одеялом. Единственный способ быть абсолютно уверенным — проанализировать весь собственный код, сгенерированный JIT-компилятором3. Профилирование вашего теста также может дать вам ответ... если ответ заключается в том, что за кулисами >есть< бокс/распаковка.
Наконец, поскольку вы не показали нам свой полный тест, вполне возможно, что ваши результаты (353 мс против 1500 мс) не отражают то, как соответствующий код будет работать в производственном контексте. Читать Как мне написать правильный микротест на Java? и различные источники, на которые ссылаются ответы.
1 - Actual performance right now, rather than potential performance in the future.
2 - However this is typically NOT the case. Even in a performance critical application, most of the lines of code for that application don't have significant impact on overall performance.
3 - Bytecodes do not give a reliable indication of code performance. Optimization is done by the JIT compiler not the bytecode compiler. There could potentially be instructions to do boxing and unboxing in the bytecodes that are completely optimized away in the native code.
Потоки имеют накладные расходы. Добавьте
RuntimeExceptionиз методаpeek(), и вы увидите, что у вас есть несколько глубоких вызовов метода: в отличие от ни одного в вашем случае версии № 1.