标签: micro-optimization

我正在查看一些带有巨大的switch语句和每个case的if-else语句的代码,并立即感受到优化的冲动.作为一个优秀的开发人员,我总是应该着手获得一些硬性时序事实,并从三个变体开始:

1. 原始代码如下所示:

   public static bool SwitchIfElse(Key inKey, out char key, bool shift)
   {
       switch (inKey)
       {
          case Key.A: if (shift) { key = 'A'; } else { key = 'a'; } return true;
          case Key.B: if (shift) { key = 'B'; } else { key = 'b'; } return true;
          case Key.C: if (shift) { key = 'C'; } else { key = 'c'; } return true;
          ...
          case Key.Y: if (shift) { key = 'Y'; } else { key …

   Run Code Online (Sandbox Code Playgroud)

我在我正在构建的一些搜索代码中使用了Levenshtein算法的优化版本.我有功能单元测试来验证算法返回正确的结果,但在这种情况下,算法的性能也非常重要.

我希望为项目添加一些测试覆盖率,以便如果将来的任何修改影响优化,它们将显示为失败测试 - 因为算法是确定性的并且针对已知测试数据运行,这可能与计数一样详细为给定的一组测试输入执行的指令数.换句话说,我不打算使用定时器测量算法性能 - 我对实际测试算法的内部行为而不仅仅是输出感兴趣.

有什么想法我会如何在C#/ .NET 4中解决这个问题？

编辑:我不想只使用挂钟时间的原因是它会随着CPU负载和测试控制之外的其他因素而变化.例如,这可能导致在构建服务器负载时测试失败.这里将是挂钟监控的部署系统的一部分.

编辑2:这样想吧......当性能是关键要求时,你会如何应用red-> green-> refactor？

有一个现有的问题“3 个长整数的平均值”，它特别关注三个有符号整数的平均值的有效计算。

然而，无符号整数的使用允许额外的优化不适用于上一个问题中涵盖的场景。这个问题是关于三个无符号整数的平均值的有效计算，其中平均值向零舍入，即在数学术语中我想计算？(a + b + c) / 3 ?。

计算此平均值的一种直接方法是

 avg = a / 3 + b / 3 + c / 3 + (a % 3 + b % 3 + c % 3) / 3;

首先，现代优化编译器会将除法转换为具有倒数加移位的乘法，并将模运算转换为反向乘法和减法，其中反向乘法可能使用许多体系结构上可用的scale_add习语，例如leax86_64的，add用lsl #n在ARM，iscadd在NVIDIA GPU。

在尝试以适用于许多常见平台的通用方式优化上述内容时，我观察到整数运算的成本通常在逻辑关系中？（添加|子）？转移？规模_添加？MUL。这里的成本是指所有延迟、吞吐量限制和功耗。当处理的整数类型比本地寄存器宽度更宽时，例如在uint64_t32 位处理器上处理数据时，任何此类差异都会变得更加明显。

因此，我的优化策略是尽量减少指令数量，并在可能的情况下用“廉价”操作替换“昂贵”操作，同时不增加寄存器压力并为宽无序处理器保留可利用的并行性。

第一个观察结果是，我们可以通过首先应用产生和值和进位值的 CSA（进位保存加法器）将三个操作数的和减少为两个操作数的和，其中进位值的权重是和的两倍价值。在大多数处理器上，基于软件的 CSA 的成本是五个逻辑s。一些处理器，如 …

我一直看到人们声称MOV指令可以在x86中免费,因为寄存器重命名.

对于我的生活,我无法在一个测试用例中验证这一点.每个测试用例我尝试揭穿它.

例如,这是我用Visual C++编译的代码:

#include <limits.h>
#include <stdio.h>
#include <time.h>

int main(void)
{
    unsigned int k, l, j;
    clock_t tstart = clock();
    for (k = 0, j = 0, l = 0; j < UINT_MAX; ++j)
    {
        ++k;
        k = j;     // <-- comment out this line to remove the MOV instruction
        l += j;
    }
    fprintf(stderr, "%d ms\n", (int)((clock() - tstart) * 1000 / CLOCKS_PER_SEC));
    fflush(stderr);
    return (int)(k + j + l);
}

这为循环生成以下汇编代码(随意生成这个你想要的;你显然不需要Visual C++):

LOOP:
    add edi,esi
    mov …

我正在迭代一个数组并按值将其分类为一周中的几天.

为了做到这一点,我使用了许多if陈述.如果我使用多个ifs而不是一组else if语句,它对处理速度有什么影响吗？

一时兴起,我最近测试了这两种方法timeit,看看哪种评估方法更快:

import timeit

"""Test method returns True if either argument is falsey, else False."""

def and_chk((a, b)):
    if not (a and b):
        return True
    return False

def not_or_chk((a, b)):
    if not a or not b:
        return True
    return False

......并得到了这些结果:

 VALUES FOR a,b ->      0,0         0,1         1,0         1,1
        method
    and_chk(a,b)    0.95559     0.98646     0.95138     0.98788
 not_or_chk(a,b)    0.96804     1.07323     0.96015     1.05874
                                            ...seconds per 1,111,111 cycles.

效率的差异在1%到9%之间,总是有利于if not (a and b),这与我的预期相反,因为我理解if not a or not b它将按顺序评估其术语(if …

我意识到这在微优化领域太过分了,但我很想知道为什么调用DateTime.Now和DateTime.UtcNow是如此"昂贵".我有一个示例程序运行几个做"一些"工作的场景(添加到一个计数器)并试图这样做1秒钟.我有几个接近让它在有限的时间内完成工作.这些示例显示DateTime.Now和DateTime.UtcNow明显慢于Environment.TickCount,但与仅让一个单独的线程休眠1秒然后设置一个值以指示工作线程停止相比,即使这样也很慢.

所以我的问题是:

• 我知道UtcNow更快,因为它没有时区信息,为什么它仍然比TickCount慢得多？
• 为什么读取布尔值比int更快？
• 处理这些类型场景的理想方法是什么,你需要允许某些东西在有限的时间内运行,但是你不想浪费更多时间来检查时间而不是实际工作？

请原谅这个例子的详细程度:

class Program
{
    private static volatile bool done = false;
    private static volatile int doneInt = 0;
    private static UInt64 doneLong = 0;

    private static ManualResetEvent readyEvent = new ManualResetEvent(false);

    static void Main(string[] args)
    {
        MethodA_PrecalcEndTime();
        MethodB_CalcEndTimeEachTime();
        MethodC_PrecalcEndTimeUsingUtcNow();

        MethodD_EnvironmentTickCount();

        MethodX_SeperateThreadBool();
        MethodY_SeperateThreadInt();
        MethodZ_SeperateThreadLong();

        Console.WriteLine("Done...");
        Console.ReadLine();
    }

    private static void MethodA_PrecalcEndTime()
    {
        int cnt = 0;
        var doneTime = DateTime.Now.AddSeconds(1);
        var startDT = DateTime.Now;
        while (DateTime.Now <= doneTime)
        {
            cnt++;
        }
        var endDT = DateTime.Now;
        Console.WriteLine("Time …

这与此问题有关,但不一样:x86-64汇编的性能优化 - 对齐和分支预测与我之前的问题略有关系:无符号64位到双倍转换:为什么这个算法来自g ++

以下是一个不真实的测试用例.这种素性测试算法是不明智的.我怀疑任何真实世界的算法都不会执行如此多的小内循环(num大概是2**50的大小).在C++ 11中:

using nt = unsigned long long;
bool is_prime_float(nt num)
{
   for (nt n=2; n<=sqrt(num); ++n) {
      if ( (num%n)==0 ) { return false; }
   }
   return true;
}

然后g++ -std=c++11 -O3 -S生成以下内容,包含RCX n和包含XMM6 sqrt(num).请参阅我之前发布的剩余代码(在此示例中从未执行过,因为RCX永远不会变得足够大,不能被视为带符号的否定).

jmp .L20
.p2align 4,,10
.L37:
pxor    %xmm0, %xmm0
cvtsi2sdq   %rcx, %xmm0
ucomisd %xmm0, %xmm6
jb  .L36   // Exit the loop
.L20:
xorl    %edx, %edx
movq    %rbx, %rax …

Consider this simple C++ function to calculate the prefix sum of an array:

void prefix_sum(const uint32_t* input, uint32_t* output, size_t size) {
    uint32_t total = 0;
    for (size_t i = 0; i < size; i++) {
        total += input[i];
        output[i] = total;
    }
}

The loop compiles to the following assembly on gcc 5.5:

.L5:
        add     ecx, DWORD PTR [rdi+rax*4]
        mov     DWORD PTR [rsi+rax*4], ecx
        add     rax, 1
        cmp     rdx, rax
        jne     .L5

I don't see anything that would prevent …

我试图找到最有效的方法来计算 32 位无符号整数的模 255。我的主要重点是找到一种可以在 x86 和 ARM 平台上运行良好的算法，并着眼于除此之外的适用性。首先，我试图避免内存操作（这可能很昂贵），所以我正在寻找有点复杂的方法，同时避免使用表格。我还试图避免可能昂贵的操作，例如分支和乘法，并尽量减少使用的操作和寄存器的数量。

下面的 ISO-C99 代码捕获了我迄今为止尝试过的八个变体。它包括一个用于详尽测试的框架。我对这个粗略的执行时间测量进行了猛烈抨击，这似乎工作得很好，可以获得第一次性能印象。在一些平台上我试过（全部具有快速整数倍）的变种WARREN_MUL_SHR_2，WARREN_MUL_SHR_1和DIGIT_SUM_CARRY_OUT_1似乎是最高效的。我的实验表明，我在Compiler Explorer 中尝试的 x86、ARM、PowerPC 和 MIPS 编译器都很好地利用了特定于平台的功能，例如三输入LEA、字节扩展指令、乘法累加和指令预测。

该变体NAIVE_USING_DIV使用整数除法，与除数反乘，然后减法。这是基线情况。现代编译器知道如何有效地实现 255 的无符号整数除法（通过乘法），并将在适当的情况下使用离散替换反乘。要计算模数，base-1可以对base数字求和，然后折叠结果。例如3334 mod 9: sum 3+3+3+4 = 13, fold 1+3 = 4. 如果折叠后的结果是base-1，我们需要生成0来代替。DIGIT_SUM_THEN_FOLD使用这种方法。

A. Cockburn，“使用 8/16 位算法有效实现 OSI 传输协议校验和算法”，ACM SIGCOMM 计算机通信评论，卷。17, No. 3, 七月/八月 1987 年，第 13-20 页

展示了base-1在校验和计算模 255 的上下文中有效地添加数字模数的不同方法。计算数字的逐字节总和，并且在每次添加之后，也添加来自加法的任何进位。所以这将是一个ADD a, b …