[cconstantine]

Memory allocation is something that is typically O(1), or O(log(n)). The constants attached are fairly large, but doing lots of allocations/deallocations isn't a BigO issue.

The schlemiel problem still exists when doing '+=' in a loop. Each copy requires some code to walk the length of both sides of the operator, same as strlen in Joel's example. The loop is an O(n^2) operation, even if it has a smaller constant on it than a memcpy(src, dest, strlen(src)).

It's "Schlemiel", but with different constants attached. For big enough N the O(1) or O(log(n)) of the allocations lose importance making the entire thing O(n^2) just like "Schlemiel".

[tptacek]

So we may be saying the same thing, but, he didn't say allocation was N log N --- and allocation/deallocation is really expensive; it's consistently on the top of profiles of programs I work on.

[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. =)