malloc() execution time?

[dgoodmaniii]

+AMDG

I have a question about execution speed between allocating
storage dynamically with malloc() and doing so statically
with arrays. Which is faster?

I've finished with K&R's Exercise 5-7, which asks to rewrite
a program sorting character arrays with qsort to use an
array for storage rather than calling alloc() (I used
malloc() from stdlib, just for the exercise), and asks, "How
much faster is the program?" I inferred from this that the
array version should be faster than malloc(). My admittedly
novice intuition leads me to the same conclusion.

However, when running the version with malloc() through
standard Linux time (on Debian GNU/Linux, kernel 2.6.26, on
an x86_64 processor), I got the following results for the
malloc() version:
*******
real: 0m0.029s
user: 0m0.024s
sys: 0m0.004s
*******
And the following results with the array version:
*******
real: 0m0.043s
user: 0m0.020s
sys: 0m0.020s
*******
In other words, the malloc() version ran faster. Both were
run on the same file, of course, which was of almost the
maximum size permitted by the program (4999 lines).

I'm not going to post the programs themselves, unless you
all tell me it's necessary to answer the question. But is
this the behavior one would expect?

 

[Seebs]

I have a question about execution speed between allocating
storage dynamically with malloc() and doing so statically
with arrays. Which is faster?

Why is a duck?

Basically, uhm. There's no guaranteed/universal answer. You can
easily create special cases for either, depending on the platform.
I know of at least one case on at least one platform where allocating
a really large chunk of space with malloc/calloc, then not using most
of it, is MUCH faster than allocating an array of the same size.

I'm not going to post the programs themselves, unless you
all tell me it's necessary to answer the question. But is
this the behavior one would expect?

Long story short, there is no definite answer. Typically, probably, you'll
find that malloc has more overhead in most cases... But not necessarily
in all, and the overhead is usually completely trivial compared to the
computation you're doing.

-s

 

[Keith Thompson]

I have a question about execution speed between allocating
storage dynamically with malloc() and doing so statically
with arrays. Which is faster?

I've finished with K&R's Exercise 5-7, which asks to rewrite
a program sorting character arrays with qsort to use an
array for storage rather than calling alloc() (I used
malloc() from stdlib, just for the exercise), and asks, "How
much faster is the program?" I inferred from this that the
array version should be faster than malloc(). My admittedly
novice intuition leads me to the same conclusion.

However, when running the version with malloc() through
standard Linux time (on Debian GNU/Linux, kernel 2.6.26, on
an x86_64 processor), I got the following results for the
malloc() version:
*******
real: 0m0.029s
user: 0m0.024s
sys: 0m0.004s
*******
And the following results with the array version:
*******
real: 0m0.043s
user: 0m0.020s
sys: 0m0.020s
*******
In other words, the malloc() version ran faster. Both were
run on the same file, of course, which was of almost the
maximum size permitted by the program (4999 lines).

I'm not going to post the programs themselves, unless you
all tell me it's necessary to answer the question. But is
this the behavior one would expect?

It might help to post the programs. There's no definitive answer,
since the C standard says nothing about performance, but if we can see
the code we might be able to provide some hints.

One interesting thing about the performance numbers you posted: The
array version appears to use less user time (20 ms vs. 24 ms), but the
malloc version uses *much* less system time (4 ms vs. 20 ms).

Also, the times you quote are fairly small, and subject to random
variations. If you modify both programs to repeat, say, 1000 times,
you might get better information.

(You confirmed that they both produce the same output, right?)

 

[Michael Foukarakis]

+AMDG

I have a question about execution speed between allocating
storage dynamically with malloc() and doing so statically
with arrays.  Which is faster?

I've finished with K&R's Exercise 5-7, which asks to rewrite
a program sorting character arrays with qsort to use an
array for storage rather than calling alloc() (I used
malloc() from stdlib, just for the exercise), and asks, "How
much faster is the program?"  I inferred from this that the
array version should be faster than malloc().  My admittedly
novice intuition leads me to the same conclusion.

However, when running the version with malloc() through
standard Linux time (on Debian GNU/Linux, kernel 2.6.26, on
an x86_64 processor), I got the following results for the
malloc() version:
*******
real:  0m0.029s
user:  0m0.024s
sys:   0m0.004s
*******
And the following results with the array version:
*******
real:  0m0.043s
user:  0m0.020s
sys:   0m0.020s
*******
In other words, the malloc() version ran faster.  Both were
run on the same file, of course, which was of almost the
maximum size permitted by the program (4999 lines).

I assume those results were from only one execution of 'time ./
yourprog', right? It'd be much more helpful to run several iterations,
and provide a mean and std deviation...another way of timing
(gettimeofday etc.) would be preferable, too.

 

[bartc]

+AMDG

I have a question about execution speed between allocating
storage dynamically with malloc() and doing so statically
with arrays. Which is faster?

I've finished with K&R's Exercise 5-7, which asks to rewrite
a program sorting character arrays with qsort to use an
array for storage rather than calling alloc() (I used
malloc() from stdlib, just for the exercise), and asks, "How
much faster is the program?" I inferred from this that the
array version should be faster than malloc(). My admittedly
novice intuition leads me to the same conclusion.

However, when running the version with malloc() through
standard Linux time (on Debian GNU/Linux, kernel 2.6.26, on
an x86_64 processor), I got the following results for the
malloc() version:
*******
real: 0m0.029s
user: 0m0.024s
sys: 0m0.004s
*******
And the following results with the array version:
*******
real: 0m0.043s
user: 0m0.020s
sys: 0m0.020s
*******
In other words, the malloc() version ran faster. Both were
run on the same file, of course, which was of almost the
maximum size permitted by the program (4999 lines).

(Why didn't you just change the MAXLINES value; 5000 lines was a big deal
when K&R came out, but not any more.)

Usually you don't have a choice between static and dynamic allocation,
because you don't know the sizes needed at compile time, or you have arrays
of different-sized elements or whatever.

But malloc does have an overhead associated with it (and sometimes a small
extra overhead when accessing the data). The signficance depends on how much
work is going to be done with the allocated block.

You say your static array was slower, which is unexpected, but then we can't
see the code; something you're doing is slowing things down: presumably
you're setting a maximum line length and having an array of those. This can
cause the data to be more spread out, usually a bad thing. Or maybe you're
copying the maximum characters in each line rather than what is actually
used.

 

[Michael Foukarakis]

Completely meaningless numbers. It is just plain ridiculous to compare
the execution time of two programs that each run for less than 50
milliseconds.

Not meaningless. Insufficient. Be more constructive with your feedback.

 

[dgoodmaniii]

+AMDG

But malloc does have an overhead associated with it (and
sometimes a small extra overhead when accessing the data).
The signficance depends on how much work is going to be
done with the allocated block.

Well, that probably explains it. I do very little with the
allocated blocks; I just switch around some pointers to each
and then print them out. The sorting is precisely the same
in both versions (just pointer-juggling); all I did was
change the storage.

You say your static array was slower, which is unexpected,
but then we can't see the code; something you're doing is
slowing things down: presumably you're setting a maximum
line length and having an array of those. This can cause
the data to be more spread out, usually a bad thing. Or
maybe you're copying the maximum characters in each line
rather than what is actually used.

I've gone over the code and am pretty certain that I'm not
copying the maximum characters, but rather only those that
are used. However, I am setting a maximum line length and
having an array of those.

Thanks for all your responses; I'm happy with the notion
that while you'd normally expect malloc to be slower, it
won't always be. I was just quite surprised by it.

 

[Michael Foukarakis]

Completely meaningless numbers. It is just plain ridiculous to compare
the execution time of two programs that each run for less than 50
milliseconds.

Not meaningless. Insufficient. Be more constructive with your feedback.

 

[Michael Foukarakis]

Completely meaningless numbers. It is just plain ridiculous to compare
the execution time of two programs that each run for less than 50
milliseconds.

Not meaningless. Insufficient. Be more constructive with your feedback.

 

[Eric Sosman]

+AMDG

I have a question about execution speed between allocating
storage dynamically with malloc() and doing so statically
with arrays. Which is faster?

How long is a piece of string? [*]

Calling malloc() -- and perhaps free(), too -- will most
likely consume some execution time that a static allocation
would not incur. On the other hand, a large static allocation
might slow down the program's startup. Or not. Furthermore,
the trade-offs will be different on different C implementations.

My advice is that you not choose between allocation styles
(static, automatic, dynamic) because of speed, but make your
choice based on the "logical" needs of the program:

1) If you've got something whose size is known at compile
time, which needs to exist throughout all or most of
the program's execution, and of which you need exactly
one copy, static allocation is attractive.

2) If you've got something whose size is known at compile
time but whose use is associated with a particular
invocation of a function (that is, you only need it
while a function runs, and you need a fresh one for
each function call), automatic allocation is called for.

3) If you've got something whose size won't be known until
run-time, or which needs to be created in one function
call and persist after that function returns, use
dynamic allocation.

These aren't absolute rules, but useful guidelines. Since
you're in the process of learning C, I'd suggest you not worry
about the exceptions and corner cases just yet. Follow the
"rules" for the moment, but be aware that other considerations
(that you'll learn about later) may override them.

[*] Smart-aleck answer: strlen(piece).

 

[Keith Thompson]

I've gone over the code and am pretty certain that I'm not
copying the maximum characters, but rather only those that
are used. However, I am setting a maximum line length and
having an array of those.

You've gone over the code, but we haven't been able to. Please post
it.

Thanks for all your responses; I'm happy with the notion
that while you'd normally expect malloc to be slower, it
won't always be. I was just quite surprised by it.

There's probably a good reason for the difference in performance, but
we just don't have enough information to guess what it might be.

 

[Kaz Kylheku]

In other words, the malloc() version ran faster. Both were
run on the same file, of course, which was of almost the
maximum size permitted by the program (4999 lines).

Try aligning the string buffers carved from the array to at least
a four byte boundary.

 

[Kaz Kylheku]

Try aligning the string buffers carved from the array to at least
a four byte boundary.

Another thing.

Learn about the tool called ``oprofile'' and install it. It requires a
kernel module and some software tools.

A profiler can tell you where your program is spending its time. You
can find out out much percentage of your program's time is really spent
in malloc versus elsewhere.

 

[Nobody]

I have a question about execution speed between allocating
storage dynamically with malloc() and doing so statically
with arrays. Which is faster?

The latter. Of course, this isn't specified by the standard, but it's
almost invariably true in practice (the "almost" being that there will
always be obscure platforms which behave in a radically different matter
to the mainstream).

The absolute worst plausible case is that a static array *might* be as
slow as malloc(), but this is unlikely. It will typically be substantially
faster, particularly if the array isn't so large that it dominates the
process' memory consumption.