Кирилл Епифанов

21 Июн 2024

Теги:

#Knowledge #Java

Побитовые проверки в Java и почему они так неоднозначны

21 Июн 2024

Автор: Кирилл Епифанов

Перед тем как начнём
С чего всё началось
Операторы и их разница
Чем дальше в лес...
Почему всё-таки плохо?
Заключение

Операторы "&" и "|" не вызывают вопросов, когда применяются в подходящих ситуациях. Но знаете ли вы о всех последствиях использования побитовых операторов вместо логических в Java? В этой статье мы рассмотрим как плюсы производительности такого подхода, так и минусы его читабельности.

Перед тем как начнём

Это третья и заключительная статья, написанная после проверки 24-ой версии DBeaver статическим анализатором PVS-Studio. Он нашёл несколько подозрительных мест, зацепивших нашу команду разработки достаточно для того, чтобы мы выделили их в разные статьи. Если вы не видели остальные, то вот их список для ознакомления:

Ловушки volatile, DCL и синхронизации в Java
Как шаблонный метод может сломать ваш Java код
Побитовые проверки и почему они так неоднозначны (эта статья)

С чего всё началось

Рассматривая срабатывания проекта, мы столкнулись со срабатыванием статического анализатора на логические выражения с использованием побитовых операций в блоке if. По мнению анализатора, это подозрительный код, на который выдавалось предупреждение второго (medium) уровня V6030. Представлю вам несколько сообщений PVS-Studio:

Файл ExasolSecurityPolicy.java(123)

public ExasolSecurityPolicy(....) {
  ....
  String value = JDBCUtils.safeGetString(dbResult, "SYSTEM_VALUE");
  
  if (value.isEmpty() | value.equals("OFF"))
    this.enabled = false;
  } else {
    assignValues(ExasolSecurityPolicy.parseInput(value));
  }
}

Анализатор сигнализирует о том, что метод value.equals("OFF") вызовется даже в случае, если value.isEmpty() окажется true, что бессмысленно. Сообщение анализатора:

V6030 The method located to the right of the '|' operator will be called regardless of the value of the left operand. Perhaps, it is better to use '||'.

Файл ExasolConnectionManager.java(151)

@Override
protected void addObjectModifyActions(....) {
  ....
  // url, username or password have changed
  if (com.containsKey("url") | com.containsKey("userName") |
      com.containsKey("password"))
  {
    // possible loss of information - warn
    ....
    if (!(con.getUserName().isEmpty() | con.getPassword().isEmpty())) {
      ....
    }
  }
}

А здесь подряд идут проверки Map'ы com на ключи url, userName или password, после чего проверяется отсутствие одного из параметров подключения в таком же стиле. И мы получаем идентичное прошлому случаю сообщение:

V6030 The method located to the right of the '|' operator will be called regardless of the value of the left operand. Perhaps, it is better to use '||'.

Из документации анализатора PVS-Studio следует, что справа от побитового оператора находится возвращающая boolean значение функция, что, возможно, является опечаткой. Меня заинтересовал такой стиль кода. Ведь если бы это срабатывание было одним, то можно было бы подумать, что это опечатка. Однако в проекте набралось 16 таких мест, и мне стало интересно, нет ли в таком паттерне двойного дна.

Операторы и их разница

Немного погрузимся в теорию. Не будем обсуждать весь большой список операторов в Java, а перейдём сразу к нужным нам побитовым и логическим:

&& — логическое И
|| — логическое ИЛИ
& — побитовое И
| — побитовое ИЛИ

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

public static void main(String[] args) {
    // updateA() и updateB() всегда выполнятся
    if (updateA() & updateB()) { 
      // Что-то делаем
    }
}

public boolean updateA() {
    // Меняем состояние...
    return ....;
}

public boolean updateB() {
    // Меняем состояние...
    return ....;
}

Если же мы заменим побитовый оператор на логический, и первое условие вернёт false, то выполнение проверок остановится. Попробуем пофантазировать и продолжим приводить примеры, меняющие внутреннее состояние. В следующем коде, если prepareConnection() вернёт false, то метод establishConnection() выполняться не будет.

public static void main(String[] args) {
    // establishConnection() выполнится только если prepareConnection() -> false
    if (prepareConnection() && establishConnection()) { 
        ....
    }
}

public boolean prepareConnection() {
    ....
}

public boolean establishConnection() {
    ....
}

Т.е. если оператор, вычислив левый аргумент, уже может утверждать о значении операции, то второй аргумент оператора не вычисляется за ненадобностью. Этот механизм называется вычислением по короткой схеме (short-circuit evaluation). Возможно, самым частым использованием short-circuit являются проверки на null перед использованием переменной:

public boolean testString(String str) {
    return str != null && str.equals("test");
}

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

Чем дальше в лес...

Ещё глубже погрузимся в детали... Оказывается, что побитовая операция в зависимости от ситуации может выполняться быстрее, чем логическая. Это, в частности, обусловлено отсутствием у этого оператора механизма предсказания ветвлений (branch prediction).

Предсказание ветвления (branch prediction) — модуль, входящий в состав процессора. Позволяет осуществлять предварительную выборку инструкций, а также выполнять инструкции, находящиеся после условного перехода (например, блок if), до того, как он будет выполнен. Предсказатель переходов является неотъемлемой частью всех современных процессоров c конвейерной архитектурой и позволяет оптимально использовать вычислительные ресурсы.

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

Итак, современные процессоры имеют конвейерную архитектуру выполнения команд. Каждая исполняемая инструкция имеет несколько состояний: выборка, декодирование, исполнение и сохранение.

Выборка (Fetch): инструкция передаётся из памяти в процессор;
Декодирование (Decoding): процессор расшифровывает команду;
Исполнение (Executing): происходит выполнение операции;
Сохранение (Saving): сохраняем результат операции.

Внутри процессора разные операции могут выполнятся параллельно: пока одна инструкция выполняется, другая может передаваться из памяти в процессор. Это можно проиллюстрировать следующей таблицей:

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

Поэтому современные процессоры пытаются предсказать поток выполнения программы и предугадать команды, которые должны выполниться дальше. Это позволяет оптимизировать выполнение кода, если оно не подразумевается. Например:

private boolean debug = false;

public void test(....) {
    ....
    if (debug) {
        log("....");
    }
    ....
}

В представленной ситуации процессор (компилятор и JVM тоже могут внести свои коррективы, но сейчас мы вынесем их за скобки) с очень большой вероятностью может предсказать, что вызов метода log не случится, и просто не подготавливаться к выполнению этого кода, исходя из статистики выполнения. Но в случае, если процессор все-таки ошибётся (произойдёт промах), конвейер придётся пересобрать, и это может стоить нам производительности.

Этого механизма лишены побитовые операции: они не подразумевают ветвления и лишены его накладных расходов.

Чтобы в этом удостовериться, я прогнал небольшой бенчмарк, основанный на исходном коде, предоставленном разработчиком с ником Rostor (источник).

Код

Загрузил на GitHub Gist

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

Результаты исследования на моём ПК меня удивили. Кажется, что в среднем в тесте без использования функциональных интерфейсов и других примочек ООП побитовые операции выполнятся быстрее логических аж на 40 процентов. Предлагаю ознакомиться с диаграммой, показывающей затраченное время для каждого отдельного вида операций:

В тесте мы сравниваем как отдельно конъюнкции и дизъюнкции, так и всё вместе. Для удобства просмотра вверху представлены самые тяжёлые. И один вывод можно сделать сразу: логические операторы в этой ситуации оказались явно медленнее.

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

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

Почему всё-таки плохо?

Возможно, прочитав всю эту информацию, вы можете задаться вопросом: "А зачем эта диагностика существует в вашем анализаторе, если такой код может выполняться быстрее, и даже если программист опечатался, это просто code smell?"

Но всё же я, как ни странно, противник такого кода, и вот почему:

Во-первых, я покажу вам два интересных срабатывания из этого же проекта, которые были найдены вместе с остальными "ложными".

Файлы ExasolTableColumnManager.java(79), DB2TableColumnManager.java(77)

@Override
public boolean canEditObject(ExasolTableColumn object) {
    ExasolTableBase exasolTableBase = object.getParentObject();
    if (exasolTableBase != null &
        exasolTableBase.getClass().equals(ExasolTable.class)) {
        return true;
    } else {
        return false;
    }
}

V6030 The method located to the right of the '&' operator will be called regardless of the value of the left operand. Perhaps, it is better to use '&&'.

Используя такую практику, мы создаём пространство для ошибки с NullPointerExeption.

В этом случае нужно учитывать побочные эффекты и быть внимательными. Иногда можно просто не заметить, что вы пишете код неправильно. В случае выше, если параметр exasolTableBase окажется null, то произойдёт исключение. И что-то мне подсказывает, что разработчик не хотел падения программы при простой проверке возможности редактирования :)

Ко всему прочему, один из разработчиков скопировал код с ошибкой и утянул её в другой программный модуль. Добавляем к списку грехов ещё и Copy-Paste. Именно поэтому выше указаны два файла с ошибками.

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

Например, как в этом случае, который также нашёл анализатор:

Файл: ExasolDataSource.java(950)

@Override
public ErrorType discoverErrorType(@NotNull Throwable error) {
  String errorMessage = error.getMessage();
  if (errorMessage.contains("Feature not supported")) {
    return ErrorType.FEATURE_UNSUPPORTED;
  } else if (errorMessage.contains("insufficient privileges")) {
    return ErrorType.PERMISSION_DENIED;
  } else if (
      errorMessage.contains("Connection lost") | 
      errorMessage.contains("Connection was killed") | 
      errorMessage.contains("Process does not exist") | 
      errorMessage.contains("Successfully reconnected") | 
      errorMessage.contains("Statement handle not found") |
      ....
      )
  {
    return ErrorType.CONNECTION_LOST;
  }
  return super.discoverErrorType(error);
}

V6030 The method located to the right of the '|' operator will be called regardless of the value of the left operand. Perhaps, it is better to use '||'.

В этом методе разработчик проверяет строку errorMessage и возвращает тип ошибки. И всё как бы хорошо, но в else if он применяет битовый оператор, отказываясь от оптимизации с короткой схемой вычисления. Очевидно, это плохо, ведь при нахождении любой подстроки мы могли бы перейти сразу к return вместо проверки остальных вариантов.

Третье, но не факт, что это вообще будет работать у вас. А даже если и будет, то это микро оптимизация на несколько наносекунд.

Четвёртое: синтетический тест, описанный выше, работает из-за того, что предоставленные значения имеют нормальное распределение и закономерности за ними не наблюдаются. В тесте предсказание ветвлений работает только в худшую сторону.

Если же предсказатель ветвлений будет работать правильно, побитовые операции не смогут догнать по скорости логические. Это очень специфичный кейс.

Суммируя всё вышеперечисленное, последним минусом будет то, что с точки зрения стиля написания кода постоянные побитовые проверки кажутся странной затеей. Особенно если в коде ведётся реальная работа с побитовыми операциями. Несложно представить лицо современного Java-программиста, увидевшего побитовый оператор в if во время ревью или правок:

Заключение

На этом всё. Я провёл исследование вопроса актуальности паттерна замены логических операторов на побитовые, а также диагностики нашего анализатора. А вы узнали ещё немного о нашем любимом языке Java и практиках его использования =)

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

#Knowledge #Java