**
前言：
**
为什么要学习 python？可能因为它是“胶水”吧
**
开始：
**
说出来可能不信，我最近在追剧，《老友记》《生活大爆炸》《黑袍纠察队》等等，果然心有多大，这个浪的舞台就有多大，考试的事情要不是有人提醒，已然把它扔到爪哇国了；心中天天带着木有学习的愧疚感，再杂夹着追剧所带来的愉悦，啊，人果然是矛盾的生物啊；但是我又很开心，你说这个事气不气人吧？
看完上述描述，是不是觉得我又习惯性跑题了？其实这种矛盾感在写代码的时候也是常常发生，比如我第一门语言学的是 C，但是工作常常用 Java；虽然用 Java 让人觉得写起来很爽（面向对象，你懂的，只是处理业务上的逻辑，其他方面的细节几乎可以忽略掉），但是我的内心是抗拒的；
如果没有对象，那么就 new 一个出来，看似简单平直的想法却带来了很大的性能上的问题，随着对象的日益增多，硬件便很难长久的支撑下去，这个事情就会变得很气人，本来 new 出来一个对象就是为了方便使用的，结果我还是得了解它的生老病死，否则生怕一个不小心就把硬件给撑爆掉；为了解决这种会一不小心撑爆硬件的事情发生，最直白的想法就是少 new 对象，如果非 new 不可，那么就 new 一个足够精简的，所以最后的问题又被转移到如何设计对象上面去了，，，
所以，写 Java 时间久了真的会有一种成就感，你看我就是我那堆代码的上帝，我掌握着它们的生老病死，，，可是上帝也不是那么好当的啊，咱也没那么多精力去维护啊，所以我就觉得写 Java 就是矛盾感特别严重的一件事情：为了省心，我选择面向对象，但是我选择了面向对象，却再也没省过心，，，
从上述吐槽当中，我的大脑又开了一个脑洞，我觉得设计一门语言绝对是个哲学问题，想要满足所有人的需求是不可能，那么这种不可能是不是可以用某种简化思维来替代，比如：需要对象的时候我用 Java，需要性能的时候我用 C，需要写的优雅的时候，我就选择 ruby？（maybe or not,who care?）
所以，我现在想选择 python（hahaha,,, 没想到吧，上面提到的我都不要）
据说这货已经被纳入高考考试范畴了，这你敢信？但是，事实就是,,,emmmm，怎么说好呢？如果第一门语言学的是 python，那么学其他语言要付出更多的辛苦，而且学 python 不就是为了使用更多的语言吗???（此处手动狗头，仅为一家之言）
所以，吐槽完一遍，最后琢磨了一下，还是要有一门特别熟悉的语言作为模板，再辅以《编译原理》等精神食粮以滋养，才能在日新月异的互联网时代生存下去，在不同的事物之间寻找共性是一个比较耗时费力的事情，但是也是比较有成就感的事情吧，，，
所以，今天还是再探索一下 计算机底层 吧，，，hia,hia, hia~~~
下面是一个实验，可能里面的数字不甚准确，但是意思差不多，领会到就好：
注：这个实验是在 2009 年全国信息学奥林匹克冬令营论文 中看到的，作者未知，但是很感谢这位提供实验数据的仁兄
题目：在一堆数字中，找到其中的最大值；
分析：最朴素的想法就是循环一遍，找出最大值即可，这样的话这个算法的复杂度主要集中在数字的多少上，设一共有 n 个数字，则算法复杂度的上限为 O(n)
1. 这个时候写一个 for 循环解法，令输入 10000000 个数字，每隔 100 个数字计算一次其平均时钟周期，大概处理一个数字会占到 7~8 个时钟周期，总的测量周期值为：75305510
代码如下：
int get_max(int* a,int l){
int mx=0,i;
for(i=0;i<l;i++){if(a[i]>mx) mx=a[i];
}
return mx;
}2. 显然，上面这个思想太朴素了，一定可以有个缩减效率的办法，仔细观察会发现 a[i] 出现了两次，实际上就是对 a[i] 做了两次寻址的操作，那么干脆用地址如何？
int get_max(int* a,int l){
int mx=0,*ed=a+l;
while(a!=ed){if(*a>mx)mx=*a;
a++;
}
return mx;
}这一段代码直接读取 a 的地址，所以理论上效率一定是有所提升的，结果也的确如此，大概处理一个数字会平均占 6~7 个始终周期，总的测量周期值为：66047005
3.emmmm，难到这就是结束了吗？好像再怎么从语言语法的层面观察都不能再简化操作了，那应该怎么办？思考一下，一共 1 千万个数字，上述操作是进行了一遍循环，如果我同时分成 8 个线路，同时进行寻找最大值的操作会不会更快一些?
int get_max(int* a,int l){assert(l%8==0);
#define D(x) mx##x=0
int D(0),D(1),D(2),D(3),
D(4),D(5),D(6),D(7),*ed=a+l;
#define CMP(x) if(*(a+x)>mx##x)mx##x=*(a+x);
while(a!=ed){CMP(0);CMP(1);
CMP(2);CMP(3);
CMP(4);CMP(5);
CMP(6);CMP(7);
a+=8;
}
#define CC(x1,x2) if(mx##x1>mx##x2)mx##x2=mx##x1;
CC(1,0);CC(3,2);
CC(5,4);CC(7,6);
CC(2,0);CC(6,4);
CC(4,0);
return mx0;
}总的测量周期值为：34818706
看起来效果很显著，比第一个想法的时钟周期缩短了近一半，但是有个疑问，只不过是单路运行转成了 8 路运行而已，然后速度就快了一倍，是不是有些太夸张了？那么这里如何解释呢？
简单的讲，在最初两个程序中，每次计算新的 mx 都会依赖于上一步的计算结果，相关的计算指令也必须依次运行，而将求值过程分为多路处理，mx0,mx1 等变量的相关指令之间互相没有关联，让处理器有更大的机会将他们并发。
4. 还可以进行优化吗？来让我们回顾一下高级程序设计语言的诞生的目的，OK，你懂的，为了方便人类使用其实是在 汇编语言 的基础之上做了一些性能上的让步，高级语言过于依赖内存变量这一概念，而读写内存，是处理器最低效的操作之一，所以直接用 汇编语言 编写 1 号 代码会发生什么？
int get_max(int* a,int l){
int ret;
__asm__ __volatile__ (
"movl $0, %%eax\n\t"
".p2align 4,,15\n"
"LP1:\n\t"
"cmpl -4(%1,%2,4), %%eax\n\t"
"jge ED\n\t"
"movl -4(%1,%2,4), %%eax\n"
"ED:\n\t"
//"loop LP1\n\t"
"decl %2\n\t"
"jnz LP1\n\t"
"movl %%eax, %0\n\t"
:"=m"(ret)
:"r"(a),"c"(l)
:"%eax");
return ret;
}总的测量周期值为：21322853
其实思路上与 1 号 代码是相同的，但是效果是显著的，优化了近 72%，打量一下这个程序，核心循环中，有 5 条指令，其中甚至有两条是条件分支指令，还有两条需要访问内存，而且使用了最复杂的 sib 寻址方式。感觉起来，平均 2 个时钟周期，是没有道理的，其实这主要得益于现代 CPU 各种强大的优化机制：高速数据 cache 使两次访问同一内存如同访问寄存器一般迅速，第一个条件跳转大部分时间不会成立，而相反第二个跳转总会成立，这让 CPU 的分支预测发挥到极致。而强大的乱序执行引擎使得循环中的这些小指令得以以接近双倍的时间运行。
当然，在上述代码中有一条 loop 语句被注释掉了，如果利用 loop 进行循环操作会是怎样的效果？结果令人大跌眼镜：平均耗费 56457348 个时钟周期，整整慢了一倍还多，为什么会这么慢？
其实这个主要是因为 cpu 厂商对 指令集 的优化处理的结果，因为工程师们发现，事实上人们所使用的 80% 的指令都处于 20% 的指令集中，于是设计了 RISC(精简指令集计算机)，通过采用一个较小但功能完备的指令集，大大简化处理器的设计。RISC 中不再需要微指令的概念，而直接硬件执行指令码，在一个时钟周期执行一条指令，性能极高且容易控制。
所以我们可以预见到 loop 这种需要解析成多条微指令的复杂指令是不会被 cpu 的制造商进行优化处理的，所以用这条语句执行命令，自然会慢
5. 既然用 汇编语言 重写一遍 1 号代码带来的优化如此巨大，那么用 汇编语言 重新 2 号代码呢？
int get_max(int* a,int l){assert(l%2==0);
int ret;
__asm__ __volatile__ (
"movl $0, %%eax\n\t"
"movl $0, %%edx\n\t"
".p2align 4,,15\n"
"LP2:\n\t"
"cmpl (%1), %%eax\n\t"
"jge ED2\n\t"
"movl (%1), %%eax\n"
"ED2:\n\t"
"cmpl 4(%1), %%edx\n\t"
"jge ED3\n\t"
"movl 4(%1), %%edx\n"
"ED3:\n\t"
"addl $8, %1\n\t"
"subl $2, %2\n\t"
"jnz LP2\n\t"
"cmpl %%edx, %%eax\n\t"
"cmovll %%edx, %%eax\n\t"
"movl %%eax, %0\n\t"
:"=m"(ret)
:"r"(a),"r"(l)
:"%eax","%edx");
return ret;
}总的测量周期值为：17447544
emmmm, 确实是有些优化，但是却近乎可以忽略不计，这是为什么呢？
主要是因为汇编语言生成的代码，代码已经十分精简，在每次循环体第一句 mov 指令 cache miss 时，后面并没有指令可以提前来执行。
那么如果我重写 3 号代码呢？（单路变 8 路）oh,,,god,,, 居然比上面这个还慢，，，为什么？
因为过多的条件跳转指令也让处理器吃不消，，，emmmm，所以了解硬件的上限很重要，无脑的多线程是会要命的，，，
6. 已经做到了这个程度，考察程序各处似乎都无利可图了，优化再次陷入了僵局。要想再取得优化，必须再打开思维才行。这里要提到的，是所谓的单指令多数据 (SIMD) 的方法。
由题目可知，循环是不可避免的，上述的优化都是通过语言特性（汇编语言比高级程序设计语言执行快）和 对寻址操作进行优化的，那么如果我对循环优化呢？上面也提到了，单路执行变成多路执行很容易“翻车”，那么如果把多路执行变得足够小如何？测试一下 4 路执行的效果如何
int get_max(int* a,int l){assert(l%4==0);
assert(sse2);
int ret,tmp[4];
__asm__ __volatile__ (
"\txorps %%xmm0, %%xmm0\n"
"LP3:\n"
"\tmovdqa %%xmm0, %%xmm1\n"
"\tpcmpgtd (%1), %%xmm1\n"
"\tandps %%xmm1, %%xmm0\n"
"\tandnps (%1), %%xmm1\n"
"\torps %%xmm1, %%xmm0\n"
"\taddl $16, %1\n"
"\tsubl $4, %2\n"
"\tjnz LP3\n"
"\tmovdqu %%xmm0, (%3)\n"
"\tmovl (%3), %%eax\n"
"\tcmpl 4(%3), %%eax\n"
"\tcmovll 4(%3), %%eax\n"
"\tcmpl 8(%3), %%eax\n"
"\tcmovll 8(%3), %%eax\n"
"\tcmpl 12(%3), %%eax\n"
"\tcmovll 12(%3), %%eax\n"
"\tmovl %%eax, %0\n"
:"=m"(ret)
:"r"(a),"r"(l),"r"(tmp)
:"%eax");
return ret;
}总的测量周期值为：15898751
虽然跟 5 号代码比没快多少，但是 simd 这个指令是要比 5 号代码的指令复杂的许多的，那为什么用复杂指令还变快了？主要是因为 cpu 的厂商对这个指令做了优化处理，，，
是的，答案就是这么扯淡，越贴近底层就发现越玄学，如何制作一款 cpu 还真是一个难以回答的问题；但是我们有以下几点是可以确定的：
1. 除法 命令很慢，且难以优化，一般在 高级程序设计语言 层次是尽量转换成 乘法
2. 既然 除法 命令，那么 取模 也快不了多少，所以 取模 运算 一般是不会出现在循环里面的，都是最后执行，对 负数 取模建议这么写：
inline int mod(int a){a%=M;if(a<0)a+=M;return a;};3. 减少浮点除法，其实浮点数的除法可以想成： a÷b 等价于 a×(1÷b)
所以遇到浮点除法转成 乘法 是值得一试的，几乎 3 次乘法效率约等于做一次除法
4. 我们日常使用的是有符号整数，但是在进行除法时操作数常常可以保证都是非负的，这时我们应当先将操作数转换为无符号类型再做除法：无符号类型的除法比有符号类型进行得更快，所以这样确实可以起到优化作用
5. 除以 2 的 k 次幂，其实就相当于向右移动 k 位
上述的一些优化处理仅仅是冰山一角，如果再深究下去，估计这篇文章没半个多月是搞不定的，所以先暂时停在这里，日后再说，下回再见~