«

+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?

On 2009-12-30, <> wrote:
> 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
--
Copyright 2009, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

writes:
> 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?)

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

On Dec 30, 4:18*am, dgoodman...@gmail.com wrote:
> +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.

<> wrote in message
news:hhed8o$s3r$...
> +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.

--
Bartc

On Dec 30, 2:45*pm, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:
> > 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
>
> 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.

+AMDG

bartc <> wrote:
> 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.

On Dec 30, 2:45*pm, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:
> > 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
>
> 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.

On Dec 30, 2:45*pm, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:
> > 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
>
> 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.

On 12/29/2009 9:18 PM, wrote:
> +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).

--
Eric Sosman
lid