Index Cache Eviction Strategy

[chocolate42]

It's possible the default eviction strategy of "always evict" could be improved upon, here's some preliminary data. Based on luma61.run64, which is a tweaked version of the latest experimental branch. It doesn't matter much what the build is as the point is to compare between strategies.

qoi-l61r64: Vanilla for comparison
qoi-l61r64c*: A cache strategy described below

//Increment a value whenever an index is used
//When we try to evict an index we check this value. On zero we evict,
//otherwise the value is reduced depending on strategy:
// 0: vanilla, always evict
// 1: After failing to evict, set to zero
// 2: After failing to evict, decrement
// 3: After failing to evict, divide by 2
// 4: After failing to evict, divide by 4
// 5: After failing to evict, divide by 8
// 6: After failing to evict, divide by 16

## Benchmarking ../qoitests/images/tango512/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:              3.1        20.5         85.13         12.78        51
stbi:                2.1        20.5        124.91         12.77        69
qoi-l61r64:          0.6         0.8        476.06        328.86        86
qoi-l61r64c1:        0.7         0.9        366.43        304.27        83
qoi-l61r64c2:        0.7         0.9        358.94        302.28        86
qoi-l61r64c3:        0.7         0.9        359.54        307.98        83
qoi-l61r64c4:        0.7         0.8        361.45        310.28        83
qoi-l61r64c5:        0.7         0.8        362.30        308.45        83
qoi-l61r64c6:        0.7         0.8        363.78        310.00        83

## Benchmarking ../qoitests/images/kodak/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:              9.7       180.1         40.61          2.18       717
stbi:               10.2        99.9         38.71          3.94       979
qoi-l61r64:          2.6         4.4        153.22         89.33       675
qoi-l61r64c1:        3.5         5.1        111.14         77.45       678
qoi-l61r64c2:        3.8         5.0        102.18         78.11       680
qoi-l61r64c3:        3.7         4.8        105.19         82.21       679
qoi-l61r64c4:        3.5         4.7        110.82         84.04       678
qoi-l61r64c5:        3.6         4.8        108.33         82.41       678
qoi-l61r64c6:        3.5         4.7        111.40         83.19       678

## Benchmarking ../qoitests/images/misc/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:             12.0       102.9         73.98          8.64       283
stbi:               10.6        97.6         84.11          9.11       415
qoi-l61r64:          2.1         3.2        417.70        278.41       503
qoi-l61r64c1:        2.8         3.4        319.73        259.87       500
qoi-l61r64c2:        2.9         3.5        309.54        251.76       495
qoi-l61r64c3:        3.0         3.5        298.79        254.31       498
qoi-l61r64c4:        2.9         3.4        311.53        260.90       499
qoi-l61r64c5:        2.8         3.4        318.56        259.64       500
qoi-l61r64c6:        2.9         3.4        311.75        258.41       500

## Benchmarking ../qoitests/images/textures/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:              3.1        43.3         41.76          3.00       163
stbi:                2.8        24.2         46.19          5.37       232
qoi-l61r64:          0.7         1.1        199.69        115.21       179
qoi-l61r64c1:        0.8         1.1        160.15        114.00       177
qoi-l61r64c2:        0.8         1.2        156.88        111.28       179
qoi-l61r64c3:        0.8         1.1        158.34        116.67       177
qoi-l61r64c4:        0.9         1.1        152.24        113.22       177
qoi-l61r64c5:        0.9         1.2        146.05        107.64       177
qoi-l61r64c6:        0.8         1.2        156.20        112.66       177

## Benchmarking ../qoitests/images/screenshots/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:             57.8       622.7        142.49         13.22      2219
stbi:               50.7       748.1        162.22         11.00      2821
qoi-l61r64:         20.6        26.6        400.49        309.33      2475
qoi-l61r64c1:       26.9        27.6        305.70        297.89      2455
qoi-l61r64c2:       27.8        28.8        295.87        285.81      2467
qoi-l61r64c3:       27.3        27.9        301.21        295.01      2451
qoi-l61r64c4:       27.8        27.4        296.28        300.17      2454
qoi-l61r64c5:       26.9        27.5        305.59        299.68      2455
qoi-l61r64c6:       26.8        27.4        307.46        300.61      2455

## Benchmarking ../qoitests/images/wallpaper/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:            189.9      2893.7         49.35          3.24      9224
stbi:              221.1      1786.6         42.40          5.25     13299
qoi-l61r64:         64.3        85.4        145.69        109.80      9964
qoi-l61r64c1:       83.0        93.8        112.97         99.91     10021
qoi-l61r64c2:       89.1       100.0        105.23         93.76     10179
qoi-l61r64c3:       87.1        94.2        107.55         99.47     10079
qoi-l61r64c4:       84.8        92.8        110.48        101.01     10039
qoi-l61r64c5:       83.4        91.5        112.32        102.46     10027
qoi-l61r64c6:       82.9        91.5        112.99        102.43     10023

Performance tanks hard so even if it was a decent gain in compression (it isn't) it still wouldn't be viable. It's hard to see how a strategy can be implemented with less performance impact but maybe someone smarter can figure something out. It's most likely a dead end.

qoi-cache.h.txt