Review: ImageCache policy bug fix

In poking around ImageCache internals, I noticed what I think is a bug: although find_tile_main_cache marks the tiles it retrieves as 'used', the main outer routine find_tile -- which wraps find_tile_main_cache but only calls it if the tile we're seeking is not in the per-thread 2-tile microcache -- does not!  That means that potentially the MOST frequently accessed files -- accessed so frequently that they perpetually stay in the microcache -- may fall out of the main cache because they don't look used.

Consider this 2-thread access pattern (assume a tiny main cache):

    thread 0    thread 1  
       A                B
       A                C    (note: A not marked used)
       A                D    (A not marked used)
       A                E    (A has fallen out of the main cache, though still in 0's microcache)
       B                F
       C                C  (now A is out of 0's microcache, and thus freed)
       A <- main cache miss! Despite being the most commonly used file!

And it can even be a problem for single thread, consider the following access pattern: A, B, A, C, A, D, A, F, G, A  <- main cache miss, despite A being the most commonly used tile.

I don't know if this actually results in worse performance for typical scenes (we certainly see a great cache hit rate for production scenes).  Today I'll try a couple benchmarks and see how it changes the stats.  But either way, I still think it's a bug and can't be a good thing.  Do you guys agree?

The solution is to move the used() call out of find_tile_main_cache and into find_tile (the only other place that ever calls find_tile_main_cache already explicitly calls used() immediately thereafter.  I believe this marks every retrieved tile as used, regardless of whether it was retrieved from the main or micro cache.

[larrygritz, 2010-12-16 01:14:09]

Update after catching a minor bug in my original diff

[larrygritz, 2010-12-16 01:16:28]

I tried this on a few "real" scenes today, and it doesn't seem to make any real
performance difference.  But I still think it's an improvement (or bug fix) in
that it addresses an access pattern that, if it ever did come up, would perform
worse than we might hope.

[larrygritz, 2010-12-16 01:42:29]

Update: simplify, I prefer this formulation of the patch

[larrygritz, 2010-12-17 07:03:19]

Typo fix (used -> use!) and make m_used atomic

[larrygritz, 2010-12-17 07:06:00]

On 2010/12/17 07:03:19, larrygritz wrote:
> Typo fix (used -> use!) and make m_used atomic

I noticed that the last patch I submitted had a typo -- I had used() where I
meant use().  Also, I made the ImageCacheTile m_used field an atomic_int instead
of an unprotected bool.  I'm not sure it makes a practical difference, but it
makes me feel better.  I reran the benchmarks, and it doesn't increase the cost.

So I stand by this patch and wish to commit it if I get a LGTM from somebody.

[larrygritz, 2010-12-24 19:04:47]

Going once... going twice...

[Chris Foster, 2011-01-08 14:52:30]

On Fri, Dec 17, 2010 at 5:06 PM,  <larrygritz@gmail.com> wrote:
> On 2010/12/17 07:03:19, larrygritz wrote:
>>
>> Typo fix (used -> use!) and make m_used atomic
>
> I noticed that the last patch I submitted had a typo -- I had used()
> where I meant use().  Also, I made the ImageCacheTile m_used field an
> atomic_int instead of an unprotected bool.  I'm not sure it makes a
> practical difference, but it makes me feel better.  I reran the
> benchmarks, and it doesn't increase the cost.
>
> So I stand by this patch and wish to commit it if I get a LGTM from
> somebody.

Ok, I'm reviewing on list, since the code review tool is throwing a fit
with this patch for some reason.

Anyway, LGTM.  I'm not sure whether using an atomic type for m_used is
strictly necessary, but in the absence of a performance hit it can't
hurt :)

~Chris