PhysX帧分配器：一帧一擦的高效艺术

写满就擦擦完再写永不停歇引子数学老师的白板还记得高中数学课吗老师走进教室面前是一块干干净净的白板。他开始讲解——写公式、画图形、列步骤白板渐渐被填满。下课铃响老师拿起板擦唰唰几下白板又干干净净了。下节课的老师走进来面对的又是一块崭新的白板。没有人会在意上节课写了什么。没有人需要把每个字单独擦掉。一块板擦从左到右一抹所有内容瞬间消失。这就是PhysX帧分配器的全部哲学。每一帧就是一节课。帧开始时白板是空的。物理引擎在上面疯狂书写——碰撞对、接触点、约束矩阵、岛组数据。帧结束时板擦一抹一切归零。下一帧白板重新开始。不需要一个字一个字地擦。不需要记住哪个字写在哪里。不需要回收、合并、整理。一行代码清空一切。mCurrentOffset0;// 这就是那块板擦一、为什么需要帧分配器1.1 物理模拟中的一次性数据┌──────────────────────────────────────────────────┐ │ │ │ 物理引擎每帧的工作流程 │ │ │ │ ┌─────────┐ │ │ │ 宽阶段 │ 产出潜在碰撞对列表 │ │ └────┬────┘ 哪些物体的包围盒重叠了 │ │ ↓ │ │ ┌─────────┐ │ │ │ 窄阶段 │ 产出精确接触点 │ │ └────┬────┘ 碰撞发生在哪里法线是什么 │ │ ↓ │ │ ┌─────────┐ │ │ │ 岛分析 │ 产出岛组划分 │ │ └────┬────┘ 哪些物体连在一起需要一起求解 │ │ ↓ │ │ ┌─────────┐ │ │ │ 约束构建│ 产出约束矩阵 │ │ └────┬────┘ 求解器需要的数学数据 │ │ ↓ │ │ ┌─────────┐ │ │ │ 求解器 │ 产出速度修正 │ │ └────┬────┘ 每个物体该怎么动 │ │ ↓ │ │ ┌─────────┐ │ │ │ 积分 │ 产出新的位置和旋转 │ │ └─────────┘ │ │ │ │ │ │ 注意看那些产出 │ │ │ │ 潜在碰撞对列表 → 窄阶段用完就不需要了 │ │ 精确接触点 → 约束构建用完就不需要了 │ │ 岛组划分 → 求解器用完就不需要了 │ │ 约束矩阵 → 求解器用完就不需要了 │ │ 速度修正 → 积分用完就不需要了 │ │ │ │ 每一步的产出都是下一步的输入。 │ │ 下一步用完后上一步的产出就是垃圾。 │ │ 到帧末尾所有中间数据全部是垃圾。 │ │ │ │ 下一帧完全重新计算。 │ │ 上一帧的碰撞对物体已经移动了全部作废。 │ │ 上一帧的接触点位置变了全部作废。 │ │ 上一帧的约束矩阵全部作废。 │ │ │ │ 这些数据的生命周期 │ │ │ │ ──诞生──使用──死亡── │ │ ←───── 一帧 ─────→ │ │ │ │ 活不过16毫秒。 │ │ │ └──────────────────────────────────────────────────┘1.2 如果用malloc管理这些数据┌──────────────────────────────────────────────────┐ │ │ │ 每帧的分配/释放操作 │ │ │ │ 宽阶段 │ │ malloc(碰撞对列表) // 分配 │ │ ...使用... │ │ free(碰撞对列表) // 释放 │ │ │ │ 窄阶段 │ │ malloc(接触点缓冲区) // 分配 │ │ ...使用... │ │ free(接触点缓冲区) // 释放 │ │ │ │ 岛分析 │ │ malloc(岛组数据) // 分配 │ │ ...使用... │ │ free(岛组数据) // 释放 │ │ │ │ 约束构建 │ │ malloc(约束矩阵) // 分配 │ │ ...使用... │ │ free(约束矩阵) // 释放 │ │ │ │ 求解器 │ │ malloc(速度修正数组) // 分配 │ │ ...使用... │ │ free(速度修正数组) // 释放 │ │ │ │ │ │ 每帧5次malloc 5次free 10次系统调用 │ │ 实际远不止5次这里只列了大类 │ │ 实际可能是几千次malloc 几千次free │ │ │ │ 而且每次free都要 │ │ 找到对应的内存块元数据 │ │ 更新空闲链表 │ │ 可能合并相邻空闲块 │ │ 可能归还页面给操作系统 │ │ │ │ 这些数据明明16毫秒后就全部作废 │ │ 为什么要花这么大力气一个一个释放 │ │ │ │ 就像考试结束后 │ │ 你不会一个字一个字地把草稿纸上的字擦掉。 │ │ 你直接把草稿纸揉成一团扔进垃圾桶。 │ │ │ │ 帧分配器做的事情比扔垃圾桶还简单 │ │ 它连扔都不扔。 │ │ 它只是假装草稿纸是空白的然后继续用。 │ │ │ └──────────────────────────────────────────────────┘二、帧分配器的核心实现2.1 最纯粹的形态线性分配器// 文件source/lowlevel/pipeline/include/// PxcScratchAllocator.h// 简化后的核心逻辑classFrameAllocator{PxU8*mBuffer;// 预分配的大缓冲区PxU8*mEnd;// 缓冲区末尾PxU8*mCurrent;// 当前分配位置笔尖// 构造一次性分配一大块内存FrameAllocator(size_t totalSize){mBuffer(PxU8*)PX_ALLOC(totalSize,FrameBuffer);mEndmBuffertotalSize;mCurrentmBuffer;}// 分配把笔尖往后移void*alloc(size_t size){size(size15)~15;// 16字节对齐if(mCurrentsizemEnd)returnnullptr;// 写满了void*ptrmCurrent;mCurrentsize;returnptr;}// 重置笔尖回到起点voidreset(){mCurrentmBuffer;}};┌──────────────────────────────────────────────────┐ │ │ │ 就三个指针。 │ │ 整个分配器的状态三个指针就够了。 │ │ │ │ mBuffer白板的左边缘 │ │ mEnd白板的右边缘 │ │ mCurrent笔尖当前的位置 │ │ │ │ │ │ 分配操作 │ │ │ │ ① 检查剩余空间够不够 │ │ ② 记录当前笔尖位置这就是返回的指针 │ │ ③ 笔尖往后移 │ │ │ │ 三步。没有搜索。没有链表。没有锁。 │ │ 约5纳秒。 │ │ │ │ │ │ 重置操作 │ │ │ │ mCurrent mBuffer; │ │ │ │ 一步。约1纳秒。 │ │ 不管这一帧分配了5次还是50000次 │ │ 重置的成本都是一次赋值。 │ │ │ └──────────────────────────────────────────────────┘2.2 图解一帧的生命周期┌──────────────────────────────────────────────────┐ │ │ │ ═══════════ 第N帧开始 ═══════════ │ │ │ │ 白板状态512KB缓冲区 │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ │ │ │ │ 全部可用 │ │ │ │ 524288字节 │ │ │ │ │ │ │ └────────────────────────────────────────────┘ │ │ ↑ ↑ │ │ mBuffer mEnd │ │ mCurrent │ │ │ │ │ │ ─── 宽阶段开始 ─── │ │ │ │ alloc(32000) // 2000个碰撞对 × 16字节 │ │ │ │ ┌────────────┬───────────────────────────────┐ │ │ │ 碰撞对列表 │ │ │ │ │ 32000B │ 剩余492288B │ │ │ └────────────┴───────────────────────────────┘ │ │ ↑ │ │ mCurrent │ │ │ │ 耗时5纳秒。 │ │ 对比malloc(32000)约500纳秒。 │ │ │ │ │ │ ─── 窄阶段开始 ─── │ │ │ │ alloc(144000) // 3000个接触点 × 48字节 │ │ │ │ ┌────────────┬──────────────┬────────────────┐ │ │ │ 碰撞对列表 │ 接触点缓冲 │ │ │ │ │ 32000B │ 144000B │ 剩余348288B │ │ │ └────────────┴──────────────┴────────────────┘ │ │ ↑ │ │ mCurrent │ │ │ │ 注意碰撞对列表其实已经没用了。 │ │ 但我们不释放它。不需要释放。 │ │ 它就静静地躺在那里占着32000字节。 │ │ 帧末会统一回收。 │ │ │ │ │ │ ─── 岛分析 ─── │ │ │ │ alloc(12000) // 500个岛节点 × 24字节 │ │ │ │ ┌────────────┬──────────────┬───────┬────────┐ │ │ │ 碰撞对列表 │ 接触点缓冲 │ 岛数据│ │ │ │ │ 32000B │ 144000B │12000B │336288B │ │ │ └────────────┴──────────────┴───────┴────────┘ │ │ ↑ │ │ mCurrent │ │ │ │ │ │ ─── 约束构建 ─── │ │ │ │ alloc(256000) // 2000个约束 × 128字节 │ │ │ │ ┌──────┬──────────┬─────┬──────────┬─────────┐ │ │ │碰撞对│ 接触点 │岛数据│ 约束矩阵 │ 80288B │ │ │ │32000 │ 144000 │12000│ 256000 │ 剩余 │ │ │ └──────┴──────────┴─────┴──────────┴─────────┘ │ │ ↑ │ │ mCurrent │ │ │ │ │ │ ─── 求解器 ─── │ │ │ │ alloc(48000) // 2000个物体 × 24字节速度修正 │ │ │ │ ┌──────┬────────┬─────┬────────┬──────┬──────┐ │ │ │碰撞对│接触点 │岛 │约束 │速度 │32288 │ │ │ │32000 │144000 │12000│256000 │48000 │ 剩余 │ │ │ └──────┴────────┴─────┴────────┴──────┴──────┘ │ │ ↑ │ │ mCurrent │ │ │ │ 512KB的缓冲区用了492000字节还剩32288字节。 │ │ 整帧只做了5次分配5次指针移动。 │ │ 没有一次malloc。没有一次free。 │ │ │ │ │ │ ═══════════ 第N帧结束 ═══════════ │ │ │ │ reset() │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ │ │ │ │ 全部可用 │ │ │ │ 524288字节 │ │ │ │ │ │ │ └────────────────────────────────────────────┘ │ │ ↑ │ │ mCurrent mBuffer │ │ │ │ 上一帧的数据还在内存里吗 │ │ 物理上在。那些字节没有被清零。 │ │ 逻辑上不在。mCurrent回到了起点。 │ │ 下一帧的新数据会直接覆盖它们。 │ │ │ │ 就像白板没有被擦干净 │ │ 只是老师说这些都不算了我从头开始写。 │ │ 新内容写上去时旧内容自然被覆盖。 │ │ │ │ │ │ ═══════════ 第N1帧开始 ═══════════ │ │ │ │ 一切重新来过。 │ │ 同一块512KB的内存承载着全新的数据。 │ │ 永远不需要申请新内存。 │ │ 永远不需要释放旧内存。 │ │ 永远不会产生碎片。 │ │ │ └──────────────────────────────────────────────────┘三、Scratch BufferPhysX的官方草稿纸3.1 用户接口// PhysX允许用户在simulate时提供scratch buffer// 游戏初始化时void*scratchMemoryallocAligned(512*1024,16);// 每帧模拟时scene-simulate(1.0f/60.0f,// 时间步长nullptr,// 完成回调scratchMemory,// 草稿纸 ← 就是这个512*1024// 草稿纸大小);scene-fetchResults(true);// simulate结束后scratchMemory自动重置// 不需要用户做任何事情// 下一帧继续传同一块内存进去┌──────────────────────────────────────────────────┐ │ │ │ 为什么让用户提供scratch buffer │ │ 而不是PhysX自己分配 │ │ │ │ │ │ 原因1大小可控 │ │ │ │ 手机游戏内存紧张 │ │ → 给128KB的scratch │ │ → PhysX在128KB内尽量工作 │ │ → 不够用时回退到用户分配器慢但能用 │ │ │ │ PC大作内存充裕 │ │ → 给2MB的scratch │ │ → PhysX几乎所有临时数据都在scratch内 │ │ → 极少回退性能拉满 │ │ │ │ 主机游戏内存固定 │ │ → 根据场景复杂度精确计算scratch大小 │ │ → 不浪费一个字节 │ │ │ │ │ │ 原因2来源可控 │ │ │ │ 可以从主内存分配 │ │ 可以从预留的物理内存区域分配 │ │ 可以从内存映射的特殊区域分配 │ │ 甚至可以从上一帧不用的渲染缓冲区借用 │ │ │ │ PhysX不关心内存从哪来。 │ │ 它只关心给我一个指针和一个大小。 │ │ │ │ │ │ 原因3生命周期可控 │ │ │ │ 用户分配用户释放。 │ │ PhysX不持有这块内存的所有权。 │ │ 游戏切换关卡时用户可以释放scratch │ │ 换一块更大或更小的。 │ │ PhysX完全不受影响。 │ │ │ └──────────────────────────────────────────────────┘3.2 内部实现带溢出处理的scratch分配器// 文件source/lowlevel/pipeline/include/// PxcScratchAllocator.h// 更完整的实现classPxcScratchAllocator{PxU8*mStart;PxU8*mEnd;PxU8*mCurrent;// 溢出分配的记录用于释放structOverflowRecord{void*mPtr;size_t mSize;};PxArrayOverflowRecordmOverflows;void*alloc(size_t size){size(size15)~15;// 快路径scratch够用if(mCurrentsizemEnd){void*ptrmCurrent;mCurrentsize;returnptr;// 5纳秒结束}// 慢路径scratch不够了回退到用户分配器void*ptrPX_ALLOC(size,ScratchOverflow);mOverflows.pushBack({ptr,size});returnptr;// 300纳秒但至少不会崩溃}voidreset(){// 重置scratch指针mCurrentmStart;// 释放所有溢出分配for(autorec:mOverflows)PX_FREE(rec.mPtr);mOverflows.clear();}};┌──────────────────────────────────────────────────┐ │ │ │ 溢出处理的设计哲学 │ │ │ │ 尽力而为优雅降级 │ │ │ │ │ │ 理想情况99%的帧 │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ 数据A │ 数据B │ 数据C │ 数据D │ 剩余 │ │ │ └────────────────────────────────────────────┘ │ │ ← ─ ─ ─ ─ ─ scratch buffer ─ ─ ─ ─ ─ ─ ─ → │ │ │ │ 所有数据都在scratch内。 │ │ 零malloc。零free。极致性能。 │ │ │ │ │ │ 极端情况1%的帧比如大爆炸 │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ 数据A │ 数据B │ 数据C │ 数据D │ 数据E│满│ │ │ └────────────────────────────────────────────┘ │ │ ← ─ ─ ─ ─ ─ scratch buffer ─ ─ ─ ─ ─ ─ ─ → │ │ │ │ scratch写满了数据F放不下了 │ │ │ │ 怎么办崩溃丢弃数据 │ │ 都不。优雅降级 │ │ │ │ 数据F → malloc分配慢但能用 │ │ 数据G → malloc分配 │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ 数据A │ 数据B │ 数据C │ 数据D │ 数据E│ │ │ │ └────────────────────────────────────────────┘ │ │ │ │ 堆上 │ │ ┌────────┐ ┌────────┐ │ │ │ 数据F │ │ 数据G │ ← 溢出到堆上 │ │ └────────┘ └────────┘ │ │ │ │ 帧结束时reset() │ │ ① mCurrent mStart重置scratch │ │ ② free(数据F), free(数据G)释放溢出 │ │ │ │ 下一帧又恢复正常。 │ │ │ │ │ │ 这个设计的精妙之处 │ │ │ │ scratch不够用时不会崩溃只会变慢。 │ │ 就像高速公路堵车了车辆自动走辅路。 │ │ 辅路慢一点但至少能到达目的地。 │ │ │ │ 而且PhysX会在日志中警告 │ │ Scratch buffer overflow, consider increasing │ │ scratch buffer size │ │ 提醒你下次给大一点的scratch。 │ │ │ └──────────────────────────────────────────────────┘四、栈式帧分配器精确回退4.1 纯线性分配器的遗憾┌──────────────────────────────────────────────────┐ │ │ │ 纯线性分配器有一个小遗憾 │ │ │ │ 宽阶段分配了碰撞对列表32KB │ │ 窄阶段用完了碰撞对列表 │ │ 窄阶段需要分配接触点缓冲144KB │ │ │ │ 此时碰撞对列表已经没用了。 │ │ 如果能回收那32KB接触点缓冲就有更多空间。 │ │ │ │ 但纯线性分配器做不到。 │ │ 笔尖只能往前走不能往回退。 │ │ │ │ ┌──────────┬──────────────────────────────┐ │ │ │碰撞对32KB│ │ │(已没用了)│ 剩余空间 │ │ │ └──────────┴──────────────────────────────┘ │ │ ↑ │ │ mCurrent只能往右不能往左 │ │ │ │ 那32KB就这么浪费了直到帧末reset。 │ │ │ │ 如果scratch本来就紧张 │ │ 这32KB的浪费可能导致后面的分配溢出到堆上。 │ │ 本来不用走慢路径的现在被迫走慢路径。 │ │ │ │ 能不能让笔尖有条件地往回退 │ │ │ └──────────────────────────────────────────────────┘4.2 栈式回退的实现// 文件source/lowlevel/pipeline/include/// PxcScratchAllocator.h// 栈式回退的核心逻辑classStackFrameAllocator{PxU8*mStart;PxU8*mEnd;PxU8*mCurrent;// 每次分配时在数据前面塞一个书签structBookmark{size_t mTotalSize;// 这次分配的总大小PxU8*mPrevCurrent;// 分配前笔尖在哪};void*alloc(size_t requestedSize){size_t alignedSize(requestedSize15)~15;size_t headerSize(sizeof(Bookmark)15)~15;size_t totalSizeheaderSizealignedSize;if(mCurrenttotalSizemEnd)returnfallbackAlloc(requestedSize);// 写入书签Bookmark*bm(Bookmark*)mCurrent;bm-mTotalSizetotalSize;bm-mPrevCurrentmCurrent;// 返回书签后面的地址用户数据区void*userPtrmCurrentheaderSize;mCurrenttotalSize;returnuserPtr;}voidfree(void*ptr){if(!ptr)return;size_t headerSize(sizeof(Bookmark)15)~15;Bookmark*bm(Bookmark*)((PxU8*)ptr-headerSize);// 关键判断这是不是最后一次分配if((PxU8*)bmbm-mTotalSizemCurrent){// 是最后一次笔尖可以回退mCurrentbm-mPrevCurrent;}// 不是最后一次什么都不做。// 等帧末reset统一回收。}voidreset(){mCurrentmStart;}};4.3 图解栈式回退┌──────────────────────────────────────────────────┐ │ │ │ 想象一摞书。 │ │ │ │ 你只能拿走最上面的那本。 │ │ 想拿中间的不行。 │ │ 想拿最下面的更不行。 │ │ 只有最上面的那本才能被安全地拿走。 │ │ │ │ 这就是栈的规则后进先出LIFO。 │ │ │ │ │ │ 实际操作过程 │ │ │ │ │ │ 步骤1分配A碰撞对32KB │ │ │ │ ┌────┬──────────┬───────────────────────────┐ │ │ │书签│ A │ 剩余 │ │ │ │ A │ 32KB │ │ │ │ └────┴──────────┴───────────────────────────┘ │ │ ↑ │ │ mCurrent │ │ │ │ 书签A记录了 │ │ mPrevCurrent 缓冲区起点 │ │ mTotalSize 32KB 书签大小 │ │ │ │ │ │ 步骤2分配B接触点144KB │ │ │ │ ┌────┬──────────┬────┬──────────────┬───────┐ │ │ │书签│ A │书签│ B │ │ │ │ │ A │ 32KB │ B │ 144KB │ 剩余 │ │ │ └────┴──────────┴────┴──────────────┴───────┘ │ │ ↑ │ │ mCurrent │ │ │ │ 书签B记录了 │ │ mPrevCurrent A结束的位置 │ │ mTotalSize 144KB 书签大小 │ │ │ │ │ │ 步骤3分配C岛数据12KB │ │ │ │ ┌────┬──────┬────┬──────────┬────┬─────┬────┐ │ │ │书签│ A │书签│ B │书签│ C │剩余│ │ │ │ A │ 32KB │ B │ 144KB │ C │12KB │ │ │ │ └────┴──────┴────┴──────────┴────┴─────┴────┘ │ │ ↑ │ │ mCurrent │ │ │ │ │ │ 现在C用完了想释放C │ │ │ │ free(C) │ │ → C是最后一次分配吗 │ │ → 书签C的位置 书签C的totalSize mCurrent │ │ → 是的C就是最上面那本书 │ │ → 笔尖回退到书签C记录的mPrevCurrent │ │ │ │ ┌────┬──────┬────┬──────────┬────────────────┐ │ │ │书签│ A │书签│ B │ 剩余 │ │ │ │ A │ 32KB │ B │ 144KB │ (C的空间回来) │ │ │ └────┴──────┴────┴──────────┴────────────────┘ │ │ ↑ │ │ mCurrent回退了 │ │ │ │ C的12KB空间被回收了 │ │ 后续的分配可以复用这块空间。 │ │ │ │ │ │ 继续B也用完了想释放B │ │ │ │ free(B) │ │ → B现在是最后一次分配吗 │ │ → 是的C已经被释放了B变成了最上面的 │ │ → 笔尖回退到书签B记录的mPrevCurrent │ │ │ │ ┌────┬──────┬───────────────────────────────┐ │ │ │书签│ A │ 剩余 │ │ │ │ A │ 32KB │ (B和C的空间都回来了) │ │ │ └────┴──────┴───────────────────────────────┘ │ │ ↑ │ │ mCurrent又回退了 │ │ │ │ 太棒了144KB 12KB 156KB的空间被回收 │ │ │ │ │ │ 但如果顺序不对呢 │ │ │ │ 如果先释放B再释放C │ │ │ │ free(B) │ │ → B是最后一次分配吗 │ │ → 不是C在B后面B不是最上面那本书 │ │ → 什么都不做。B的空间暂时无法回收。 │ │ │ │ free(C) │ │ → C是最后一次分配吗 │ │ → 是的 │ │ → 笔尖回退回收C的空间。 │ │ → 但B的空间仍然无法回收A还在B前面。 │ │ │ │ ┌────┬──────┬────┬──────────┬────────────────┐ │ │ │书签│ A │书签│ B(废弃) │ 剩余 │ │ │ │ A │ 32KB │ B │ (空洞) │ (C的空间回来) │ │ │ └────┴──────┴────┴──────────┴────────────────┘ │ │ │ │ B变成了一个空洞。 │ │ 这个空洞要等到帧末reset才能回收。 │ │ │ │ │ │ 所以栈式回退有一个前提 │ │ 释放顺序必须和分配顺序相反。 │ │ 后分配的先释放。 │ │ 就像叠盘子后放的先拿。 │ │ │ └──────────────────────────────────────────────────┘4.4 为什么物理管线天然适合栈式回退┌──────────────────────────────────────────────────┐ │ │ │ 物理管线的数据流天然是后进先出的 │ │ │ │ 时间轴 → │ │ │ │ 分配A碰撞对 │ │ ├── 宽阶段使用A │ │ │ 分配B接触点 │ │ │ ├── 窄阶段使用A和B │ │ │ │ 分配C约束 │ │ │ │ ├── 约束构建使用B和C │ │ │ │ │ 分配D求解器临时数据 │ │ │ │ │ ├── 求解器使用C和D │ │ │ │ │ │ │ │ │ │ │ 释放D ← 最后分配的最先释放 │ │ │ │ 释放C │ │ │ 释放B │ │ 释放A │ │ │ │ 完美的栈结构 │ │ │ │ A最先分配最后释放整帧都需要碰撞对信息 │ │ D最后分配最先释放求解器用完就不需要了 │ │ │ │ 这不是巧合。 │ │ 物理管线本身就是一个层层深入、层层退出的过程。 │ │ 就像函数调用栈 │ │ main() → broadPhase() → narrowPhase() │ │ → buildConstraints() → solve() │ │ → solve返回 → buildConstraints返回 │ │ → narrowPhase返回 → broadPhase返回 │ │ │ │ 每一层的临时数据在退出该层时就可以释放。 │ │ 天然的后进先出。 │ │ 栈式帧分配器就是为这种模式量身定做的。 │ │ │ └──────────────────────────────────────────────────┘五、多线程下的帧分配器5.1 问题多个线程同时写白板┌──────────────────────────────────────────────────┐ │ │ │ PhysX是多线程的。 │ │ 窄阶段碰撞检测会分配到4-8个工作线程上。 │ │ 每个线程都需要分配临时内存。 │ │ │ │ 如果共享一个帧分配器 │ │ │ │ 线程0mCurrent在100处要分配48字节 │ │ 线程1mCurrent在100处也要分配48字节 │ │ 它们同时读到了mCurrent 100 │ │ │ │ 线程0mCurrent 100 48 148 │ │ 线程1mCurrent 100 48 148 │ │ 它们都把mCurrent设成了148 │ │ │ │ 结果两个线程拿到了同一块内存 │ │ 线程0写入的数据被线程1覆盖。 │ │ 物理模拟产生错误结果。 │ │ 或者直接崩溃。 │ │ │ │ │ │ 解决方案1加锁 │ │ │ │ mutex.lock(); │ │ ptr mCurrent; │ │ mCurrent size; │ │ mutex.unlock(); │ │ │ │ 可以但每次分配都要加锁解锁。 │ │ 锁的开销20-50纳秒。 │ │ 分配本身只要5纳秒。 │ │ 锁比分配还贵 │ │ 而且多线程竞争时锁的开销会飙升到微秒级。 │ │ │ │ │ │ 解决方案2原子操作 │ │ │ │ ptr atomicAdd(mCurrent, size); │ │ │ │ 比锁快约10-20纳秒。 │ │ 但仍然有竞争开销。 │ │ 而且原子操作会导致缓存行失效 │ │ 影响其他线程的缓存性能。 │ │ │ │ │ │ 解决方案3PhysX的选择——分区 │ │ │ │ 不竞争。 │ │ 每个线程有自己的区域。 │ │ 零锁。零原子操作。零竞争。 │ │ │ └──────────────────────────────────────────────────┘5.2 分区策略┌──────────────────────────────────────────────────┐ │ │ │ PhysX把scratch buffer切成多个分区 │ │ │ │ ┌──────────────────────────────────────────┐ │ │ │ 512KB Scratch Buffer │ │ │ ├──────────┬──────────┬──────────┬─────────┤ │ │ │ 分区0 │ 分区1 │ 分区2 │ 分区3 │ │ │ │ 128KB │ 128KB │ 128KB │ 128KB │ │ │ │ │ │ │ │ │ │ │ 线程0用 │ 线程1用 │ 线程2用 │ 线程3用 │ │ │ │ │ │ │ │ │ │ │ 自己的 │ 自己的 │ 自己的 │ 自己的 │ │ │ │ mCurrent │ mCurrent │ mCurrent │mCurrent │ │ │ └──────────┴──────────┴──────────┴─────────┘ │ │ │ │ │ │ 每个线程在自己的128KB分区内线性分配。 │ │ 线程0的mCurrent和线程1的mCurrent完全独立。 │ │ 互不干扰。 │ │ │ │ 线程0分配48字节 │ │ 自己的mCurrent 48 │ │ 不需要看其他线程的脸色 │ │ 5纳秒和单线程一样快 │ │ │ │ 线程1同时分配128字节 │ │ 自己的mCurrent 128 │ │ 不需要等线程0 │ │ 5纳秒 │ │ │ │ 四个线程同时分配总耗时5纳秒。 │ │ 不是20纳秒4×5而是5纳秒。 │ │ 因为它们完全并行没有任何串行瓶颈。 │ │ │ │ │ │ 帧结束时 │ │ 四个分区同时reset。 │ │ 每个分区mCurrent mStart。 │ │ 4纳秒搞定。 │ │ │ │ │ │ 就像一间教室里有4块白板。 │ │ 4个老师同时上课各写各的白板。 │ │ 互不干扰互不等待。 │ │ 下课铃响4个老师同时擦白板。 │ │ │ └──────────────────────────────────────────────────┘5.3 分区不均匀怎么办┌──────────────────────────────────────────────────┐ │ │ │ 问题 │ │ │ │ 线程0负责的碰撞对特别多场景左半边很拥挤 │ │ 线程3负责的碰撞对很少场景右半边很空旷 │ │ │ │ ┌──────────┬──────────┬──────────┬─────────┐ │ │ │ 分区0 │ 分区1 │ 分区2 │ 分区3 │ │ │ │██████████│████░░░░░░│███░░░░░░░│█░░░░░░░░│ │ │ │ 快满了 │ 用了一半 │ 用了1/3 │ 几乎没用│ │ │ └──────────┴──────────┴──────────┴─────────┘ │ │ │ │ 线程0的128KB快用完了 │ │ 而线程3的128KB几乎是空的。 │ │ 总共还有大量空间但线程0要溢出了。 │ │ │ │ │ │ PhysX的应对策略 │ │ │ │ │ │ 策略A溢出到堆 │ │ │ │ 线程0的分区满了 │ │ 走慢路径从用户分配器malloc。 │ │ 不完美但简单可靠。 │ │ 大多数情况下分区足够大不会溢出。 │ │ │ │ │ │ 策略B任务粒度均衡 │ │ │ │ PhysX的任务调度器会尽量把工作均匀分配。 │ │ 不是按空间区域分而是按碰撞对数量分。 │ │ │ │ 总共2000个碰撞对4个线程 │ │ 线程0碰撞对 0-499 │ │ 线程1碰撞对 500-999 │ │ 线程2碰撞对 1000-1499 │ │ 线程3碰撞对 1500-1999 │ │ │ │ 每个线程处理500个碰撞对 │ │ 产生的临时数据量大致相同 │ │ 分区使用率大致均匀。 │ │ │ │ │ │ 策略C动态分区大小 │ │ │ │ 根据上一帧的实际使用量 │ │ 动态调整下一帧各分区的大小。 │ │ │ │ 上一帧线程0用了120KB线程3用了20KB。 │ │ 下一帧 │ │ 线程0分到180KB线程3分到60KB。 │ │ 总量不变但分配更合理。 │ │ │ │ ┌──────────────┬────────┬────────┬──────┐ │ │ │ 分区0 │ 分区1 │ 分区2 │分区3 │ │ │ │ 180KB │ 140KB │ 120KB │ 72KB │ │ │ └──────────────┴────────┴────────┴──────┘ │ │ │ │ 像一个聪明的班主任 │ │ 上次考试发现小明写得多小红写得少。 │ │ 这次考试给小明多发几张草稿纸 │ │ 小红少发几张。 │ │ 总草稿纸数量不变但分配更合理。 │ │ │ └──────────────────────────────────────────────────┘六、帧分配器的隐藏优势缓存友好6.1 为什么连续内存这么重要┌──────────────────────────────────────────────────┐ │ │ │ CPU读取内存不是一个字节一个字节读的。 │ │ 它一次读取一个缓存行Cache Line │ │ 通常是64字节。 │ │ │ │ 当你访问地址0x1000时 │ │ CPU实际上把0x1000-0x103F这64字节全部读进缓存。 │ │ 如果你接下来访问0x1010已经在缓存里了。 │ │ 不需要再去主存取。 │ │ │ │ 缓存命中约4纳秒 │ │ 缓存未命中约100纳秒 │ │ 差25倍。 │ │ │ │ │ │ malloc分配的内存 │ │ │ │ 接触点1 → 地址 0x7F001200 │ │ 接触点2 → 地址 0x7F00A800 相距38KB │ │ 接触点3 → 地址 0x7F003400 跳回来了 │ │ 接触点4 → 地址 0x7F00F000 又跳走了 │ │ │ │ 遍历这4个接触点4次缓存未命中。 │ │ 4 × 100纳秒 400纳秒。 │ │ │ │ │ │ 帧分配器分配的内存 │ │ │ │ 接触点1 → 地址 0x7F001200 │ │ 接触点2 → 地址 0x7F001230 紧挨着 │ │ 接触点3 → 地址 0x7F001260 紧挨着 │ │ 接触点4 → 地址 0x7F001290 紧挨着 │ │ │ │ 遍历这4个接触点 │ │ 第1个缓存未命中100纳秒。 │ │ 但CPU把0x1200-0x123F都读进来了。 │ │ 第2、3个缓存命中4纳秒。 │ │ 第4个可能命中可能需要读下一个缓存行。 │ │ 总计约112纳秒。 │ │ │ │ 400纳秒 vs 112纳秒。 │ │ 帧分配器快了3.6倍。 │ │ │ │ 当接触点数量是3000个时 │ │ malloc3000 × 100 300微秒 │ │ 帧分配器3000 / (64/48) × 100 ≈ 140微秒 │ │ 每个缓存行能装1.3个接触点 │ │ │ │ 省下160微秒。 │ │ 看起来不多每帧省160微秒 │ │ 60fps下每秒省9.6毫秒。 │ │ 一秒钟多出来将近一帧的时间。 │ │ │ │ │ │ 帧分配器的内存布局天然是连续的 │ │ │ │ ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ │ │ CP │ CP │ CP │ CP │ CP │ CP │ CP │ CP │ │ │ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │ │ └────┴────┴────┴────┴────┴────┴────┴────┘ │ │ ← ─ ─ ─ ─ 连续的内存地址 ─ ─ ─ ─ ─ → │ │ │ │ 因为帧分配器就是从左到右依次切割的。 │ │ │ 先分配的在左边后分配的在右边。 │ │ 中间没有间隙没有元数据没有对齐填充 │ │ 对齐填充最多15字节微不足道。 │ │ │ │ 这种布局对CPU的预取器Prefetcher也很友好。 │ │ 预取器发现你在顺序访问内存 │ │ 会提前把后面的数据读进缓存。 │ │ 等你真正需要时数据已经在缓存里等着了。 │ │ │ │ 就像一个贴心的助手 │ │ 看你在翻第3页就提前把第4、5页翻好放在旁边。 │ │ 你翻到第4页时零等待。 │ │ │ └──────────────────────────────────────────────────┘七、帧分配器的大小选择一门平衡的艺术7.1 给多大的scratch才合适┌──────────────────────────────────────────────────┐ │ │ │ PhysX文档的建议 │ │ │ │ scratchSize nbActiveObjects * 128 │ │ │ │ 500个活跃物体 → 64KB │ │ 2000个活跃物体 → 256KB │ │ 5000个活跃物体 → 640KB │ │ │ │ 但这只是起点。实际需要多少取决于 │ │ │ │ │ │ 因素1碰撞密度 │ │ │ │ 500个物体散落在大地图上 │ │ → 碰撞对很少 → 临时数据少 → 128KB够用 │ │ │ │ 500个物体挤在一个小房间里 │ │ → 碰撞对爆炸 → 临时数据多 → 可能需要512KB │ │ │ │ │ │ 因素2碰撞形状复杂度 │ │ │ │ 全是球体 │ │ → 每对碰撞最多1个接触点 → 数据少 │ │ │ │ 全是凸多面体 │ │ → 每对碰撞可能4-8个接触点 → 数据多 │ │ │ │ 有三角网格 │ │ → 每对碰撞可能几十个接触点 → 数据爆炸 │ │ │ │ │ │ 因素3关节数量 │ │ │ │ 布娃娃有大量关节 │ │ 每个关节产生约束数据 │ │ 10个布娃娃 × 15个关节 150个约束 │ │ 约束数据可能占用几十KB │ │ │ │ │ │ 最佳实践 │ │ │ │ ① 先给一个保守的大小比如512KB │ │ ② 运行游戏观察是否有溢出警告 │ │ ③ 有溢出 → 加大 │ │ ④ 没溢出 → 尝试减小直到刚好不溢出 │ │ ⑤ 在最终值上加20%余量应对突发情况 │ │ │ └──────────────────────────────────────────────────┘7.2 太大和太小的代价┌──────────────────────────────────────────────────┐ │ │ │ │ │ 太小比如只给32KB │ │ │ │ ┌──────────────────────────────────┐ │ │ │ 碰撞对 │ 接触点(部分) │ 满了 │ │ │ └──────────────────────────────────┘ │ │ │ │ 堆上溢出 │ │ ┌──────────┐ ┌──────┐ ┌────────┐ ┌──────┐ │ │ │接触点剩余│ │岛数据│ │约束矩阵│ │速度 │ │ │ └──────────┘ └──────┘ └────────┘ └──────┘ │ │ │ │ 大量数据溢出到堆上。 │ │ 每次溢出都是一次malloc。 │ │ 帧末每次溢出都要free。 │ │ 帧分配器的优势几乎完全丧失。 │ │ 还不如不用帧分配器。 │ │ │ │ 而且溢出的数据散落在堆上 │ │ 缓存友好性也丧失了。 │ │ 双重打击。 │ │ │ │ │ │ 太大比如给64MB │ │ │ │ ┌──────────────────────────────────────────┐ │ │ │碰撞│接触│岛│约束│速度│ │ │ │ │ │ │ │ │ │ 63.5MB空着 │ │ │ └──────────────────────────────────────────┘ │ │ │ │ 只用了0.5MB63.5MB白白占着。 │ │ 这64MB是实打实分配的物理内存。 │ │ 在内存紧张的平台上手机、Switch │ │ 这是不可接受的浪费。 │ │ │ │ 而且64MB的连续内存可能导致地址空间碎片化 │ │ 影响其他系统的大块分配。 │ │ │ │ │ │ 刚刚好比如512KB │ │ │ │ ┌──────────────────────────────────────────┐ │ │ │碰撞│接触│岛│约束│速度│ 余量20% │ │ │ │ │ │ │ │ │ (安全缓冲) │ │ │ └──────────────────────────────────────────┘ │ │ │ │ 正常帧全部在scratch内零malloc。 │ │ 极端帧偶尔溢出一点点可以接受。 │ │ 内存占用合理不浪费。 │ │ │ │ 这就是刚好够用的艺术。 │ │ │ └──────────────────────────────────────────────────┘八、帧分配器 vs 其他分配器各有各的战场┌──────────────────────────────────────────────────┐ │ │ │ ┌──────────┬──────────┬──────────┬──────────┐ │ │ │ │帧分配器 │池分配器 │malloc │ │ │ ├──────────┼──────────┼──────────┼──────────┤ │ │ │分配速度 │ 5ns │ 8ns │ 300ns │ │ │ │释放速度 │ 0ns(*) │ 5ns │ 200ns │ │ │ │内存碎片 │ 零 │ 低 │ 高 │ │ │ │缓存友好 │ 极好 │ 好 │ 差 │ │ │ │单独释放 │ 不支持(**) │ 支持 │ 支持 │ │ │ │生命周期 │ 仅限一帧 │ 任意 │ 任意 │ │ │ │多线程 │ 分区无锁 │ 需要处理 │ 需要锁 │ │ │ │实现复杂度│ 极简 │ 中等 │ 复杂 │ │ │ └──────────┴──────────┴──────────┴──────────┘ │ │ │ │ (*) 帧末reset是O(1)不管分配了多少次 │ │ (**) 栈式回退可以有限度地支持 │ │ │ │ │ │ PhysX的选择策略 │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ │ │ │ │ 这个数据活不过一帧 │ │ │ │ ├── 是 → 帧分配器 │ │ │ │ │ 碰撞对、接触点、约束矩阵、 │ │ │ │ │ 岛组数据、求解器临时变量 │ │ │ │ │ │ │ │ │ └── 否 → 这个数据是固定大小的同类对象 │ │ │ │ ├── 是 → 池分配器 │ │ │ │ │ ContactManager、 │ │ │ │ │ RigidBody、Shape │ │ │ │ │ │ │ │ │ └── 否 → 用户分配器(malloc) │ │ │ │ 大小不固定的数组、 │ │ │ │ 用户创建的资源 │ │ │ │ │ │ │ └────────────────────────────────────────────┘ │ │ │ │ 三种分配器各守一方互不越界。 │ │ 帧分配器处理最多的分配帧临时数据占大头。 │ │ 池分配器处理最频繁的创建销毁。 │ │ 用户分配器兜底处理剩下的杂活。 │ │ │ └──────────────────────────────────────────────────┘九、终极比喻三种白板┌──────────────────────────────────────────────────┐ │ │ │ 想象一所学校里有三种白板 │ │ │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ │ │ │ │ 白板A教室里的大白板帧分配器 │ │ │ │ │ │ │ │ 每节课开始空白的 │ │ │ │ 上课期间老师疯狂书写 │ │ │ │ 下课铃响板擦一抹全部清空 │ │ │ │ 下节课又是一块崭新的白板 │ │ │ │ │ │ │ │ 特点 │ │ │ │ - 写得快从左到右依次写 │ │ │ │ - 擦得快一抹就干净 │ │ │ │ - 不能只擦中间某个字 │ │ │ │ - 每节课的内容都是临时的 │ │ │ │ │ │ │ └────────────────────────────────────────────┘ │ │ │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ │ │ │ │ 白板B办公室的磁性白板池分配器 │ │ │ │ │ │ │ │ 上面贴着一个个磁性卡片 │ │ │ │ 每个卡片大小一样员工信息卡 │ │ │ │ 新员工入职从抽屉里拿一张空白卡贴上 │ │ │ │ 员工离职把卡片摘下来放回抽屉 │ │ │ │ 抽屉空了去文具店买一盒新卡片 │ │ │ │ │ │ │ │ 特点 │ │ │ │ - 可以单独摘下某张卡片 │ │ │ │ - 卡片可以反复使用 │ │ │ │ - 每张卡片大小固定 │ │ │ │ - 卡片的生命周期不确定 │ │ │ │ │ │ │ └────────────────────────────────────────────┘ │ │ │ │ │ │ ┌────────────────────────────────────────────┐ │ │ │ │ │ │ │ 白板C校长办公室的公告板用户分配器 │ │ │ │ │ │ │ │ 什么都能贴通知、照片、图表、奖状 │ │ │ │ 大小不一形状各异 │ │ │ │ 贴上去要走流程申请空间 │ │ │ │ 摘下来也要走流程释放空间 │ │ │ │ 流程慢但什么都能处理 │ │ │ │ │ │ │ │ 特点 │ │ │ │ - 最灵活 │ │ │ │ - 最慢 │ │ │ │ - 兜底方案 │ │ │ │ │ │ │ └────────────────────────────────────────────┘ │ │ │ │ │ │ PhysX的智慧在于 │ │ │ │ 把90%的工作交给白板A帧分配器。 │ │ 把9%的工作交给白板B池分配器。 │ │ 只把1%的工作交给白板C用户分配器。 │ │ │ │ 最快的方式处理最多的工作。 │ │ 最慢的方式只处理最少的工作。 │ │ │ │ 这就是分层设计的力量。 │ │ │ └──────────────────────────────────────────────────┘后记帧分配器是我见过的最优雅的内存管理方案。它的代码不超过50行。它的核心思想不超过一句话写满就擦擦完再写。但就是这么简单的一个想法让PhysX在每帧16毫秒的铁律下从容地处理几万次内存分配而几乎不花任何时间在内存管理上。它不是什么高深的算法。它只是对一个朴素事实的深刻洞察如果你知道数据什么时候死你就不需要费力去埋葬它。每一帧结束所有临时数据同时死亡。既然同时死亡何必一个一个收尸把墓地铲平下一帧的新生命直接在上面生长。生生死死周而复始。白板永远是那块白板。但每一帧写在上面的故事都是全新的。