simple c malloc

Question

While there are lots of different sophisticated implementations of malloc / free for C/C++, I'm looking for a really simple and (especially) small one that works on a fixed-size buffer and supports realloc. Thread-safety etc. are not needed and my objects are small and do not vary much in size. Is there any implementation that you could recommend?

EDIT:

I'll use that implementation for a communication buffer at the receiver to transport objects with variable size (unknown to the receiver). The allocated objects won't live long, but there are possibly several objects used at the same time.

As everyone seems to recommend the standard malloc, I should perhaps reformulate my question. What I need is the "simplest" implementation of malloc on top of a buffer that I can start to optimize for my own needs. Perhaps the original question was unclear because I'm not looking for an optimized malloc, only for a simple one. I don't want to start with a glibc-malloc and extend it, but with a light-weight one.

Adlib

Could you clarify what you mean by "support realloc"? One compliant implementation of realloc uses only malloc, free and memcpy. Is that acceptable to you? Technically, another compliant implementation always returns NULL, but it's clear you do not mean that one. – Chuff

You need to explain why you can't use one that came with your compiler. If this is because you're working in some sort of environment where your compiler didn't come with malloc (perhaps for embedded software), you need to describe the environment for any answers to be of use to you. Right now, this question cannot be satisfactorily answered (except for Martin York's suggestion to use the one bundled with your compiler). – Onto

Yes, a very simple realloc (that does not return NULL if enough space is available in the buffer) would be acceptable. – Adlib

support for realloc appears inconsistent with working on a fixed-size buffer - do you mean 'works within a fixed subset of available memory" or "works with fixed-size objects" - or something else? – Important

I mean: malloc etc. work on a fixed subset of available memory that is provided by me. – Adlib

@Adlib - thanks - what is your platform? – Important

You shouldn't use malloc() and friends in C++. – Hyposensitize

Using new instead of malloc makes my code about 200 kB larger - that is a lot if the whole memory is only 256 kB. – Adlib

@Thomas: (You should properly @address when you reply in comments or we won't see it in our responses tab. I only come upon this one by accident.) The reason for that is that new does more than malloc() does. As long as you're only using PODs, it will work. As soon as you're using non-PODs, you're deep into Undefined Behavior land. – Hyposensitize

@sbi: int *x = new int vs. int *x = static_cast<int*> (malloc (sizeof (int))) (in an otherwise empty main()) yields executable sizes of 322514 vs. 52687 bytes on my platform - I'd be interested in knowing the reason (I guess some big c++ libs are linked). – Adlib

@Thomas: I guess so, too. But I wouldn't know. I don't know your platform, and even if I did, I never had a look at any's innards. If you worry about ~250jB, I suppose you're on an embedded platform. I don't know much about those. – Hyposensitize

Answer 1

Kerninghan & Ritchie seem to have provided a small malloc / free in their C book - that's exactly what I was looking for (reimplementation found here). I'll only add a simple realloc.

I'd still be glad about suggestions for other implementations that are as simple and concise as this one (for example, using doubly-linked lists).

Adlib

@Ben: OP answered his own question. :-) – Murvyn

Could you please share your realloc code? – Mok

Answer 2

I recommend the one that came with standard library bundled with your compiler.

One should also note there is no legal way to redefine malloc/free

Diaphone

If anything, small objects that have some variance are ideal for the default allocators. – Complementary

That would possibly be okay (and I'm currently using it), but I would like to know if a very simple and restricted implementation could provide some speedup for my application. – Adlib

@Thomas: Anything is possible. But other implementations are designed to solve specific problems that there implementers had. Unless you had exactly the same characteristics as them it is unlikely it will help. – Diaphone

@Thomas: it's likely that the version of malloc that came with your C library has been optimised very carefully over a number of years to be as fast as possible for most common usage profiles. You'll probably find it's fast enough. – Gilley

I'm definitely not denying that the standard implementation would be okay - I'd just like to see the difference, and I wasn't able to pick up that particular "small and simple" implementation among the many ones google/sf gave me. – Adlib

Could you please expand on the legality of redefining malloc/free? Isn't linking in your own allocator object files instead of the stdlib's ones "legal"? – Understate

Sorry to zombie a 4 year old comment thread. But I ended up here looking for an implementation for use in an embedded application where space is limited. Sure, I could statically build libc malloc(), but its going to be bigger and have more features than I need. If I can shave precious kbytes of code off by only implementing what I need, then I have won. – Misplace

@kris: I have exactly the same problem. Even by using the gcc nano lib, the malloc/free provided is wasting almost 100 bytes of RAM, where I definitively need them. I just cannot understand why people cannot just answer the question instead of denying other's problems. – Lepper

Downwote because: if someone wants to implement a simple malloc and asks for help then it is not helpful to recommend the use of standard malloc. and does not answer the question. Indeed I think it is disrespectful to assume that the asker does not know of the risk of implementing their own. – Surveillance

Answer 3

The malloc/free/realloc that come with your compiler are almost certainly better than some functions you're going to plug in.

It is possible to improve things for fixed-size objects, but that usually doesn't involve trying to replace the malloc but rather supplementing it with memory pools. Typically, you would use malloc to get a large chunk of memory that you can divide into discrete blocks of the appropriate size, and manage those blocks.

Onto

Answer 4

There's a relatively simple memory pool implementation in CCAN:

http://ccodearchive.net/info/antithread/alloc.html

This looks like fits your bill. Sure, alloc.c is 1230 lines, but a good chunk of that is test code and list manipulation. It's a bit more complex than the code you implemented, but decent memory allocation is complicated.

Series

Answer 5

It sounds to me that you are looking for a memory pool. The Apache Runtime library has a pretty good one, and it is cross-platform too.

It may not be entirely light-weight, but the source is open and you can modify it.

Tergum

Yes, 2601 lines of code in apr_pools.c is not exactly light-weight. Perhaps I should really spend an hour and write my own tiny implementation. I was only thinking that perhaps a lot of people have already written such a basic malloc, so I could reuse and extend it. – Adlib

Answer 6

I would generally not reinvent the wheel with allocation functions unless my memory-usage pattern either is not supported by malloc/etc. or memory can be partitioned into one or more pre-allocated zones, each containing one or two LIFO heaps (freeing any object releases all objects in the same heap that were allocated after it). In a common version of the latter scenario, the only time anything is freed, everything is freed; in such a case, malloc() may be usefully rewritten as:

char *malloc_ptr;
void *malloc(int size)
{
  void *ret;
  ret = (void*)malloc_ptr;
  malloc_ptr += size;
  return ret;
}

Zero bytes of overhead per allocated object. An example of a scenario where a custom memory manager was used for a scenario where malloc() was insufficient was an application where variable-length test records produced variable-length result records (which could be longer or shorter); the application needed to support fetching results and adding more tests mid-batch. Tests were stored at increasing addresses starting at the bottom of the buffer, while results were stored at decreasing addresses starting at the top. As a background task, tests after the current one would be copied to the start of the buffer (since there was only one pointer that was used to read tests for processing, the copy logic would update that pointer as required). Had the application used malloc/free, it's possible that the interleaving of allocations for tests and results could have fragmented memory, but with the system used there was no such risk.

Crackerbarrel

Answer 7

Echoing advice to measure first and only specialize if performance sucks - should be easy to abstract your malloc/free/reallocs such that replacement is straightforward.

Given the specialized platform I can't comment on effectiveness of the runtimes. If you do investigate your own then object pooling (see other answers) or small object allocation a la Loki or this is worth a look. The second link has some interesting commentary on the issue as well.

Important

The second link ("micro-allocator") looks good, but it has still too much features: threading support, different handling of different chunk sizes etc. - I really don't need all this. I'm thinking of some 100-200 lines of code that do the basics and nothing more, but are stable and tested. – Adlib

Could this be applicable to your scenario, given you appear to be handling incoming data in FIFO fashion? Small and perfectly-formed :-) boost.org/doc/libs/1_44_0/libs/circular_buffer/doc/… – Important

Yes - I already started to code a simple malloc and used a circular buffer for that, but I realized a bit too late that one list for the free chunks was not enough and instead of thinking about using two lists or extending my "header" structure to allocated chunks, I thought that it would be better to start with an existing implementation of malloc. – Adlib

I suspect that anything you find that works will be > the LoC size you wish. Also that your final result will be. – Important