3

I'm overloading new and delete to implement my own small-objects/thread-safe allocator.

The problem is that when I am overloading new, I cannot use new without breaking universal causality or at least the compiler. Most examples I found where new is overloaded, use Malloc() to do the actual allocation. But from what I understood of C++, there is no use-case for Malloc() at all.

Multiple answers similar to this one, some with less tort outside of SO: In what cases do I use malloc vs new?

My question, is how do I allocate the actual memory when overloading operator new without using Malloc() ?

(This is out of curiosity more than anything, try not to take the reasoning behind the overload too seriously; I have a seperate question out on that anywho!)

Community
  • 1
  • 1
Anne Quinn
  • 12,609
  • 8
  • 54
  • 101
  • Sounds like a hard to answer question since I can't think of any other way to allocate memory in C++ without (in)directly calling `new` or `malloc()`? Did I misunderstand something? – Mysticial Sep 18 '11 at 03:54
  • @Mysticial - I don't believe so! I guess we'll both find out if there is a way or not soon enough. :P – Anne Quinn Sep 18 '11 at 03:58
  • And of course I forgot about the OS-specific memory allocators... :) – Mysticial Sep 18 '11 at 03:59
  • 1
    The `new vs malloc` question didn't consider the "overloading `new`" case. The biggest problem with `malloc()` - not calling ctors - is irrelevant here. – MSalters Sep 19 '11 at 08:56

2 Answers2

4

Short answer: if you don't want existing malloc, you need to implement your own heap manager.

A heap manager, for example malloc in glibc of Linux, HeapAlloc in Windows, is a user-level algorithm. First, keep in mind that heap is optimized for allocating small sizes of objects like 4~512 bytes.

How to implement your own heap manager? At least, you must call a system API that allocates a memory chunk in your process. There are VirtualAlloc for Windows and sbrk for Linux. These APIs allocate a large chunk of memory, but the size must be multiple of page size. Typically, the size of page in x86 and Windows/Linux is 4KB.

After obtaining a chunk of page, you need to implement your own algorithms how to chop down this big memory into smaller requests. A classic (still very practical) implementation and algorithm is dlmalloc: http://g.oswego.edu/dl/html/malloc.html

To implement, you need to have several data structures for book-keeping and a number of policies for optimization. For example, for small objects like 16, 20, 36, 256 bytes, a heap manager maintains a list of blocks of each size. So, there are a list of lists. If requested size is bigger than a page size, then it just call VirtualAlloc or sbrk. However, an efficient implementation is very challenging. You must consider not only speed and space overhead, but also cache locality and fragmentation.

If you are interested in heap managers optimized for multithreaded environment, take a look a tcmalloc: http://goog-perftools.sourceforge.net/doc/tcmalloc.html

minjang
  • 8,860
  • 9
  • 42
  • 61
  • Oh neat! Granted, it's dependent on the OS, but I imagine that's the cost of overloading `new` to begin with. Thanks! – Anne Quinn Sep 18 '11 at 04:07
  • Dependency on OS is inevitable in this case, but it's trivial. You simply make abstracted function calls for virtual memory allocation APIs. A simple #ifdef is also okay (see dlmalloc source code). – minjang Sep 18 '11 at 04:12
3

I see no problem in calling malloc() inside a new overload, just make sure you overload delete so it calls free(). But if you really don't want to call malloc(), one way is to just allocate enough memory another way:

class A {
    public:
        /* ... */
        static void* operator new (size_t size) {
            return (void *)new unsigned char[size];
        }
        static void operator delete (void *p) {
            delete[]((unsigned char *)p);
        }
        /* ... */
};
fbafelipe
  • 4,862
  • 2
  • 25
  • 40
  • This is just delegating to the global new/delete, which is what would happen automatically if you didn't even implement these two functions. Am I missing something that makes this somehow useful? – wjl Sep 30 '11 at 14:43
  • 2
    @wjl Yes, it is only delegating to the global new/delete, but since he stated in the question that it's for a small object thread safe allocator, he can change the example (which just show how he can alloc memory) and implement a cache or whatever he need over it. – fbafelipe Sep 30 '11 at 20:22