关于设计绝对值abs的一些思考

本文最后更新于:2021年9月18日 下午

关于设计绝对值abs的一些思考

取绝对值」对于 Integer 毫无疑问直接判断正负

  • Math::abs(int)
1
2
3
public static int abs(int a) {
return (a < 0) ? -a : a;
}

注意到双精度浮点数 Double 官方使用以下实现

  • Math::abs(double)
1
2
3
public static double abs(double a) {
return (a <= 0.0D) ? 0.0D - a : a;
}

Java 遵循 IEEE-754 标准,因此实现上存在 +0.0 & -0.0,两者除了文本表示不同,在计算过程中也不同。如:1 / +- 0.0 得到的结果是 +Infinity & -Infinity

  • abs 计算结果仍然是负数,出现错误,原因既是 +0.0 == -0.0
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public static void main(String[] args) {
double x = -0.0;
if (1 / abs(x) < 0) {
System.out.println("abs(x) < 0");
}
}
public static double abs(double a) {
return (a < 0) ? -a : a;
}
}

尝试解决问题,添加判断条件:if (val < 0 || val == -0.0)-0.0 单独考虑,进行双重判断,这里采用 Double::compare(double, double) 实现

  • 成功实现
1
2
3
4
5
6
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 进行额外的四次比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int compare(double d1, double d2) {
if (d1 < d2)
return -1; // Neither val is NaN, thisVal is smaller
if (d1 > d2)
return 1; // Neither val is NaN, thisVal is larger

// Cannot use doubleToRawLongBits because of possibility of NaNs.
long thisBits = Double.doubleToLongBits(d1);
long anotherBits = Double.doubleToLongBits(d2);

return (thisBits == anotherBits ? 0 : // Values are equal
(thisBits < anotherBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
1)); // (0.0, -0.0) or (NaN, !NaN)
}

而实际上,要想实现只需要 Double::doubleToLongBits 方法,将 DoubleLong

1
2
3
4
5
6
7
8
9
10
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;
}

不过 Double::doubleToLongBits 也只有微不足道的性能提升,因为它会对 NaN 进行约束,NaN 会赋值为 0x7ff8000000000000L ,如果确保 abs 入参肯定是 double,则只需要取出 Double::doubleToRawLongBits

1
2
3
4
5
6
public static long doubleToLongBits(double value) {
if (!isNaN(value)) {
return doubleToRawLongBits(value);
}
return 0x7ff8000000000000L;
}

于是就变成这样实现

1
2
3
4
5
6
7
8
9
10
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;
}

JDK8 就结束了,而 JDK9 开始引入 @HotSpotIntrinsicCandidate 注解,即 HotSpot JVM 内部的 JIT compiler 会移除 JDK 中的实现方法,采用 CPU 指令直接实现,这会比高级语言转汇编转机器语言要快很多,毕竟 CPU 并不会在乎数据类型的问题,只需要重新解释(reinterpreting) 储存在 CPU 寄存器的一组位的问题,以便于与 Java 数据类型一致。

1
2
@HotSpotIntrinsicCandidate
public static native long doubleToRawLongBits(double value);

但这么实现,仍然有条件分支,如果 CPU 分支预测(branch predictor) 失误,性能开销就会增大。接下来考虑减少条件分支。

利用 0.0+/0.0 作差,都会使正负零转化为正零

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

对方法进行改写

1
2
3
4
5
6
7
8
9
public static double abs(double value) {
if (value == 0) {
return 0.0 - value;
}
if (value < 0) {
return -value;
}
return value;
}

注意到对于普通负数而言,0.0 - value-value 的结果相同,所以合并分支

1
2
3
4
5
6
public static double abs(double value) {
if (value <= 0) {
return 0.0 - value;
}
return value;
}

AKA

1
2
3
public static double abs(double a) {
return (a <= 0.0) ? 0.0 - a : a;
}
  • 会发现,JDK Math::abs(double,double) 实现相同(逃

遵循 IEEE-754 的双精度浮点数二进制表达形式,只需要将二进制在高位符号位改成 0 即可实现转正数(abs),需要掩码 0x7fffffffffffffffL == 63位 1 bit

1
System.out.println(Long.bitCount(0x7fffffffffffffffL)); // 63

最终实现

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

📌此版本不存在分支,在某些条件下的吞吐量增加 **10%**,单分支实现在 Java 标准库存在多年,在随即到来的 JDK 18 中,改进版本已经提交「From: 2021/9/18」

然而在许多情况下,这些改进并没有太大意义,因为 JIT 编译器会适当使用汇编指令(if available) 会完全替代 Java code,所以这种改动并不能使程序显著性提升很多(逃

🔗Reference

One does not simply calculate the absolute value

OpenJDK Double::compare

JavaSE 8 doubleToLongBits


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!