Re: Optimizing a CHI-based data throttler

[bliako]

(I will not comment on how efficient the general idea is (with the specific key structure and counters etc.) as this is only part of the code. I will comment on just what I see here.) I understand that you loop over ALL keys to find the non-expired keys. Then you forget about the hard-earned array of NON expired keys @keys you have constructed and proceed to conditionally call purge() which probably has to do it again (internally, it has to find the set of expired keys this time I guess), in a similar or more efficient way.

If you want to retain the data structure you are using, then you could break the loop as soon as you find even one expired key and forget about the array, just retain the fact that expired keys were found and purge() must be called (conditionally). Given that you purge if there is at least one expired key (on a 5% basis). Then you are left with finding if there is additional space (the return 1:0) but can't purge() return you the number of keys purged so that you could calculate if there is still space?

A more drastic change would be to find all expired keys yourself. Given that you are doing it already now, or with my above suggestion you will probably have to partially do it, it will be a benefit if you believe you can do it in a more efficient way than purge. But then you must pass that set of expired keys you found to purge() so that it does not have to re-construct it. Does it take hints? And does it return some info?

A different path would be to observe that purging will be done when there are expired keys ONLY 5% of the time (rand()<0.05). So, if there is another way to calculate whether there is space left (return @keys <= $self->{max_items} ? 1:0;) the expensive loop AND purge() could be avoided. You only have to find expired keys 5% of the time. But you need alternative way to find out if you are full.

bw, bliako

[perlancar]

Thanks for the comments. I've just scrapped the first implementation, because recording every "push" in a separate cache key quickly becomes too slow as the number of "push"es/keys range in the thousands.