Adaptive PIC scheme (Re: [Vm-dev] InterpreterSimulator)
leves at caesar.elte.hu
Tue Mar 15 18:46:26 UTC 2016
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, 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.
- simple bookkeeping
- sorting can be done in-place
- 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
- 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
- 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.
 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.
More information about the Vm-dev