5 ms·
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
by cconstantine 18y ago
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 18y agoSo 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 18y ago... 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_science)#Generational_GC_.28aka_Ephemeral_GC.29 http://en.wikipedia.org/wiki/Garbage_collection_(computer_sc...
- tptacek 18y agoYou're right; I should have said, "malloc/free is really expensive".
- palish 18y agoJust curious, what do you do? It's interesting that you optimize a lot of C/C++ programs... game development maybe?
- Xichekolas 18y agoMy guess is something cryptographic.
- tptacek 18y agocperciva is the resident crypto person here. =)
- tptacek 18y agoNetwork 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 18y agoI'd like to hear the other malloc/free stories whenever you're inclined.
- deleted 18y ago[deleted]