C++ Memory Management Innovation: GC Allocator

If you prefer chinese, see http://cpp.winxgui.com/cn:memory-management-innovation.

Introduction

Most of c++ programmers don't benefit from GC. They are sick of deleting objects but have to do this. There are some C/C++ memory GC implementations, but they are complex and aren't wide to use.

Now I'll introduce a new memory management technology to you which I call it "GC Allocator". "GC Allocator" isn't an implementation, but a concept. Now, we have two "GC Allocator" implementations, named "AutoFreeAlloc" and "ScopeAlloc". "AutoFreeAlloc" and "ScopeAlloc" are based on the same class named "GCAllocT". "GCAllocT" is a tiniest, fastest allocator. And it is easy to use.

At first, let's see a very simple example.

A very simple example

#include <stdext.h>
 
class Obj
{
private:
    int m_val;
public:
    Obj(int arg = 0) {
        m_val = arg;
        printf("construct Obj: %d\n", m_val);
    }
    ~Obj() {
        printf("destruct Obj: %d\n", m_val);
    }
};
 
int main()
{
    const int count = 10;
    std::AutoFreeAlloc alloc;
 
    int* intObj = STD_NEW(alloc, int);
    int* intArray = STD_NEW_ARRAY(alloc, int, count);
 
    Obj* obj = STD_NEW(alloc, Obj);
    Obj* objWithArg = STD_NEW(alloc, Obj)(100);
    Obj* objArray = STD_NEW_ARRAY(alloc, Obj, count);
 
    return 0;
}

Here we use AutoFreeAlloc to allocate memory. And it can be replaced with ScopeAlloc:

int main()
{
    const int count = 10;
 
    std::BlockPool recycle;
    std::ScopeAlloc alloc(recycle);
 
    int* intObj = STD_NEW(alloc, int);
    int* intArray = STD_NEW_ARRAY(alloc, int, count);
 
    Obj* obj = STD_NEW(alloc, Obj);
    Obj* objWithArg = STD_NEW(alloc, Obj)(100);
    Obj* objArray = STD_NEW_ARRAY(alloc, Obj, count);
 
    return 0;
}

All allocated objects don't need to be deleted manually! They will be destroyed when the alloc allocator object is being destructed.

Difference between AutoFreeAlloc and ScopeAlloc

Both of AutoFreeAlloc and ScopeAlloc are based on GCAllocT class. The only different thing is that AutoFreeAlloc is based on malloc/free allocation functions, while ScopeAlloc is based on a recyclable allocator named BlockPool. This difference cause AutoFreeAlloc and ScopeAlloc have distinct performance difference. For the detail information, see "AutoFreeAlloc vs ScopeAlloc".

Here is our suggestion:

If you don't know you want AutoFreeAlloc or ScopeAlloc, please choose ScopeAlloc. It have good performance in any condition indeed.

Why GC Allocator is a Memory Management Innovation

Difference between new/delete and GC Allocator

When we use new/delete, we have to remember to destroy allocated objects when and where.
But when you are using GC Allocator, It is like GC languages (eg. Java, C#, etc), and deleting allocated objects is no need.

Difference between STL Allocator and GC Allocator

I think STL Allocator is a good start. It tells us we could use an allocator object, not a global new/delete procedure to manage memory. But, It's difficult to use since it doesn't support GC.

STL Allocator is designed for internal use. It's not recommended that you use STL allocators in your applications (see "The Standard Librarian: What Are Allocators Good For?").

Memory management is a primary service of any language. It plays the most important role. But, STL Allocator says that you can't use me. It is strange to me.

STL Allocator also has a defect that one allocator instance can only allocate one type objects. If you want allocate another type object, you must use rebind technology. It's really not easy to use and it is NOT all C++ compilers support rebind technology (eg. Visual C++ 6.0).

Applications based on GC Allocator

Is GC Allocator useful? Yes. Things are changed to C++ developers! We also can benefit from GC like Java and C#! And we already have applications based on it. Here are some of them:

The Fastest Word File Writer

I wrote a word file format writer by using GC Allocator. I was excited that It was the fastest word file writer component I had seen.

Interested in it? See The fastest word file writer.

Rope based on GC Allocator

Rope is a complex string implementation with scaled performance. The original rope version is implemented in SGI STL. I rewrite the rope class based on GC Allocator. It reduce many code lines and get a better performance.

Interested in it? See Rope on GC Allocator.

STL Containers based on GC Allocator

Not only rope, but most of all STL containers can be based on GC Allocator, including:

Need a performance comparison between these containers and STL containers? See "Allocators Performance on STL Collections".

Note that we don't provide all STL containers based on GC Allocator. STL containers of linear data structure (eg. std::vector, std::basic_string/std::string, etc) don't need a GC allocator.

Performance Comparison with Other Allocators

Why is GC Allocator so fast?

  • Don't need a multithread lock.
  • In comparison with "Memory Pool" technology (such as "boost pool", "gnu stdlibc++ mt_allocator", "sgi stl alloc"), GC Allocator doesn't need to divide memblock into chunks. And "Memory Pool" always need a lock for multithread safe, which waste too many time.
  • In comparison with "apache portable runtime (APR)", APR pools are similar to our GC Allocator. APR pools have better performance than other allocators what I have seen. But it is implemented by C, not C++. It makes apr pools have worse performance than GC Allocator (You may think that C is faster than C++. But I don't think so).
  • Need a performance comparison? See "Allocators Performance Comparison".

Why doesn't it need a lock?

Memory allocation = System memory block management + Memory management algorithm

System (underlying) memory block management is provided by OS. It only need to support large memory block allocation. And It is thread/process safe.

Memory management algorithm is provided by C/C++ runtime library, or other libraries. Memory management algorithm IS only an algorithm. Most of them are designed to be thread safe.

If we use a global new/delete or malloc/free procedure to allocate memory. Thread safe is MUST, not OPTIONAL. But if we use allocator instances to manage memory, then thread safe become OPTIONAL. This is why I say STL Allocator is a good start.

Sharing GC Allocator in multi threads is not recommended. Don't use any lock for GC Allocators.

We suggest that there only ONE BlockPool instance in ONE thread, and ONE thread may have many PRIVATE "ScopeAlloc" instances (depend on your need) to allocate memory.

And this make our GC Allocator being the fastest allocator!

Is GC Allocator open source?

Yes. Its homepage is http://code.google.com/p/stdext/.

Related Topics

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License