free() performance question

L

Lianjun Jiang

Hi,
In my code, I need to concat two buffer into one. I take following
steps:
1 malloc a new space
2 copy two buffers over,
3. and then free the originial two buffers.
I put timer on each step. And I found that under some stress
condition(cpu intensive, lots of memory used), the last step took a
lot more time than step 1 and 2. Did anyone know what could be the
reason?
 
K

Keith Thompson

Lianjun Jiang said:
In my code, I need to concat two buffer into one. I take following
steps:
1 malloc a new space
2 copy two buffers over,
3. and then free the originial two buffers.
I put timer on each step. And I found that under some stress
condition(cpu intensive, lots of memory used), the last step took a
lot more time than step 1 and 2. Did anyone know what could be the
reason?

It's extremely system-specific.

The C standard says absolutely nothing about the performance of malloc
and free (or of anything else, for that matter).

malloc and free have to manipulate whatever internal data structures
the implementation uses for memory allocation. It's possible that
malloc() merely has to find the first available free chunk of at least
the requested size, but free() has to do considerable work to
rearrange things (merging adjacent free chunks, updating statistics,
whatever) for future allocations. But that's pure speculation on my
part.
 
P

pandaj

It's extremely system-specific.

The C standard says absolutely nothing about the performance of malloc
and free (or of anything else, for that matter).

malloc and free have to manipulate whatever internal data structures
the implementation uses for memory allocation. It's possible that
malloc() merely has to find the first available free chunk of at least
the requested size, but free() has to do considerable work to
rearrange things (merging adjacent free chunks, updating statistics,
whatever) for future allocations. But that's pure speculation on my
part.

--
Keith Thompson (The_Other_Keith) (e-mail address removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

I'm using gcc-3.0.4, is there some documentation to check its "free"
implementation? Also this program is a multithread program. The buffer
freed in one thread is like to be allocated by another thread. Does it
matter?

Thanks
 
P

pandaj

I'm using gcc-3.0.4, is there some documentation to check its "free"
implementation? Also this program is a multithread program. The buffer
freed in one thread is like to be allocated by another thread. Does it
matter?

Thanks


I did the following test:

struct my_buf *tmp1, *tmp2;
{
MY_TIMER(timer1);

tmp1 = (struct my_buf*) malloc(sizeof(p1[0])*n1);
tmp2 = (struct my_buf*) malloc(sizeof(p2[0])*n2);
memcpy(tmp1, p1, sizeof(p1[0])*n1);
memcpy(tmp2, p2, sizeof(p2[0])*n2);
}
{
MY_TIMER(timer2);
free(p1);
free(p2);
}
{
MY_TIMER(timer3);
free(tmp1);
free(tmp2);
}

p1 and p2 are buffers allocated elsewhere and passed into the
function. In one test, timer1 report 0.003 ms, timer2 report 3.1 ms
and timer3 report 0.18 ms. So free definitely doing more work than
malloc in my case, but I still don't know why the free of foreign
buffers could take so much time than free "local" buffers.

Thanks
 
S

Spiros Bousbouras

Hi,
In my code, I need to concat two buffer into one. I take following
steps:
1 malloc a new space
2 copy two buffers over,
3. and then free the originial two buffers.
I put timer on each step. And I found that under some stress
condition(cpu intensive, lots of memory used), the last step took a
lot more time than step 1 and 2. Did anyone know what could be the
reason?

I have no idea why free takes a long time but one suggestion
is that you use realloc to make the first buffer large
enough to also fit the second buffer , then add the
second buffer to the end of the first and free the second.
Perhaps this will run faster.

Are you sure that the timer you're using is reliable ?
 
P

pandaj

I have no idea why free takes a long time but one suggestion
is that you use realloc to make the first buffer large
enough to also fit the second buffer , then add the
second buffer to the end of the first and free the second.
Perhaps this will run faster.

Are you sure that the timer you're using is reliable ?

At first, my implementation is using realloc, and then realloc takes
similar time as free. I think that is because realloc need one free
call, too. So I used current approach, and kind of verify it is the
free that slow down realloc.

For the timers, it at least provides very consistent result.
 
K

Keith Thompson

Please don't quote signatures. When you post a followup, quote just
enough of the previous article so your followup makes sense.
I'm using gcc-3.0.4, is there some documentation to check its "free"
implementation? Also this program is a multithread program. The buffer
freed in one thread is like to be allocated by another thread. Does it
matter?

<OT>gcc has no free implementation; free is provided by the runtime
library, not the compiler.</OT>

There may or may not be documentation for your runtime library's
implementation of malloc and free. Multithreading might affect the
behavior of malloc and free, at least internally, but the standard C
language doesn't support multithreading.

Your question are about your specific implementation. You'll need to
find a newsgroup or other forum that discusses your implementation.
This newsgroup discusses the C language as defined by the standard.
 
W

websnarf

In my code, I need to concat two buffer into one. I take following
steps:
1 malloc a new space
2 copy two buffers over,
3. and then free the originial two buffers.
I put timer on each step. And I found that under some stress
condition(cpu intensive, lots of memory used), the last step took a
lot more time than step 1 and 2. Did anyone know what could be the
reason?

In balanced heap implementations, the cost of free() and malloc()
should be *roughly* the same. free() needs to merge the memory with
adjacent free buffers if possible, and then update the new free
buffers relative to whatever structures they exist in to assist the
malloc() function to find them quickly.
 
C

CBFalconer

Lianjun said:
In my code, I need to concat two buffer into one. I take following
steps:
1 malloc a new space
2 copy two buffers over,
3. and then free the originial two buffers.
I put timer on each step. And I found that under some stress
condition(cpu intensive, lots of memory used), the last step took
a lot more time than step 1 and 2. Did anyone know what could be
the reason?

Yes. It usually depends on the number of malloced pieces in effect
at the time and the effort required to detect and join them. I
wrote nmalloc to avoid it (and a few other problems). See:

<http://cbfalconer.home.att.net/download/>

for an (almost) standard C implementation for DJGPP and others.
 
C

CBFalconer

In balanced heap implementations, the cost of free() and malloc()
should be *roughly* the same. free() needs to merge the memory with
adjacent free buffers if possible, and then update the new free
buffers relative to whatever structures they exist in to assist the
malloc() function to find them quickly.

I don't know what you mean by 'balanced heap', but in general the
cause is the excessive searching for adjacent blocks to merge
during the free operation. This is often an O(n) operation. In
nmalloc, it is cut to O(1).
 
B

Barry

CBFalconer said:
Yes. It usually depends on the number of malloced pieces in effect
at the time and the effort required to detect and join them. I
wrote nmalloc to avoid it (and a few other problems). See:

<http://cbfalconer.home.att.net/download/>

for an (almost) standard C implementation for DJGPP and others.

Although in most cases I agree with you, how do you find an
almost because I wrote it, appropriate for clc?
 
J

jacob navia

Barry said:
Although in most cases I agree with you, how do you find an
almost because I wrote it, appropriate for clc?

Can you explain what's wrong with the message?
Or you think it is forbidden to speak about what one's writes
in this newsgroup?

jacob
 
B

Barry

jacob navia said:
Can you explain what's wrong with the message?
Or you think it is forbidden to speak about what one's writes
in this newsgroup?

jacob

I wrote my response in simple English. What part confuses you?
 
J

jacob navia

Barry said:
I wrote my response in simple English. What part confuses you?

You wrote:

"Although in most cases I agree with you, how do you find an
almost because I wrote it, appropriate for clc?"

Parse error. "How do you find an almost" ???
Something is missing I would say.
 
B

Barry

jacob navia said:
You wrote:

"Although in most cases I agree with you, how do you find an
almost because I wrote it, appropriate for clc?"

Parse error. "How do you find an almost" ???
Something is missing I would say.

"How do you find an almost," is not what it says. Had I written:
How do you find a purple polka dot elephant in a bowl of cherries?
Would you ask how do you find a purple?
 
R

Richard Tobin

You wrote:

"Although in most cases I agree with you, how do you find an
almost because I wrote it, appropriate for clc?"

Parse error. "How do you find an almost" ???
Something is missing I would say.
[/QUOTE]
"How do you find an almost," is not what it says. Had I written:
How do you find a purple polka dot elephant in a bowl of cherries?
Would you ask how do you find a purple?

I'm a native speaker of English, and I can't make any sense of your
sentence.

-- Richard
 
R

Richard Bos

"How do you find an almost," is not what it says. Had I written:
How do you find a purple polka dot elephant in a bowl of cherries?
Would you ask how do you find a purple?

I'm a native speaker of English, and I can't make any sense of your
sentence.[/QUOTE]

I'm not a native speaker of English, and I find that sentence completely
understandable provided it is not ripped cruelly out of context.

Richard
 
C

CBFalconer

Barry said:
.... snip ...

Although in most cases I agree with you, how do you find an
almost because I wrote it, appropriate for clc?

Please attempt to write a fully standard general malloc package.
Can't be done. That is one reason it is part of the
implementation.
 
C

CBFalconer

Richard said:
I'm a native speaker of English, and I can't make any sense of your
sentence.

I am also (a native speaker), yet I can make sense out of it. It
is an effort, but possible.

BTW someone has been grossly careless in snipping attributions for
quoted material.
 
B

Barry

CBFalconer said:
Please attempt to write a fully standard general malloc package.
Can't be done. That is one reason it is part of the
implementation.

Chuck, the post was partially in gest because you are typically the
first person to point out off topic posts. I didn't expect it to be a big
deal :).
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top