[palish]

... allocation/deallocation is really expensive ...

The cost of allocating memory in .NET (and probably other GC environments) is basically equivalent to the cost of incrementing a pointer, which is to say, basically free. The reason is because the .NET garbage collector periodically "packs together" objects in memory, so the memory allocation algorithm essentially becomes:

  result = _freeMemoryPtr;
  _freeMemoryPtr += numBytesToAllocate;
  return result;

... in other words, since objects in memory are periodically "packed together" by the GC, there isn't a lot of memory fragmentation, so the allocator can simply allocate from the end of the heap. It doesn't need to try to find a "large enough free block" within fragmented memory, because memory isn't fragmented.

At least, that is my understanding. I could be wrong because I haven't investigated this thoroughly yet.

http://en.wikipedia.org/wiki/Garbage_collection_(computer_sc...

[tptacek]

You're right; I should have said, "malloc/free is really expensive".

[palish]

Just curious, what do you do? It's interesting that you optimize a lot of C/C++ programs... game development maybe?

[tptacek]

Network security software, reverse engineering, and (a bit earlier in my career) streaming video/multicast.

I got a 7x performance improvement in a performance-critical component at Arbor Networks within a couple weeks of starting there just by profiling, finding malloc/free at the top of the profile, and switching to an arena allocator. I have other malloc stories, but that's the simplest. I've learned to fear malloc.

[palish]

I'd like to hear the other malloc/free stories whenever you're inclined.

[Xichekolas]

My guess is something cryptographic.

[tptacek]

cperciva is the resident crypto person here. =)