LRU cache for ~=

[Robert Jacques]

On Tue, 20 Oct 2009 11:24:21 -0400, Steven Schveighoffer  
<schveiguy at yahoo.com> wrote:

> On Tue, 20 Oct 2009 10:48:31 -0400, Robert Jacques <sandford at jhu.edu>  
> wrote:
>
>> On Tue, 20 Oct 2009 10:05:42 -0400, Steven Schveighoffer  
>> <schveiguy at yahoo.com> wrote:
>>
>>> I'd think you only want to clear the entries affected by the  
>>> collection.
>>>
>>
>> If it was free and simple to only clear the affected entries, sure. But  
>> doing so requires (very heavy?) modification of the GC in order to  
>> track and check changes.
>
> Why?  All you have to do is check whether a block is referenced in the  
> LRU while freeing the block.  I don't even think it would be that  
> performance critical.  Using my vastly novice assumptions about how the  
> GC collection cycle works:
>
> step 1, mark all blocks that are not referenced by any roots.
> step 2, check which blocks are referenced by the LRU, if they are, then  
> remove them from the LRU.
> step 3, recycle free blocks.

I agree, but my mind hadn't gotten there yet. (It was thinking of the  
overhead of generational/concurrent collections, for some strange reason)

>> But this requires the LRU to be part of the GC.
>
> I think we're already in that boat.  If the LRU isn't attached to the  
> GC, then ~= becomes a locking operation even if the GC is thread-local,  
> which makes no sense.
>
> -Steve

Of course, Andrei just stated the cache should be thread-local (and  
probably in the function, not the GC) which throws a spanner into the  
works.