Review: ImageCache automip experiment

Recently, I committed a change that attempted to address an automip problem -- automipping a file that is itself bigger than the allocated cache size would thrash the cache horribly just in the process of creating the automip tiles.  The solution I proposed and committed was for the read_unmipped() routine to bump up the cache size to a minimum of twice the size of the automipped file, so that automipping the file would have room to do its job.

Chris Kulla pointed out at the time that this worked well as long as only one thread was automipping at a time, but if two threads were simultaneously automipping separate files, it would bump the cache to the bigger of them, not the sum of them.  And therefore, we could still thrash rather badly.  Marcos and his team have encountered this in the wild, and it does seem to be a big problem.  (Aside: I never see it myself, because at SPI everything is run through maketx first; at worst we have 1 or 2 unmipped files, and we shoot for none.)

I had another idea, which is that instead of making it the max, it would simply increase the cache size temporarily while automipping, then set it back (decreasing by the same amount)  after the automipping was finished.  Thus, if multiple threads are automipping at the same time, it should make the cache (temporarily) big enough to accommodate both of them.

I have no idea if this will make it better, or have problems elsewhere, and not a good way to test it (alas, I don't have time to extensively create test cases that are unlike anything we see at SPI).  But I offer the following patch, which adds an undocumented IC attribute "automip_growth" that lets you select the strategy: 0 = nothing, 1 = set cache to be big enough for the file (i.e. current method), 2 = add to cache size per-thread, then decrease when done automipping (newly proposed method).  The default is 1, which means that anybody not trying these experiments should see no change in behavior.  The idea is to allow people who care to compare the two methods, or extend it to other ideas we may have, and report back, and eventually if there's a clear winner we will make that the one true behavior.

Frankly, I'm still skeptical because even though these techniques both make the cache big enough to not thrash during the automip operation itself, they still are not kind to the cache, because all the automipped tiles (which mostly are high-res MIP levels only read in to make the low-res ones we want, but not actually desired in and of themselves) end up marked as recently used, and the other tiles that used to be in the cache (from all the other files) now look not very recently used, so when the cache size is restored, guess who gets kicked out of the cache first?  Right, the innocent bystanders.  If anybody has alternate ideas, I'm all ears. I'd really like a robust solution to the problem.

[erich.ocean_me.com, 2010-12-14 09:30:26]

One solution to the LRU cache-poluttion issue is using an adaptive replacement
cache (ARC)[1]. ARC gracefully handles situations where you're paging through a
lot of stuff in a row that you only use once, without evicting stuff you
actually care about.

ARC is used in Sun's ZFS file system, and when I reviewed the code there, it
seemed straightforward enough to me.

Best, Erich

[1] http://en.wikipedia.org/wiki/Adaptive_replacement_cache

On Dec 13, 2010, at 11:11 PM, larrygritz@gmail.com wrote:

> Reviewers: oiio-dev_openimageio.org,
> 
> Description:
> Recently, I committed a change that attempted to address an automip
> problem -- automipping a file that is itself bigger than the allocated
> cache size would thrash the cache horribly just in the process of
> creating the automip tiles.  The solution I proposed and committed was
> for the read_unmipped() routine to bump up the cache size to a minimum
> of twice the size of the automipped file, so that automipping the file
> would have room to do its job.
> 
> Chris Kulla pointed out at the time that this worked well as long as
> only one thread was automipping at a time, but if two threads were
> simultaneously automipping separate files, it would bump the cache to
> the bigger of them, not the sum of them.  And therefore, we could still
> thrash rather badly.  Marcos and his team have encountered this in the
> wild, and it does seem to be a big problem.  (Aside: I never see it
> myself, because at SPI everything is run through maketx first; at worst
> we have 1 or 2 unmipped files, and we shoot for none.)
> 
> I had another idea, which is that instead of making it the max, it would
> simply increase the cache size temporarily while automipping, then set
> it back (decreasing by the same amount)  after the automipping was
> finished.  Thus, if multiple threads are automipping at the same time,
> it should make the cache (temporarily) big enough to accommodate both of
> them.
> 
> I have no idea if this will make it better, or have problems elsewhere,
> and not a good way to test it (alas, I don't have time to extensively
> create test cases that are unlike anything we see at SPI).  But I offer
> the following patch, which adds an undocumented IC attribute
> "automip_growth" that lets you select the strategy: 0 = nothing, 1 = set
> cache to be big enough for the file (i.e. current method), 2 = add to
> cache size per-thread, then decrease when done automipping (newly
> proposed method).  The default is 1, which means that anybody not trying
> these experiments should see no change in behavior.  The idea is to
> allow people who care to compare the two methods, or extend it to other
> ideas we may have, and report back, and eventually if there's a clear
> winner we will make that the one true behavior.
> 
> Frankly, I'm still skeptical because even though these techniques both
> make the cache big enough to not thrash during the automip operation
> itself, they still are not kind to the cache, because all the automipped
> tiles (which mostly are high-res MIP levels only read in to make the
> low-res ones we want, but not actually desired in and of themselves) end
> up marked as recently used, and the other tiles that used to be in the
> cache (from all the other files) now look not very recently used, so
> when the cache size is restored, guess who gets kicked out of the cache
> first?  Right, the innocent bystanders.  If anybody has alternate ideas,
> I'm all ears. I'd really like a robust solution to the problem.
> 
> 
> 
> Please review this at http://codereview.appspot.com/3620042/
> 
> Affected files:
>  src/libtexture/imagecache.cpp
>  src/libtexture/imagecache_pvt.h
> 
> 
> _______________________________________________
> Oiio-dev mailing list
> Oiio-dev@lists.openimageio.org
> http://lists.openimageio.org/listinfo.cgi/oiio-dev-openimageio.org

[lg_imageworks.com, 2010-12-14 18:50:21]

Thanks for the tip.  The Wikipedia article mentions straightaway that it's
patented, and also I think it might be even more complicated than we need.  We
know a priori that the tiles we are reading solely for the sake of automipping
are not likely to be needed and should be lower priority for keeping in cache. 
I bet I can make a rather simple modification to just mark them "not recently
used" immediately so that they will t end to be preferentially freed.

	-- lg


On Dec 14, 2010, at 1:30 AM, Erich Ocean wrote:

> One solution to the LRU cache-poluttion issue is using an adaptive replacement
cache (ARC)[1]. ARC gracefully handles situations where you're paging through a
lot of stuff in a row that you only use once, without evicting stuff you
actually care about.
> 
> ARC is used in Sun's ZFS file system, and when I reviewed the code there, it
seemed straightforward enough to me.
> 
> Best, Erich
> 
> [1] http://en.wikipedia.org/wiki/Adaptive_replacement_cache
> 
> On Dec 13, 2010, at 11:11 PM, larrygritz@gmail.com wrote:
> 
>> Reviewers: oiio-dev_openimageio.org,
>> 
>> Description:
>> Recently, I committed a change that attempted to address an automip
>> problem -- automipping a file that is itself bigger than the allocated
>> cache size would thrash the cache horribly just in the process of
>> creating the automip tiles.  The solution I proposed and committed was
>> for the read_unmipped() routine to bump up the cache size to a minimum
>> of twice the size of the automipped file, so that automipping the file
>> would have room to do its job.
>> 
>> Chris Kulla pointed out at the time that this worked well as long as
>> only one thread was automipping at a time, but if two threads were
>> simultaneously automipping separate files, it would bump the cache to
>> the bigger of them, not the sum of them.  And therefore, we could still
>> thrash rather badly.  Marcos and his team have encountered this in the
>> wild, and it does seem to be a big problem.  (Aside: I never see it
>> myself, because at SPI everything is run through maketx first; at worst
>> we have 1 or 2 unmipped files, and we shoot for none.)
>> 
>> I had another idea, which is that instead of making it the max, it would
>> simply increase the cache size temporarily while automipping, then set
>> it back (decreasing by the same amount)  after the automipping was
>> finished.  Thus, if multiple threads are automipping at the same time,
>> it should make the cache (temporarily) big enough to accommodate both of
>> them.
>> 
>> I have no idea if this will make it better, or have problems elsewhere,
>> and not a good way to test it (alas, I don't have time to extensively
>> create test cases that are unlike anything we see at SPI).  But I offer
>> the following patch, which adds an undocumented IC attribute
>> "automip_growth" that lets you select the strategy: 0 = nothing, 1 = set
>> cache to be big enough for the file (i.e. current method), 2 = add to
>> cache size per-thread, then decrease when done automipping (newly
>> proposed method).  The default is 1, which means that anybody not trying
>> these experiments should see no change in behavior.  The idea is to
>> allow people who care to compare the two methods, or extend it to other
>> ideas we may have, and report back, and eventually if there's a clear
>> winner we will make that the one true behavior.
>> 
>> Frankly, I'm still skeptical because even though these techniques both
>> make the cache big enough to not thrash during the automip operation
>> itself, they still are not kind to the cache, because all the automipped
>> tiles (which mostly are high-res MIP levels only read in to make the
>> low-res ones we want, but not actually desired in and of themselves) end
>> up marked as recently used, and the other tiles that used to be in the
>> cache (from all the other files) now look not very recently used, so
>> when the cache size is restored, guess who gets kicked out of the cache
>> first?  Right, the innocent bystanders.  If anybody has alternate ideas,
>> I'm all ears. I'd really like a robust solution to the problem.
>> 
>> 
>> 
>> Please review this at http://codereview.appspot.com/3620042/
>> 
>> Affected files:
>> src/libtexture/imagecache.cpp
>> src/libtexture/imagecache_pvt.h
>> 
>> 
>> _______________________________________________
>> Oiio-dev mailing list
>> Oiio-dev@lists.openimageio.org
>> http://lists.openimageio.org/listinfo.cgi/oiio-dev-openimageio.org
> 
> _______________________________________________
> Oiio-dev mailing list
> Oiio-dev@lists.openimageio.org
> http://lists.openimageio.org/listinfo.cgi/oiio-dev-openimageio.org
> 

--
Larry Gritz
lg@imageworks.com