C Coding Tip - Self-Manage Memory Alllocation

An anonymous reader inputs: "The C programming language defines two standard memory management functions: malloc() and free(). C programmers frequently use those functions to allocate buffers at run time to pass data between functions. In many situations, however, you cannot predetermine the actual sizes required for the buffers, which may cause several fundamental problems for constructing complex C programs. This article advocates a self-managing, abstract data buffer. It outlines a pseudo-C implementation of the abstract buffer and details the advantages of adopting this mechanism."

Comments

Um

[be-fan]

*cough* garbage collection *cough*

Re:Um

[Screaming Lunatic]

Which means you don't have predictable destruction. Which means you don't have destructors. Which means you can't use idioms like resource-allocation-is-initialization.

So in the presence of exceptions, you won't leak memory on the heap. But you will leak mutexes, file handles, etc. You need another idiom to handle those cases.

In the .NET world, C# introduced synchronization blocks to handle the leaking mutex problem. But it is a pain in Managed C++ and VB.NET.

Garbage collection is not the be all and end all.

If I ruled the world, I would create a multi-paradigm (object-oriented, generic, functional, and modular support) strongly-typed low-level language that let you program at a high-level. A second high-level langauge that was loosely-typed, garbage collected, and could be interpreted or natively compiled. Then I would define a standard to interface the two languages.

In other words, take C++ and add the concept of components/packages. Take Python and add the features (such as generics) that are missing from C++. And then define an interface between components written in both langauges.

Currently Boost.Python and SWIG exist. But I wish that they would just work automagically, everytime I typed make at the command line or build in VC++.

Re:Um

[egomaniac]

Which means you don't have predictable destruction. Which means you don't have destructors. Which means you can't use idioms like resource-allocation-is-initialization.

So in the presence of exceptions, you won't leak memory on the heap. But you will leak mutexes, file handles, etc. You need another idiom to handle those cases.

Java is probably the most widely-used garbage-collected language in existence. I think I speak for all Java programmers when I say "WTF are you talking about?"

It is true that you can't guarantee timely execution of finalizers. Because of that, Java is no different than any other language in that you should close files when you're done with them. However, if you forget to close a file here and there, it's generally no big deal because they will be closed during finalization. It only becomes a problem when you're leaking tons of file handles very quickly.

Now, this article is about C, so let's compare the two.

Java: failing to close a file == usually no problem whatsoever

C: failing to close a file == permanently leaked handle

I'd take the garbage-collected case any day of the week, personally.

As far as the other case you mention, mutexes, goes, Java has two means of providing mutual exclusion. The "synchronized" keyword, which is almost always the way things are done, works properly in the face of exceptions, with no extra work by the user. The wait and notify methods, which are the more advanced case, need to be balanced, so you can end up with deadlocks if you fail to do a notify for some reason (such as an exception).

Well, that's what the "finally" clause is for. Yes, you need to be careful to do things the right way, but that's true of any language.

I freely admit that Java is not the be-all and end-all of languages. There may be ways of handling these situations that guarantee these problems can never occur. But you make it sound as if garbage collection is a step backwards from malloc/free, and it most certainly is not. Everywhere you can get into trouble with a garbage collected language, you can get into ten times as much trouble with a manual-free language.

Re:Um

[Curien]

Java is probably the most widely-used garbage-collected language in existence. I think I speak for all Java programmers when I say "WTF are you talking about?"

He's talking about the unpredictability of resource release using GC. If unpredictability isn't a problem, fine. If you need to synchronize your resources carefully (which is what a mutex is /all about/), then you've got a problem.

Now, this article is about C, so let's compare the two.

The post you're responding to wasn't about C: it was about a weakness of GC compared to, say, RAII (which is the idiom C++, among others, uses). But just for fun, let's go on to see how little you know about C.

Java: failing to close a file == usually no problem whatsoever

Unless you need to open the file again before the garbage collector decides to reclaim the handle.

C: failing to close a file == permanently leaked handle

Bzzt... wrong. All file handles are released upon program termination. I like how you used '==' to try impress people with your programming skillz, though.

As far as the other case you mention, mutexes, goes, Java has two means of providing mutual exclusion. The "synchronized" keyword

Wait, wait... you're saying... hold on a second, now... that Java uses a different idiom to handle mutexes? That's exactly what the parent post said it would have to do... because GC isn't as useful as RAII when it comes to general resource allocation (not just memory).

But you make it sound as if garbage collection is a step backwards from malloc/free

He made no such comparison. He compared it (unfavorably) to RAII.

Re:Um

[Nevyn]

If you amortize the time the GC spends in collection over the allocations, the average allocation isn't that much slower than the corresponding malloc/free. Best of all, the gap is shrinking. Soon, GC may be FASTER overall than malloc/free in many real-world situations. It obviously depends on memory usage patterns and collection strategies, but it is starting to happen.

I've heard that for years, it's yet to be true for the general case ... and most people doing manual allocation don't call malloc/free for every single grow/shrink operation. The caching slab allocator was put into solaris a long time ago now.

If you're using GC, your program doesn't have to do all of the bookkeeping anymore.

The keyword being all, yes you can sometimes just completely forget about designing how you use memory and everything "works". However sometimes those bits of memory have other resources associated with them.

An L1 cache miss costs around 4-10 cycles; an L2 miss can cost 100-400 cycles; a page fault costs millions. The CPU time spent in garbage collection can become insignificant when compared with storage access time.

You seem to be under the impression that running the GC isn't going to blow your cache ... why is that?

But compacting GC implementations are starting to take things like that into consideration when they collect, and they rearrange the memory of the process to maximize cache hits and minimize memory waste.

And the GC knows when to move memory, and when it's just wasting CPU/cache ... how? It's fairly simple to have double pointers (both win32 and MacOS9 use HANDLE types a lot IIRC). The big problem is working out when you can/should move them.

GCs usually collect on a separate thread. That means that with a properly designed collector, while your program is blocked on IO or waiting for user input, the GC might be cleaning up the heap on a low priority thread. With luck, your main thread might NEVER actually be interrupted for a collection

If you actually want threads ... which many of us don't. It also seems to think that cross CPU cache invalidates are free (accessing the same data from more than one CPU -- this can have a massive cycle cost), and that the GC does some kind of magic locking which will never affect the application.

It's also amusing that, by definition, it means that as your application does more work (and hence needs more CPU) it is guaranteed to not get it ... because you will then suddenly start fighting with the GC thread.

While I don't think GC is quite to the point where it is free or beneficial to the performance of the average application, it is a lot less harmful than most people think.

It's my experience that the people who think GC is expensive generally know what they are talking about, and are in the minority. Most people either don't need to care (GC is good enough for them -- fair enough, I've written things where I used perl and didn't need to know how it allocated), or just don't care.

There are other ways of managing memory than just giving up and saying well the GC will save me. Vstr, which is a decent implementation of what the IBM article was trying to say removes almost all the allocation/deallocation headache when dealing with byte data ... but it's still controllable and predictable.

Re:Um

[moocat2]

Yes, the article is about C, but the poster was talking about predictable destruction, so he was not referring to C when dissing GC.

My guess is that he or she was referring to C++ using the RAII (resource acquisition is initialization) paradigm. Every resource is wrapped in a object and all objects are put on the stack. Voila, no resource leaks.

Also, I think your example is far from complete. While failing to close a file handle may be "no problem whatsoever" for the application itself, but can be a problem in the larger context. Some platforms will not allow a file to be deleted when it is open. If a programmer forgets to close a file handle, the user may not be able to delete the file until some time in the future. Far from an ideal situation.

And consider a different example. Think about trying to create a different synch primitive such as a reader-writer lock. Under a GC system, the programmer is still required to release the lock. If he doesn't, the system could essentially hang.

As for the finally clause, we all know that guaranteeing that there is no path that allows leaks is just plain damn hard to do. If finally was such a great answer, why even both with GC, just free data in the finally clause.

Gee, isn't that handy

[c]

Anyone who's done C coding for more than, oh, a day would have already figured that out. It's not a coincidence that every programming language that doesn't have "smart" arrays built into the language ends up with some sort of buffer class (Java's ByteStream class, C++'s stream IO buffers, etc).

The fundamental problem is that this sort of thing needs to be done at the C library level. And if it's not done in a flexible fashion, you end up with a library call that rarely gets used. Anyone used hsearch() lately?

If only clib streams (FILE* and friends) were extensible, this article would never have had to be written.

c.

Hmmm

[JMZero]

Many small programs are no longer memory, or even performance, constrained. As such, a reasonable strategy for a lot of desktop software is to allocate a huge buffer at startup, and do repetitive flushes and complete reloads of data (always using the same pre-allocated buffers).

This is simple to do, and avoids a lot of errors. It's also not much of a headline.

Useful

[dtfinch]

But this is like teaching calculus students remedial math. The "Level: Intermediate" at the top of the article should have given that away.

Re:realloc

[Permission Denied]

Regarding realloc:

When you call realloc, you're very likely to cause the data to be copied from the old buffer to the new buffer. This is very high overhead. The article discusses how to do similar things, but without this unecessary copying (eg, low overhead). It's actually not that interesting of an article as what it describes is hardly new and I believe any competent programmer could come up with that solution when faced with the particular circumstances that inspired it.

Realloc works by seeing if there is free memory after the end of the allocated block, and changing the block's size if so. Realloc can do this because it knows about the internals of the malloc/free implementation. If there is allocated memory right after the block in question, a new block must be allocated, as you cannot "move" the later block in a language like C where any memory location can be a pointer. You could try this kind of stuff in other languages (or in some bastardized C where you do not have direct access to memory, but go through more indirection, the next logical abstraction after the article), but when you start automatically finding/checking/updating memory pointers, you get into GC.

You may be able to overcome some overhead on realloc if you move the problem down into the kernel. The kernel could play page table games so there is little or no actual copying involved, just updating of page tables. This would be fairly easy to implement, but I don't think anyone's done it because (a) flushing the relevant TLB entries could hurt performance more than the copying, and (b) the system call overhead might be more overhead than the copying. Realloc is generally only used for small buffers (due to programmers knowing about the copying overhead) and this trick would only have gains for large buffers spanning multiple pages. For small buffers, the library-level realloc could avoid the system call and do the copying itself, avoiding system call overhead and TLB entry flushes.

This scheme I describe could make for an interesting paper (especially determining for what size of buffer and what type of program it has gains), but I doubt it would make much difference in real system performance as programmers avoid realloc for large buffers, and there are very few cases where one needs direct linear access to a large range of memory rather than being better-served by organizing that memory into some data structure.