是否比乘法和赋值快?

如果我们谈论的是c,而blah不在你的控制范围内,那么就这样做:

if(blah) number += (1<<n);

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

number += (blah&1)<<n;

不一定有效,因为0x2或0x4或任何带零位清除的非零都被认为是真的。通常,您会发现0xfff…ffff(减去一个或全部)用作真值,但您不能依赖于典型值。

现在,如果您完全控制blah中的值,并将其严格保持为0表示假,1表示真,那么您可以执行您所要求的操作:

number += blah<<n;

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

但回到一般情况,采用这种一般解决方案:

unsigned int fun ( int blah, unsigned int n, unsigned int number )
{
    if(blah) number += (1<<n);
    return(number);
}

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

    testl   %edi, %edi
    movl    %edx, %eax
    je  .L2
    movl    $1, %edx
    movl    %esi, %ecx
    sall    %cl, %edx
    addl    %edx, %eax
.L2:

上面使用了条件分支。

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

  cmp   r0,#0
  movne r3,#1
  addne r2,r2,r3,asl r1
  mov   r0,r2
  bx    lr

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

编辑:

如建议:

unsigned int fun ( int blah, unsigned int n, unsigned int number )
{
    number += ((blah!=0)&1)<<n;
    return(number);
}

  subs  r0, r0, #0
  movne r0, #1
  add   r0, r2, r0, asl r1
  bx    lr

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

编辑2:

看看我理解的C99标准:

==(等于)和!=(不等于 to)运算符类似于 关系运算符,除了 低优先级。每个 如果指定了 关系为真,如果为假,则为0。

这就解释了为什么上面的编辑有效,为什么你得到movne r0,1,而不是其他随机数。

海报询问了关于C的问题,但也注意到Ada是当前语言,从语言独立的角度来看,您不应假定“功能”,如上面的C功能,并使用if(blah)数字=数字+(1<<n)。但这是用一个C标签来询问的,所以一般来说(独立于处理器的)C的最快结果是,我认为,number+=(blah!=0)<<n;所以Steven Wright的评论是正确的,他应该为此得到赞扬。

海报的假设也基本上是正确的,如果你能把blah变成0或1的形式,那么在没有分支的意义上,在数学中使用它会更快。把它做成那样的形状而不比树枝贵是诀窍。

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

这里了解的唯一方法是检查生产的组装器(通常 -S 作为编译器选项)和度量。

在艾达…

原配方:

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:

我会遵守条件的。 你不应该担心低水平 此时的优化细节。 编写描述您的 算法最好相信你 编译器。

我会遵守条件的。此时,您不必担心低级优化细节。编写最能描述算法的代码,并信任编译器。在某些CPU上,乘法速度较慢(例如,每个指令上都有条件的ARM处理器)。您也可以使用?:在某些编译器下优化的表达式。例如:

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

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

在c中,关于blah*2^n:您有理由相信blah取0和1的值吗?语言只承诺0<->错误和(其他所有内容)<->正确。C允许您将一个“布尔”临时数字与另一个数字相乘,但结果未定义,除非结果=0<=>bool为假或数字为零。

在Ada中,关于blah*2^n:语言没有在boolean类型上定义乘法运算符。因此,blah不能是bool,也不能被乘法。

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

一般来说,尤其是在与ADA合作时,您不应该担心这样的微观优化问题。编写代码,以便读者能够清楚地看到它,并且只在性能出现问题时才担心性能问题,并让它跟踪到代码的这一部分。

不同的CPU有不同的需求,它们可能非常复杂。例如,在这种情况下,更快的速度很大程度上取决于CPU的管道设置、当时缓存中的内容以及分支预测单元的工作方式。编译器的一部分工作是成为这些方面的专家,它将比除最好的汇编程序员以外的所有人做得更好。确实比你(或我)好。

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

对于所述的问题,确实有C语言中的简单表达式可以生成有效的代码。

这个 n 功率 2 可以用 << 操作员组件 1 << n ,提供 n 小于 int .

如果 blah 是一个 布尔值 ,即 int 值为 0 或 1 ,可以编写代码片段:

number += blah << n;

如果 瞎说 是可以测试其真值的任何标量类型 if (blah) ,表达更为细致:

number += !!blah << n;

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

测试仍然存在,但对于现代体系结构,生成的代码不会有任何跳跃,可以使用 Godbolt's compiler explorer .

在这两种情况下,都不能避免分支(内部),所以不要尝试!

在

number = number + blah*2^n

除非编译器足够聪明,当blah为0时停止,否则必须始终计算完整表达式。如果是,如果blah为0,您将得到一个分支。如果不是,你总是得到一个昂贵的乘法。如果blah是假的,你也会得到不必要的添加和分配。

在“if-then”语句中,只有当blah为真时,该语句才会执行添加和赋值。

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

这段代码显示它们的执行方式类似,但乘法通常稍微快一点。

@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;
    }
}