评估 sizeof 导致性能改进 C

Question

我有一个动态数组，并且有一个热循环，它花费大量时间向我实现的动态数组添加大量元素。

动态数组的工作原理是在值数组的开头存储一个标头：

typedef struct
{
    unsigned char* begin; // Pointer to first element (should just point to end of struct, the header is stored prior data)
    unsigned char* end; // Pointer to last element
    size_t typeSize; // Size of type that the array stores
    size_t capacity; // capacity of array (when size ((end - begin) / typeSize) exceeds capacity, realloc)
} dynamicArr;

出于某种原因，当我将 与sizeof item进行比较时，循环运行得更快，而当我不进行比较时typeSize，它的幅度很大（增加了 30%）。

请注意，比较只是为了防止添加不同类型的项目并导致数组中的未对齐。如果正确使用动态数组来存储 1 种类型，则无论如何都不会发生这种情况，因此在实践中应始终评估为真。

这是将元素添加到列表的代码：

if (arr)
{
    dynamicArr* header = dynamicArr_Header(arr);
    if (header->typeSize && header->typeSize == sizeof item) //If I remove "header->typeSize == sizeof item" performance decreases.
    {
        size_t arrSize = dynamicArr_Size(header);
        if (arrSize == header->capacity)
        {
            size_t newCapacity = (size_t)(header->capacity * 1.5f);
            if (newCapacity == header->capacity) ++newCapacity;
            void* tmp = realloc(header, sizeof(dynamicArr) + header->typeSize * newCapacity);
            if (tmp)
            {
                dynamicArr_Construct(header, tmp, newCapacity, arrSize, header->typeSize);
                *((void**)&(arr)) = header->begin;
                arr[arrSize] = item;
                header->end += header->typeSize;
            }
            else 
            { 
                free(header); 
                arr = NULL; 
            }
        }
        else
        {
            arr[arrSize] = item;
            header->end += header->typeSize;
        }
    }
}

我不明白为什么会这样。我也不擅长阅读汇编，从我所看到的虽然它们非常不同，但如果有人能在这里帮助我，我将不胜感激！

（在 MSVC 中使用 /O2 和 /Tc 编译）

链接到程序集和其他相关代码。

编辑1： 很多人似乎认为原因是因为sizeof item只是在编译时进行了评估。我不认为是这样的情况，因为如果我删除的条件和替换的所有实例header->typeSize与sizeof item表现仍比如果最坏if条件在那里。=> 我似乎错过了更改导致这种混乱header->typeSize的宏中的使用dynamicArr_Size，请参阅标记的答案。

这是完整的代码：

typedef struct
{
    unsigned char* begin; // Pointer to data
    unsigned char* end; // Pointer to last element
    size_t typeSize; // Size of type
    size_t capacity; // Capacity of array (not number of elements in array)
} dynamicArr;

#define dynamicArr_ConstructBase(dest, src, newCapacity) dest = src; dest->capacity = newCapacity; dest->begin = (unsigned char*)dest + sizeof *dest
#define dynamicArr_Construct(dest, src, newCapacity, currSize, typeSize) dynamicArr_ConstructBase(dest, src, newCapacity); dest->end = dest->begin + typeSize * (currSize)

#define dynamicArr_Header(arr) ((dynamicArr*)((unsigned char*)(arr) - sizeof(dynamicArr)))
static inline size_t dynamicArr_Size(dynamicArr* arr)
{
    return (arr->end - arr->begin) / arr->typeSize;
}

#define dynamicArr_Create(typename, arr) typename* arr = (typename*)dynamicArr_Create_(sizeof(typename))
static inline unsigned char* dynamicArr_Create_(size_t typeSize)
{
    dynamicArr* dynArr;
    void* tmp = malloc(sizeof * dynArr + typeSize * 10);
    if (!tmp) return NULL;

    dynArr = tmp;
    dynArr->begin = (unsigned char*)dynArr + sizeof * dynArr;
    dynArr->end = dynArr->begin;
    dynArr->capacity = 10;
    dynArr->typeSize = typeSize;

    return dynArr->begin;
}

#define dynamicArr_Free(arr) free(dynamicArr_Header(arr))

#define dynamicArr_Push(arr, item) \
do {\
if (arr) \
{ \
    dynamicArr* header = dynamicArr_Header(arr); \
    if (header->typeSize && header->typeSize == sizeof item) \
    { \
        size_t arrSize = dynamicArr_Size(header); \
        if (arrSize == header->capacity) \
        { \
            size_t newCapacity = (size_t)(header->capacity * 1.5f); \
            if (newCapacity == header->capacity) ++newCapacity; \
            void* tmp = realloc(header, sizeof(dynamicArr) + header->typeSize * newCapacity); \
            if (tmp) \
            { \
                dynamicArr_Construct(header, tmp, newCapacity, arrSize, header->typeSize); \
                *((void**)&(arr)) = header->begin; \
                arr[arrSize] = item; \
                header->end += header->typeSize; \
            } \
            else  \
            {  \
                free(header);  \
                arr = NULL;  \
            } \
        } \
        else \
        { \
            arr[arrSize] = item; \
            header->end += header->typeSize; \
        } \
    } \
} \
} while(0)

和示例使用：

void Func()
{
    dynamicArr_Create(int, intArr);
    dynamicArr_Push(intArr, 10);
    printf("%i\n", intArr[0]);
    dynamicArr_Free(intArr);
}

至于一个简单的分析测试：

int main()
{
    dynamicArr_Create(int, intArr);

    clock_t begin = clock();

    for (int i = 0; i < 1000000000; ++i)
    {
        dynamicArr_Push(intArr, 10);
    }

    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("%f\n", time_spent);

    dynamicArr_Free(intArr);
}

在 Windows 上使用 /Tc 在 Visual Studio 2019 中以发布模式编译我得到结果：

• 使用header->typeSize == sizeof item=> 3.65 秒
• 没有header->typeSize == sizeof item=> 9.374 秒
• 更换header->typeSize用sizeof item以及去除header->typeSize == sizeof item=>9.302秒

我重复了 10 次测试，结果与上面的结果一致。

Answer 1

这是非常简单的常量传播，它使编译器能够使用更高效的指令。

由于 的值sizeof是编译时已知的常量，因此在进行比较的版本中，编译器知道 的值，typeSize因此可以使用更有效的指令。例如，这里是 的计算dynamicArr_Size(header)，也就是说，(header->end - header->begin) / header->typeSize：

--- without sizeof
+++ with sizeof
-        mov     rax, QWORD PTR [rbx+8]
-        xor     edx, edx
-        sub     rax, QWORD PTR [rbx]
-        div     r8
+        mov     rdi, QWORD PTR [rbx+8]
+        sub     rdi, QWORD PTR [rbx]
+        shr     rdi, 2

在没有 的版本中sizeof，编译器必须将元素大小视为未知并使用实际的除法指令（这也需要将rdx寄存器清零，因为该指令在rdx:rax寄存器对中取 128 位被除数）。当大小已知时，编译器可以替代更快的位移位并避免接触rdx. 这可能是最具影响力的差异，因为与其他算术相比，除法指令往往非常慢；大多数编译器，只要有机会（当除数为常数时），就会改为使用位移位或环绕乘法技巧来避免使用除法指令。（马特·戈德博特有在他关于编译器优化的一整节是关于除法的.) 更有效地使用寄存器还可以释放寄存器以在其他地方使用，并且可以防止将值溢出到内存中（尽管在这种情况下它似乎没有太大区别）。

另一个例子，这里是如何sizeof(dynamicArr) + header->typeSize * newCapacity计算：

--- without sizeof
+++ with sizeof
-        mov     rdx, rsi
-        imul    rdx, r8
-        add     rdx, 32
+        lea     rdx, QWORD PTR [rsi*4+32]

在没有与 比较的版本中sizeof，编译器必须将其header->typeSize视为未知并使用通用乘法指令。当大小已知时，它可以改为使用lea具有特殊寻址模式的指令，该指令允许在单个指令中计算值。尽管通用乘法不像除法那么慢，但位移仍然会胜过它。但即使lea本身不一定更快，更高的代码密度也允许更多的代码放入指令缓存中，并避免由于缓存未命中而导致速度减慢。

最后，你声称

很多人似乎认为原因是因为sizeof item只是在编译时进行了评估。我不认为是这样的情况，因为如果我删除的条件和替换的所有实例header->typeSize与sizeof item性能比如果如果条件是还有更糟糕的。

我假设您只替换了宏内部字段的直接使用，而不是dynamicArr_Size实用程序函数内部的间接使用。当您也替换该使用时，生成的代码几乎相同，模标签名称和if条件检查中的立即值。与 相比sizeof，编译器只是在内联该函数时自动执行此操作。