StringBuilder 中的按位运算符优势

algorithm java bit-manipulation

2022-09-03 13:20:08

为什么 / 类中的方法使用按位运算符？reverse()StringBufferStringBuilder

我想知道它的优点。

public AbstractStringBuilder reverse() {
    boolean hasSurrogate = false;
    int n = count - 1;
    for (int j = (n-1) >> 1; j >= 0; --j) {
        char temp = value[j];
        char temp2 = value[n - j];
        if (!hasSurrogate) {
            hasSurrogate = (temp >= Character.MIN_SURROGATE && temp <= Character.MAX_SURROGATE)
                || (temp2 >= Character.MIN_SURROGATE && temp2 <= Character.MAX_SURROGATE);
        }
        value[j] = temp2;
        value[n - j] = temp;
    }
    if (hasSurrogate) {
        // Reverse back all valid surrogate pairs
        for (int i = 0; i < count - 1; i++) {
            char c2 = value[i];
            if (Character.isLowSurrogate(c2)) {
                char c1 = value[i + 1];
                if (Character.isHighSurrogate(c1)) {
                    value[i++] = c1;
                    value[i] = c2;
                }
            }
        }
    }
    return this;
}

答案 1

右移一意味着除以二，我认为你不会注意到任何性能差异，编译器将在编译时执行这些优化。

许多程序员习惯于在除法而不是编写时右移二，这是一个风格问题，或者也许有一天右移真的更有效，而不是实际除以写入，（在优化之前）。编译器知道如何优化这样的东西，我不会浪费时间试图编写其他程序员可能不清楚的东西（除非他们真的有所作为）。无论如何，该循环等效于：/ 2/ 2

int n = count - 1;
for (int j = (n-1) / 2; j >= 0; --j)

正如@MarkoTopolnik在他的评论中提到的，JDK是在完全没有考虑任何优化的情况下编写的，这也许可以解释为什么他们明确地将数字右移了一，而不是明确地将其除以，如果他们考虑了优化的最大功率，他们可能会写。/ 2

万一你想知道为什么它们是等价的，最好的解释是通过例子，考虑数字32。假设 8 位，其二进制表示形式为：

00100000

将其右移 1：

00010000

其值为 16 （1 * 2⁴)

答案 2

综上所述：

Java 中的运算符称为“符号扩展右位移位”运算符。>>
X >> 1在数学上等价于，对于 X 的所有严格正值。X / 2
X >> 1总是比快，比例大约为 1：16，尽管由于现代处理器架构，这种差异在实际基准测试中可能变得不那么重要。X / 2
所有主流JVM都可以正确执行此类优化，但是在这些优化实际发生之前，未优化的字节码将在解释模式下执行数千次。
JRE源代码使用了很多优化习语，因为它们对在解释模式下执行的代码（最重要的是，在JVM启动时）产生了重要影响。
系统地使用被整个开发团队接受的经过验证的有效代码优化习语并不是过早的优化。

长答案

以下讨论试图正确解决此页面上其他评论中提出的所有问题和疑问。它之所以如此之长，是因为我觉得有必要强调为什么某些方法更好，而不是炫耀个人的基准结果，信念和实践，其中千分可能因人而异。

因此，让我们一次回答一个问题。

1. 在 Java 中，X >> 1（或 X << 1，或 X >>> 1）是什么意思？

和统称为位移运算符。通常称为符号扩展右位移位或算术右位移位。是非符号扩展右位移位（也称为逻辑右位移位），并且只是左位位移（符号扩展不适用于该方向，因此不需要逻辑和算术变体）。>><<>>>>>>>><<

Bit Shift运算符在许多编程语言中都可用（尽管具有不同的表示法）（实际上，从快速调查中，我想说，几乎所有语言都或多或少是C语言的后代，以及其他一些语言）。位移是基本的二进制操作，并且相应地，几乎每个CPU都为这些操作提供汇编指令。位移位器也是电子设计中的经典建筑模块，在给定合理数量的传输器的情况下，它可以在一个步骤中提供最终结果，并具有恒定且可预测的稳定周期。

具体来说，位移运算符通过将数字的所有位向左或向右移动 n 个位置来转换数字。掉落的位被遗忘了;“进入”的位被强制为 0，除非在符号扩展的右位偏移的情况下，其中最左边的位保留其值（因此保留其符号）。请参阅维基百科以获取此内容的一些图形。

2. X >> 1 等于 X / 2 吗？

是的，只要股息保证为正数。

更一般地说：

左移 by 等效于乘以N2^N;
逻辑右移 by 等效于无符号整数除以N2^N;
算术右移 by 等效于非整数除以，舍入为负无穷大的整数（这也等效于任何严格正整数的有符号整数除以）。N2^N2^N

3. 在 CPU 级别，位移是否比等效的关节运算更快？

是的，它是。

首先，我们可以很容易地断言，在CPU的级别上，位移确实比等效的算术运算需要更少的工作。对于乘法和除法都是如此，其原因很简单：整数乘法和整数除法电路本身都包含几个位移位器。换句话说：位移位单位仅代表乘法或除法单位复杂程度的一小部分。因此，可以保证执行简单的位移而不是完整的算术运算所需的能量更少。然而，最后，除非您监控CPU的电耗或散热，否则我怀疑您可能会注意到CPU正在使用更多能量的事实。

现在，让我们谈谈速度。在具有合理简单架构的处理器上（即粗略地说，在奔腾或PowerPC之前设计的任何处理器，以及大多数没有某种形式的执行管道的最新处理器），整数除法（和乘法，在较小程度上）通常通过迭代其中一个操作数上的位（实际上是位组，称为基数）来实现。每次迭代都需要一个 CPU 周期，这意味着 32 位处理器上的整数除法（最多）需要 16 个周期（假设在假设处理器上使用 Radix 2 SRT 除法单元）。乘法单元通常一次处理更多位，因此 32 位处理器可能会在 4 到 8 个周期内完成整数乘法。这些单位可能使用某种形式的可变位移位器来快速跳过连续零的序列，因此在乘以或除以简单操作数（例如2的正幂）时可能会快速终止;在这种情况下，算术运算将在较少的周期内完成，但仍需要比简单的位移位运算更多。

显然，指令时序因处理器设计而异，但前置比（位移 = 1，乘法 = 4，除法 = 16）是这些指令实际性能的合理近似值。作为参考，在英特尔 486 上，SHR、IMUL 和 IDIV 指令（对于 32 位，假设按常量寄存）分别需要 2、13-42 和 43 个周期（有关 486 条指令及其时序的列表，请参阅此处）。

现代计算机中的CPU呢？这些处理器是围绕管道架构设计的，允许同时执行几条指令。结果是，现在大多数指令只需要一个周期的专用时间。但这是误导性的，因为指令在发布之前实际上在管道中停留了几个周期，在此期间它们可能会阻止其他指令完成。在此期间，整数乘法或除法单位保持“保留”状态，因此任何进一步的除法都将被保留。这在短循环中尤其成问题，其中单个多应用或除法最终将被尚未完成的先前调用自身所停滞。位移指令不会受到这种风险的影响：大多数“复杂”处理器都可以访问多个位移位单元，并且不需要长时间保留它们（尽管由于流水线架构固有的原因，通常至少保留2个周期）。实际上，为了将其归纳，快速浏览一下Atom的英特尔优化参考手册似乎表明SHR，IMUL和IDIV（与上述参数相同）分别具有2，5和57个延迟周期;对于 64 位操作数，它是 8、14 和 197 个周期。类似的延迟适用于最新的英特尔处理器。

所以，是的，位移位比等效的算术运算更快，即使在某些情况下，在现代处理器上，它实际上可能完全没有区别。但在大多数情况下，这是非常重要的。

4. Java 虚拟机会为我执行此类优化吗？

当然可以。井。。。最肯定的是，而且...最终。

与大多数语言编译器不同，常规 Java 编译器不执行优化。据认为，Java 虚拟机最适合决定如何针对特定的执行上下文优化程序。这在实践中确实提供了良好的结果。JIT 编译器对代码的动态有非常深入的了解，并利用这些知识来选择和应用大量次要代码转换，以便生成非常高效的本机代码。

但是，将字节码编译为优化的本机方法需要大量的时间和内存。这就是为什么JVM甚至不会考虑在执行数千次代码块之前对其进行优化的原因。然后，即使已计划优化代码块，编译器线程也可能需要很长时间才能实际处理该方法。之后，各种条件可能会导致该优化的代码块被丢弃，从而恢复为字节代码解释。

尽管 JSE API 的设计目标是可由各种供应商实现，但声称 JRE 也是如此是不正确的。Oracle JRE作为参考实现提供给其他人，但它与另一个JVM一起使用是不鼓励的（实际上，在Oracle开源JRE的源代码之前，它不久前就被禁止了）。

JRE源代码中的优化是JRE开发人员采用的约定和优化工作的结果，即使在JIT优化尚未或根本无法提供帮助的情况下也能提供合理的性能。例如，在调用 main 方法之前，将加载数百个类。那么早，JIT 编译器尚未获得足够的信息来正确优化代码。此时，手工优化会产生重要差异。

5. 这不是过早优化吗？

它是，除非有理由不这样做。

现代生活中的一个事实是，每当一个程序员在某个地方演示代码优化时，另一个程序员就会反对唐纳德·高德纳（Donald Knuth）关于优化的引用（好吧，这是他的吗？谁知道呢...）它甚至被许多人认为是Knuth的明确断言，即我们永远不应该尝试优化代码。不幸的是，这是对Knuth过去几十年对计算机科学的重要贡献的重大误解：Knuth实际上撰写了数千页关于实用代码优化的素养。

正如高德纳所说：

程序员浪费了大量的时间来思考或担心程序中非关键部分的速度，而这些提高效率的尝试实际上在考虑调试和维护时会产生很大的负面影响。我们应该忘记小效率，比如说大约97%的时间：过早的优化是万恶之源。然而，我们不应该在这个关键的3%中错过我们的机会。

—— Donald E. Knuth，“结构化编程与Goto语句”

Knuth所谓的过早优化是需要大量思考并且仅适用于程序的非关键部分的优化，并且对调试和维护具有强烈的负面影响。现在，所有这些都可以争论很长一段时间，但让我们不要。

然而，应该理解的是，小的局部优化，已被证明是有效的（也就是说，至少在总体上是平均的），不会对程序的整体构建产生负面影响，不会降低代码的可维护性，也不需要无关的思考，这根本不是一件坏事。这样的优化实际上是好的，因为它们不会花费你任何费用，我们不应该错过这样的机会。

然而，这是要记住的最重要的事情，在一个上下文中对程序员来说微不足道的优化在另一个上下文中对程序员来说可能是无法理解的。由于这个原因，位移位和掩蔽习语尤其成问题。知道这个习语的程序员可以不假思索地阅读它并使用它，这些优化的有效性得到了证明，尽管除非代码包含数百个事件，否则通常无关紧要。这些习语很少是错误的实际来源。尽管如此，不熟悉特定习语的程序员会浪费时间理解特定代码片段的作用，原因和方式。

最后，无论是赞成还是不支持这种优化，以及应该使用哪些习语实际上是团队决策和代码上下文的问题。我个人认为一定数量的习语在所有情况下都是最佳实践，任何加入我团队的新程序员都会很快获得这些习惯用语。更多的习语被保留给关键代码路径。放入内部共享代码库的所有代码都被视为关键代码路径，因为它们可能是从此类关键代码路径调用的。无论如何，这是我的个人做法，你的血统可能会有所不同。