GC Blacklisting

[Vladimir Panteleev]

On Fri, 25 Feb 2011 06:38:52 +0200, dsimcha <dsimcha at yahoo.com> wrote:

> I've been optimizing the druntime garbage collector lately, and as I've  
> found several smaller optimizations since I submitted my patch last  
> week, I've temporarily forked the druntime Git repository to store those  
> optimizations.  The results are here:
>
> https://github.com/dsimcha/druntime/wiki/Druntime-GC-Optimization-Fork

Good work!

> In the process, I've built up such a good mental model of the GC  
> codebase that I'd hate to see it go to waste.
>
> On 32-bit systems, false pointers are a big problem with conservative  
> garbage collection.  Apparently this problem can be drastically  
> mitigated by blacklisting memory addresses that have false pointers  
> pointing at them.  (See  
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.961&rep=rep1&type=pdf)  
>   I'm wondering if such a technique is worth implementing in the D  
> garbage collector.

Blacklisting deals with cases when data is allocated at referenced  
addresses, but seems useless when false references are created to  
already-existing data, which seems to me like the more common case.  
Furthermore, if the false pointers have a high-enough entropy (and there  
are enough of them), they will cover the address space densely and  
consistently enough that blacklisting becomes almost useless. Not to  
mention the inherent waste of memory associated with this?

I have very successfully dealt with false pointers to large objects in the  
following way:

https://github.com/CyberShadow/data.d

This method also has other advantages (as mentioned).

Personally, I would prefer that D's GC remains fast and lean, optimized  
for scanning small heaps of small objects, and a method similar to mine be  
used for handling large data.

P.S. I'm currently in the process of tracking down a memory corruption  
bug, which *might* result in a GC patch for D1. I'm also instinctively  
worried that touching the GC code may introduce new memory corruption  
bugs, which can be EXTREMELY hard to find. I've been chasing this one for  
4 years.

-- 
Best regards,
  Vladimir                            mailto:vladimir at thecybershadow.net