8

How does the defragmentation of dynamically allocated memory (allocated using the new and malloc operator ) work in C++?

Bourne
  • 1,905
  • 13
  • 35
  • 53
  • 7
    It doesn't. Once an object is allocated, it's stuck in place until it dies. – n. m. could be an AI Jun 09 '13 at 11:06
  • 2
    what do you mean with defragmentation? a code example would help here. – blue Jun 09 '13 at 11:07
  • 4
    if you are concerned about memory fragmentation due to allocation/deallocation of a high number of small objects, the canonical way to deal with this is to use a memory pool to allocate your instances - try boost http://www.boost.org/doc/libs/1_47_0/libs/pool/doc/index.html – kfmfe04 Jun 09 '13 at 11:13

2 Answers2

10

There is no defragmentation in the C++ heap because the application is free to keep pointers to allocated memory. Thus the heap manager cannot move memory around that is already allocated. The only "defragmentation" possible is if you free two adjacent blocks. Then the heap manager will combine the two blocks to a single larger free block that can be used for allocation again.

Martin Liversage
  • 104,481
  • 22
  • 209
  • 256
  • Why can't the heap manager defragment memory just like the garbage collector of java does during garbage collection by moving around objects? If the memory in the C++ heap is fragmented it could be possible that the new requests to allocate memory may fail even though the total free space is available but it is not available as a contiguous chunk. – Bourne Jun 09 '13 at 14:31
  • 1
    In Java the garbage collector can move blocks around to defragment the heap because it knows about all the references to all the blocks on the heap. When a block is moved during defragmentation the actual memory address is updated but all the managed references are also updated. This is not possible in C++ where an actual address is returned when a block is allocated on the heap. The C++ program can dereference any pointer that points into the block and these pointers can be computed by pointer arithmetic. If the block moves the pointers stored by the application code becomes invalid. – Martin Liversage Jun 09 '13 at 14:48
  • Can't the pointers be updated in C++ just like the Garbage collector updates the references? – Bourne Jun 09 '13 at 18:22
  • @bourne: But how? These pointers are in other memory locations or registers and the C++ runtime doesn't know about all these pointers. In theory you could perhaps write a virtual machine and a C++ compiler that allowed pointers to be updated in the same way as it is done in the Java virtual machine but then you would also have the overhead of that environment and it would be silly to not switch to a fully garbage collected environment. I.e. use Java as your language. – Martin Liversage Jun 09 '13 at 19:06
  • 1
    There is no entity in C++ keeping track of where are the variables containing pointers, nor there is a garbage collector. Memory in C++ must be managed carefully. You could defragmentate memory if you code a memory manager yourself, but that would add CPU cost to your application, and thats exactly what coding in C++ is all about to avoid. – Havenard Jun 11 '13 at 21:38
  • @MartinLiversage: It makes sense to mention that it is possible to create "defragmentable garbage collected pointer" class in C++, along with garbage collector. However, those "pointers" will be very different from standard pointers, and such GC won't be able to manage standard pointers/allocations. – SigTerm Jun 11 '13 at 22:34
  • What about [virtual memory](https://en.wikipedia.org/wiki/Virtual_memory) which according to the linked Wikipedia page is done at the operating system level, and as I understand it is ubiquitous in modern computers. This would provide the requisite level of indirection behind the scenes to *transparently* de-fragment the memory would it not? – M.J. Rayburn May 27 '22 at 22:57
  • Also Apple had this whole thing about [operating system level memory compression](https://www.youtube.com/watch?v=4FunXnJQxYU&t=788s) back in 2013. If it's possible to do memory compression transparently behind the scenes I would think it's also possible to do memory de-fragmentation. – M.J. Rayburn May 27 '22 at 23:07
  • @M.J.Rayburn Virtual memory does not allow C++ to defragment memory allocated on the heap. The virtualization is performed by the OS and CPU is transparent to the user mode code executing (i.e. compiled from C++) that will use virtual addresses and never know about physical addresses. The mapping is not done for a single address but instead for a memory page which typically is 4K but there can be many C++ heap allocations in a single page and they can straddle pages. Virtual memory can not be used to somehow compact "holes" left when C++ heap blocks are freed. – Martin Liversage Apr 21 '23 at 13:46
3

You might want to look into slab allocators. This won't be your silver bullet but for specific problems you may be able to relief the pressure. In a past project of mine we've had our own allocator written which was quite a complex affair but it certainly managed to get a grip on the issue.

While I agree with the other answers in general, sometimes there is hope in specific use cases. Such as similar objects that may be tackled with pool allocators: http://www.boost.org/doc/libs/1_53_0/libs/pool/doc/index.html

Also an interesting read are the allocators that come with boost interprocess: http://www.boost.org/doc/libs/1_53_0/doc/html/interprocess/allocators_containers.html#interprocess.allocators_containers.stl_allocators_adaptive