The sampling is not random during evictions in fill_sample

[alfa07]

The rust iterators over HashMap do not work the same as in golang. In rust iteration order is stable between calls if hashmap does not change. If it changes the iteration order is still mostly the same. That not the case for golang where iteration order is different between calls to k := range map.

stretto/src/policy.rs

Line 321 in 262f340

for (k, v) in self.key_costs.iter() {

https://github.com/dgraph-io/ristretto/blob/3177d9c9520c37d36b18113be01fea6393f63860/policy.go#L317

I suspect that cache performance (hit rates) suffer significantly because of this.

[al8n]

Good catch! Thanks. Do you have any suggestions about this? I have no idea how to make Rust's map behave like the Go's.

[alfa07]

Thinking about it I see two options:

• Implement custom (specialized?) hash map
• Fork hashbrown and add iter_from iterator which starts from arbitrary place in the HashMap's backing array

[phantomhker]

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

[al8n]

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

[phantomhker]

It seems that the ring buffer is related to frequency in admit policy, why do you think it's useless?

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

[al8n]

It seems that the ring buffer is related to frequency in admit policy, why do you think it's useless?

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

On https://github.com/dgraph-io/ristretto/blob/main/cache.go#L229, what they do is that they only push the keyhash to the getBuf, and there is the only place the getBuf is used, so I think the ringbuffer is doing nothing in the current implementation. In admit policy, it seems that they are not using ringbuffer anymore.

[phantomhker]

The defaultPolicy in ristretto actually implements the ringConsumer interface, the Push() method will be called in getBuf, maybe you can see here https://github.com/dgraph-io/ristretto/blob/main/policy.go#L113. And that's why the push() method in LFUPolicy in stretto is not called, it should be called in getBuf. It seems that you're confused by the duck type in golang

It seems that the ring buffer is related to frequency in admit policy, why do you think it's useless?

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

On https://github.com/dgraph-io/ristretto/blob/main/cache.go#L229, what they do is that they only push the keyhash to the getBuf, and there is the only place the getBuf is used, so I think the ringbuffer is doing nothing in the current implementation. In admit policy, it seems that they are not using ringbuffer anymore.

[al8n]

The defaultPolicy in ristretto actually implements the ringConsumer interface, the Push() method will be called in getBuf, maybe you can see here https://github.com/dgraph-io/ristretto/blob/main/policy.go#L113. And that's why the push() method in LFUPolicy in stretto is not called, it should be called in getBuf.

It seems that the ring buffer is related to frequency in admit policy, why do you think it's useless?

between calls to k := range map.

Thank u very much for your discovery, I'm recently migrating a golang project whose cache library is ristretto to rust with stretto. However, I found the cache hit ratio dropped over time after reaching the max_cost. I will try your branch and give u feed back today. By the way, when will this fix be merged into master? And why did you removed the getBuf and related ring buffer? Will this cause some other problem? @al8n

I think the ring buffer actually does nothing in the current Golang's implementation. For the fix, I decided to implement Golang's map to solve the problem, but I am recently busy with my work.

On https://github.com/dgraph-io/ristretto/blob/main/cache.go#L229, what they do is that they only push the keyhash to the getBuf, and there is the only place the getBuf is used, so I think the ringbuffer is doing nothing in the current implementation. In admit policy, it seems that they are not using ringbuffer anymore.

Ah, good catch! You are right! Thanks! I will try to fix this as soon as possible. But I have to say that at least after May 1.

[al8n]

In conclusion, there are two bugs that need to be fixed.

• The order of the iter of the map should be nonstable. Thanks for @alfa07 has been submitted a PR for hashbrown, let us see when it will we merged by the hashbrown.
• The ringbuffer stuff should be implemented. fix: add get_buf to caclulate admit freq #39

Thanks for @alfa07 and @phantomhker report the problems!