Garbage Collection for C

I was ignorant. An hour ago, I thought it is impossible to implement a garbage collector (GC) for C, but this is certainly wrong.

For an interpretated language like Perl, it is cheap to keep track of memory that is not referenced and therefore it is not so hard to identify and free unused memory in most cases except circular referencing. Java disallows pointers, of course including internal pointers. Objects out of the scope can be easily identified and freed. C is very different. At the first sight, it is impossible to directly tell where pointer variables point to. Then how to identify unused memory? This page gives the answer: we can scan registers, stacks and static data regions to collect information on pointers. Knowing this information makes it possible to implement a GC for C. The most famous implementation is the Boehm-Demers-Weiser GC library. A third-party review shows that this GC may outperform manual memory management. It also thoroghly discusses the advantages and disadvantages of this library in the end. The memory management reference is another website that provides insight into GC.

Probably I will not use GC in C. Although GC can be faster, its behaviour is less predictable than manual memory management. This makes me feel uneasy when I am used to controlling the memory. What is more important, BDW GC seems not to do boundary check. When such an error occurs, it will be very difficult to identify the problem when GC effectively cripples valgrind which should pinpoint the error otherwise.

Read Full Post »

Memory Allocation on the Heap vs. on the Stack

This topic sounds pretty elementary, but I did not know the difference a week ago. Just explain it here as a record. You may also want to have a look at this page.

Memory can be allocated on the heap or on the stack. When a program calls malloc() family, the memory will be allocated on the heap. When you define a variable or an array or call alloca(), the memory will be allocated on the stack. The data on the stack are separated by frames. Each time a open-brace is met, a scope is initiated and a frame which contains the data in the scope will be pushed on the stack; each time a close-brace is met, the scope is over and the frame will be removed. To this end, memory allocated on the stack is transcient. Pointers pointed to such memory become invalid when the scope is over.

Allocation on the stack is more convenient and cheaper, but the maximum stack size is limited. It may cause stack overflow if your program allocates large memory on the stack. In addition, allocating large arrays on the stack may fool valgrind (see here). Usually, large arrays should be allocated on the heap.

Read Full Post »

Mastering C Pointers (or not)?

C pointer is the most powerful and nasty concept. Whether marstering C points or not separate intermediate C programers from the elementary ones. Want to know whether you have mastered C pointers? Have a look at this program. If the basic idea is clear to you, you are qualified to be an intermediate programmer. If you have difficulty, you should learn hard from other programmers. It is unwise to study this program as a beginner. The catch in the program is too complicated.

This program is adapted from an example in the C bible “The C Programming Language” written by Kernighan & Ritchie. I commented it and extended its function a bit. This allocator is usually not as efficient as malloc family that comes with the system, but it is good enough for a lot of practical applications. Also, this allocator is simple and clear. You can largely predict its behaviour. In comparison, it is not always easy to understand malloc is doing.

I came to know this allocator from Phil Green’s Phrap assembler. I then found the book and reimplemented in my way.

Read Full Post »