   memory compaction in c++
  Hi, I'm planning to enable my custom memory manager to compact its managed memory.IMHO one of the main problems is how to update pointers if objects are moved.Using handles that should not be that big a problem, but I'd like to use pointers instead (or objects that can transparently used like pointers). I did some research but I couldn't find any information if that is possible or how.Among the hits was that article where the author states they focused on supporting pointers rather than handles (but he didn't clearly state if their memory manager supported moving objects).So my questions are:1. Is memory compaction using pointers or pointer-like objects possible? (Something like Player* player = new Player(); where player might be a pointer or pointer-like object, so I'm not talking about handles here, like Handle<Player> player = new Player(); )2. If that is possible, would you mind sharing some implementation details? Thanks in advance.Thomas   
Quote:1. Is memory compaction using pointers or pointer-like objects possible?(Something like Player* player = new Player(); where player might be a pointer or pointer-like object, so I'm not talking abount handles here, like Handle<Player> player = new Player(); )It's next to impossible to use raw pointers. With handles or smart pointers, you just iterate across all of them, and reallocate them.One way is for memory manager to keep track of both, use count and pointer to real data. When compacting, it then simply uses this internal structure to reallocate actual data, while users retain references to this internal structure.Java's GC traverses the tree of references. It starts with all static members, then follows references and copies them to new heap. Objects which are not copied are no longer referenced, and are garbage collected.Quote:2. If that is possible, would you mind sharing some implementation details? See how Java virtual machine does it.But IMHO, going to great lengths of implementing compacting garbage collector in C++ for use in C++ is not worth it.   ;  You will have to use smart-pointers (pointer-like objects). If you want to be able to update pointers in the event that an object is moved, the object could itself store (raw) pointers to any (smart) pointers that point to the object.template<class T>class Pointer{public://constructors, assignment, comparison, -> operator, etc...private:  T* m_Address;}class Object{private: std::vector<Pointer*> m_Pointers;//list of all pointers pointing to this object}template<class T>Pointer::Pointer( T* o ){ o->m_Pointers.push_back( this );};  Well, I'm not planning on implementing a fully fledged gc in C++.But I'm planning to use compaction for cases where data of unknown size is allocated and deallocated quite often, thus potentially fragmenting the used heap and making compaction necessary. Deallocation would still be done manually, except that the manager might drop an entire heap at once in some rare cases. Thanks for the hint at the JVM. I'll take a look at the source.   ;Quote:Original post by Lord_EvilWell, I'm not planning on implementing a fully fledged gc in C++.But I'm planning to use compaction for cases where data of unknown size is allocated and deallocated quite often, thus potentially fragmenting the used heap and making compaction necessary.Deallocation would still be done manually, except that the manager might drop an entire heap at once in some rare cases.Then you either use custom pre-allocated storage, perhaps as std::allocator, or you allocate on stack.Heap compaction cannot be implemented partially. It's either application-wide, functionally complete fully featured GC, or it's broken, due to the way C++ works. There is no middle ground.From:Quote:that articleQuote:This article is also slanted toward the C language as written for console game machinesC is a whole different ball game than C++. It's several factors easier to write a memory manager for C than it is for C++.And, if you are on OS with virtual memory support, fragmentation effectively isn't a problem.   ;Quote:Original post by AntheusThen you either use custom pre-allocated storage...That's what I'm planning to do for situations with frequent allocations and deallocations. Since objects in those situations tend to be rather small (like particles etc.) a buddy-system like heap or a fixed-size memory pool might be sufficient.Quote:And, if you are on OS with virtual memory support, fragmentation effectively isn't a problem.I'd use OS allocation when allocation/deallocation isn't that frequent and the pre-allocated storage otherwise.Edit: Hodgman, thanks for the hint. The smartpointer is actually what I meant with "handle" since it would not be that "smart" [smile] (no reference counting and the like). However, I guess using a smartpointer that points to a memory handle which in turn points to the object and is known by the memory manager could be an option.   ;Quote:That's what I'm planning to do for situations with frequent allocations and deallocations. Since objects in those situations tend to be rather small (like particles etc.) a buddy-system like heap or a fixed-size memory pool might be sufficient.I've written about particle systems in particular before. The code is C#, but same applies to C++. There is no need for any kind of dynamic allocations in such cases.   ;Quote:Original post by AntheusQuote:That's what I'm planning to do for situations with frequent allocations and deallocations. Since objects in those situations tend to be rather small (like particles etc.) a buddy-system like heap or a fixed-size memory pool might be sufficient.I've written about particle systems in particular before. The code is C#, but same applies to C++. There is no need for any kind of dynamic allocations in such cases.Particles might be a bad example, since I actually use fixed-size arrays using the swapping approach [smile]. Unfortunately I can't come up with a better example quickly, since I don't know if I'll have many of those situations.In fact I just wanted to find out if I had to use handles/smartpointers in order to support compaction or if I could just use pointers and overload global new in some way to add compaction later.If I understand you (and the information I found on the net) correctly, handles/smartpointers are a necessity in that case, so I'll design my memory manager to support them.;Quote:1. Is memory compaction using pointers or pointer-like objects possible? Yes, there is no problem, as long as you use self-registering smart pointers. It just won't be as optimal as what a virtual machine does, however, but it's just slower by a constant factor.You can do precise garbage collection without any issue, also.   ;Quote:Original post by loufoqueQuote:1. Is memory compaction using pointers or pointer-like objects possible? Yes, there is no problem, as long as you use self-registering smart pointers. It just won't be as optimal as what a virtual machine does, however, but it's just slower by a constant factor.You can do precise garbage collection without any issue, also.What would such a self-registering smart pointer look like? Do you mean it registers itself with the memory manager when created?As stated above (maybe not clearly) I don't smartpointers consider pointer-like in this context if I have to use something like Pointer<Object> p = new Object(); .