一种更快的实现 Math.abs(a - b) - Math.abs(c - d) 的方法是什么？

Question

我有一个Java方法，它在一个非常紧密的循环中重复评估以下表达式，并且重复次数非常大：

Math.abs(a - b) - Math.abs(c - d)

< p > a、b、c和d是可以跨越整个类型范围的long值。它们在每次循环迭代中都不同，并且我不知道它们是否满足任何不变量。

分析器表明，处理器时间的大部分用于此方法。虽然我将首先尝试其他优化方法，但我想知道是否有更聪明的方法来计算上述表达式。

除了手动内联Math.abs()调用以获得微小（如果有的话）性能增益外，是否有任何数学技巧可以加速评估此表达式？

- thkala

---

如果值跨越其类型的整个范围，那么如果a是一个非常大的负数，b是一个非常大的正数（或反之亦然），则此代码将有很多溢出。请检查您的算法。 - JB Nizet

@JBNizet：我还没有遇到任何溢出，所以我想那是某种不变量。跨越整个范围的条件主要是为了避免假设所有变量都适合于32位的答案。 - thkala

请注意，这种溢出不会引起任何异常：只会导致错误的计算值。因此可能会被忽略。 - JB Nizet

@JBNizet：我知道整数溢出是静默的 - 我主要是C程序员 :-) 我有一个测试用例，使用已知良好代码的结果作为参考。我仍在寻找边角情况，但我还没有遇到任何问题。 - thkala

@thkala 简单的边界情况：a=-2^63; b=任意正数值。如果你的测试工具没有测试这样的数字，最好确保这种情况是不可能发生的。特别有趣的情况是：a=-2^63; b = 0 - 我希望你的算法能够处理 Math.abs 的结果为负数的情况！ - Voo

@thkala 另一个想法可能是你甚至不需要进行那个计算。我知道这听起来并不特别有帮助，但如果你能发布一些额外的代码来展示如何使用这个值，那么就可以实现更加激进的优化。除非循环的目的是计算|a-b|-|c-d|的值，否则可能可以用另一种方式来实现它。 - Patrick87

Answer 1

我怀疑性能分析器并没有给出真实的结果，因为它试图对这样一个微不足道的"方法"进行分析（从而增加了负担）。没有性能分析，Math.abs可以转换成少量的机器码指令，并且你无法使其更快。

我建议你进行微型基准测试以确认这一点。我认为加载数据的开销要昂贵一个数量级。

long a = 10, b = 6, c = -2, d = 3;

int runs = 1000 * 1000 * 1000;
long start = System.nanoTime();
for (int i = 0; i < runs; i += 2) {
    long r = Math.abs(i - a) - Math.abs(c - i);
    long r2 = Math.abs(i - b) - Math.abs(d - i);
    if (r + r2 < Integer.MIN_VALUE) throw new AssertionError();
}
long time = System.nanoTime() - start;
System.out.printf("Took an average of %.1f ns per abs-abs. %n", (double) time / runs);

打印

Took an average of 0.9 ns per abs-abs. 

- Peter Lawrey

---

当然可以，虽然我认为循环足够紧凑以示意。顺便问一下，你确定在x86_64上有这样的64位整数指令吗？ - thkala

哼，它有movabs但似乎不是我想要的。 - Peter Lawrey

这实际上是在测试解释器的性能（JIT本身似乎认识到循环可以被优化掉 - 对我来说，运行此测试多次返回178, 176, 0, 0, 0,..）。 - Voo

将变量提升到方法外似乎可以正常工作：每个测试运行100次，每次循环迭代1亿次，平均值为185毫秒，方差为13毫秒。 - Voo

Answer 2

我最终使用了这个小方法：

public static long diff(final long a, final long b, final long c, final long d) {
    final long a0 = (a < b)?(b - a):(a - b);
    final long a1 = (c < d)?(d - c):(c - d);

    return a0 - a1;
}

我经历了明显的性能提升-整个应用程序大约提高了10-15%。我认为这主要归功于以下原因：

• 消除了一个方法调用：不再调用Math.abs()两次，而是只调用一次。虽然静态方法调用并不会过于昂贵，但它们仍然会产生影响。
• 消除了几个否定操作：这可能会被代码稍微增加的大小所抵消，但我很乐意相信它确实有所改变。

编辑： 看来实际情况恰恰相反。在我的微基准测试中，显式地内联代码似乎不会影响性能。改变绝对值计算的方式会......

- thkala

---

你的第一点并不重要。JIT会内联这样简单的调用 - 你可以通过将逻辑放入函数并调用它来轻松测试，时间上没有任何区别（而且这也是一个好习惯 ;)）。然而，第二点似乎是有效的 - 在微基准测试中我得到了约10%的加速（可以发布代码，但是我确实观察到了OSR、热身等等！） - Voo

@Voo：没错，我的基准测试在计数器方面出了问题，导致结果失真。 - thkala

Answer 3

如果您没有更多的缓存丢失，您可以尝试展开函数和手动优化。

如果我正确地进行了展开操作，它可能是这样的：

    if(a<b)
{
    if(c<d)
    {
        r=b-a-d+c;
    }
    else
    {
        r=b-a+d-c;
    }
}
else
{
    if(c<d)
    {
        r=a-b-d+c;
    }
    else
    {
        r=a-b+d-c;
    }
}

- Valmond

Answer 4

你确定是方法本身引起了问题吗？也许是因为这个方法被大量调用，而你在分析器中只看到了聚合结果（比如方法执行时间 X 调用次数）？

- Mark Bramnik