free() performance question

C

CBFalconer

Barry said:
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 :).

OK. However, I did refrain from posting the code here. :)
 
W

websnarf

I don't know what you mean by 'balanced heap',

I mean 'balanced (heap) *implementation*'. Balanced, as in, one
operation is not penalized for the performance of another. For
example, its easy to make a super-fast malloc with a correspondingly
super-slow free and vice-versa. You can argue that the System V
implementation, for example, does favor malloc over free.
[...] 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).

Right, but even being O(1), its not necessarily that fast. The OP is
talking real numbers, not just the theoretical stuff. Personally,
I've measured various implementations of malloc and free to be in the
100 clocks (on an Athlon CPU) kind of range (my recollection from
looking through your sources, is that you should have similar
performance), indicating that heap operations are worth minimizing.

But even in fair implementations you can see how mallocs from a fresh
heap might be fast-pathed and may be very fast when you measure it
directly under a simplistic test scenario. But the compiler developer
may have been lazy or it just might be difficult to implement a
corresponding fast-path for free (or perhaps its only fast-path if you
treat the heap like a stack, which you are unlikely to do, for
example, if you are allocating and deallocating an array of elements.)
 

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