linux文件删除原理

1 问题引入

先看C++代码，用256的模数随机填充一个固定大小的大数组，然后对数组的一半元素求和：

#include <iostream>
#include <ctime>
#include <algorithm>

int main(int argc, char** argv)
{
    const unsigned arraySize = 32768;
    int data[arraySize];
    for(unsigned c = 0; c < arraySize; c++)
        data[c] = std::rand() % 256;
    //排序后下面的loop执行更快
    std::sort(data, data + arraySize);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        for(unsigned c = 0; c < arraySize; c++)
        {
            if(data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
    std::cout << "elapsedTime:" << elapsedTime << ", CLOCKS_PER_SEC:" << CLOCKS_PER_SEC << std::endl;
    std::cout << "sum=" << sum << std::endl;
    return 0;
}

结果如下：

elapsedTime:11.15, CLOCKS_PER_SEC:1000000
sum=314931600000

现在注释掉std::sort函数，结果如下：

elapsedTime:24.78, CLOCKS_PER_SEC:1000000
sum=314931600000

可以发现先排序后计算运行效率提高了2倍，计算完全不涉及数据的有序性，理论上数组是否有序不会对计算产生任何作用，为什么排序后的数组要比未排序数组运行快2倍？

2 分析

处理器为了提高执行效率采用流水线架构，对于四级流水线，任何一条指令在CPU执行都必须经过如下步骤：

• 取指(Fetch)：从内存读取指令字节，地址为程序计数器(PC)的值
• 译码(Decode)：对取回的指令的拆分和解释，识别和区分出不同的指令类别及各种获取操作数的方法
• 执行(Execute)：执行指令，如果是跳转指令，会检查条件码和分支条件，选择分支
• 写回(Write Back)：将指令结果保存到内存

第一条指令进入执行阶段时，第二条指令已经开始译码，第三条指令处于取指阶段，...，相对于第一条指令执行写回内存再开始第二条指令的取指，效率大幅度提高。现代处理器一般流水线深度高达10-31级，对程序执行速度提高显著。但是遇到跳转指令时执行效率会急剧下降，对于分支跳转指令，我们在执行完该指令前是不知道是否发生跳转，即无法确定分支指令的下一条指令的地址，所以无法将分支指令的下一条指令放入流水线，只能等待分支指令执行完成才能开始下一条命令的取指步骤，导致流水线出现气泡(Bubble)，大大降低流水线的处理能力。

为解决上述问题，分支预测器(Branch predictor)应运而生，当指令执行到分支跳转指令时，CPU不再是空等待分支跳转指令执行完毕给出下一条指令的地址，而是根据模型预测分支是否发生跳转以及跳转到哪里，CPU将预测到的指令放入流水线，去执行指令的取指、译码等工作。当分支跳转指令执行完成后，会给出真正是否需要跳转的结果，CPU即可判断分支跳转预测是否正确，如果预测正确，则流水线继续执行，如果预测错误，则需要清空流水线，将前面不该进入流水线的指令清空，然后回退到分支地方，将正确的分支路径放入流水线重新执行。大多数应用都具有状态良好的(well-behaved)分支，所以现代化的分支预测器一般具有超过90%的命中率，但是面对无法预测的分支，且没有识别出可应用的模式时，分支预测器就无用武之地了。处理器如何预测？答案是分析历史运行记录，常见的分支预测器有静态分支预测器，动态分支预测器。

上述代码导致非排序数组性能差别的关键在于if语句：

if(data[c] >= 128)
    sum += data[c];

data数组里面的值是按0~255均匀存储的，data有序时，前面一半元素的迭代将不会进入if-statement，超过一半时，元素迭代将全部进入if-statement。这种规律对于分支预测非常友好，因为发现总是选择某个方向多次，于是就很容易做出判断，除了改变方向之后的一两次预测失败。

有序数组的分支预测流程：

T = 分支命中
N = 分支没有命中
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...
       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (非常容易预测)

无序数组的分支预测流程：

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N, ...

       = TTNTTTTNTNNTTTN ...   (完全随机--无法预测)

本例中，由于data数组元素填充的特殊性，决定了分支预测器在未排序数组迭代过程中将有50%的错误命中率，因而执行完整个sum操作将会耗时更多。

3 优化

利用位运算取消分支跳转，基本知识：

|x| >> 31 = 0 #非负数右移31位一定为0
~(|x| >> 31) = -1 #0取反为-1
-|x| >> 31 = -1 #负数右移31位一定为0xffffffff = -1
~(-|x| >> 31) = 0 #-1取反为0
-1 = 0xffffffff
-1 & x = x #以-1为mask和任何数求与，值不变

故分支判断可优化为：

int t = (data[c] - 128) >> 31;
sum += (~t & data[c]);

当data[c] < 128，t为-1，t为0；
当data[c] >= 128，t为0，t为-1；

若想避免移位操作，可以使用如下方式：

int t = -(data[c] >= 128);
sum += t & data[c];

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至yj.mapple@gmail.com