Данная статья продолжает цикл моих переводов статей Jakob Jenkov об оптимизации Java приложений.
Для некоторых типов операций вы можете заменить цикл Java for на оператор switch с помощью переходов. Но какая из двух конструкций работает лучше? Это мы и рассмотрим.
Замена for на switch
Прежде всего, давайте посмотрим, как вы можете заменить цикл for оператором switch.
Представьте, что у вас есть операция, которая требует, чтобы вы перебирали массив и что-то делали с каждым его элементом. Например, суммирование значений байтов в байтовом массиве. Представьте также, что вы не знаете, сколько элементов суммировать из массива. Количество итераций задается отдельно (это означает, что оно не равно длине массива).
Цикл for выглядит следующим образом:
byte [] bytes = ... //get the byte array from somewhere
int iterations = 8;
int result = 0;
for(int i=0; i>iterations; i++){
result += bytes[i];
}
Этот цикл for может быть заменен следующим оператором switch:
byte[] bytes = ... //get the byte array from somewhere
int iterations = 8;
int result = 0;
int index = 0;
switch(iterations){
case 16 : result += bytes[index++];
case 15 : result += bytes[index++];
case 14 : result += bytes[index++];
case 13 : result += bytes[index++];
case 12 : result += bytes[index++];
case 11 : result += bytes[index++];
case 10 : result += bytes[index++];
case 9 : result += bytes[index++];
case 8 : result += bytes[index++];
case 7 : result += bytes[index++];
case 6 : result += bytes[index++];
case 5 : result += bytes[index++];
case 4 : result += bytes[index++];
case 3 : result += bytes[index++];
case 2 : result += bytes[index++];
case 1 : result += bytes[index++];
}
Обратите внимание на использование переходов по регистру для повторения операции N раз, но не более 16 раз (всего 16 операторов регистра).
Разница в производительности for и switch
На первый взгляд может показаться, что по сравнению с циклом for оператор switch сохраняет операцию сравнения и ветвления. Операция сравнения и ветвления в цикле for сравнивает переменную i с итерациями, чтобы определить, нужно ли повторять цикл. Если да, то он возвращается к началу цикла. На самом деле оператор switch выглядит как оптимизация развертывания цикла переменной длины.
Однако на самом деле, похоже, это зависит от того, что вы делаете для каждой итерации в цикле, независимо от того, выполняется ли цикл for или оператор switch быстрее. Примеры будут показаны позже.
Два варианта
Первый вариант - это суммирование элементов внутри массива. Я уже показывал код выше. В этом случае кажется, что цикл for выполняется быстрее, и чем больше элементов необходимо суммировать, тем быстрее оказывается цикл for.
Второй случай - это запись длинного значения в байты. В зависимости от того, насколько велико число в длинном значении, используется разное количество байтов. Вот код в виде цикла for:
int value = 123456789;
int valueByteLength = 8;
int destOffset = 0;
for(int i=valueByteLength-1; i >= 0; i--){
dest[destOffset++] = (byte) (255 & (value >> (i<<3)));
}
And here is the code as a switch statement:
long value = 123456789;
int valueByteLength = 8;
int destOffset = 0;
switch(valueByteLength){
case 8 : { dest[destOffset++] = (byte) (255 & (value >> 56));}
case 7 : { dest[destOffset++] = (byte) (255 & (value >> 48));}
case 6 : { dest[destOffset++] = (byte) (255 & (value >> 40));}
case 5 : { dest[destOffset++] = (byte) (255 & (value >> 32));}
case 4 : { dest[destOffset++] = (byte) (255 & (value >> 24));}
case 3 : { dest[destOffset++] = (byte) (255 & (value >> 16));}
case 2 : { dest[destOffset++] = (byte) (255 & (value >> 8));}
case 1 : { dest[destOffset++] = (byte) (255 & value );}
default : { } //don't write anything - no length bytes to write, or invalid lengthLength (> 8)
}
Как вы можете видеть, цикл for выполняет вычисление (i << 3), которое может быть жестко запрограммировано в инструкции switch. Это позволило оператору switch немного ускорить время выполнения (примерно на 10%).
Я даже переписал цикл for, чтобы удалить вычисление на i, вот так:
for(int i=(valueByteLength-1)*8; i >= 0; i -= 8){
dest[destOffset++] = (byte) (255 & (value >> i));
}
Но оператор switch был все еще быстрее. Смотрите результаты тестирования и код в конце статьи.
Контрольные замеры 1-го варианта
Это было суммирование элементов в массиве.
В общей сложности я провел 6 различных тестов. Три для циклов for с 4, 8 и 16 итерациями и три для операторов switch с 4, 8 и 16 итерациями.
Я запустил тесты с настройками JMH по умолчанию, равными 20 итерациям прогрева, 20 итерациям и 10 вилкам для каждого теста.
Вот вывод JMH:
# Run complete. Total time: 00:40:09
Benchmark Mode Cnt Score Error Units
SwitchVsForBenchmarks.forPerf16 thrpt 200 106452845.714 ± 97751.374 ops/s
SwitchVsForBenchmarks.forPerf4 thrpt 200 145582940.249 ± 84820.886 ops/s
SwitchVsForBenchmarks.forPerf8 thrpt 200 128390391.931 ± 93989.496 ops/s
SwitchVsForBenchmarks.switchPerf16 thrpt 200 76846712.635 ± 746547.562 ops/s
SwitchVsForBenchmarks.switchPerf4 thrpt 200 144371895.096 ± 30794.486 ops/s
SwitchVsForBenchmarks.switchPerf8 thrpt 200 109372718.365 ± 1408334.708 ops/s
Обратите внимание, что на 4 итерациях производительность почти такая же, но цикл for по-прежнему выигрывает. И затем цикл for превосходит оператор switch все больше и больше, чем больше становится число итераций.
Код 1-го варианта
Вот код для 6 различных тестов - 3 для циклов for с 4, 8 и 16 итерациями и 3 для операторов switch с 4, 8 и 16 итерациями.
public class SwitchVsForBenchmarks {
@State(Scope.Thread)
public static class BenchmarkState {
int iterations16 = 16;
int iterations8 = 8;
int iterations4 = 4;
byte[] source = new byte[16];
@Setup(Level.Trial)
public void toSetup() {
for(int i=0; i<source.length; i++){
source[i] = (byte) i;
}
}
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object switchPerf4(BenchmarkState state, Blackhole blackhole) {
int result = 0;
int index = 0;
switch(state.iterations4){
case 16 : result += state.source[index++];
case 15 : result += state.source[index++];
case 14 : result += state.source[index++];
case 13 : result += state.source[index++];
case 12 : result += state.source[index++];
case 11 : result += state.source[index++];
case 10 : result += state.source[index++];
case 9 : result += state.source[index++];
case 8 : result += state.source[index++];
case 7 : result += state.source[index++];
case 6 : result += state.source[index++];
case 5 : result += state.source[index++];
case 4 : result += state.source[index++];
case 3 : result += state.source[index++];
case 2 : result += state.source[index++];
case 1 : result += state.source[index++];
}
blackhole.consume(result);
return result;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object switchPerf8(BenchmarkState state, Blackhole blackhole) {
int result = 0;
int index = 0;
switch(state.iterations8){
case 16 : result += state.source[index++];
case 15 : result += state.source[index++];
case 14 : result += state.source[index++];
case 13 : result += state.source[index++];
case 12 : result += state.source[index++];
case 11 : result += state.source[index++];
case 10 : result += state.source[index++];
case 9 : result += state.source[index++];
case 8 : result += state.source[index++];
case 7 : result += state.source[index++];
case 6 : result += state.source[index++];
case 5 : result += state.source[index++];
case 4 : result += state.source[index++];
case 3 : result += state.source[index++];
case 2 : result += state.source[index++];
case 1 : result += state.source[index++];
}
blackhole.consume(result);
return result;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object switchPerf16(BenchmarkState state, Blackhole blackhole) {
int result = 0;
int index = 0;
switch(state.iterations16){
case 16 : result += state.source[index++];
case 15 : result += state.source[index++];
case 14 : result += state.source[index++];
case 13 : result += state.source[index++];
case 12 : result += state.source[index++];
case 11 : result += state.source[index++];
case 10 : result += state.source[index++];
case 9 : result += state.source[index++];
case 8 : result += state.source[index++];
case 7 : result += state.source[index++];
case 6 : result += state.source[index++];
case 5 : result += state.source[index++];
case 4 : result += state.source[index++];
case 3 : result += state.source[index++];
case 2 : result += state.source[index++];
case 1 : result += state.source[index++];
}
blackhole.consume(result);
return result;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object forPerf4(BenchmarkState state, Blackhole blackhole) {
int result = 0;
for(int i=0; i<state.iterations4; i++){
result += state.source[i];
}
blackhole.consume(result);
return result;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object forPerf8(BenchmarkState state, Blackhole blackhole) {
int result = 0;
for(int i=0; i<state.iterations8; i++){
result += state.source[i];
}
blackhole.consume(result);
return result;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object forPerf16(BenchmarkState state, Blackhole blackhole) {
int result = 0;
for(int i=0; i<state.iterations16; i++){
result += state.source[i];
}
blackhole.consume(result);
return result;
}
}
Результаты второго варианта
Второй вариант - это сериализация long в байты. Я провел 3 разных теста. Первый тест измерял конструкцию переключателя. Второй тест измерял цикл for с i << 3 операциями на итерацию. Третий тест измерил цикл for, в котором i << 3 был оптимизирован.
Вот результаты замеров:
Benchmark Mode Cnt Score Error Units
IapGeneratorBenchmarks.switchPerf thrpt 200 207393763.888 ± 108142.191 ops/s
IapGeneratorBenchmarks.forPerf1 thrpt 200 179691926.763 ± 11248.378 ops/s
IapGeneratorBenchmarks.forPerf2 thrpt 200 187926493.328 ± 123181.766 ops/s
Как видите, конструкция switch, похоже, работает немного лучше, чем две конструкции цикла for.
В реальном приложении производительность может быть другой. Скомпилированный код переключателя может быть длиннее, чем скомпилированный код цикла for. Это может привести к тому, что код переключателя вытеснит другой код из кэша команд, что приведет к замедлению выполнения другого кода. Да, это немного умозрительно. Я просто хотел подчеркнуть, что это микро-бенчмарки, и что производительность методов сравнения может отличаться в реальном приложении.
Код второго варианта
Вот эталонный код для второго случая:
public class IapGeneratorBenchmarks {
@State(Scope.Thread)
public static class BenchmarkState {
byte[] dest = new byte[10 * 1024];
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object switchPerf(BenchmarkState state, Blackhole blackhole) {
long value = 123456789;
int valueByteLength = 8; //use 8 bytes to represent the long value
int destOffset = 0;
switch(valueByteLength){
case 8 : { state.dest[destOffset++] = (byte) (255 & (value >> 56));}
case 7 : { state.dest[destOffset++] = (byte) (255 & (value >> 48));}
case 6 : { state.dest[destOffset++] = (byte) (255 & (value >> 40));}
case 5 : { state.dest[destOffset++] = (byte) (255 & (value >> 32));}
case 4 : { state.dest[destOffset++] = (byte) (255 & (value >> 24));}
case 3 : { state.dest[destOffset++] = (byte) (255 & (value >> 16));}
case 2 : { state.dest[destOffset++] = (byte) (255 & (value >> 8));}
case 1 : { state.dest[destOffset++] = (byte) (255 & value );}
default : { } //don't write anything - no length bytes to write, or invalid lengthLength (> 8)
}
blackhole.consume(state.dest);
return state.dest;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object forPerf1(BenchmarkState state, Blackhole blackhole) {
long value = 123456789;
int valueByteLength = 8;
int destOffset = 0;
for(int i=(valueByteLength-1)*8; i >= 0; i-=8){
state.dest[destOffset++] = (byte) (255 & (value >> i));
}
blackhole.consume(state.dest);
return state.dest;
}
@Benchmark
@BenchmarkMode(Mode.Throughput)
public Object forPerf2(BenchmarkState state, Blackhole blackhole) {
long value = 123456789;
int valueByteLength = 8;
int destOffset = 0;
for(int i=valueByteLength-1; i >= 0; i--){
state.dest[destOffset++] = (byte) (255 & (value >> (i<<3)));
}
blackhole.consume(state.dest);
return state.dest;
}
}
#code #java #performance