7

我有一个简单的问题，假设我有以下代码，并且它以类似的方式重复了 10 次。

if blah then
    number = number + 2^n
end if

评估是否会更快：

number = number + blah*2^n?

这也带来了一个问题，你能不能将一个布尔值乘以一个整数（虽然我不确定从 2^n 返回的类型，它是整数还是无符号......等等）？（我在 Ada 工作，但让我们试着概括一下吧？）

编辑：对不起，我应该澄清一下，我正在查看 2 的 n 次方，我将 c 放在那里，因为如果我在 c 中遇到这个问题，我对自己的学习感兴趣，我认为还有更多 c这些板上的程序员然后是 Ada（我假设你知道这意味着什么），但是我目前的问题是 Ada 语言，但问题应该是与语言无关的（我希望）。

4

10 回答 10

10

这样的问题没有一般的答案，这在很大程度上取决于您的编译器和 CPU。现代 CPU 有条件移动指令，所以一切皆有可能。

在这里了解的唯一方法是检查生成的汇编器（通常-S作为编译器选项）并进行测量。

于 2010-10-26T13:45:53.103 回答
7

如果我们在谈论 C 并且 blah 不在您的控制范围内，那么只需执行以下操作：

if(blah) 数字 += (1<<n);

C 中确实没有布尔值，也不需要，false 为零，true 不为零，因此您不能假设不是 0 是 1，这是您的解决方案所需要的，也不能假设任何特定的blah 中的位已设置，例如：

数字 += (blah&1)<<n;

不一定会起作用，因为 0x2 或 0x4 或任何非零且位零清除的东西都被认为是真的。通常，您会发现 0xFFF...FFFF（减一或全一）被用作真值，但您不能依赖典型值。

现在，如果您完全控制 blah 中的值，并将其严格控制为 0 表示假，1 表示真，那么您可以按照您的要求进行操作：

数字+=废话<<n;

并避免潜在的分支、额外的缓存行填充等。

回到通用案例，采用这个通用解决方案：

unsigned int fun (int blah, unsigned int n, unsigned int number )
{
    if(blah) 数字 += (1<<n);
    返回（数字）；
}

并为两个最流行/最常用的平台编译：

    测试 %edi, %edi
    movl %edx, %eax
    杰.L2
    移动 $1, %edx
    移动 %esi, %ecx
    销售 %cl, %edx
    添加 %edx, %eax
.L2：

以上使用条件分支。

下面的一个使用条件执行，没有分支，没有管道刷新，是确定性的。

  cmp r0,#0
  移动 r3,#1
  添加 r2,r2,r3,asl r1
  移动 r0,r2
  bx lr

可以通过重新排列函数调用中的参数来保存 mov r0,r2 指令，但这是学术性的，您通常不会对此进行函数调用。

编辑：

如建议：

unsigned int fun (int blah, unsigned int n, unsigned int number )
{
    数字 += ((blah!=0)&1)<<n;
    返回（数字）；
}

  潜艇 r0, r0, #0
  移动 r0, #1
  添加 r0, r2, r0, asl r1
  bx lr

当然更便宜，而且代码看起来不错，但我不会假设 blah!=0 的结果，即零或任何编译器定义为 true 的结果总是具有 lsbit 集。它不必为编译器设置该位来生成工作代码。也许标准规定了 true 的具体值。通过重新排列函数参数 if(blah) number +=... 也将导致三个单时钟指令并且没有假设。

编辑2：

看看我理解的 C99 标准：

==（等于）和 !=（不等于）运算符类似于关系运算符，只是它们的优先级较低。如果指定的关系为真，则每个运算符产生 1，如果为假，则产生 0。

这解释了为什么上述编辑有效，以及为什么你得到 movne r0,#1 而不是其他随机数。

发帖人问的是关于 C 的问题，但也指出 ADA 是当前语言，从语言独立的角度来看，你不应该假设像上面的 C 功能这样的“功能”并使用 if(blah) number = number + (1 <<n)。但是这是用 C 标记询问的，所以我认为 C 的一般（独立于处理器）最快的结果是 number += (blah!=0)<<n; 所以史蒂文赖特的评论是正确的，他应该为此受到赞扬。

海报的假设也基本正确，如果您可以将 blah 转换为 0 或 1 形式，那么在没有分支的意义上，在数学中使用它会更快。把它变成那种形式而不比分支更昂贵是诀窍。

于 2010-10-27T14:18:51.197 回答
5

在阿达...

原配方：

if Blah then
  Number := Number + (2 ** N);
end if;

另一种通用公式，假设 Blah 是 Boolean 类型并且 Number 和 N 是合适的类型：

Number := Number + (Boolean'pos(Blah) * (2 ** N));

（对于用户定义N的Number整数或浮点类型，可能需要合适的定义和类型转换，这里的关键点是Boolean'pos()构造，Ada 保证将为您提供预定义的布尔类型的 0 或 1。）

至于这是否更快，我同意@Cthutu：

我会保留它的条件。此时您不应该担心低级优化细节。编写最能描述您的算法的代码并相信您的编译器。

于 2010-10-26T14:18:46.867 回答
4

我会保留它的条件。此时您不应该担心低级优化细节。编写最能描述您的算法的代码并相信您的编译器。在某些 CPU 上，乘法速度较慢（例如，每条指令都有条件的 ARM 处理器）。您还可以使用 ?: 在某些编译器下优化得更好的表达式。例如：

number += (blah ? 2^n : 0);

如果由于某种原因，这个小计算是分析后应用程序的瓶颈，那么请担心低级优化。

于 2010-10-26T13:47:54.057 回答
4

在 C 中，关于 blah*2^n：你有什么理由相信 blah 取值 0 和 1？该语言只承诺 0 <-> FALSE 和（其他所有）<-> TRUE。C 允许您将“布尔”临时值与另一个数字相乘，但结果未定义，除非 result=0 <=> bool 为假或数字为零。

在 Ada 中，关于 blah*2^n：该语言没有在布尔类型上定义乘法运算符。因此 blah 不能是布尔值并且不能相乘。

于 2010-10-26T13:50:01.090 回答
1

如果您的语言允许布尔值和数字之间的乘法，那么是的，这比条件要快。条件需要分支，这会使 CPU 的管道无效。此外，如果分支足够大，它甚至会导致指令中的缓存未命中，尽管在您的小示例中这不太可能。

于 2010-10-26T13:41:24.243 回答
1

一般来说，特别是在使用 Ada 时，您不应该担心这样的微优化问题。编写您的代码，以便读者清楚地了解，并且只在您遇到性能问题时才担心性能，并将其跟踪到代码的那部分。

不同的 CPU 有不同的需求，而且它们可能非常复杂。例如，在这种情况下，哪个更快取决于您的 CPU 的管道设置、当时缓存中的内容以及其分支预测单元的工作方式。你的编译器的一部分工作就是成为这些方面的专家，它会比最好的汇编程序员做得更好。当然比你（或我）更好。

因此，您只需要担心编写好的代码，而让编译器担心如何从中生成高效的机器代码。

于 2010-10-26T14:38:58.103 回答
1

对于所述问题，C 中确实存在可以生成高效代码的简单表达式。

的nth 次方2可以用<<运算符 as计算1 << n，前提n是它小于 中的值位数int。

如果blah是boolean，即 anint值为0or 1，您的代码片段可以写成：

number += blah << n;

如果blah是任何可以测试其真值的标量类型为if (blah)，则表达式稍微复杂一些：

number += !!blah << n;

这相当于number += (blah != 0) << n;

测试仍然存在，但对于现代架构，生成的代码不会有任何跳转，这可以使用Godbolt 的编译器资源管理器在线验证。

于 2017-08-01T18:51:10.107 回答
0

无论哪种情况，您都无法避免分支（内部），所以不要尝试！

在

number = number + blah*2^n

始终必须评估完整的表达式，除非编译器足够聪明，可以在 blah 为 0 时停止。如果是，如果 blah 为 0，您将获得一个分支。如果不是，您总是会得到一个昂贵的乘法。如果 blah 为假，您还将获得不必要的添加和分配。

在“if then”语句中，只有当 blah 为真时，该语句才会进行加法和赋值。

简而言之，在这种情况下，您的问题的答案是“是”。

于 2010-10-26T13:55:33.223 回答
0

这段代码显示它们的性能相似，但乘法通常稍快一些。

@Test
public void manual_time_trial()
{
    Date beforeIfElse = new Date();
    if_else_test();
    Date afterIfElse = new Date();
    long ifElseDifference = afterIfElse.getTime() - beforeIfElse.getTime();
    System.out.println("If-Else Diff: " + ifElseDifference);

    Date beforeMultiplication = new Date();
    multiplication_test();
    Date afterMultiplication = new Date();
    long multiplicationDifference = afterMultiplication.getTime() - beforeMultiplication.getTime();
    System.out.println("Mult Diff   : " + multiplicationDifference);

}

private static long loopFor = 100000000000L;
private static short x = 200;
private static short y = 195;
private static int z;

private static void if_else_test()
{
    short diff = (short) (y - x);
    for(long i = 0; i < loopFor; i++)
    {
        if (diff < 0)
        {
            z = -diff;
        }
        else
        {
            z = diff;
        }
    }
}

private static void multiplication_test()
{
    for(long i = 0; i < loopFor; i++)
    {
        short diff = (short) (y - x);
        z = diff * diff;
    }
}
于 2017-08-01T18:17:45.093 回答