LRU cache for ~=

[dsimcha]

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
> dsimcha wrote:
> > == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
> >> dsimcha wrote:
> >>> == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
> >>>> dsimcha wrote:
> >>>>> Started playing w/ the implementation a little and I see a problem.  What
about
> >>>>> the garbage collector?  There are two possibilities:
> >>>> [snip]
> >>>>> The only possible solutions I see would be to have the GC know everything
about
> >>>>> the LRU cache and evict stale entries (probably slows down GC a lot, a
huge PITA
> >>>>> to implement, couples things that shouldn't be tightly coupled), or clear the
> >>>>> cache every time GC is run (probably would make appending so slow as to
> > defeat the
> >>>>> purpose of having the cache).
> >>>> I think GC.collect may simply evict the entire cache. The collection
> >>>> cycle costs so much, the marginal cost of losing cached information is
> >>>> lost in the noise.
> >>>> Andrei
> >>> But then you have to copy the whole array again, likely triggering another GC if
> >>> the array is large.  Then things really get ugly as, for all practical purposes,
> >>> you've completely done away with the cache.
> >> This happens whether or not a cache is in use.
> >> Andrei
> >
> > But the array isn't guaranteed to get reallocated immediately after *every* GC
> > run.  If you're appending to a huge array, the GC will likely run several times
> > while you're appending, leading to several unnecessary reallocations.
> I don't think I understand this.
> 1. Request for an append comes that runs out of memory
> 2. GC runs and clears memory
> 3. Array is reallocated and the capacity cached.
> No?

This is entirely correct.

> > Each of
> > those unnecessary reallocations will increase the memory footprint of your
> > program, possibly triggering another GC run and wiping out your cache again in
> > short order, until, for sufficiently large arrays,
> >
> > a ~= b;
> >
> > is almost equivalent to
> >
> > a = a ~ b;
> I don't understand how the cache makes that all worse.
> Andrei

The cache doesn't make anything *worse* than with no cache.  The only point I'm
trying to make is that, for large arrays, if the GC clears the cache every time it
runs, things would start to get *almost as bad as* having no cache because the
copy operations become expensive and the GC may run frequently.