malloc() execution time?

Discussion in 'C Programming' started by dgoodmaniii@gmail.com, Dec 30, 2009.

  1. Guest

    +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?
    , Dec 30, 2009
    #1
    1. Advertising

  2. Seebs Guest

    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 /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    Seebs, Dec 30, 2009
    #2
    1. Advertising

  3. 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) <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"
    Keith Thompson, Dec 30, 2009
    #3
  4. On Dec 30, 4:18 am, 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.
    Michael Foukarakis, Dec 30, 2009
    #4
  5. bartc Guest

    <> wrote in message
    news:hhed8o$s3r$-september.org...
    > +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
    bartc, Dec 30, 2009
    #5
  6. On Dec 30, 2:45 pm, "christian.bau" <>
    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.
    Michael Foukarakis, Dec 30, 2009
    #6
  7. Guest

    +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.
    , Dec 30, 2009
    #7
  8. On Dec 30, 2:45 pm, "christian.bau" <>
    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.
    Michael Foukarakis, Dec 30, 2009
    #8
  9. On Dec 30, 2:45 pm, "christian.bau" <>
    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.
    Michael Foukarakis, Dec 30, 2009
    #9
  10. Eric Sosman Guest

    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
    Eric Sosman, Dec 30, 2009
    #10
  11. writes:
    [...]
    > 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.

    --
    Keith Thompson (The_Other_Keith) <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"
    Keith Thompson, Dec 30, 2009
    #11
  12. Kaz Kylheku Guest

    On 2009-12-30, <> wrote:
    > 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, Dec 31, 2009
    #12
  13. Kaz Kylheku Guest

    On 2009-12-31, Kaz Kylheku <> wrote:
    > On 2009-12-30, <> wrote:
    >> 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.


    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.
    Kaz Kylheku, Dec 31, 2009
    #13
  14. Nobody Guest

    On Wed, 30 Dec 2009 02:18:00 +0000, dgoodmaniii wrote:

    > 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.
    Nobody, Dec 31, 2009
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John
    Replies:
    13
    Views:
    699
  2. ravi
    Replies:
    0
    Views:
    450
  3. Peter
    Replies:
    34
    Views:
    1,936
    Richard Tobin
    Oct 22, 2004
  4. porting non-malloc code to malloc

    , Feb 18, 2005, in forum: C Programming
    Replies:
    3
    Views:
    479
    Walter Roberson
    Feb 19, 2005
  5. Johs32

    to malloc or not to malloc??

    Johs32, Mar 30, 2006, in forum: C Programming
    Replies:
    4
    Views:
    320
    Captain Winston
    Mar 30, 2006
Loading...

Share This Page