为何添加memset后自定义freelist分配器分配速度显著提升

• 开发freelist空闲链表内存分配器时，初始化阶段曾添加一行memset代码用于调试，移除该代码后发现：test1_managed测试函数中的内存分配逻辑，保留初始化memset时的运行速度比移除memset的版本快3~4倍。
• 编译环境：Visual Studio 2019 Release模式，MSVC 19.29.30140编译器，已开启/O2优化选项。

#pragma once
#include <cstdio>
#include <iostream>
#include <chrono>

using namespace std;
using namespace chrono;

const uint64_t MemSize = 1 << 20;
const uint64_t TestSize = 1 << 12;
typedef int TestType;

struct MemSegInfo {
    MemSegInfo* m_next{ 0 };
    MemSegInfo* m_nextFree{ 0 };
    uint64_t m_size{ 0 };
    uint64_t m_handle{ 0 };
};
const uint64_t infoSize = sizeof(MemSegInfo);
const uint64_t ptrSize = sizeof(MemSegInfo*);
const uint64_t maxAlignment = 16;

char* m_dataBuffer{ 0 };
char* m_dataBufferEnd{ 0 };
MemSegInfo* m_head;

MemSegInfo m_segFree;
MemSegInfo* m_segFreeCursor;

inline void* OffsetFromMemSegInfo(MemSegInfo* seg) {
    return ((char*)seg) + infoSize;
}
inline MemSegInfo* OffsetToMemSegInfo(void* ptr) {
    return (MemSegInfo*)(((char*)ptr) - infoSize);
}

template<class T>
inline void SetMem(MemSegInfo* seg, T&& val) {
    *((T*)OffsetFromMemSegInfo(seg)) = val;
}
template<class T>
inline void SetMem(MemSegInfo* seg, const T& val) {
    *((T*)OffsetFromMemSegInfo(seg)) = val;
}
template<class T>
inline T GetMem(MemSegInfo* seg) {
    return *((T*)OffsetFromMemSegInfo(seg));
}

void Init() {
    m_dataBuffer = (char*)malloc(MemSize);
    if (!m_dataBuffer)
        throw "Out of mem! ";
    m_dataBufferEnd = m_dataBuffer + MemSize;

    m_head = (MemSegInfo*)m_dataBuffer;
    m_head->m_next = m_head;
    //m_head->m_last = m_head;
    m_head->m_size = MemSize - infoSize;
    m_head->m_nextFree = &m_segFree;

    m_segFree.m_size = 0;
    m_segFree.m_nextFree = m_head;

    m_segFreeCursor = &m_segFree;

    /***THE MEMSET I AM TALKING ABOUT***/
    memset(OffsetFromMemSegInfo(m_head), 0xfafafafa, m_head->m_size);
}

MemSegInfo* Allocate(size_t size) {
    const uint64_t sizeAligned = ((size - 1) / maxAlignment + 1) * maxAlignment;
    const uint64_t sizeAlloc = sizeAligned + infoSize;
    MemSegInfo* segCurPrev = m_segFreeCursor;
    while (segCurPrev->m_nextFree->m_size < sizeAlloc) { // Go through freelist to find the First Fit. 
        segCurPrev = segCurPrev->m_nextFree;
        if (segCurPrev == m_segFreeCursor)
            throw "Out of mem! ";
    }
    MemSegInfo* const segCur = segCurPrev->m_nextFree;
    const uint64_t sizeRest = segCur->m_size - sizeAligned;
    if (sizeRest <= infoSize) { // There is not enough space for another seg. Just gonna use it. 
        segCurPrev->m_nextFree = segCur->m_nextFree; // This can also deal with the case where this is the last one available. 
        m_segFreeCursor = segCurPrev;
    }
    else { // There is enough space for another seg. Separate and make a new seg. 
        MemSegInfo* const segNew = (MemSegInfo*)(((char*)segCur) + sizeAlloc);
        MemSegInfo* const segNext = segCur->m_next;
        MemSegInfo* const segNextFree = segCur->m_nextFree;

        // Rearrange seg list
        //segNew->m_last = segCur;
        //segNext->m_last = segNew;
        segNew->m_next = segNext;
        segCur->m_next = segNew;
        segNew->m_size = sizeRest - infoSize;
        segCur->m_size = sizeAligned;
        segCur->m_nextFree = nullptr;

        // Join freelist
        segNew->m_nextFree = segNextFree;
        segCurPrev->m_nextFree = segNew;
        m_segFreeCursor = segCurPrev;
    }
    return segCur;
}

inline void Free(MemSegInfo* segFree) {
    // Join the freelist
    segFree->m_nextFree = m_segFree.m_nextFree;
    m_segFree.m_nextFree = segFree->m_nextFree;
}

void Cleanup() {
    free(m_dataBuffer);
}

MemSegInfo* mems[16];

struct MyStruct
{
    uint64_t m_a;
    uint64_t m_b;
    uint32_t m_c;
    uint32_t m_d;
};

void test0() {
    Init();

    mems[0] = Allocate(8);
    SetMem<uint64_t>(mems[0], 128);
    uint64_t t0 = GetMem<uint64_t>(mems[0]);
    mems[1] = Allocate(4);
    uint64_t t1 = GetMem<uint64_t>(mems[0]);
    SetMem<uint32_t>(mems[1], 256);
    uint64_t t2 = GetMem<uint64_t>(mems[0]);
    mems[2] = Allocate(64);
    int* a = (int*)OffsetFromMemSegInfo(mems[2]);
    for (int i = 0; i < 16; ++i) {
        a[i] = i;
    }
    mems[3] = Allocate(sizeof(MyStruct) * 8);
    MyStruct* b = (MyStruct*)OffsetFromMemSegInfo(mems[3]);
    for (int i = 0; i < 8; ++i) {
        b[i] = { (uint64_t)i, (uint64_t)i * 2, (uint32_t)i * 3, (uint32_t)i * 4 };
    }

    for (int i = 0; i < 16; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");

    Free(mems[1]);
    printf("%lld\n", GetMem<uint64_t>(mems[0]));
    for (int i = 0; i < 16; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
    for (int i = 0; i < 8; ++i) {
        printf("%lld %lld %ld %ld\t", b[i].m_a, b[i].m_b, b[i].m_c, b[i].m_d);
    }

    Cleanup();
}


TestType* bufferManaged[TestSize];
void test1_managed() {
    Init();
    
    /***ALLOCATION START***/
    system_clock::time_point beg_alloc = system_clock::now();
    TestType sum = 0;
    for (uint64_t i = 0; i < TestSize; ++i) {
        TestType val = i % INT32_MAX;
        bufferManaged[i] = new (OffsetFromMemSegInfo(Allocate(sizeof(TestType)))) TestType(val);
        sum += *bufferManaged[i];
    }
    /***ALLOCATION END***/
    std::atomic_signal_fence(std::memory_order_seq_cst);
    system_clock::time_point end_alloc = system_clock::now();
    printf("managed %llu ns\n", (std::chrono::duration_cast<std::chrono::nanoseconds>(end_alloc - beg_alloc)).count());
    printf("sum %d\n", sum);

    system_clock::time_point beg_free = system_clock::now();
    for (uint64_t i = 0; i < TestSize; ++i) {
        Free((MemSegInfo*)OffsetToMemSegInfo(bufferManaged[i]));
    }
    Cleanup();
    std::atomic_signal_fence(std::memory_order_seq_cst);
    system_clock::time_point end_free = system_clock::now();
    printf("managedfree %llu ns\n\n", (std::chrono::duration_cast<std::chrono::nanoseconds>(end_free - beg_free)).count());
}

TestType* bufferUnmanaged[TestSize];
void test1_unmnged() {
    system_clock::time_point beg_alloc = system_clock::now();
    TestType sum = 0;
    for (uint64_t i = 0; i < TestSize; ++i) {
        TestType val = i % INT32_MAX;
        bufferUnmanaged[i] = new TestType(val);
        sum += *bufferUnmanaged[i];
    }
    std::atomic_signal_fence(std::memory_order_seq_cst);
    system_clock::time_point end_alloc = system_clock::now();
    printf("unmnged %llu ns\n", (std::chrono::duration_cast<std::chrono::nanoseconds>(end_alloc - beg_alloc)).count());
    printf("sum %d\n", sum);

    system_clock::time_point beg_free = system_clock::now();
    for (uint64_t i = 0; i < TestSize; ++i) {
        delete bufferUnmanaged[i];
    }
    std::atomic_signal_fence(std::memory_order_seq_cst);
    system_clock::time_point end_free = system_clock::now();
    printf("unmngedfree %llu ns\n\n", (std::chrono::duration_cast<std::chrono::nanoseconds>(end_free - beg_free)).count());
}

void test1() {
    std::chrono::time_point<std::chrono::system_clock> now = std::chrono::system_clock::now();
    auto epoch = now.time_since_epoch();
    auto value = std::chrono::duration_cast<std::chrono::milliseconds>(epoch);
    long duration = value.count();
    srand(duration);

    for (int i = 0; i < 10; i++) {
        printf("test%d\n", i);
        test1_managed();
        test1_unmnged();
        printf("\n");
    }
}

void test() {
    test1();
}

造成该性能差异的核心原因是操作系统按需调页机制带来的缺页中断开销，和直觉上“多做了memset写操作应该更慢”相反，这行memset反而提前消除了分配循环中的大量高开销操作：

1. malloc申请1MB内存时，操作系统只会在进程虚拟地址空间预留对应范围，不会立刻分配物理内存、建立页表映射。只有当程序第一次访问某段虚拟地址对应的页时，才会触发缺页异常，陷入内核态分配物理页、完成页表映射，再返回用户态继续执行，单次缺页异常的开销可达数百个CPU时钟周期。
2. 移除memset时，整个分配循环中每次切分内存块、写入块头MemSegInfo、写入TestType数据的操作，都会零散触发缺页异常。1MB内存对应256个4KB常规页，零散触发的200多次缺页异常的总开销，远大于memset本身的写内存开销。
3. 保留memset时，这行代码会按地址顺序连续写完整个1MB内存区域：一方面批量触发所有缺页异常，内核处理连续地址的缺页时会启用预取机制，批量完成多页的物理内存分配和映射，比零散处理缺页的效率高一个量级；另一方面顺序写操作会被CPU硬件预取器识别，提前把后续内存加载到CPU缓存中，后续分配循环访问内存时缓存命中率极高，进一步降低访问延迟。

额外注意代码中存在一个逻辑bug：Free函数的实现有误，当前写法并不会把释放的内存块插回空闲链表，后续如果做分配-释放-再分配的测试会直接出现内存泄漏或分配错误，正确的链表插入逻辑应该把第二行赋值改为m_segFree.m_nextFree = segFree;。

内容的提问来源于stack exchange，提问作者tigerccx