Asp Forum - Malloc Query

Pushpa

5/17/2011 7:39:00 PM

Hi all,

Many users claim that malloc() and free() provided by the language
library results in considerable
amount of overhead in terms of calling the same. Can we really
eliminate overhead by using
used defined functions/user defined memory manager. Is there any
significant advantage in providing user defined malloc() and free(). I
want to exclude realtime systems or embedded systems which are memory
constrained here.
I am talking about general purpose applications. With a user defined
memory manager can it handle
memory allocation and de-allocation in a much better way than what OS
would have done. Any inputs/comments
on the same are highly appreciated.

Thanks and Regards,
Pushpa

91 Answers

blp

5/17/2011 7:55:00 PM

Pushpa <pushpa@nospam.invalid> writes:

> Many users claim that malloc() and free() provided by the language
> library results in considerable
> amount of overhead in terms of calling the same. Can we really
> eliminate overhead by using
> used defined functions/user defined memory manager. Is there any
> significant advantage in providing user defined malloc() and
> free().

According to an academic study I read some time ago, there is
rarely any significant advantage to special-purpose memory
allocators. In a quick online search, I didn't find a reference
to this paper, but perhaps someone else here has a copy of it.
--
"It wouldn't be a new C standard if it didn't give a
new meaning to the word `static'."
--Peter Seebach on C99

Joe Pfeiffer

5/17/2011 8:02:00 PM

Pushpa <pushpa@nospam.invalid> writes:

> Hi all,
>
> Many users claim that malloc() and free() provided by the language
> library results in considerable
> amount of overhead in terms of calling the same. Can we really
> eliminate overhead by using
> used defined functions/user defined memory manager. Is there any
> significant advantage in providing user defined malloc() and free(). I
> want to exclude realtime systems or embedded systems which are memory
> constrained here.
> I am talking about general purpose applications. With a user defined
> memory manager can it handle
> memory allocation and de-allocation in a much better way than what OS
> would have done. Any inputs/comments
> on the same are highly appreciated.

I haven't come across the claim that they are especially expensive. You
really aren't going to do much better trying to write a general-purpose
memory allocator. Also, by the way, you seem to be making an assumption
that malloc() and free() are OS calls -- they aren't. They're C library
calls. They go on to call an OS space allocator (something in the brk()
family, last time I checked which was years ago) if they need it.

Now, if you're doing something special, you can write a special-purpose
allocator/deallocator that's optimized for it. A long, long time ago I
wrote a program that required ridiculous numbers of memory allocations
and frees of one particular size object. I sped that program up a lot
by maintaining my own free list of those objects, and writing my own
allocator/deallocator for them, and then only calling malloc() when my
free space pool was empty. The kernel does something similar with its
slab allocator (though not on top of malloc()/free(), of course).
--
"It used to be that the USA was pretty good at producing stuff teenaged
boys could lose a finger or two playing with." -- James Nicoll

China Blue Veins

5/17/2011 8:22:00 PM

> amount of overhead in terms of calling the same. Can we really
> eliminate overhead by using
> used defined functions/user defined memory manager. Is there any
> significant advantage in providing user defined malloc() and free(). I

If you have an expert tailoring the functions to the specific needs of the
program. I would say expert because with virtual memory, ignoring VM can ruin
performance.

Few projects can afford this kind of code.

A simple alternative that works well for some programs is a mark/release
secondary stack.

> I am talking about general purpose applications. With a user defined
> memory manager can it handle
> memory allocation and de-allocation in a much better way than what OS
> would have done. Any inputs/comments
> on the same are highly appreciated.

On systems like unix, malloc is not part of the OS; users can and do freely
substitute alternatives to libc. The OS memory manager is brk, mmap, etc.

--
Damn the living - It's a lovely life. I'm whoever you want me to be.
Silver silverware - Where is the love? At least I can stay in character.
Oval swimming pool - Where is the love? Annoying Usenet one post at a time.
Damn the living - It's a lovely life. In 1492....

cr88192

5/17/2011 9:08:00 PM

On 5/17/2011 12:39 PM, Pushpa wrote:
> Hi all,
>
> Many users claim that malloc() and free() provided by the language
> library results in considerable
> amount of overhead in terms of calling the same. Can we really
> eliminate overhead by using
> used defined functions/user defined memory manager. Is there any
> significant advantage in providing user defined malloc() and free(). I
> want to exclude realtime systems or embedded systems which are memory
> constrained here.
> I am talking about general purpose applications. With a user defined
> memory manager can it handle
> memory allocation and de-allocation in a much better way than what OS
> would have done. Any inputs/comments
> on the same are highly appreciated.
>

it actually really depends...

if one doesn't have a good grasp on what they are doing, then a custom
allocator is usually a good deal worse than the native malloc()/free()
WRT overhead and/or performance.

however, special purpose allocators can do well for certain tasks, such
as being faster, or being more compact for tiny objects, but usually
there are trade-offs.

the main reason, in my case, I do a custom allocator is mostly for:
1, I use GC (often both a friend and an enemy at times);
2, I use dynamic typing, and dynamic type-checking and malloc are not
friends;
3, my heap tends to often be dominated by small objects (and so certain
special-cases, such as "cons cells" have special handling, and certain
other special types are not even in addressable memory, as the pointer
itself encodes the value);
....

for example: cons cells are 8 bytes on x86 (they only ever hold 2
pointers), so it makes sense not to waste extra bytes on things like
having a header or padding the object to a multiple of 16 bytes.

also, they can easily end up (in certain types of app, such as those
making lots of use of list-processing) being the single most common
data-type on the heap.

a secondary common data-type is strings, which if one is using
interned/immutable strings, then having compact storage (such as
byte-aligned string tables) may make a good amount of sense (as strings
are also one of those things which can easily eat *lots* of memory,
hence my personal belief that UTF-16 is rarely a sensible option vs
UTF-8 or similar). granted, in other cases, it also makes sense to have
strings in a form where they may either be mutable or are subject to
being freed (it does not make sense to intern character buffers or large
one-off strings, for example...).

but, the custom MM/GC is mostly for GC and dynamic type-checking, rather
than to try to save bytes or be faster (although it may do this in
certain cases).

but, if I were just doing "generic" stuff, then malloc would probably be
fine, and simply trying to use a custom malloc as some perceived way to
make allocating/freeing structs or arrays faster (or save a few bytes)
is, IMO, a clear case of premature optimization...

or such...

Lauri Alanko

5/18/2011 12:50:00 AM

I don't think there is very often need to shun the standard allocator
for performance reasons. Production malloc implementations are quite
mature and have reasonably good performance for the most common
scenarios.

It's worth noting that whenever you allocate and free some memory, you
are also likely to _do_ something with that memory, possibly quite a
lot. The performance overhead of malloc and free may often be
negligible compared to the actual computation that is done using the
memory.

Yet still, I can see some reasons for preferring custom allocators.

One is space efficiency. Because free() is not passed the size of the
object being freed, the allocator must somehow store this information,
and this may result in space overhead (depending on implementation
details). In particular, if you allocate a large number of very small
objects, the bookkeeping overhead may be significant. A custom
allocator can be written so that the size of an object need not be
stored in memory, if it can be known statically.

The other reason is to improve the quality of the code. Explicit calls
to free() for every allocated object can be tedious to write and it is
easy to get them wrong, resulting in memory leaks or duplicate frees
or whatnot. With a memory pool -based allocator, you don't need to
free every object individually, but instead you just free an entire
pool, along with all the objects allocated from that pool. This style
fits many programs, and it results in code that is cleaner (less
free()-calls sprinkled everywhere) and more correct (you can't
accidentally forget to free a single object).

Of course, sometimes this may not be enough and you may instead need
reference counting or even actual tracing garbage collection. But
again, using more specialized memory allocation systems should be
motivated by the structure of your programs, not by performance
reasons.

Lauri

Eric Sosman

5/18/2011 1:21:00 AM

On 5/17/2011 3:39 PM, Pushpa wrote:
> Hi all,
>
> Many users claim that malloc() and free() provided by the language
> library results in considerable
> amount of overhead in terms of calling the same.

Ah, yes, that well-known and reputable authority "many users."
Almost as reliable as "I've heard" and "some say," nearly as
infallible as "it seems." Well, I've heard that some of these
many users say it seems the Moon is made of green cheese, but even
so I'm not planning to head skyward with my Roquefort dressing
recipe.

If you can produce a claim that has substance, we'll perhaps
have something worth talking about. But if all you can come up
with is "many users" and "considerable," well, ...

> Can we really
> eliminate overhead by using
> used defined functions/user defined memory manager.

No. Since any memory manager, no matter by whom it is written
or with what design principles, will have some overhead, it follows
that the only way to eliminate overhead is to use no memory manager.

> Is there any
> significant advantage in providing user defined malloc() and free().

No. In fact, the attempt to do so yields undefined behavior.

Providing custom-written work-alikes for malloc() et al. may be
beneficial, *if* (1) you have information not available to the
implementors of the "stock" version(s), and (2) you are able to make
effective use of that extra information. Or, of course, if (3) you
are lots smarter than the stock implementors. (This is in fact a
possibility. I recall a vendor whose malloc() was essentially a
copy of the toy implementation in K&R. K&R's version was just fine
for the 64-256K memory spaces of the computers it ran on, but had
one or two teeny-tiny scalability problems with memories four
thousand times bigger...)

> I am talking about general purpose applications. With a user defined
> memory manager can it handle
> memory allocation and de-allocation in a much better way than what OS
> would have done. Any inputs/comments
> on the same are highly appreciated.

Content-free questions get content-free answers. Be more specific.

--
Eric Sosman
esosman@ieee-dot-org.invalid

Michael Press

5/18/2011 2:49:00 AM

In article <iquo8p$if4$1@news.albasani.net>, BGB <cr88192@hotmail.com>
wrote:

> On 5/17/2011 12:39 PM, Pushpa wrote:
> > Hi all,
> >
> > Many users claim that malloc() and free() provided by the language
> > library results in considerable
> > amount of overhead in terms of calling the same. Can we really
> > eliminate overhead by using
> > used defined functions/user defined memory manager. Is there any
> > significant advantage in providing user defined malloc() and free(). I
> > want to exclude realtime systems or embedded systems which are memory
> > constrained here.
> > I am talking about general purpose applications. With a user defined
> > memory manager can it handle
> > memory allocation and de-allocation in a much better way than what OS
> > would have done. Any inputs/comments
> > on the same are highly appreciated.
> >
>
> it actually really depends...
>
> if one doesn't have a good grasp on what they are doing, then a custom
> allocator is usually a good deal worse than the native malloc()/free()
> WRT overhead and/or performance.
>
> however, special purpose allocators can do well for certain tasks, such
> as being faster, or being more compact for tiny objects, but usually
> there are trade-offs.
>
>
> the main reason, in my case, I do a custom allocator is mostly for:
> 1, I use GC (often both a friend and an enemy at times);
> 2, I use dynamic typing, and dynamic type-checking and malloc are not
> friends;
> 3, my heap tends to often be dominated by small objects (and so certain
> special-cases, such as "cons cells" have special handling, and certain
> other special types are not even in addressable memory, as the pointer
> itself encodes the value);
> ...
>
> for example: cons cells are 8 bytes on x86 (they only ever hold 2
> pointers), so it makes sense not to waste extra bytes on things like
> having a header or padding the object to a multiple of 16 bytes.
>
> also, they can easily end up (in certain types of app, such as those
> making lots of use of list-processing) being the single most common
> data-type on the heap.
>
> a secondary common data-type is strings, which if one is using
> interned/immutable strings, then having compact storage (such as
> byte-aligned string tables) may make a good amount of sense (as strings
> are also one of those things which can easily eat *lots* of memory,
> hence my personal belief that UTF-16 is rarely a sensible option vs
> UTF-8 or similar). granted, in other cases, it also makes sense to have
> strings in a form where they may either be mutable or are subject to
> being freed (it does not make sense to intern character buffers or large
> one-off strings, for example...).
>
> but, the custom MM/GC is mostly for GC and dynamic type-checking, rather
> than to try to save bytes or be faster (although it may do this in
> certain cases).
>
>
> but, if I were just doing "generic" stuff, then malloc would probably be
> fine, and simply trying to use a custom malloc as some perceived way to
> make allocating/freeing structs or arrays faster (or save a few bytes)
> is, IMO, a clear case of premature optimization...
>
>
> or such...

It is difficult to impossible to fully understand
your prose unless the reader already knows this stuff;
and you are responding to somebody who does not know.
The impediments to understanding are the ellipses.
Every ellipsis makes the reader stop and try to
extrapolate what you leave unsaid.

--
Michael Press

John Doe

5/18/2011 6:08:00 AM

On Tue, 17 May 2011 19:39:15 +0000, Pushpa wrote:

> Many users claim that malloc() and free() provided by the language
> library results in considerable amount of overhead in terms of calling
> the same. Can we really eliminate overhead by using used defined
> functions/user defined memory manager. Is there any significant
> advantage in providing user defined malloc() and free(). I want to
> exclude realtime systems or embedded systems which are memory
> constrained here.
> I am talking about general purpose applications. With a user defined
> memory manager can it handle memory allocation and de-allocation in a
> much better way than what OS would have done. Any inputs/comments
> on the same are highly appreciated.

First, malloc() isn't part of the OS; it's part of the standard C library.
The application typically obtains memory from the OS as entire pages, via
e.g. sbrk() or mmap().

The efficiency problems with malloc() don't lie with a specific
implementation but with the interface. The application doesn't tell
malloc() anything beyond the amount of memory required. A custom allocator
can offer the application either more or less control, either of which may
translate to improved performance. E.g.

1. An allocator for objects of a specific size may be much simpler (and
thus faster) than a general-purpose allocator. The downside is that once
the allocator has claimed memory for its heap, any memory returned to that
heap may only be usable for subsequent allocations from that heap;
fragmentation may make it impossible to return memory to the global heap
or to the OS.

2. An allocator which allows the caller to provide additional information
about the nature of the data may be able to allocate memory for "related"
blocks in the same page, reducing the probability of cache misses at the
cost of making allocation and deallocation slower.

3. If the application can predict the lifetime of the data in advance, the
allocator can avoid allocating long-lived blocks around a short-lived
block, reducing heap fragmentation. In the extreme case, the heap becomes
a stack, with no fragmentation at all.

4. If the application can tolerate the data being moved after allocation,
heap fragmentation can be eliminated.

Bartc

5/18/2011 11:05:00 AM

"Ben Pfaff" <blp@cs.stanford.edu> wrote in message
news:87aael3xw1.fsf@blp.benpfaff.org...
> Pushpa <pushpa@nospam.invalid> writes:
>
>> Many users claim that malloc() and free() provided by the language
>> library results in considerable
>> amount of overhead in terms of calling the same. Can we really
>> eliminate overhead by using
>> used defined functions/user defined memory manager. Is there any
>> significant advantage in providing user defined malloc() and
>> free().
>
> According to an academic study I read some time ago, there is
> rarely any significant advantage to special-purpose memory
> allocators. In a quick online search, I didn't find a reference
> to this paper, but perhaps someone else here has a copy of it.

I've just done a test where allocating and freeing large numbers of 4-byte
blocks took twenty times longer using malloc/free (and probably took 2-4
times as much space) than using a special allocator.

How significant this is depends on the application, but I don't think you
can just dismiss such an allocator.

--
Bartc

Pushpa

5/18/2011 5:12:00 PM

BartC writes:
> "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
> news:87aael3xw1.fsf@blp.benpfaff.org...
>> Pushpa <pushpa@nospam.invalid> writes:
>>
>>> Many users claim that malloc() and free() provided by the language
>>> library results in considerable
>>> amount of overhead in terms of calling the same. Can we really
>>> eliminate overhead by using
>>> used defined functions/user defined memory manager. Is there any
>>> significant advantage in providing user defined malloc() and free().
>>
>> According to an academic study I read some time ago, there is rarely
>> any significant advantage to special-purpose memory allocators. In a
>> quick online search, I didn't find a reference to this paper, but
>> perhaps someone else here has a copy of it.
>
> I've just done a test where allocating and freeing large numbers of
> 4-byte blocks took twenty times longer using malloc/free (and probably
> took 2-4 times as much space) than using a special allocator.
>
> How significant this is depends on the application, but I don't think
> you can just dismiss such an allocator.

Bartc: Are you sure of this? What I really wanted to ask: Is it
reasonable to plan for saving 50% of memory allocation time by rewriting
special functions for same ? If speedup can be 20X this is amazing.

Kind Regards
Pushpa

comp.lang.c

Malloc Query

Pushpa

blp

Joe Pfeiffer

China Blue Veins

cr88192

Lauri Alanko

Eric Sosman

Michael Press

John Doe

Bartc

Pushpa

x Login to ForumsZone