对 C++ 进行碎片整理堆分配器和堆分配器STL
我正在编写一个自碎片整理内存管理器，其中一个简单的递增堆分配器与一个简单的压缩碎片整理程序结合使用。
粗略的方案是从最低内存地址开始向上分配块，并保持从最高内存地址开始向下的簿记信息。
内存管理器将传回智能指针 - boost 的 intrusive_ptr 对于簿记结构来说似乎是最明显的，然后它们本身会指向实际的内存块，从而提供一定程度的间接性，以便可以轻松地移动块。
碎片整理程序将从“生成”书签开始压缩堆，以加快进程，并且一次只对固定数量的内存进行碎片整理。指向块本身的原始指针在下一次碎片整理传递之前一直有效，因此可以自由传递，直到提高性能为止。
其具体应用是控制台游戏编程，因此在每一帧的开始或结束时，可以相对安全地完成碎片整理过程。
所以我的问题是，是否有人将这种分配方案与 STL 结合使用，它会像我怀疑的那样完全破坏 STL 吗？我可以看到 std::list< intrusive_ptr >在 intrusive_ptr 级别工作，但是 stl 列表节点本身的分配无论如何都可以覆盖下一个/上一个指针以成为 intrusive_ptr 本身，或者我只是必须在这个更动态的分配器旁边有一个标准堆分配器。
I'm looking to write a self defragmenting memory manager whereby a simple incrementing heap allocator is used in combination with a simple compacting defragmenter.
The rough scheme would be to allocate blocks starting at the lowest memory address going upwards and keeping book-keeping information starting at the highest memory address working downwards.
The memory manager would pass back smart pointers - boost's intrusive_ptr's seems the most obvious to the book-keeping structs that would then themselves point to the actual memory block thus giving a level of indirection so that the blocks can be easily moved around.
The defragmenter would compact down the heap starting at 'generation' bookmarks to speed up the process and only defragmenting a fixed amount of memory at a time. Raw pointers to the blocks themselves would be valid until the next defrag pass and so could be passed around freely until such a time improving performance.
The specific application for this is console game programming and so at the beginning or end of each frame a defrag pass could be done relatively safely.
So my question is has anybody used this kind of allocation scheme in combination with STL would it just completely blow STL apart as I suspect. I can see std::list< intrusive_ptr > working at the intrusive_ptr level but what about the allocation of the stl list nodes themselves is there anyway to override the next/prev pointers to be intrusive_ptr's themselves or am I just going to have to have a standard heap allocator along side this more dynamic one.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果您要在内存中移动对象，那么您通常无法完全做到这一点。您只能对知道可能被移动的对象执行此操作。您还需要一个锁定机制。当对对象调用函数时，它无法移动。
原因是整个 C++ 模型依赖于位于内存中固定点的对象，因此如果一个线程正在调用一个对象的方法，该线程被暂停并且对象被移动，那么当线程恢复时灾难就会发生。
任何持有指向可能移动的另一个对象（包括其自身的子对象）的原始内存指针的对象都将不起作用。
这样的内存管理方案可能有效，但你必须非常小心。您需要严格执行句柄和句柄->指针锁定语义。
对于STL容器，您可以自定义分配器，但它仍然需要返回固定的原始内存指针。您无法返回可能移动的地址。因此，如果您使用 STL 容器，它们必须是句柄容器，并且节点本身将是普通的动态分配内存。您可能会发现，与使用 STL 相比，句柄间接寻址的开销太大，而且句柄集合的碎片问题仍然存在。
使用直接理解句柄的容器可能是唯一的出路，即便如此，与使用固定在内存中的传统对象的 C++ 应用程序相比，仍然可能存在大量开销。
If you're going to be moving objects around in memory then you can't do this fully generically. You will only be able to do this with objects that know that they might be moved. You also will need a locking mechanism. When a function is being called on an object, then it can't be moved.
The reason is that the whole C++ model relies on objects sitting at fixed points in memory, so if a thread was calling a method on an object, this thread was paused and the object moved, disaster would strike when the thread resumed.
Any object which held a raw memory pointer to another object that might be moved (including a sub-object of itself) would not work.
Such a memory management scheme may work but you have to be very careful. You need to be strict about implementing handles, and the handle->pointer locking semantics.
For STL containers, you can customize the allocator, but it still needs to return fixed raw memory pointers. You can't return an address that might move. For this reason, if you're using STL containers, they must be containers of handles, and the nodes themselves will be ordinary dynamically allocated memory. You may find that you too much in overhead in the handle indirection and still have problems in the fragmentation of the handle collections than you gain by using STL.
Using containers that understand your handles directly might be the only way forward, and even then there may still be a lot of overhead compared to a C++ application that uses traditional objects fixed in memory.
STL 容器是使用裸指针实现的。
您可以在实例化它们时指定自定义分配器（以便它们使用您的分配器初始化其指针），但是（因为分配的值存储在裸指针中）您不知道这些指针在哪里，因此您不能稍后更改它们。
相反，您可以考虑自己实现 STL 的子集：然后可以使用托管指针来实现您的 STL 容器版本。
STL containers are implemented using naked pointers.
You can specify a custom allocator when you instantiate them (so they they initialize their pointers using your allocator), but (because the allocated values are stored in naked pointers) you don't know where those pointers are, and therefore you can't change them later.
Instead, you might consider implementing a subset of the STL yourself: your versions of the STL containers could then be implemented with managed pointers.
另一种众所周知的替代技术是好友系统。您应该看看它以获得更多灵感。
An alternative technique which is fairly well known is the buddy system. You should take a look at that for additional inspiration.
如果这是针对控制台游戏编程，那么在运行时禁止无范围动态内存分配会容易得多。而在启动时，但这有点难以实现。
If this is for console game programming it's a lot easier to forbid un-scoped dynamic memory allocations at runtime. And at startup time, but that's a bit difficult to achieve.
我对此的看法是，如果必须担心碎片，那就意味着您正在处理占内存很大一部分的数据片段，仅凭这一点，您就无法拥有很多数据片段。你已经知道这些会是什么吗？也许降低一个级别并做出更具体的决策会更好，从而减少对其他代码和应用程序总体性能的影响？
列表对于放入碎片整理内存管理器来说是一个非常糟糕的例子，因为它是一堆小片段，就像大多数其他 STL 数据结构一样。如果你这样做，它将产生各种明显的不良影响 - 包括碎片整理程序的性能下降，以及间接成本等。IMO 唯一有意义的结构是连续的结构 - 数组，双端队列，散列表的主要块，这些东西，只有超过一定的大小，并且只有在它们不会再调整大小之后。此类事情再次需要特定的解决方案，而不是通用的解决方案。
评论一下这一切的结果。
My take on this, is that if have to be afraid of fragmentation, that means you are juggling around with data pieces which are a huge fraction of your memory, and by this virtue alone, you cannot have many of them. Do you already know what these will be? Maybe it would be better to step down a level and make more specific decisions, thus impeding less on the other code and the general performance of your application?
A list is an exceptionally bad example to put into a defragmenting memory manager, because it's a bunch of tiny pieces, as are most other STL data structures. If you do this, it will have all kinds of obvious bad implications - including the performance of your defragmenter going down, also the indirection cost etc. The only structures where it makes sense IMO are contigious ones - array, deque, main chunk of hashtable, those things, and only beyond a certain size, and only after they are not gonna be resized any longer. These kind of things call, again, for specific solutions, instead of generic ones.
Comment back on how it all turns out.