评估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种类型，则实际上不应该发生这种情况，因此比较应始终为true。

下面是向列表添加元素的代码：

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;
        }
    }
}

我不明白为什么会出现这种情况。我对汇编语言的阅读能力也不是很好，但从我所看到的来看，它们非常不同，如果有人能帮助我解决这个问题，那将不胜感激！

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

Link to the assembly and the rest of the relevant code.

编辑1： 许多人似乎认为原因是因为sizeof item只是在编译时计算。我不认为这是正确的，因为如果我删除条件并将所有实例替换为header->typeSize，性能仍然比有if条件更差。 => 我似乎错过了在宏dynamicArr_Size中更改header->typeSize的用法，导致了这种混淆，请参阅标记的答案。

这是完整的代码：

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次测试，结果与上面的结果一致。

- name

---

如果header->typesize有时与sizeof item不同，那么通过这个测试，你可以跳过一大块代码并节省执行所需的时间。 - Nate Eldredge

即使您不跳过它，if体内每个header->typeSize的出现都可以优化为常量sizeof item。 - Nate Eldredge

在codegen中可以看到，通过对sizeof item进行测试，编译器可以假定在分支内sizeof item == 4，因此可以将昂贵的div r8替换为非常便宜的shr，rdi，2。 - Raymond Chen

如果性能是一个问题，你应该考虑用类似 size_t newCapacity = header->capacity + headerCapacity / 2; 或者 size_t newCapacity = 2 * header->capacity; 这样的代码替换掉 size_t newCapacity = (size_t)(header->capacity * 1.5f);。浮点数计算很可能比简单的位移或位移加法更昂贵，而整数计算很可能会被优化成位移或位移加法。浮点数计算可能无法被优化为位移加法，因为这可能会产生不同的值。 - Andrew Henle

@name 当使用glibc时，这种方法就会失效，因为一旦达到mmap()阈值，内存就直接分配给mmap()块，不会留下“空洞”以供重复使用。而且它假设你的分配大小是随机的。如果你的大部分内存分配都是2的幂次方，则使用2的幂次方作为大小可以减少浪费堆内存的可能性。整个“最佳增长因子”的理论始终以“假设我们有一个愚蠢的内存分配器…”开头。简而言之：在计算机科学中，过度思考性能边角案例的情况太多了… - Andrew Henle

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。这可能是最有影响力的差异，因为相对于其他算术运算，除法指令往往非常缓慢；大多数编译器只要有机会（当除数为常数时），就会使用位移或环绕乘法技巧来避免使用除法指令。（Matt Godbolt在他的关于编译器优化的演讲中有关于除法的整个部分。）更有效地使用寄存器也释放了寄存器以在其他地方使用，并且可能防止将值溢出到内存中（尽管在这种情况下似乎没有太大的区别）。

另一个例子，这里展示了如何计算 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进行比较时，编译器会在内联该函数时自动执行此操作。

- user3840170

---

感谢您清晰地解释了一切，我再次进行了分析以进行检查，这确实是情况。我假设您只替换了宏内部直接使用的字段，而没有替换 dynamicArr_Size 实用程序函数内部的间接使用。- 是的，这确实是发生的事情哈哈，我最终搞混了自己，可能也搞混了其他人。没想到使用不同指令会有如此大的性能差异！ - name

Answer 2

这里需要注意的主要是 dynamicArr_Push 是一个宏而不是函数。

if (header->typeSize && header->typeSize == sizeof item) \

而这一行向编译器提供了一个提示，即仅插入 typeSize 项，并且它可以在for循环中预先计算您需要的最大大小（ 1000000000 * sizeof(item)），并通过一次性分配一个大块来消除重复的内存分配。

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

为了测试这个，请在dynamicArr_Create_中将初始capacity大小更改为1000000000（dynArr->capacity = 10;），然后再次运行测试，删除检查header->typeSize == sizeof item。您应该观察到与size-check版本类似的性能提升。否则，请尝试像strace这样的工具来计算调用realloc的次数，有无size-check。在size-check版本中，它们必须完全被消除。

- Fractal

Answer 3

sizeof 是一个运算符，几乎所有情况下都在编译时计算（VLA 是一个例外）

- vtorri

---

我认为这不是原因，因为如果我删除if条件并将header->typeSize替换为sizeof item，性能仍然比有if条件时差。 - name