c - 评估 sizeof 导致性能改进 C

Question

我有一个动态数组，并且有一个热循环，它花费大量时间向我实现的动态数组添加大量元素。
动态数组的工作原理是在值数组的开头存储一个 header :

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 编译)
Link到程序集和其他相关代码。
编辑 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 中以 Release模式编译我得到结果:

与 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 .这可能是最具影响力的差异，因为与其他算术相比，除法指令往往非常慢；大多数编译器，只要有机会(当除数为常数时)，就会改为使用位移位或 wrap-around multiplication tricks只是为了避免使用除法指令。 (Matt Godbolt 有 a whole section about division in his talk about compiler optimisations 。)更有效地使用寄存器还可以释放寄存器以在其他地方使用，并且可以防止将值溢出到内存中(尽管在这种情况下似乎没有太大区别)。
另一个例子，这是如何 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本身不一定更快，更高的代码密度允许更多的代码适合指令缓存并避免由于缓存未命中而导致速度减慢。
最后，你声称

A lot of people seem to think that the reason is because sizeof item is simply evaluated at compile time. I don't think that this is the case because if I remove the condition and replace all instances of header->typeSize with sizeof item the performance is still worse than if the if condition was there.

我假设您只替换了宏内部字段的直接使用，而不是 dynamicArr_Size 内部的间接使用。实用功能。当您也替换该用法时， the generated code is nearly identical, modulo label names and the immediate value in the if condition check .与 sizeof 对比，编译器只是在内联该函数时自动执行此操作。