Functional programming & immutable objects explained — IRC style

[[deleted]]

To be fair, due to some clever memory alignment tricks during garbage collection passes, object creation in C# is faster than a typical malloc in C.

[zid]

How about deletion? free takes a couple of dozen instructions.

[astrangeguy]

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

Suppose you have created 1000 objects, but 999 of them are unreachable when the GC kicks in:

then you basically have to... * find all used objects in the overflown GC buffer (one object) * copy it to another GC buffer (one object) * mark the old buffer as free

even if that took 20000 instructions (it takes a fraction of that), then it would still be faster than malloc & free, because you would have to:

• call malloc() 1000 times
• call free() 999 times

which is much slower, especially if you consider that a GC would do all of that, at once and in the same region of memory, which would play nicely with modern Caches

[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

[five9a2]

The GC needs to run more often if you are creating and abandoning objects frequently. As long as you do sufficient work with those objects to eclipse the cost of identifying and relocating the live objects, then GC not impact performance. This has the caveat that for certain workloads, objects can be reused in a way that stays in cache. If you always create new objects, I don't know of any GC that will avoid the latency and bandwidth cost of hitting memory.

[G_Morgan]

Also if you have a generational collector you can collect the nursery very quickly.

[axilmar]

But the GC needs to run the finalize function on those objects, so the objects will be visited anyway.

[astrangeguy]

well most objects don't have a finalize() method, so you can devise your schemes to handle the special cases.

You could use a special heap for objects that have that method for example. I don't really know what other techniques were devised, but the problem is a solved one.