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

Kate

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


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

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

Вспомним, что в стандарте 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. Так что пользы тут мало. Но всё равно интересная статья получилась!

 
Сверху