Кажется, задача вычисления абсолютного значения (или модуля) числа совершенно тривиальна. Если число отрицательно, давайте сменим знак. Иначе оставим как есть. На 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. Так что пользы тут мало. Но всё равно интересная статья получилась!
habr.com
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. Так что пользы тут мало. Но всё равно интересная статья получилась!
Нельзя так просто взять и вычислить абсолютное значение
Кажется, задача вычисления абсолютного значения (или модуля) числа совершенно тривиальна. Если число отрицательно, давайте сменим знак. Иначе оставим как есть. На Java это будет выглядеть примерно...
habr.com