15

For example, if deallocations of dynamic memory are always done in opposite direction to allocations. In that case, is it guaranteed that heap will not become fragmented?

And from theoretical point of view: Does there exist some realistic way for a nontrivial application to manage memory to completely avoid heap fragmentation? (After each atomic change in heap, is heap still unfragmented?)

Dennis Meng
  • 5,109
  • 14
  • 33
  • 36
user3123061
  • 757
  • 5
  • 14
  • 1
    For your first case, the standard certainly doesn't guarantee it. But if the allocation pattern was that simple, you could easily make one yourself that's performant. The second case is clearly a much harder problem. Personally I've only (successfully) done it on an application-specific level. And it wasn't trivial as it required having enough information about future allocations to know where to place the current ones. – Mysticial Feb 21 '14 at 23:05
  • This sort of thing depends on the memory management scheme. You can't reason about fragmentation when using the standard memory management tools of C or C++, because those are mostly unspecified (for good reasons). So, are you asking only about these standard tools, or are we talking about custom memory managers? –  Feb 21 '14 at 23:06
  • If memory serves, it's been proved that there are patterns of allocation/deallocation that will result in fragmentation for any manager that doesn't actively compact the heap. – Jerry Coffin Feb 21 '14 at 23:09
  • This is probably the wrong [tag] to bring up compacting garbage collectors. But that's how you avoid it. It really is rather a non-issue today in 64-bit code, pretty hard to run out of VM space. The problem exists, lots of programs run just fine anyway. It is a bit about worrying about the weather. – Hans Passant Feb 21 '14 at 23:10
  • 1
    It sounds like your allocation satisfies a stack discipline, so a large chunk of contiguous memory used as a stack should be fragmentation free and satisfy your allocation needs. – Kerrek SB Feb 21 '14 at 23:10
  • 2
    @HansPassant A 64 (or rather 48) bit address space is great, but still managed at page granularity, i.e. you can still block 4 KiB of physical memory with a single stray allocation, no matter how small. VM space isn't everything. That is not to say many programs need to worry about fragmentation (they don't, and haven't for longer than we have commodity 64 bit). –  Feb 21 '14 at 23:12
  • 1
    An also may be related topic (by concerns of micro optimizations) is usage of [allocators and pre-allocated object pools](http://stackoverflow.com/questions/222557/what-uses-are-there-for-placement-new/222578#222578) – πάντα ῥεῖ Feb 21 '14 at 23:16
  • Multiple threads with a shared heap.... – Martin James Feb 21 '14 at 23:20
  • 2
    @MartinJames: It's really not clear how that comment is supposed to fit into this discussion. Please elaborate. – Ben Voigt Feb 21 '14 at 23:20
  • @Jerry Coffin: It sounds interesting. Can you provide a link to some article with the proof? – user3123061 Feb 21 '14 at 23:21
  • @user3123061: I'll look around if I get a chance, but the memory is dim enough that (if I saw it at all) it was years ago, so I'm not at all sure of finding it. – Jerry Coffin Feb 21 '14 at 23:22

7 Answers7

20

Exist some realistical way for nontrivial application how to manage memory to completely avoid heap fragmentation

Yes. Allocate everything on the stack. This may seem like a counsel of perfection but I've done it in non-trivial programs.

EDIT For absolute clarity and avoidance of doubt, I said 'the stack'. By that I clearly mean automatic storage, i.e. the local variable stack, not any stack class. Some of the comments about this are basically obtuse.

user207421
  • 305,947
  • 44
  • 307
  • 483
  • Any stack in particular...? – Martin James Feb 21 '14 at 23:20
  • 5
    @MartinJames: I don't think anyone doubts that he's talking about using variables with automatic lifetime. Most implementations put these on the call stack, managed with a CPU register that is specifically designated as the edge-of-stack pointer. – Ben Voigt Feb 21 '14 at 23:21
  • The system stack. The stack class is bad (never use STL containers). Assuming an intel machine, it's esp – phyrrus9 Feb 21 '14 at 23:22
  • 2
    Upvoted just for the huevos to suggest this approach. Though I suppose global objects/arrays can help here as well. A lot of old-school games handled everything in big global arrays. It's fugly but it worked and zero memory allocator overhead. – StilesCrisis Feb 21 '14 at 23:23
  • 1
    I would like to see someone write a comprehensive compiler (e.g. Pascal, C or C++ types of languages) that isn't severely limited (copes with large sources and large functions, isn't extremely pessimistic in code generation) using this solution... – Mats Petersson Feb 21 '14 at 23:39
  • 1
    @EJP: Amazing, that would be great. But how you solved with stack this type of action: User opens document A, then document B and then closes document A? – user3123061 Feb 21 '14 at 23:42
  • 1
    @user3123061 swap followed by pop. –  Feb 21 '14 at 23:44
  • 1
    @user3123061: You said in the question `dealocations of dynamic memory are always done in oposite direction to allocations`, which disallows that use-case. – Mooing Duck Feb 21 '14 at 23:52
  • 1
    @MatsPetersson It was a different project but I wrote an entire Cobol compiler and runtime system with only two `malloc()` calls in it, to load the bytecode. – user207421 Feb 21 '14 at 23:56
  • 1
    @StilesCrisis This is getting off topic, but almost all the execution time of Cobol is spent in the RTL, so compiler optimization isn't really required. – user207421 Feb 22 '14 at 00:09
  • @user3123061 Where exactly did I say that I had solved every computation problem without using the heap? – user207421 Jun 29 '16 at 08:40
  • @StilesCrisis I've thought about this for a couple of years. Your remark about a 'brain-dead compiler' is fundamentally offensive to several years of my work, as well as entirely baseless, and should be withdrawn. – user207421 Dec 18 '16 at 08:46
  • @EJP: No offense intended! I don't think the comment contributed very much to the discussion and don't want any hard feelings so I am happy to remove it. – StilesCrisis Dec 18 '16 at 17:00
6

The only way to really avoid heap fragmentation, is to do memory management yourself, keep track of all the pointers you use, and defragment your heap from time to time. But be aware that there is a reason why this is not done: It does not pay off. The effort in code and performance you need to spend on defragmenting your heap is way too large.

Just an anecdotal bit of history information:
The old MacOS (pre-MacOS-X era!) used so called handles for memory objects: pointers into lists of pointers to the actual memory regions. That had the advantage that the OS could move a memory object by modifying its pointer in the table; any references by the handle would remain intact. But you had to lock a handle everytime you wanted to access its data across a system call. It should be mentioned that this was before multicore became mainstream, so there was no real concurrency going on. With a multithreaded application, one would have to lock handles every time, at least if the other threads were allowed to call into the system. I repeat, there is a reason handles did not survive in MacOS-X...

cmaster - reinstate monica
  • 38,891
  • 9
  • 62
  • 106
  • 1
    Of course, Mac programmers would then either forget to unlock their handles, or intentionally just lock the handle in an "early" call, and only release it much later, essentially circumventing the movement... And yes, it's not a great system... – Mats Petersson Feb 21 '14 at 23:11
  • @MatsPetersson: In fact, given how badly it was designed, almost the only way to write code that really worked was to leave most memory locked most of the time. Big problem: lock and unlock calls didn't balance, so if you locked the same memory (say) three times, *one* call to unlock still unlocked it. 16-bit Windows used the same *basic* idea, but much more sanely (e.g., lock/unlock calls *did* balance). – Jerry Coffin Feb 21 '14 at 23:14
  • 1
    I wrote lots of classic Mac OS code. You didn't have to `HLock` everything constantly. The OS wouldn't just reshuffle everything on a whim--it could only do a compact if you actually called into an OS function. If you wrote a tight loop that didn't call into the OS at all, your handle was guaranteed to stay put. – StilesCrisis Feb 21 '14 at 23:28
  • 1
    It still is a good way to handler a few large memory chunks in a program. I use it in a situation which holds 300 documents of an average 64 KB each. Unfortunately average is misleading so i had to implement my own compaction algorithm. – Lothar Mar 23 '14 at 13:38
  • 1
    Actually Win16 also [used the handle approach](http://www.openroad.org/school/gui/winmem.html), which was abandoned once virtual memory came into life. – Ruslan Dec 04 '17 at 09:33
4

It is possible to partition the heap into regions where memory allocation of particular size is allowed. This way your heap would not be partitioned but you'll have memory consumption overhead and a risk to ran out of free chunks, but sometimes it is well justified (say when software has to stay online 24/7/365. Sizes can be powers of 2, or most typically used sizes for the application, or just new memory regions allocated on demand upon the first allocation of size N up to some sensible N.

It will look similar to this (* - allocated block, - free block)

 size=1: [*][ ][*][*][*][ ][ ][ ][ ][ ]
 size=2: [  ][  ][  ][**][**][  ][  ][  ]
 size=4: [    ][****][    ][    ][    ]
 size=8: [        ][        ][        ]
 ....

A visualizer I've written a while ago when experimented with the subject: http://bobah.net/d4d/tools/cpp-heapmap

bobah
  • 18,364
  • 2
  • 37
  • 70
  • 3
    Yes, and major OSes do this, for example the Windows "Low-Fragmentation Heap". Naturally one doesn't go to block sizes as low as 1, though, because the metadata overhead is horrendous. – Ben Voigt Feb 21 '14 at 23:23
  • 1
    Another example is in Linux. The slab allocator maintains areas for each kind of object, like dentry for directories, as well as some generic areas for 16 byte or 32 byte allocations, kmalloc-16, kmalloc-32. – Zan Lynx Feb 21 '14 at 23:49
3

I think it's theoretically possible to achieve this (assuming the heap implementation is also doing "the right thing" [e.g. merging blocks immediately as they are freed])

But in any practical application that is solving some real problem, it's unlikely. Certainly any usage of std::string or std::vector is almost certain to allocate/free the memory in "unordered ways".

If you have a scenario where heap fragmentation is a potential problem, it's almost certainly better to use a solution that reduces/eliminates this (e.g. fixed size bucket allocation, separate heaps for various types of allocations - these are just two of MANY different solutions).

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
2

In managed languages such as Java heap defragmentation happens all the time. This is possible because Java "pointers" are actually References and Java is aware of them and is able to move them when it moves objects in the heap.

In C and C++ pointers can be anything, they can be calculated, combined, updated, etc. This means that once something is allocated it cannot be moved as you never know what might actually be a pointer to it - and that immediately makes defragmentation impossible in the general case.

The only way to reduce fragmentation is to only store elements of the same size in the same area of memory, but this is so inflexible it's not practicable for many real life programming situations.

Tim B
  • 40,716
  • 16
  • 83
  • 128
2

As mentioned by delnan above, another issue is virtual memory page fragmentation that can occur when there are a lot of allocations and freeing of memory. A windows .net application relies on .net's garbage collection scheme to repack allocated memory, but this results in pauses in the running program. I'm not sure how long each pause is.

rcgldr
  • 27,407
  • 3
  • 36
  • 61
1

I did much of my software design and programming in hard real time systems. These are very critical real-time system that control oil refineries, power plants, Steel mills, Copper Smelters, Petro Chemical plants, Oil and Natural gas pipelines storage and transport facilities. We could not allow any memory fragmentation that would force loss of functionality or a reboot of any control servers as the results would be at a minimum financial loss and at worst catastrophic damage and loss of life.

We simply created three fixed buffer sizes: small, medium and large and on start up we preallocated all that memory into those 3 exact sizes and we managed the memory ourselves via a simple linked list. No garbage collection was ever required but we did, of course, have to explicitly allocate and deallocate the buffers.

Chris Schene
  • 11
  • 1
  • Just stumbling on this now. It’s very interesting to me. Is there anywhere I can go for a simple example of something like this. Or, if it’s not proprietary, can you elaborate a little? – Dan Jan 07 '20 at 15:06
  • u know that a typical malloc implementation does exactly what u just said :) it uses a linked list for allocated and free memory. – Anton Stafeyev Aug 28 '20 at 18:52