.Net garbage collection mark phase and huge linked lists

If there is a linked list with 4M+ nodes, does the mark phase needs to traverse the entire list each time to build the graph? Are there any optimizations applied in this case? In the plain sight it doesn't look efficient. Is there a way to verify if GC traverses开发者_如何学Go the entire list or not?

TIA.

---

Yes, it will need to traverse the whole object graph. I can't think how there could be any optimizations, to be honest... but it doesn't need to do very much on each node. Most of the time will probably be spent waiting on memory, I suspect, as obviously it'll burn through the cache. Of course, by the time the linked list ends up in gen2 (and if you're allocating millions of nodes, most of it will be in gen2 pretty quickly), it will only need to do that very rarely.

If this is the most reasonable data structure for your app, I would use it for the moment, but keep track of the performance hit of garbage collection using Performance Monitor etc. If it turns out to be a problem, you can consider alternative strategies.

---

What Jon said.

Also, once an object ends up in Gen2, an optimisation that's available (on Windows but not other platforms IIRC) is that the GC can register with the kernel for notifications to a given page of memory. In cases where a page remains unchanged between GC events, some work need not be repeated.

---

There is one very important optimization being made. The .NET GC is generational, and data in gen2 is only rarely traversed.

With large data structures (such as huge linked lists), most of your data will quickly end up in gen2, where the GC will only rarely access it.

Also, the GC only traverses live data during collections, dead data is collected "for free". So when your list becomes unreachable (or if most of its nodes, but not all, do), then the GC will be able to collect millions of nodes basically for free.