malloc() efficiency 
Author Message
 malloc() efficiency

I'm writing a text manipulation program, and I've used malloc
extensively.

Is there an efficiency penalty for using malloc(), versus using arrays
declared on the stack?

I like malloc(), because that way I don't have to know the size of the
array in advance.  Is there a school of thought that says "you're much
better off just allocating a huge array than using malloc()"?

I'm not interested in the issue of programming mistakes, which I know
can multiply when using pointers, malloc(), and free().

Best wishes,

sjfromm



Fri, 01 Apr 2005 21:21:16 GMT  
 malloc() efficiency

Quote:
> Is there an efficiency penalty for using malloc(), versus using arrays
> declared on the stack?

Mu.

We cannot possibly tell; it depends on factors depending on system load,
buffer size, operating system, compiler version, and phase of the moon.
The only way to be sure is to compile both versions, and measure.

Don't be surprised if the difference turns out to be underwhelming.

Richard



Fri, 01 Apr 2005 21:27:20 GMT  
 malloc() efficiency


Quote:
> I'm writing a text manipulation program, and I've used malloc
> extensively.

> Is there an efficiency penalty for using malloc(), versus using arrays
> declared on the stack?

This really depends on the implementation at some level. Usually, malloc()
is known for memory fragmentation over time which may lead to long search
times for new block allocations. But I do not think the ISO C standard
says anything about this. Some machines don't have a stack and emulate
one, others just put stack variables at fixed addresses for the program
lifetime. Again, ISO C says nothing about how stacks are implemented, I
don't recall a stack being required only that recursion must be supported.

I'm afraid you're on your own here unless you can find a newsgroup that
discusses your compiler.



Fri, 01 Apr 2005 21:38:21 GMT  
 malloc() efficiency



Quote:
> I'm writing a text manipulation program, and I've used malloc
> extensively.

> Is there an efficiency penalty for using malloc(), versus using arrays
> declared on the stack?

> I like malloc(), because that way I don't have to know the size of the
> array in advance.  Is there a school of thought that says "you're much
> better off just allocating a huge array than using malloc()"?

> I'm not interested in the issue of programming mistakes, which I know
> can multiply when using pointers, malloc(), and free().

> Best wishes,

> sjfromm

I know it's not ANSI C, but my compiler has a runtime option for tuning  the
heap and stack sizes.

  #pragma runopts(STACK(8K,4K,ANY,FREE),HEAP(4K,4K,ANY,FREE))



Fri, 01 Apr 2005 21:10:54 GMT  
 malloc() efficiency

Quote:

> I'm writing a text manipulation program, and I've used malloc
> extensively.

> Is there an efficiency penalty for using malloc(), versus using arrays
> declared on the stack?

Probably, although the C standard says nothing on the subject.

Quote:

> I like malloc(), because that way I don't have to know the size of the
> array in advance.

Yes, that's why I like it, too.

Quote:
> Is there a school of thought that says "you're much
> better off just allocating a huge array than using malloc()"?

Possibly, but you needn't pay too much attention to that. No matter how
huge you make your array, there'll come a day when it ain't big enough,
and you'll wish you'd used malloc to start off with - so you might as
well use it at the outset.

Quote:

> I'm not interested in the issue of programming mistakes,

To quote Yoda - "You will be... you will be!"

Quote:
> which I know
> can multiply when using pointers, malloc(), and free().

Yes, they can, unless you're careful. I presume you're careful. :-)

--

"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton



Sat, 02 Apr 2005 00:05:02 GMT  
 malloc() efficiency

Quote:


> > Is there an efficiency penalty for using malloc(), versus using
> > arrays declared on the stack?

> We cannot possibly tell; it depends on factors depending on system
> load, buffer size, operating system, compiler version, and phase
> of the moon. The only way to be sure is to compile both versions,
> and measure.

> Don't be surprised if the difference turns out to be underwhelming.

In general malloc usually involves at least a function call, while
local allocation may well not.  So I would be very surprised to
find any system anywhere that had improved runtime using malloc as
opposed to local allocation.  At the same time I would be
surprised to find a system where the loss of efficiency was
significant.

The places I have found problems are with free() when the count of
allocated items is high.  The MSCRT and DJGPP libraries are very
bad with this, and I have "taken steps" to improve the DJGPP
system.  This is a QOI matter, and really off topic here.

You can thrash your system with my hashlib.zip, available on my
site.  It is in standard C so should run anywhere.  In fact I
discovered the QOI problems during development.

--

   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!



Sat, 02 Apr 2005 01:06:37 GMT  
 malloc() efficiency
[snip]

Quote:
> > I like malloc(), because that way I don't have to know the size of the
> > array in advance.

> Yes, that's why I like it, too.

> > Is there a school of thought that says "you're much
> > better off just allocating a huge array than using malloc()"?

> Possibly, but you needn't pay too much attention to that. No matter how
> huge you make your array, there'll come a day when it ain't big enough,
> and you'll wish you'd used malloc to start off with - so you might as
> well use it at the outset.

Right.  That's why I made the post; I wanted to know if there are any
downsides.

Of course, there are some obvious downsides---increased use of
pointers, plus extra care needed to free() things, etc.

Quote:
> > I'm not interested in the issue of programming mistakes,

> To quote Yoda - "You will be... you will be!"

Right.  All I intended was narrowing the scope of discussion.  I've
certainly had my share of mistakes with pointers.

Quote:
> > which I know
> > can multiply when using pointers, malloc(), and free().

> Yes, they can, unless you're careful. I presume you're careful. :-)

Trying to be...

Best,

sjfromm



Sat, 02 Apr 2005 09:09:10 GMT  
 malloc() efficiency

Quote:

> I'm writing a text manipulation program, and I've used malloc
> extensively.

> Is there an efficiency penalty for using malloc(), versus using arrays
> declared on the stack?

> I like malloc(), because that way I don't have to know the size of the
> array in advance.  Is there a school of thought that says "you're much
> better off just allocating a huge array than using malloc()"?

> I'm not interested in the issue of programming mistakes, which I know
> can multiply when using pointers, malloc(), and free().

Depends on your compiler.  The malloc() library that ships with a lot of
compilers/systems can be pretty lousy.  On the other hand, there are
commercial products that offer high-performance repalcement malloc()
libraries which work very well.

Whether you need an optimized malloc() library, of course, will depend
on your code.

Personally, I'd design the code with malloc().  Then profile it.  If it
turns out that malloc() is a significant bottleneck, then you can look
into a replacement malloc() library, or tuning your code so as to not
use the library as much.

-- David



Sat, 02 Apr 2005 12:52:06 GMT  
 malloc() efficiency

Quote:


> [snip]
> > > I like malloc(), because that way I don't have to know the size of the
> > > array in advance.

> > Yes, that's why I like it, too.

> > > Is there a school of thought that says "you're much
> > > better off just allocating a huge array than using malloc()"?

> > Possibly, but you needn't pay too much attention to that. No matter how
> > huge you make your array, there'll come a day when it ain't big enough,
> > and you'll wish you'd used malloc to start off with - so you might as
> > well use it at the outset.

> Right.  That's why I made the post; I wanted to know if there are any
> downsides.

> Of course, there are some obvious downsides---increased use of
> pointers, plus extra care needed to free() things, etc.

Yes, and that's just about it for downsides [1], although I'm not
convinced that increased use of pointers is a downside - I think it's
more liberating than anything. The comp.lang.c "party line" (if there is
such a thing) is generally pro-malloc, so there probably isn't too much
point in your waiting a long time for other responses.

[1] If you push them hard enough, clc will find downsides to just about
anything, up to and including the Second Coming.

--

"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton



Sat, 02 Apr 2005 14:05:22 GMT  
 malloc() efficiency


 > I'm writing a text manipulation program, and I've used malloc
 > extensively.

 > Is there an efficiency penalty for using malloc(), versus using arrays
 > declared on the stack?

It can be a little slower, since malloc has to take care of fragmentation,
can fall back to a system call like brk (or an RPC in some OSes).

 > I like malloc(), because that way I don't have to know the size of the
 > array in advance.  Is there a school of thought that says "you're much
 > better off just allocating a huge array than using malloc()"?

I advise you to use malloc anyway for many reasons:
* memory is often more precious than CPU is, so saving a tiny bit of CPU for
  wasting memory isn't very wise
* using static buffer on the stack is way that often leads to buffer overflows
* by using static buffers, you have to fix a maximal size of your array, and
  this isn't always possible
* it's just a bad habbit that leads many programes to use things such as
  PATH_MAX or MAXPATHLEN, who are explicity said as being optionnaly by the
  POSIX spec, and doesn't exist on some systems (like the GNU system).

So, I advise you to use malloc, free and realloc; and never count on static,
hard-coded limits (and to avoid using and setting them as much as possible).

--

GSM         : 06.71.47.18.22 (in France)   ICQ UIN   : 7299959
Fingerprint : 1F2C 9804 7505 79DF 95E6 7323 B66B F67B 7103 C5DA

Member of HurdFr: http://hurdfr.org - The GNU Hurd: http://hurd.gnu.org



Sat, 02 Apr 2005 16:08:31 GMT  
 malloc() efficiency

<snip>

Quote:
> > > which I know
> > > can multiply when using pointers, malloc(), and free().

> > Yes, they can, unless you're careful. I presume you're careful. :-)

> Trying to be...

Hi Stephen,

I assume you know about dmalloc (http://dmalloc.com).

Also found this site - quite interesting:
http://www.cs.colorado.edu/~zorn/Malloc.html

Incidentally - a question open to anyone: if I were to write a C
application that required the fastest memory allocation algorithms in
the industry, which one do I choose?

Mark.



Sat, 02 Apr 2005 18:30:35 GMT  
 malloc() efficiency

Quote:
> > > > I like malloc(), because that way I don't have to know the size of
the
> > > > array in advance.

> > > Yes, that's why I like it, too.

> > > > Is there a school of thought that says "you're much
> > > > better off just allocating a huge array than using malloc()"?

> > > Possibly, but you needn't pay too much attention to that. No matter
how
> > > huge you make your array, there'll come a day when it ain't big
enough,
> > > and you'll wish you'd used malloc to start off with - so you might as
> > > well use it at the outset.

> > Right.  That's why I made the post; I wanted to know if there are any
> > downsides.

> > Of course, there are some obvious downsides---increased use of
> > pointers, plus extra care needed to free() things, etc.

> Yes, and that's just about it for downsides [1], although I'm not
> convinced that increased use of pointers is a downside - I think it's
> more liberating than anything. The comp.lang.c "party line" (if there is
> such a thing) is generally pro-malloc, so there probably isn't too much
> point in your waiting a long time for other responses.

I use malloc for dynamic arrays, automatic memory when I know the bounds and
it's not to large. I'm not an experienced C programmer, but I thought it
made sense.

If it's the status quo to use malloc for large arrays, then what is
considered large ?

I'm always prepared to tow the party line.



Sat, 02 Apr 2005 20:03:25 GMT  
 malloc() efficiency

Quote:

<snip>

> I use malloc for dynamic arrays, automatic memory when I know the bounds and
> it's not to large. I'm not an experienced C programmer, but I thought it
> made sense.

And indeed it does.

Quote:

> If it's the status quo to use malloc for large arrays, then what is
> considered large ?

Mu. ;-)  There's no good answer to your question (IMHO).

Quote:
> I'm always prepared to tow the party line.

Well, I agree that it does make sense to take advantage of other
people's experience in such matters. In this case, I'm not aware of a
clc "party line" to toe, so it's a question of doing what seems
appropriate at the time. My own personal rule of thumb is: "if in doubt,
use malloc".

--

"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton



Sat, 02 Apr 2005 22:39:00 GMT  
 malloc() efficiency

Quote:

> > I'm always prepared to tow the party line.

> Well, I agree that it does make sense to take advantage of other
> people's experience in such matters. In this case, I'm not aware of a
> clc "party line" to toe, so it's a question of doing what seems
> appropriate at the time. My own personal rule of thumb is: "if in doubt,
> use malloc".

I apologise for my poor spelling. I blame Margaret Thatcher for stopping the
free milk in the infants.


Sat, 02 Apr 2005 23:32:37 GMT  
 malloc() efficiency

Quote:
> I'm writing a text manipulation program, and I've used malloc
> extensively.

> Is there an efficiency penalty for using malloc(), versus using arrays
> declared on the stack?

> I like malloc(), because that way I don't have to know the size of the
> array in advance.  Is there a school of thought that says "you're much
> better off just allocating a huge array than using malloc()"?

Dynamic allocation is useful not only when you don't know the size or
quantity of data in advance, but when the duration of an object is
nontrivial, as in: cannot be connected to the duration of a lexical
scope.

In cases when it's clear that an object need not endure longer than
the block in which it was created, automatic allocation can be used
instead. In the C99 language, not knowing the size in advance is not
necessarily a barrier to the use of automatic allocation, because this
new C language has variable length arrays. In C99, you need not use
dynamic allocation for variable sized data that lives and dies within
a single block invocation---but of course, automatic storage might be
a precious resource in some given target environment, and there is no
standard way to recover from its exhaustion.

Indeed it's quite possible, or even likely, that automatic allocation
is more efficient (faster) than malloc. A typical implementation
simply has to move a frame pointer to reserve the space. In the case
of fixed-size data, that increment can be known at compile time: space
for the information required to return from a function, and its
automatic variables, can be reserved in one operation, so there is
little or no additional cost for additional local variables.
Liberating the storage is simply the opposite operation; restoring
some frame pointer or such thing. There is no management of free
lists, coalescing adjacent free blocks, which are typical things that
dynamic allocators have to do.

But it's entirely possible that dynamic allocation is used for
automatic storage. One can envision a ``safe C'' in which automatic
storage is dynamically allocated and subject to garbage collection, so
that for instance returning the address of a local variable is made
safe, as a conforming language extension. So obviously the performance
tradeoffs will be different on such an {*filter*} implementation.



Sun, 03 Apr 2005 06:33:45 GMT  
 
 [ 16 post ]  Go to page: [1] [2]

 Relevant Pages 

1. malloc efficiency considerations

2. Malloc 2: The revenge of Malloc

3. malloc vs 'no-malloc' - help

4. C question : redefining a new malloc() calling standard malloc()

5. to malloc() or not to malloc(), that is the question

6. malloc crashes - malloc(256) returns 0(!) (_MT)

7. Multithreading - efficiency question

8. C# vs resource efficiency

9. Efficiency issues from VC++6.0 to VC++.NET

10. switch statement efficiency

11. : code efficiency

12. switch statement efficiency

 

 
Powered by phpBB® Forum Software