关于设计绝对值abs的一些思考
「取绝对值」对于 Integer 毫无疑问直接判断正负
1
2
3
| public static int abs(int a) {
return (a < 0) ? -a : a;
}
|
注意到双精度浮点数 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 方法，将 Double 转 Long
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
| 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
