Adaptive PIC scheme (Re: [Vm-dev] InterpreterSimulator)

[Levente Uzonyi]

Hi Clément,

On Tue, 15 Mar 2016, Clément Bera wrote:

(no quote again, sorry)

So, the idea is to add a counter to each cache entry, and increase it on 
each hit. Once a counter reaches a given limit, divide all counters by 
two[1], and optionally do housekeeping stuff.
By housekeeping I mean removing entries with zero counter value, resorting 
the entries based on the counter values, and optionally reverting to a 
single method when there's only one cache entry left.
By optionally I mean that if you don't want to do the housekeeping every 
time the limit is reached, then another counter can be introduced, so that 
only every nth time will housekeeping occur.
Since there are at most six cache entries, sorting can be done by 
Insertion sort or a hardcoded Optimal sorting network. The former would be 
simple and efficient, the latter could be even more efficient but more 
complex as well.

In practice this can be done (at least) two ways:

1. If there's a free byte at each entry, then the cache entries can store 
their own counters. If we use single byte counters, then it's practical to 
use 256 as the limit. That way division happens when the counter 
overflows. That takes at least 128 cache hits between two divisions, but 
if we eventually revert to a single method when there's only one entry 
left in the PIC, then the average number will be slightly higher than 128.

Pros:
- simple bookkeeping
- sorting can be done in-place
Cons:
- there's probably no free byte
- if we don't want to do the housekeeping too often, then the PIC 
will need a few more extra bytes to store another counter for that

2. Add a single 64-bit word to the PIC. The lower 6 bytes can be used for 
the 6 counters, one per cache entry. The remaining two bytes can hold the 
housekeeping counter.

Pros:
- still fairly simple bookkeeping, but overflows will have side-effects on 
the next byte. This can be worked around by leaving an empty bit
between the counter bytes, at the cost of reducing the size of the 
housekeeping counter. Another option is to check the counter value before 
incrementing it to avoid overflows altogether.
- dividing all counters by two can be done in a few machine instructions
- 7-bit or 9-bit counters can be used as well
Cons
- incrementing a counter is a bit more complex
- sorting is trickier because the counter values will have to be 
swapped as well

Assuming there's no free byte, I'd start straight with 2., but even adding 
a 64-bit word to a PIC doesn't seem too easy.

Levente

[1] This scheme holds information about not that recent hits as well, but 
the effect of the past decreases exponentially, so it's a fairly good 
approximation of the most recent hits without the need to store any 
additional data. I came up with this method a few years ago, yet I still 
couldn't find out what it's called.