Нельзя так просто взять и вычислить абсолютное значение

Кажется, задача вычисления абсолютного значения (или модуля) числа совершенно тривиальна. Если число отрицательно, давайте сменим знак. Иначе оставим как есть. На Java это будет выглядеть примерно так:

public static double abs(double value) {
  if (value < 0) {
    return -value;
  }
  return value;
}

Вроде бы это слишком просто даже для вопроса на собеседовании на позицию джуна. Есть ли тут подводные камни?

Телеграм канал — Библиотека Java разработчика

Вспомним, что в стандарте IEEE-754 вообще и в Java в частности есть два нуля: +0.0 и -0.0. Это такие братья-близнецы, их очень легко смешать и перепутать, но вообще-то они разные. Разница проявляется не только в текстовом представлении, но и в результате выполнения некоторых операций. Например, если поделить единицу на +0.0 и -0.0, то мы получим кардинально разные ответы: +Infinity и -Infinity, отличие между которыми уже сложно игнорировать. Однако, например, в операциях сравнения +0.0 и -0.0 неразличимы. Поэтому реализация выше не убирает минус у -0.0. Это может привести к неожиданным результатам. Например:

double x = -0.0;
if (1 / abs(x) < 0) {
  System.out.println("oops");
}

Казалось бы, обратное к модулю x число не может быть отрицательным, какое бы ни было x. Но в данном случае может. Если у вас есть садистские наклонности, попросите джуна на собеседовании написать метод abs. Когда же он выдаст код вроде того что в начале статьи, можете спросить, выполнится ли при каком-нибудь x условие 1 / abs(x) < 0. После таких собеседований про вашу компанию будут ходить легенды.

Ну ладно, проблему мы нашли. А как её исправить? Наивно добавить if (value < 0 || value == -0.0) не получится, потому что +0.0 == -0.0. В итоге мы сделаем ещё хуже: теперь будет выдаваться -0.0 для положительного нуля на входе. Чтобы надёжно отличить отрицательный нуль, есть метод Double.compare:

public static double abs(double value) {
  if (value < 0 || Double.compare(value, -0.0) == 0) {
    return -value;
  }
  return value;
}

Это работает. Но метод становится ужасно медленным для такой тривиальной операции. Double.compare устроен не так уж просто, нам потребуется пара дополнительных сравнений для положительного числа, три сравнения для -0.0 и целых четыре сравнения для +0.0. Если посмотреть на реализацию Double.compare, можно понять, что нам нужна только часть связанная с doubleToLongBits. Этот метод реинтерпретирует битовое представление double-числа как битовое представление long-числа (и там, и там восемь байт). А со сравнением целых чисел никаких сюрпризов нет. Поэтому можно упростить так:

private static final long MINUS_ZERO_LONG_BITS =
  Double.doubleToLongBits(-0.0);

public static double abs(double value) {
  if (value < 0 ||
      Double.doubleToLongBits(value) == MINUS_ZERO_LONG_BITS) {
    return -value;
  }
  return value;
}

Однако, оказывается, doubleToLongBits тоже не совсем тривиален, потому что он канонизирует NaN’ы. Есть много способов закодировать not-a-number в виде double, но только один из них канонический. Эти разные NaN’ы совсем-совсем близнецы, их не отличишь ни сравнением через Double.compare, никакой операцией, ни строковым представлением. Но в памяти компьютера они выглядят по-разному. Чтобы не было сюрпризов, doubleToLongBits приводит любой NaN к каноническому виду, который записывается в long как 0x7ff8000000000000L. Конечно, это лишние проверки, которые нам здесь тоже не нужны.

Что же делать? Оказывается, можно использовать doubleToRawLongBits, который никаких умностей с NaN‘ами не делает и возвращает всё как есть:

private static final long MINUS_ZERO_LONG_BITS =
  Double.doubleToRawLongBits(-0.0);

public static double abs(double value) {
  if (value < 0 ||
      Double.doubleToRawLongBits(value) == MINUS_ZERO_LONG_BITS) {
    return -value;
  }
  return value;
}

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

Ладно, у нас осталось два ветвления для всех положительных чисел и нулей. Всё равно кажется, что много. Мы знаем, что ветвления — это плохо, если branch predictor не угадает, они могут очень дорого стоить. Можно ли сделать меньше? Оказывается, можно любой нуль превратить в положительный, если вычесть его из 0.0:

System.out.println(0.0-(-0.0)); // 0.0
System.out.println(0.0-(+0.0)); // 0.0

Таким образом, можно написать:

public static double abs(double value) {
  if (value == 0) {
    return 0.0 - value;
  }
  if (value < 0) {
    return -value;
  }
  return value;
}

Зачем так сложно, спросите вы. Ведь можно просто вернуть 0.0 в первом условии. Кроме того, у нас всё равно два сравнения. Однако можно заметить, что для обычных отрицательных чисел 0.0 - value и просто -value дают одинаковый результат. Поэтому первые две ветки легко слопнуть в одну:

public static double abs(double value) {
  if (value <= 0) {
    return 0.0 - value;
  }
  return value;
}

Отлично, у нас теперь всегда одна ветка. Победа? Но как насчёт сделать всегда ноль веток? Возможно ли это?

Если посмотреть на представление числа double в стандарте IEEE-754, можно заметить, что знак — это просто старший бит. Соответственно, нам нужно просто безусловно сбросить этот старший бит. Остальная часть числа при выполнении этой операции не меняется. В этом плане дробные числа даже проще целых, где отрицательные превращаются в положительные через двоичное дополнение. Сбросить старший бит можно через операцию & с правильной маской. Но для этого надо интерпретировать дробное число как целое (и мы уже знаем как это сделать), а потом интерпретировать назад (для этого есть longBitsToDouble, и он тоже практически бесплатный):

public static double abs(double value) {
  return Double.longBitsToDouble(
    Double.doubleToRawLongBits(value) & 0x7fffffffffffffffL);
}

Этот способ действительно не содержит ветвлений, и профилирование показывает, что пропускная способность метода при определённых условиях увеличивается процентов на 10%. Предыдущая реализация с одним ветвлением была в стандартной библиотеке Java с незапамятных времён, а вот в грядущей Java 18 уже закоммитили улучшенную версию.

В ряде случаев, впрочем, эти улучшения ничего не значат, потому что JIT-компилятор может использовать соответствующую ассемблерную инструкцию при её наличии и полностью проигнорировать Java-код. Например, на платформе ARM используется инструкция VABS. Так что пользы тут мало. Но всё равно интересная статья получилась!

Возможно вам будет интересно:

Java фреймворк (Frameworks)- подборка для программистов на 2021

Подборка Java книг за 2018 год, топ книг для разработчика

 

 

источник