小编Mik*_*e B的帖子

首先让我先说明这一点,我知道这种微观优化很少具有成本效益.我很好奇这些东西是如何起作用的.对于所有的高速缓存行数等,我在考虑x86-64 i5 Intel CPU.对于不同的CPU,数字显然会有所不同.

我常常觉得走向阵列向前走的速度比走向后走得快.我相信这是因为大量数据是以前向方式完成的 - 也就是说,如果我读取字节0x128,那么高速缓存行(假设长度为64字节)将以字节0x128读取 - 0x191包含.因此,如果我想要访问的下一个字节是0x129,它就已经在缓存中了.

但是,看了一下后,我现在的印象是它实际上没关系？因为高速缓存行对齐将在最接近的64可分边界处选择起始点,然后如果我选择字节0x127开始,我将加载0x64-0x127(包括端点),因此将在缓存中具有数据以供我向后移动.当从0x128转换到0x127时,我会遇到缓存,但这是我为这个例子选择地址的结果,而不是任何现实世界的考虑.

我知道高速缓存行是以8字节块的形式读入的,因此如果我们向后走,第一次操作可能会开始之前必须加载完整的高速缓存行,但我怀疑它会产生巨大的显着差异.

如果我就在这里,有人可以清理,老我错了吗？我已经搜索了一整天,仍未能得到最终答案.

tl; dr:我们走一个阵列的方向真的那么重要吗？它真的有所作为吗？它在过去有所作为吗？(到15年前左右)

我已经使用以下基本代码进行了测试,并且向前和向后看到了相同的结果:

#include <windows.h>
#include <iostream>
// Size of dataset
#define SIZE_OF_ARRAY 1024*1024*256
// Are we walking forwards or backwards?
#define FORWARDS 1

int main()
{
    // Timer setup
   LARGE_INTEGER StartingTime, EndingTime, ElapsedMicroseconds;
   LARGE_INTEGER Frequency;

   int* intArray = new int[SIZE_OF_ARRAY];
    // Memset - shouldn't affect the test because my cache isn't 256MB!
   memset(intArray, 0, SIZE_OF_ARRAY);

    // Arbitrary numbers for break points
   intArray[SIZE_OF_ARRAY - 1] = 55;
   intArray[0] …

struct Object
{
    int x;
    int y;
    bool isXValid()
    {
       return x > 0;
    }
};

bool mySort(const Object& lhs, const Object& rhs)
{
    // Note the short-circuit here
    bool isValidForCheck = lhs.isXValid() && rhs.isXValid();

    // rhs may be valid because short-circuit, or both may be invalid
    if (isValidForCheck)
    {
       return lhs.x < rhs.x;
    }

    return lhs.y < rhs.y;
}

int main()
{
    std::vector<Object> myVec;
    // random populating of myVec
    std::sort(myVec.begin(), myVec.end(), mySort);
    return 0;
}

我的比较函数是反射性的,但不尊重传递性.

stl排序 - 严格的弱排序 …