我有一个动态数组,其中有一个热循环,花费了大量时间向我实现的动态数组中添加许多元素。
动态数组通过在值数组的开头存储一个头部来工作:
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秒。
header->typesize
有时与sizeof item
不同,那么通过这个测试,你可以跳过一大块代码并节省执行所需的时间。 - Nate Eldredgeif
体内每个header->typeSize
的出现都可以优化为常量sizeof item
。 - Nate Eldredgesizeof item == 4
,因此可以将昂贵的div r8
替换为非常便宜的shr,rdi,2
。 - Raymond Chensize_t newCapacity = header->capacity + headerCapacity / 2;
或者size_t newCapacity = 2 * header->capacity;
这样的代码替换掉size_t newCapacity = (size_t)(header->capacity * 1.5f);
。浮点数计算很可能比简单的位移或位移加法更昂贵,而整数计算很可能会被优化成位移或位移加法。浮点数计算可能无法被优化为位移加法,因为这可能会产生不同的值。 - Andrew Henleglibc
时,这种方法就会失效,因为一旦达到mmap()
阈值,内存就直接分配给mmap()
块,不会留下“空洞”以供重复使用。而且它假设你的分配大小是随机的。如果你的大部分内存分配都是2的幂次方,则使用2的幂次方作为大小可以减少浪费堆内存的可能性。整个“最佳增长因子”的理论始终以“假设我们有一个愚蠢的内存分配器…”开头。简而言之:在计算机科学中,过度思考性能边角案例的情况太多了… - Andrew Henle