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

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.

Please

[YellowElectricRat]

This article, I believe, has already been published in the well known programmers' journal "No shit Sherlock - monthly"

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

[scrytch]

> garbage collection stops system response while it's cleaning up

And malloc is of course free, right? ("well no wally, they're opposites" ... yeah yeah you get my drift)

Good gc's operate incrementally. Good gc's let you turn gc on and off at will and disable it altogether for designated arenas. Good gc's can run in a separate thread on another CPU, whereas malloc/free cannot.

The reason java's gc goes wiggy is not because the gc is bad (it's just not very tunable except on solaris), it's because it allocates new objects all over the place (and is happily helped at it by the standard libraries). If you go hog wild with resource consumption, yes you're going to pay for it later.

For the 99.99% of programs that do NOT need hard realtime, you're better off with gc. Cripes, it's like saying homes shouldn't have thermostats because a home thermostat isn't suitable for a reactor sensor.

Re:Um

[be-fan]

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.
----------
You just described Scheme/CL/Dylan.

Memory Allocation

[rmohr02]

Just like slashdot allocated extra space for the third "l" in "alllocation".

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.

Wow!

[arkanes]

Man, I never thought of that. An abstract memory buffer. What a concept! I don't need to define the lengths of everything at compile time then!

Now, I'll need a nice short catchy name for it... oh! I know! I'll call it a heap!

Re:Um

[Tom7]

Of course, there are also hard real-time garbage collectors (ie Cheng's), though I don't think you'll find them in general-purpose production compilers. However, you will find good garbage collectors in a number of real production compilers (say, in mlton). It's definitely worth benchmarking.

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.

A memory leak IN THE SPECIFICATION?!?

[MarkusQ]

From the article:

• The pLostBlock points to the linked list's last memory block.

pLostBlock?!? This almost sounds as if it's designed to leak!

-- MarkusQ

P.S. Seriously, I think this is a fine idea, if not particularly earth shaking. But the typo was too ironic not to point out.

Re:Um

[cookd]

It's even better than that. In many cases, GC can be almost as fast as malloc/free. Looking at the way things are going, I am pretty sure that in the near future GC-based code will be faster, not slower, than equivalent malloc/free code:

• A compacting GC heap can make allocation into a REALLY fast operation (unless it triggers a collection), and there is no time spent deallocating. On normal heaps, malloc/new can take quite a lot of work (thread synchronization, best-fit free list searching, etc.). 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.
  
• If you're using GC, your program doesn't have to do all of the bookkeeping anymore. The amount of time spent in resource tracking in big programs is fairly significant -- where the same object is shared by many parts of the program, figuring out when the item can be released is nontrivial. Under a GC, this is handled by the collector. In some cases, the GC can handle the bookkeeping more efficiently than would have been feasible with manual bookkeeping.
  
• As CPUs get faster and storage (memory and disk) gets (relatively) slower, it becomes more and more attractive to spend extra CPU cycles to try to make better use of cache and memory. 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. Do you take the cache line size into consideration when you call malloc? I sure don't. 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. They can help your program make more efficient use of the cache, and perhaps reduce the working set. Just a 5% reduction in page faults would more than offset all but the most CPU-intensive garbage collectors.
  
• 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 -- all of the collection can be done while your work threads were waiting for something else. Your memory management tax was paid in the background, while the machine was otherwise idle. On the other hand, with malloc and free, the memory management tax is paid up front by the currently executing thread. While this isn't always the case (i.e. CPU-bound processes), most apps are NOT CPU-bound, so this is a likely scenario in the future (if not the present).

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. Given that it simplifies the code and eliminates a lot of bugs (usually more than it introduces), it is definitely worthwhile in almost all new application code (kernel-mode code isn't quite there yet, but it's coming), with only a small performance penalty. And I suspect that it won't be too long before it starts to be more of a speed booster, not a perf hit.

I think this is just another step in the process of handing another menial task over to the CPU. We moved from binary to assembly, assembly to low-level languages, low-level languages to higher-level languages, etc. At each step, the new method had a performance penalty at first, then as the new method matured, it turned out to actually be faster than the old method it replaced, while dramatically increasing programmer productivity (i.e. modern optimizers can usually do a better job than an assembly language programmer; often C++ code is faster than the equivalent C code since the compiler has more information to work with and the programmer can make use of more effective techniques like templates).

Vstr

[Nevyn]

The article basically proposes a very bad implementation of Vstr, most of the advise was extremly simplified at best but more likely just uninformed: an "efficient" abstract buffer that mixes shorts and pointers -- words almost fail me, how to solve the problem of "what do you do with the data when it's all in the buffer" -- "let's just copy it back out again (hey whats a couple of extra copies between friends). Representing in memory object sizes with "long int" *sigh*.

If you are interested in the article, go read this explanation of why you want it for security and this explanation of why you want it for speed .

Vstr is LGPL, has actual benchmark data behind the block sizes it picks, has an extensive test suite ... and has documentation for the many functions that come with the library (including a fully compliant printf like function). Of course, I don't have a PhD ... but after reading this, you might well count that as a plus too

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.