[Question] LeCaR implementation

[lynnliu030]

Hi, I have a question related to the LeCaR implementation in this repo.

    # Cache Miss
    def miss(self, oblock):
        evicted = None

        freq = 1
        if oblock in self.lru_hist:
            entry = self.lru_hist[oblock]
            freq = entry.freq + 1
            del self.lru_hist[oblock]
            reward_lru = -(self.discount_rate
                           **(self.time - entry.evicted_time))
            self.adjustWeights(reward_lru, 0)
        elif oblock in self.lfu_hist:
            entry = self.lfu_hist[oblock]
            freq = entry.freq + 1
            del self.lfu_hist[oblock]
            reward_lfu = -(self.discount_rate
                           **(self.time - entry.evicted_time))
            self.adjustWeights(0, reward_lfu)

        # If the cache is full, evict
        if len(self.lru) == self.cache_size:
            evicted, policy = self.evict()

        self.addToCache(oblock, freq)

        return evicted

In this case, the frequency of the newly-added object is the old frequency (before eviction) + 1. Why is this the case? The new object should have frequency of 1 considering that it has been evicted already by the cache, is that right?

[lia54]

Hi there,

For the case of new items, the frequency should be the smallest value or base frequency (1 from the code above). Frequency is only incremented whenever we encounter a hit in history, which means items that have been previously evicted from cache but are still in history (these items do not fall into the newly-added item's category because they have been seen before).

Also, in this implementation, we started counting from 1 instead of 0 which is just a shift in the values of the stored frequency distribution and does not have any impact on the correctness of the algorithm or the eviction sequence.

Thanks for the interest!

[sylab]

Closing due to no activity.