83

I'm studying computer engineering, and I have some electronics courses. I heard, from two of my professors (of these courses) that it is possible to avoid using the free() function (after malloc(), calloc(), etc.) because the memory spaces allocated likely won't be used again to allocate other memory. That is, for example, if you allocate 4 bytes and then release them you will have 4 bytes of space that likely won't be allocated again: you will have a hole.

I think that's crazy: you can't have a not-toy-program where you allocate memory on the heap without releasing it. But I don't have the knowledge to explain exactly why it's so important that for each malloc() there must be a free().

So: are there ever circumstances in which it might be appropriate to use a malloc() without using free()? And if not, how can I explain this to my professors?

trincot
  • 317,000
  • 35
  • 244
  • 286
Nick
  • 10,309
  • 21
  • 97
  • 201
  • I get their point, they are noting if you try to allocate *contiguous* memory later, it likely will not use that address since it is only a small contiguous block. But as you, and others, noted it is bad practice. It leaks memory, and plus that address could be available for non-contiguous memory (like linked lists) – Cory Kramer Mar 18 '14 at 13:44
  • 12
    They are not "wrong" - they have a valid (if limited) point about fragmentation of very small isolated free regions, and probably stated it a bit more carefully than you have reported it. – Chris Stratton Mar 18 '14 at 14:28
  • 2
    The only times you don't need to free memory is when using managed memory or when you are going to reuse the original allocated memory. I suspect that the reason two instructors have said this is because you are talking about a specific program which can reuse the memory. In this case you would still use free() but only at the end of your application. Are you sure that this wasn't their meaning? – krowe Mar 18 '14 at 15:01
  • 18
    @Marian: I had a professor claim that in C and C++ it is necessary to free your allocated memory in a function defined in the same .c/.cxx file as it was allocated... These people sometimes seem to severely suffer from hypoxia due to living too high in an ivory tower. – PlasmaHH Mar 18 '14 at 20:22
  • 1
    I would say a memory allocator will handle fragmentation in most of the cases & that's why you should free your memory. – Nilesh Mar 18 '14 at 23:29
  • 4
    There are quite a few non-toy programs that don't deallocate memory, and letting the OS clean it all up on process exit is _much_ faster than (fussily) keeping lots of book-keeping so you can do it yourself. – Donal Fellows Mar 18 '14 at 23:42
  • 1
    Also "it is possible to avoid `free()`" is significantly different than, e.g. "it sometimes makes no difference if you call `free()`", are you sure your professors said the former? – Jason C Mar 19 '14 at 08:38
  • 2
    As [pointed out](http://stackoverflow.com/a/22501021/667820) by @mfro `free()` does not return memory to the OS, but still marks it for reuse by `malloc()`. This will postpone future calls to `mmap()/sbrk()`, and conserve system memory. Once entire pages go unused they will get paged out. Long-lived processes should however address this issue and actually return memory to the OS (easier when using `mmap()` than `brk()`, but it's so much easier to just restart a process. This is where development and operations need to understand the implications. – Henk Langeveld Mar 19 '14 at 09:54
  • 9
    Never merge stuff you heard into your brain unquestioned. I've had many teachers and lectors and correctors who were wrong or out-of-date. And always analyse what they say very precisely. Our folk is often quite precise and may say stuff that is correct, but is easy to understand wrongly or with the wrong priority by someone who feels home only in common parlance. E.g., I remember in school, a teacher said "Did you do your homework.", I said "No.". While I was correct, the teacher found this offensive, because I saved me the time to find lame excuses, which he did not expect. – Sebastian Mach Mar 19 '14 at 11:24
  • 2
    @PlasmaHH: While freeing in the same compilation unit is not required, the free really should be in the same library as the allocation, possibly by explicitly exposing a deallocator. That is especially true of shared libraries. Assuming that the "free" of the base program is compatible with the "malloc" used in a library is not safe. It also can result in being unable to use an API from a different language without leaking memory, since those languages may not have access to the same "free". – Kevin Cathcart Mar 19 '14 at 20:27
  • @KevinCathcart: Funny that in the past two decades I never had any problems doing that, and appearantly almost all software on linux doesn't too. Is that maybe a myth creeping from extraordinary broken implementations? Since the standard doesn't require such a thing, I would call such implementations noncompliant and broken. – PlasmaHH Mar 19 '14 at 20:36
  • 1
    Sure, but shared libraries are not even considered by the language standards to begin with, so using them is undefined behavior. Reasonably sized applications running under windows will often have a minumum of two different malloc implementations, which may but are not required to co-operate. Further, even under linux programs and shared libraries are free to use a C library other than libc.so, such as a static libc, or alternate implementation. It can be really, really annoying/expensive to fix when a library makes this assumption, but the environment does not permit it. – Kevin Cathcart Mar 19 '14 at 20:50
  • I'm sure you've misunderstood the topic. They were either telling you to avoid mallocing/freeing tiny blocks of memory, or to reuse the memory blocks if possible. – Danubian Sailor Mar 20 '14 at 09:31

11 Answers11

100

Easy: just read the source of pretty much any half-serious malloc()/free() implementation. By this, I mean the actual memory manager that handles the work of the calls. This might be in the runtime library, virtual machine, or operating system. Of course the code is not equally accessible in all cases.

Making sure memory is not fragmented, by joining adjacent holes into larger holes, is very very common. More serious allocators use more serious techniques to ensure this.

So, let's assume you do three allocations and de-allocations and get blocks layed out in memory in this order:

+-+-+-+
|A|B|C|
+-+-+-+

The sizes of the individual allocations don't matter. then you free the first and last one, A and C:

+-+-+-+
| |B| |
+-+-+-+

when you finally free B, you (initially, at least in theory) end up with:

+-+-+-+
| | | |
+-+-+-+

which can be de-fragmented into just

+-+-+-+
|     |
+-+-+-+

i.e. a single larger free block, no fragments left.

References, as requested:

unwind
  • 391,730
  • 64
  • 469
  • 606
  • 1
    Can you provide me some references? – Nick Mar 18 '14 at 13:45
  • 4
    I think, it'd be worth mentioning that virtual address space is not direct representation of physical memory. And that fragmentation in physical memory can be dealt with by OS, while virtual memory not released by process will not be released physically either. – lapk Mar 18 '14 at 13:49
  • @PetrBudnik it would be rare that virtual memory maps 1-1 to physical memory anyway, the OS will think in page mappings and be able to swap it in and out with minimal fuss – ratchet freak Mar 18 '14 at 14:33
  • 3
    Very nitpicky comment: While the concept is well explained, the actual example was chosen a bit.. unlucky. For anybody looking at the source code of say dlmalloc and getting confused: Blocks below a specific size are always powers of 2 and are merged/split accordingly. So we'd end up (possibly) with one 8-byte block and 1 4-byte block, but no 12-byte block. That's a pretty standard approach for allocators at least on desktops, although maybe embedded applications try to be more careful with their overhead. – Voo Mar 19 '14 at 01:24
  • @Voo I removed the mention of a size for the blocks in the example, it didn't matter anyway. Better? – unwind Mar 19 '14 at 07:41
  • Just to clarify @Voo answer, the reason the compiler allocates a power-of-2 number of bytes instead of the value you asked for is to reduce fragmentation. I am not entirely sure what most compilers do without the -O flag set, but with it set it most surely will allocate a power of two instead of the amount you asked. See http://stackoverflow.com/questions/3190146/is-it-better-to-allocate-memory-in-the-power-of-two – Hoffmann Mar 19 '14 at 16:26
  • "Reading the source" of a serious `malloc` implementation in Windows will be completely useless. You'll just see a call to `HeapAlloc`, whose source you can't read... – user541686 Mar 20 '14 at 10:03
43

The other answers already explain perfectly well that real implementations of malloc() and free() do indeed coalesce (defragmnent) holes into larger free chunks. But even if that wasn't the case, it would still be a bad idea to forego free().

The thing is, your program just allocated (and wants to free) those 4 bytes of memory. If it's going to run for an extended period of time, it's quite likely that it will need to allocate just 4 bytes of memory again. So even if those 4 bytes will never coalesce into a larger contiguous space, they can still be re-used by the program itself.

Angew is no longer proud of SO
  • 167,307
  • 17
  • 350
  • 455
  • 7
    +1 Exactly. The thing is, if `free` is being called enough times to have an impact on performance, then it is probably also being called enough times such that leaving it out will make a very large dent in available memory. It is hard to imagine a situation on an embedded system where performance continuously suffers due to `free` but where `malloc` is only called a finite number of times; it is a fairly rare use case to have an embedded device that does one-shot processing of data then resets. – Jason C Mar 19 '14 at 08:36
10

It's total nonsense, for instance there are many different implementations of malloc, some try to make the heap more efficient like Doug Lea's or this one.

Paul Evans
  • 27,315
  • 3
  • 37
  • 54
9

Are your professors working with POSIX, by any chance? If they're used to writing lots of small, minimalistic shell applications, that's a scenario where I can imagine this approach wouldn't be all too bad - freeing the whole heap at once at the leisure of the OS is faster than freeing up a thousand variables. If you expect your application to run for a second or two, you could easily get away with no de-allocation at all.

It's still a bad practice of course (performance improvements should always be based on profiling, not vague gut feeling), and it's not something you should say to students without explaining the other constraints, but I can imagine a lot of tiny-piping-shell-applications to be written this way (if not using static allocation outright). If you're working on something that benefits from not freeing up your variables, you're either working in extreme low-latency conditions (in which case, how can you even afford dynamic allocation and C++? :D), or you're doing something very, very wrong (like allocating an integer array by allocating a thousand integers one after another rather than a single block of memory).

Luaan
  • 62,244
  • 7
  • 97
  • 116
  • Letting the OS free everything at the end is not just about performance - it also needs much less logic to get working. – hugomg Mar 24 '14 at 00:09
  • @missingno In other words, it lets you get away with how hard memory management can be :) However, I would see that as an argument against non-managed languages - if your reason is complicated freeing logic rather than performance, you might be better off using a language / environment that takes care of it for you. – Luaan Mar 24 '14 at 08:30
5

You mentioned they were electronics professors. They may be used to writing firmware/realtime software, were being able to accurately time somethings execution is often needed. In those cases knowing you have enough memory for all allocations and not freeing and reallocating memory may give a more easily computed limit on execution time.

In some schemes hardware memory protection may also be used to make sure the routine completes in its allocated memory or generates a trap in what should be very exceptional cases.

Paddy3118
  • 4,704
  • 27
  • 38
  • 10
    That's a good point. However, I'd expect that they wouldn't use `malloc` and such at all in that case, instead relying on static allocation (or perhaps allocate a large chunk and then manually handle the memory). – Luaan Mar 19 '14 at 08:38
2

Taking this from a different angle than previous commenters and answers, one possibility is that your professors have had experience with systems where memory was allocated statically(ie: when the program was compiled).

Static allocation comes when you do things like:

define MAX_SIZE 32
int array[MAX_SIZE];

In many real-time and embedded systems(those most likely to be encountered by EEs or CEs), it is usually preferable to avoid dynamic memory allocation altogether. So, uses of malloc, new, and their deletion counterparts are rare. On top of that, memory in computers has exploded in recent years.

If you have 512 MB available to you, and you statically allocate 1 MB, you have roughly 511 MB to trundle through before your software explodes(well, not exactly...but go with me here). Assuming you have 511 MB to abuse, if you malloc 4 bytes every second without freeing them, you will be able to run for nearly 73 hours before you run out of memory. Considering many machines shut off once a day, that means your program will never run out of memory!

In the above example, the leak is 4 bytes per second, or 240 bytes/min. Now imagine that you lower that byte/min ratio. The lower that ratio, the longer your program can run without problems. If your mallocs are infrequent, that is a real possibility.

Heck, if you know you're only going to malloc something once, and that malloc will never be hit again, then it's a lot like static allocation, though you don't need to know the size of what it is you're allocating up-front. Eg: Let's say we have 512 MB again. We need to malloc 32 arrays of integers. These are typical integers - 4 bytes each. We know the sizes of these arrays will never exceed 1024 integers. No other memory allocations occur in our program. Do we have enough memory? 32 * 1024 * 4 = 131,072. 128 KB - so yes. We have plenty of space. If we know we will never allocate any more memory, we can safely malloc those arrays without freeing them. However, this may also mean that you have to restart the machine/device if your program crashes. If you start/stop your program 4,096 times you'll allocate all 512 MB. If you have zombie processes it's possible that memory will never be freed, even after a crash.

Save yourself pain and misery, and consume this mantra as The One Truth: malloc should always be associated with a free. new should always have a delete.

Shaz
  • 1,376
  • 8
  • 18
  • 2
    In most embedded and real-time systems, a time-bomb that causes failure after only 73 hours would be a severe problem. – Ben Voigt Mar 19 '14 at 14:16
  • _typical integers_??? Integer is at least 16-bit number and on small microchips usually is 16-bit. Generally there are more devices with `sizeof(int)` equals 2 rather 4. – ST3 Mar 25 '14 at 13:12
2

I think the claim stated in the question is nonsense if taken literally from the programmer's standpoint, but it has truth (at least some) from the operating system's view.

malloc() will eventually end up calling either mmap() or sbrk() which will fetch a page from the OS.

In any non-trivial program, the chances that this page is ever given back to the OS during a processes lifetime are very small, even if you free() most of the allocated memory. So free()'d memory will only available to the same process most of the time, but not to others.

mfro
  • 3,286
  • 1
  • 19
  • 28
2

Your professors aren't wrong, but also are (they are at least misleading or oversimplifying). Memory fragmentation causes problems for performance and efficient use of memory, so sometimes you do have to consider it and take action to avoid it. One classic trick is, if you allocate a lot of things which are the same size, grabbing a pool of memory at startup which is some multiple of that size and managing its usage entirely internally, thus ensuring you don't have fragmentation happening at the OS level (and the holes in your internal memory mapper will be exactly the right size for the next object of that type which comes along).

There are entire third-party libraries which do nothing but handle that kind of thing for you, and sometimes it's the difference between acceptable performance and something that runs far too slowly. malloc() and free() take a noticeable amount of time to execute, which you'll start to notice if you're calling them a lot.

So by avoiding just naively using malloc() and free() you can avoid both fragmentation and performance problems - but when you get right down to it, you should always make sure you free() everything you malloc() unless you have a very good reason to do otherwise. Even when using an internal memory pool a good application will free() the pool memory before it exits. Yes, the OS will clean it up, but if the application lifecycle is later changed it'd be easy to forget that pool's still hanging around...

Long-running applications of course need to be utterly scrupulous about cleaning up or recycling everything they've allocated, or they end up running out of memory.

Matthew Walton
  • 9,809
  • 3
  • 27
  • 36
1

Your professors are raising an important point. Unfortunately the English usage is such that I'm not absolutely sure what it is they said. Let me answer the question in terms of non-toy programs that have certain memory usage characteristics, and that I have personally worked with.

Some programs behave nicely. They allocate memory in waves: lots of small or medium-sized allocations followed by lots of frees, in repeating cycles. In these programs typical memory allocators do rather well. They coalesce freed blocks and at the end of a wave most of the free memory is in large contiguous chunks. These programs are quite rare.

Most programs behave badly. They allocate and deallocate memory more or less randomly, in a variety of sizes from very small to very large, and they retain a high usage of allocated blocks. In these programs the ability to coalesce blocks is limited and over time they finish up with the memory highly fragmented and relatively non-contiguous. If the total memory usage exceeds about 1.5GB in a 32-bit memory space, and there are allocations of (say) 10MB or more, eventually one of the large allocations will fail. These programs are common.

Other programs free little or no memory, until they stop. They progressively allocate memory while running, freeing only small quantities, and then stop, at which time all memory is freed. A compiler is like this. So is a VM. For example, the .NET CLR runtime, itself written in C++, probably never frees any memory. Why should it?

And that is the final answer. In those cases where the program is sufficiently heavy in memory usage, then managing memory using malloc and free is not a sufficient answer to the problem. Unless you are lucky enough to be dealing with a well-behaved program, you will need to design one or more custom memory allocators that pre-allocate big chunks of memory and then sub-allocate according to a strategy of your choice. You may not use free at all, except when the program stops.

Without knowing exactly what your professors said, for truly production scale programs I would probably come out on their side.

EDIT

I'll have one go at answering some of the criticisms. Obviously SO is not a good place for posts of this kind. Just to be clear: I have around 30 years experience writing this kind of software, including a couple of compilers. I have no academic references, just my own bruises. I can't help feeling the criticisms come from people with far narrower and shorter experience.

I'll repeat my key message: balancing malloc and free is not a sufficient solution to large scale memory allocation in real programs. Block coalescing is normal, and buys time, but it's not enough. You need serious, clever memory allocators, which tend to grab memory in chunks (using malloc or whatever) and free rarely. This is probably the message OP's professors had in mind, which he misunderstood.

david.pfx
  • 10,520
  • 3
  • 30
  • 63
  • Compilers definitely are *not* like you describe. Check e.g. the various forms the memory allocation has taken in GCC, and why. – vonbrand Mar 18 '14 at 14:31
  • 1
    The bad behaving programs show that decent allocators should use separate pools for chunks of different sizes. With virtual memory, having many different pools far apart should not be a major problem. If every chunk is rounded up to a power of two, and every pool contains thus rounded chunks of only one size, I cannot see how fragmentation could ever get very bad. At worst a program could suddenly stop being interested in a certain size range altogether, leaving some largely empty pools to remain unused; I don't think this is very common behaviour though. – Marc van Leeuwen Mar 18 '14 at 16:31
  • 5
    Citation very much required for the claim that competently written programs don't free memory until the app closes. –  Mar 18 '14 at 17:52
  • 12
    This entire answer reads like a series of random guesses and supposition. Is there anything to back up any of this? – Chris Hayes Mar 18 '14 at 18:54
  • 4
    I'm not sure what you mean by saying that the .NET CLR runtime doesn't free any memory. As far as I've tested it does, if it can. – Theodoros Chatzigiannakis Mar 18 '14 at 19:10
  • .NET CLR frees memory rather aggressively once you pass a threshold, in fact. We're not talking about individual bytes or kilobyte, but as you get to megabytes, it indeed deallocates a lot. If a .NET application isn't freeing up memory, you're doing something very wrong (a prime example being unmanaged pointers to managed memory, which prevent heap compaction). – Luaan Mar 19 '14 at 08:42
  • 1
    @vonbrand: GCC has multiple allocators, including its own brand of garbage collector. It consumes memory during passes, and collects it between passes. Most compilers for other languages have at most 2 passes and free little or no memory between passes. If you disagree, I'm happy to research any example you give. – david.pfx Mar 19 '14 at 10:11
  • @marc: you're right, but you presume multiple allocators, which is my point. A single malloc/free won't hack it. – david.pfx Mar 19 '14 at 10:12
  • @jon: citation impossible, every big program is unique. I say that multiple custom allocators is a common strategy, and returning memory to the malloc heap before the end of the program is pointless. Can you cite a big program that does otherwise? – david.pfx Mar 19 '14 at 10:12
  • @luaan: you totally don't get it. The CLR (and JVM) are themselves programs written in C++ or whatever. I'm not talking about memory usage by the application program, I'm talking about the strategy used by the CLR or JVM itself, which is manages and hands out to the application. That memory is not freed, as far as I am aware. Do you know enough about the CLR or JVM internals to say I'm wrong? – david.pfx Mar 19 '14 at 10:13
  • Unless we don't understand each other at all, yes, it's plainly visible in either VMMap or even just resource monitor. It does allocate virtual memory, and it does free it. In fact, VMMap shows a lot of how the CLR manages memory (including JIT compilation and such). It does use `VirtualAlloc` a lot (from my observations, almost exclusively), but that doesn't really matter - in the end, it is allocating and freeing memory. I can't speak about JVM (or any of its given implementations), from my (very limited) observations, it seemed that it indeed didn't free memory. But there's a lot of JVMs. – Luaan Mar 19 '14 at 10:44
  • 1
    The JVM can definitely return memory to the OS, although it depends on the specific JVM and the garbage collector used. Oracle's JVM has a couple of collectors that return memory to the OS, including the shiny new G1 collector. Oracle's ConcurrentMarkSweep collector is a notable exception, but it is designed specifically for "only application on a server" workloads, where it would be of no benefit to return memory to the OS. See http://www.stefankrause.net/wp/?p=14 – James_pic Mar 19 '14 at 15:01
1

I'm surprised that nobody had quoted The Book yet:

This may not be true eventually, because memories may get large enough so that it would be impossible to run out of free memory in the lifetime of the computer. For example, there are about 3 ⋅ 1013 microseconds in a year, so if we were to cons once per microsecond we would need about 1015 cells of memory to build a machine that could operate for 30 years without running out of memory. That much memory seems absurdly large by today’s standards, but it is not physically impossible. On the other hand, processors are getting faster and a future computer may have large numbers of processors operating in parallel on a single memory, so it may be possible to use up memory much faster than we have postulated.

http://sarabander.github.io/sicp/html/5_002e3.xhtml#FOOT298

So, indeed, many programs can do just fine without ever bothering to free any memory.

oakad
  • 6,945
  • 1
  • 22
  • 31
1

I know about one case when explicitly freeing memory is worse than useless. That is, when you need all your data until the end of process lifetime. In other words, when freeing them is only possible right before program termination. Since any modern OS takes care freeing memory when a program dies, calling free() is not necessary in that case. In fact, it may slow down program termination, since it may need to access several pages in memory.