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));

(对于用户定义NNumber整数或浮点类型,可能需要合适的定义和类型转换,这里的关键点是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

如果blahboolean,即 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 回答