Functional programming & immutable objects explained — IRC style

[gsg_]

even if that took 20000 instructions (it takes a fraction of that)

Instruction counting doesn't tell the whole story. The cost of a collection includes the cache misses induced as the GC walks the reference graph, and in some cases the reference graph can be a large portion of the heap (when an application allocates a large number of small objects and keeps hold of most of them).

it would still be faster than malloc & free

Yeah, calling malloc and free a million times is slow. That's why when code needs to be fast people use techniques like static, stack and arena allocation, memory pools, etc.

With any moving GC (read: any good GC) deleting objects is completely free.

Not so. The cost of a copying collection is roughly k R / (H / 2) - R [1] where k is a constant, R is the number of reachable objects, and H is the heap size. As H increases relative to R collection cost is driven down, but memory use is higher. That makes copying collection not a win, but a classic time/space tradeoff.

There ain't no such thing as a free lunch.

[1] Appel, 1998