HPC Algorithm 回顾

这部分博客主要是对于HPC Algorithms的书籍回顾，进行总结，该部分内容和性能优化学习笔记相关联，写这个笔记记录主要是方便回顾，如果想看细节就回去看原文

第一章到第二章

第一章的目录如上图所示，主要包括：

经典的计算复杂度定义
同源复杂度，BIG O
摩尔定律的失效
不同种类的编程语言

其中，对于摩尔定律失效这一章节，讲了关于如何更高效使用更多的晶体管来驱动计算架构设计：

重叠执行指令，使 CPU 的不同部分保持忙碌（流水线）；
执行操作时不一定要等待前一个操作完成（投机和无序执行）；
增加多个执行单元，同时处理独立运算（超标量处理器）；
增加机器字的大小，以至于可以添加指令，对分成组的 128、256 或 512 位数据块执行相同的操作（SIMD）；
在芯片上增加多层高速缓存，以加快 RAM 和外部存储器的访问速度（存储器并不完全遵循硅扩展定律）；
在芯片上增加多个相同的内核（并行计算、图形处理器）；
在主板上使用多个芯片，在数据中心使用多台更便宜的计算机（分布式计算）；
使用定制硬件解决特定问题，提高芯片利用率（ASIC、FPGA）。

而对于第二章的内容，主要讲的是计算机架构，主要目录结构如下所示：

第一个内容讲的是ISA，大概讲了RISC和CISC，其中ARM是RISC，而x86是CISC。（CISC能够实现更多的复杂的特殊的指令，而RISC要去实现就需要用子程序实现）。目前的X86架构基本上被两家公司控制，Intel和AMD，而ARM架构则是被ARM公司控制，ARM架构的优势在于低功耗，而X86架构的优势在于高性能。

第二个内容讲的是汇编语言，这部分没什么好讲的，就是讲了一些基本的汇编语言的知识。

第三个、第四个内容讲的是循环、条件、函数以及递归，其核心就是将这些和汇编语言联系起来，其中不乏包括循环展开，跳转等技巧，比如说我们对于跳转，可以不显式地使用跳转指令，而是通过条件判断来实现跳转，不过是通过其它指令修改的FLAGS寄存器来实现的。而对于函数，其核心就是一个栈的问题，函数调用的时候，会将参数压入栈中，然后调用函数，函数返回的时候，会将返回值压入栈中，然后返回，这样就可以实现函数的调用。并且处理函数调用的最佳方法就是避免函数调用，因为函数调用会有一定的开销。同时我们也可以通过Inlining的方法去解决Caller和Callee之间使用寄存器冲突的问题。

但是对于内联函数，并不适用于递归函数，因为递归函数会有很多的调用，如果内联的话，会导致栈空间的消耗过大，所以递归函数不适合内联。这里还定义了如果递归之后直接返回，那么这个递归就是尾递归，尾递归可以通过循环来实现，这样就可以避免栈空间的消耗。

第五个内容讲的是间接的分支，其中一种就是switch-case情况，另一种就是常见的动态分支，比如虚函数的实现。为了正确实现调用虚函数，比如我有一个动物的虚类，然后有一个狗类继承了动物类，那么我在调用动物类的时候，实际上是调用狗类的函数，这就是动态分支的实现。而对于这种情况，我们可以通过虚函数表来实现，虚函数表是一个指针数组，里面存放的是虚函数的地址，然后在调用的时候，通过虚函数表来调用函数。但是会遇到问题：pipeline flushing，这个问题就是在调用虚函数的时候，会导致流水线的刷新，这样会导致性能的下降。实际上对于运行时多态，最好的方法就是避免运行时多态，因为运行时多态会导致性能的下降。 (感觉说了等于白说啊哈哈哈哈哈哈哈哈哈哈哈 🤣)

第六个内容比较有意思， 😎是关于机器码的Layout，实际上，所有的性能优化，在最后都会转化为机器码，所以我们需要了解机器码的布局，这样才能更好地进行性能优化。机器码在内存中的布局会以一种奇怪的方式影响性能，比如说我移除掉没用的代码、交换if甚至改变函数参数的顺序，都会是的性能发生提高或者变差。

一个很有意思的例子就是，Inline并不一定都很有效，这就涉及Instruction Cache，如果Inline的函数太大，那么会导致Instruction Cache的命中率下降，从而导致性能的下降。所以Inline并不是越多越好，而是要根据实际情况来决定。而对于展开循环亦是如此，CPU在执行的时候，一次性取太多的指令，会导致Instruction Cache的命中率下降，从而导致性能的下降。（不过大的代码对齐虽然会需要更多的指令缓存，但是也要比缓存命中率下降好）

我们总是习惯性的使用前人给的建议，实际上我们不清楚为什么好用，以及什么情况下好用，就比如这个Inline 😟

其中，对于不均等的分支问题，书中做了详细的说明，尽管在C语言的角度看一个简单的计算差值函数是对称的，但是在汇编里面并不是：

int length(int x, int y) {
    if(x>y)
    	return x - y;
    else
    	return y - x;
}

length:
    cmp  edi, esi
    jle  less
    ; x > y
    sub  edi, esi
    mov  eax, edi
done:
    ret
less:
    ; x <= y
    sub  esi, edi
    mov  eax, esi
    jmp  done

我们可以发现，实际上不同的分支花费的指令数目是不一样的，这就是不均等的分支问题，这个问题会导致性能的下降，所以我们要尽量避免不均等的分支。

那么如果我们考虑进行xchg(exchange),那么函数的参数顺序就比较重要，同理如果我们给编译器一个hint提示哪个路径是不经常的，那么函数参数顺序依旧很重要。实际上，一个比较好的方法就是类似C语言三元组的形式来实现：(x > y ? y - x : x - y) or calling abs(x - y):

length:
    mov   edx, edi
    mov   eax, esi
    sub   edx, esi
    sub   eax, edi
    cmp   edi, esi
    cmovg eax, edx  ; "mov if edi > esi"
    ret