Generalize PixmapCache implementation to LRUCache
ClosedPublic

Authored by mwolff on Mar 29 2020, 1:27 PM.

Details

Summary

Use a std::array internally as we don't expect the cache to be
copied a lot. The test case is also greatly expanded to test the
full (new) API surface of this new container class.

Diff Detail

Repository
R865 Ruqola
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
mwolff requested review of this revision.Mar 29 2020, 1:27 PM
mwolff created this revision.
mwolff edited the summary of this revision. (Show Details)Mar 29 2020, 1:32 PM
mwolff added reviewers: dfaure, mlaurent.
dfaure requested changes to this revision.Mar 29 2020, 2:51 PM

Cool stuff, but...

LRUCache and its predecessor PixmapCache seem to disagree on the meaning of "Used" in LRU.
Only LRUCache::insert counts as "using", while PixmapCache was marking the entry as "used" also in findCachedPixmap().
The goal was: if we keep viewing the same pixmap then we shouldn't evict it. Imagine switching between 6 channels, all of which happen to show one pixmap. If you switch A, B, A, C, A, D, A, E, A, F then LRUCache would evict the A pixmap once reaching F, because it was *inserted* before all others. It seems to me that B should be evicted, instead (least recently viewed, not least recently inserted) .

This revision now requires changes to proceed.Mar 29 2020, 2:51 PM

doh yes very much, what was I thinking :D

mwolff updated this revision to Diff 78806.Mar 29 2020, 8:09 PM

actually update LRU order on use too, not just on insert

dfaure added inline comments.Mar 29 2020, 8:32 PM
src/core/lrucache.h
61

Can you add a unittest for find() on an empty container? I sense problems....

67

is rotate the right thing to do? It affects all other entries and might send the "previously most recently used" entry all the way to the back of the list, no?

Shouldn't this be a remove-and-prepend?

68

remove it = since the value isn't used?

mwolff marked 2 inline comments as done.Mar 29 2020, 9:15 PM
mwolff added inline comments.
src/core/lrucache.h
61

I don't see any :) can you elaborate? when it's empty, mNumEntries == 0 and then begin == end?

67

rotate is a remove-and-prepend, no?

see the test for QCOMPARE(contents(), expected); in both loops, this checks that it does the right thing, no?

mwolff updated this revision to Diff 78809.Mar 29 2020, 9:16 PM
mwolff marked an inline comment as done.

expand test on empty LRU cache

dfaure added inline comments.Mar 29 2020, 9:21 PM
src/core/lrucache.h
61

OK. I thought calling rbegin() on an empty container was invalid, but I was wrong.

67

https://en.cppreference.com/w/cpp/algorithm/rotate

 // simple rotation to the left
std::rotate(v.begin(), v.begin() + 1, v.end());

(value before):       0 1 2 2 3 4 5 7 7 10 
simple rotate left : 1 2 2 3 4 5 7 7 10 0
mwolff updated this revision to Diff 78815.Mar 29 2020, 10:01 PM

fixup the rotate call, thanks! also expanded the test to catch this

see also: https://cpp.godbolt.org/z/Aj7Yjv

mwolff updated this revision to Diff 78816.Mar 29 2020, 10:20 PM

use forward iterators, see also: https://cpp.godbolt.org/z/msSQar

mwolff marked an inline comment as done.Mar 29 2020, 10:21 PM
dfaure accepted this revision.Mar 29 2020, 10:24 PM

Thanks!

src/core/lrucache.h
78

no rotate? :-)

This revision is now accepted and ready to land.Mar 29 2020, 10:24 PM
dfaure accepted this revision.Mar 29 2020, 10:33 PM

Nice :-)

This revision was automatically updated to reflect the committed changes.