3

相同功能的以下 2 个版本（基本上尝试通过蛮力恢复密码）不提供相同的性能：

版本 1：

private static final char[] CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".toCharArray();
private static final int N_CHARS = CHARS.length;
private static final int MAX_LENGTH = 8;

private static char[] recoverPassword()
{
   char word[];
   int refi, i, indexes[];

   for (int length = 1; length <= MAX_LENGTH; length++)
   {
      refi = length - 1;
      word = new char[length];
      indexes = new int[length];
      indexes[length - 1] = 1;

      while(true)
      {
         i = length - 1;
         while ((++indexes[i]) == N_CHARS)
         {
            word[i] = CHARS[indexes[i] = 0];
            if (--i < 0)
               break;
         }

         if (i < 0)
            break;

         word[i] = CHARS[indexes[i]];

         if (isValid(word))
            return word;
      }
   }
   return null;
}

版本 2：

private static final char[] CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".toCharArray();
private static final int N_CHARS = CHARS.length;
private static final int MAX_LENGTH = 8;

private static char[] recoverPassword()
{
   char word[];
   int refi, i, indexes[];

   for (int length = 1; length <= MAX_LENGTH; length++)
   {
      refi = length - 1;
      word = new char[length];
      indexes = new int[length];
      indexes[length - 1] = 1;

      while(true)
      {
         i = refi;
         while ((++indexes[i]) == N_CHARS)
         {
            word[i] = CHARS[indexes[i] = 0];
            if (--i < 0)
               break;
         }

         if (i < 0)
            break;

         word[i] = CHARS[indexes[i]];

         if (isValid(word))
            return word;
      }
   }
   return null;
}

我希望版本 2 会更快，因为它确实如此（这是唯一的区别）：

i = refi;

...与版本 1 相比：

i = length -1;

然而，恰恰相反：版本 1 快了 3% 以上！有人知道为什么吗？这是因为编译器做了一些优化吗？

谢谢大家到目前为止的回答。只是补充一点，目标实际上不是优化这段代码（这已经很优化了），而是更多地从编译器/CPU/架构的角度来理解，什么可以解释这种性能差异。您的回答很有帮助，再次感谢！

钥匙

4

4 回答 4

5

很难在微基准测试中检查这一点，因为如果不阅读生成的机器代码，您无法确定代码是如何优化的，即使这样 CPU 可以做很多技巧来优化它，例如。它将 RISC 样式指令中的 x86 代码转换为实际执行。

一次计算只需一个周期，CPU 一次最多可以执行三个。访问 L1 高速缓存需要 4 个周期，而对于 L2、L3、主存储器则需要 11、40-75、200 个周期。

在许多情况下，存储值以避免简单计算实际上会更慢。顺便说一句，使用除法和模数非常昂贵，并且在微调代码时缓存这个值是值得的。

于 2013-08-15T06:44:45.070 回答
1

正确的答案应该可以通过反汇编程序检索（我的意思是 .class -> .java 转换器），但我的猜测是编译器可能已经决定完全摆脱 iref 并决定存储length - 1一个辅助寄存器。我更像是一个 c++ 人，但我会先尝试：

const int refi = length - 1;

在 for 循环内。你也应该使用

indexes[ refi ] = 1;
于 2013-08-15T06:49:29.287 回答
1

比较代码的运行时间并不能给出准确或隔离的结果

首先，这不是比较性能的方式。这里需要进行运行时间分析。两个代码具有相同的循环结构并且它们的运行时间相同。运行代码时，您可能有不同的运行时间。但是，它们的主要区别在于缓存命中、I/O 时间、线程和进程调度。没有隔离，代码总是在准确的时间完成。

但是，您的代码仍然存在差异，要了解差异，您应该查看您的 CPU 架构。我基本上可以按照x86架构来解释。

幕后会发生什么？

i = refi;

CPU从 ram获取refi和到它的寄存器。i如果缓存中的值不在缓存中，则有 2 次访问 ram。和值i将被写入 ram。但是，根据线程和进程计划，它总是需要不同的时间。此外，如果这些值在虚拟内存中，则需要更长的时间。

i = length -1;

CPU 还可以从 ram 或缓存中访问i和访问。length访问次数相同。此外，这里还有一个减法，这意味着额外的 CPU 周期。这就是为什么你认为这需要更长的时间才能完成。这是意料之中的，但我上面提到的问题解释了为什么这需要更长的时间。

求和

正如我所解释的，这不是比较性能的方式。我认为，这些代码之间没有真正的区别。CPU内部和编译器中有很多优化。如果您反编译.class文件，您可以看到优化的代码。

我的建议是最好尽量减少 BigO 运行时间分析。如果您找到更好的算法，这是优化代码的最佳方式。如果您的代码仍然存在瓶颈，您可以尝试微基准测试。

也可以看看

算法分析

大 O 符号

微处理器

编译器优化

CPU调度

于 2013-08-15T07:12:16.767 回答
0

首先，您无法仅通过运行程序来比较性能 - Java 中的微基准测试很复杂。

此外，现代 CPU 上的减法平均只需三分之一时钟周期。在 3GHz CPU 上，这是 0.1 纳秒。没有什么能告诉你减法实际上发生了，因为编译器可能已经修改了代码。

所以：

  • 您应该尝试检查生成的汇编代码。
  • 如果您真的关心性能，请创建一个适当的微基准。
于 2013-08-15T06:54:15.887 回答