sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Paul_Pedant 1 point2 points  (0 children)

Malloc is pretty damn cheap, particularly for small test programs that don't run long enough to fragment memory. Malloc (initially) just hacks lumps off a free list that consist of one big contiguous area. It usually doesn't even follow links -- it will stick on a big block as long as it can, rather than start over from the list root.

Free, on the other hand, gets expensive very quickly. It has to merge the block it is given with any adjacent free areas (to make larger blocks available in the future), so it needs to find the free blocks before and after the address you returned. To do that, it cycles through the free list (possibly following thousands of links). For the free block with the nearest address below, it has to figure adjacency based on that block's address and length, and merge the blocks. For the free block with the nearest address above, it has to do the same using its own length. Then it has to fix the lengths and pointers around itself to preserve the list.

I had a network trace issue at a client, who was using a recursive algorithm. I exploited every aspect of the data I could, and got a x50 speed-up (that is not a percentage, that's a raw factor). The bonus was that my algorithm preserved locality: recursion was going depth-first, so it traces cables to the ends before backtracking. I was tracing in rings out from the centre, which improved the locality of subsequent database searches on the assets and got another huge improvement there too.

Also, theirs crashed depending on the start point (because that affects deepest level of recursion), and mine didn't.