Related links: 1. stack overflow question(asked but nobody answers) 2. Antirez's article Random notes on improving the Redis LRU algorithm 3. evict.c on unstable branch

questions: 1. Antirez wrote in the article mentioned above > the value of the counter is halved if it is an high value, or just decremented if it is a lower value.

but in `db.c` I can only find code below, and function `LFUDecrAndReturn` just minus counter by time elapsed div `lfu-decay-time`. Anything I missed?
```c
void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);
    counter = LFULogIncr(counter);
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}
```

  1. According to comments in evict.c, which says > After the pool is populated, the best key we have in the pool is expired. However note that we don't remove keys from the pool when they are deleted so the pool may contain keys that no longer exist.

    But in freeMemoryIfNeeded(void), once a best entry is found in eviction pool, I find pool[k].key = NULL etc...
    I can understand that ghost keys may appear since other calls can trigger freeMemoryIfNeeded (please points the err if I'm wrong), but why does the comment say we don't remove keys from the pool?

  2. Why don't we use linked list instead of continuous memory when alloc eviction pool? In evictionPoolPopulate, once a key find its position, several memmove calls is needed, can linked list structure decrease this cost? I guess memmove on only 16 eviction pool entry may have better performance than linked list(since CPU cache or sth)? But I'm not sure...

Comment From: Forec

Anyone who can help?

Comment From: hwware

Hello @Forec, sorry for my late reply, but here is my understanding of your three questions: 1. I think this is the approximication, please note that the author's sentence after that, in the hope that we can better discriminate among keys with few accesses, given that our counter resolution is very small, which means he considers the key has been accessed few times, which brings the log decrease function here: https://github.com/antirez/redis/blob/17bf0b25c1171486e3a1b089f3181fff2bc0d4f0/src/evict.c#L315 , this function is interesting since if the counter is big, max is 255, it has very low chance to get increased, however when the counter is small, it has high chance, therefore, I think you can understand the author's sentence now why this can happens.

  1. I think the comment means if the key was deleted, the entry in eviction pool will still be there,https://github.com/antirez/redis/blob/17bf0b25c1171486e3a1b089f3181fff2bc0d4f0/src/evict.c#L568,the place actually removes the entry from pool is by shifting the entrieswhen calling memmove: https://github.com/antirez/redis/blob/17bf0b25c1171486e3a1b089f3181fff2bc0d4f0/src/evict.c#L227 and L237. (btw this also means the old key idle time which was removed still have some influence of the new keys adding into the eviction pool )

  2. yep I guess so, the memmove might have better performance than linkedlist in this case, but I did not test the performance yet. Hopfully that helps .

Comment From: Forec

Thanks @hwware

I have new understandings after some discussion.

  1. In Q1, codes handling high/low counter do not have difference. The LFU counter is an approximate Morris counter, so the author may want to explain that if value of counter is large(such as 255), compared with a small counter(such as 5 which is also the default value), after decreasing a same value N, the indeed value represented by the former will be significantly reduced than the latter(2^255 - 2^(255-N) >> 2^5 - 2^(5-N)). But I misunderstood that the author meant that the value of the counter itself would be halved.

  2. Thanks for your explanation about Q2, but I think the comments are not modified in sync with the code. Eviction pool contains 16 entries with contiguous memory. In order to provide a suitable position for a new entry in eviction pool, some existing entries need to be adjusted, the memmove you mentioned is working for this instead of removing a no longer existed entry.

  3. I'm still not sure about Q3. Sorry for bothering, but I wonder if @antirez has done comparisons before or can give us some tips?