Re: Optimizing a CHI-based data throttler

As noted in my other comment, I'm scrapping this first implementation because it quickly becomes too slow when the number of keys/hits reaches thousands. I'm now using the "buckets" approach like done in Data::Throttler. And my module is now consistently an order of magnitude slower than Data::Throttler for various values of max_items.

package Data::Throttler_CHI;

use strict;
use warnings;

use List::Util qw(sum);

sub new {
    my ($class, %args) = @_;

    defined $args{max_items} or die "new: Please specify max_items";
    $args{max_items} >= 1    or die "new: max_items must be at least 1
+";
    defined $args{interval}  or die "new: Please specify interval";
    $args{interval} >= 1     or die "new: interval must be at least 1"
+;
    defined $args{cache}     or die "new: Please specify cache";

    # calculate nof_buckets
    my $nof_buckets;
    if (defined $args{nof_buckets}) {
        $args{nof_buckets} >= 1 or die "new: nof_buckets must be at le
+ast 1";
        $nof_buckets = $args{nof_buckets};
    } else {
        $nof_buckets = $args{interval} ** 0.5;
    }
    $nof_buckets = int($nof_buckets);

    my $self = {
        t0              => time(),
        max_items       => $args{max_items},
        interval        => $args{interval},
        cache           => $args{cache},
        nof_buckets     => $nof_buckets,
        secs_per_bucket => $args{interval} / $nof_buckets,
    };
    bless $self, $class;
}

sub try_push {
    my $self = shift;

    my $now = time();

    my $secs_after_latest_interval = ($now - $self->{t0}) % $self->{in
+terval};
    my $bucket_num = int(
        $secs_after_latest_interval / $self->{interval} * $self->{nof_
+buckets}
    ) + 1; # 1 .. nof_buckets

    my $hits = $self->{cache}->get("hits.$bucket_num");

    my $all_hits = $self->{cache}->get_multi_arrayref(
        [map {"hits.$_"} 1..$self->{nof_buckets}]);
    my $total_hits = sum(grep {defined} @$all_hits) || 0;

    return 0 if $total_hits >= $self->{max_items};

    if ($hits) {
        $self->{cache}->set(
            "hits.$bucket_num", $hits+1,
            {expires_at=>$self->{cache}->get_expires_at("hits.$bucket_
+num")});
    } else {
        $self->{cache}->set(
            "hits.$bucket_num", 1,
            {expires_at => $now + $self->{interval} - $secs_after_late
+st_interval + ($bucket_num-1) * $self->{secs_per_bucket}});
    }

    1;
}

1;
[download]

Once again, the more complete version resides on CPAN.

Comment on Re: Optimizing a CHI-based data throttler Download Code

Replies are listed 'Best First'.
Re^2: Optimizing a CHI-based data throttler by bliako (Abbot) on Feb 20, 2020 at 13:17 UTC
Now, performance obviously depends on CHI's search/get/set and I don't know what that is (can't see that from a diagonal look at the documentation). But something obvious is that Data::Throttler uses the notion of buckets, which are counters for a time range. And from what I can gather it uses an array to store those buckets. But you (CHI that is) use a hashtable (I guess?). So there is definetely a penalty there in terms of amortized performance but definetely it is not accounting for the order of magnitude you observe. But, still, the advantage of Data::Throttler is that it uses data structures and algorithms for that specific use-case (of summing buckets). It pays to be specific. So, it costs time to create the list of indices of items, fetch them and then sum them, as you do. Data::Throttler will only sum a continuous range (i.e. a loop) in its internal buckets array. That's a 3rd of your cost already. If CHI had a method to apply an operation (sum) over a list of indices or better still a continuous range of items, you could cut your costs a bit. But then that's not something one would expect from cache storage! The "really bad" news is that Data::Throttler can optimise its internal logic even more. And also add more features. Can you keep up with that by using a generic tool? Having said all that, I can think of one way to improve performance (but then Data::Throttler can also do that and be ahead, again). Instead of having each bucket storing a count of hits over its time-interval, make it keep an incremental count of hits. I.e. keep the sum of counts in each bucket of all its previous buckets (not the dead ones). In this way you do not need to do a sum each time `try_push()` is called. You will have that sum ready waiting for you in the last bucket. However, that sum will be invalid once a bucket is too old and had to be removed. Whenever a bucket gets too old, you have to subtract its count from the total count. So, create a function `total_count()` which either re-calculates the count if buckets were invalidated since last time it was called, or returns a cached count. Re-calculating is really easy: subtract the difference of the old bucket's count to its newer neighbour from all buckets. Then, if a hit is added, you only need to add it to the newest bucket. The total count will be held by the newest bucket and will need to be re-calculated if you ask for it after time-interval seconds since last time you called it. So, here is finally some use of cache :) bw, bliako	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^2: Optimizing a CHI-based data throttler
by bliako (Abbot) on Feb 20, 2020 at 13:17 UTC

Now, performance obviously depends on CHI's search/get/set and I don't know what that is (can't see that from a diagonal look at the documentation).

But something obvious is that Data::Throttler uses the notion of buckets, which are counters for a time range. And from what I can gather it uses an array to store those buckets. But you (CHI that is) use a hashtable (I guess?). So there is definetely a penalty there in terms of amortized performance but definetely it is not accounting for the order of magnitude you observe. But, still, the advantage of Data::Throttler is that it uses data structures and algorithms for that specific use-case (of summing buckets). It pays to be specific.

So, it costs time to create the list of indices of items, fetch them and then sum them, as you do. Data::Throttler will only sum a continuous range (i.e. a loop) in its internal buckets array. That's a 3rd of your cost already. If CHI had a method to apply an operation (sum) over a list of indices or better still a continuous range of items, you could cut your costs a bit. But then that's not something one would expect from cache storage!

The "really bad" news is that Data::Throttler can optimise its internal logic even more. And also add more features. Can you keep up with that by using a generic tool?

Having said all that, I can think of one way to improve performance (but then Data::Throttler can also do that and be ahead, again). Instead of having each bucket storing a count of hits over its time-interval, make it keep an incremental count of hits. I.e. keep the sum of counts in each bucket of all its previous buckets (not the dead ones). In this way you do not need to do a sum each time try_push() is called. You will have that sum ready waiting for you in the last bucket. However, that sum will be invalid once a bucket is too old and had to be removed. Whenever a bucket gets too old, you have to subtract its count from the total count. So, create a function total_count() which either re-calculates the count if buckets were invalidated since last time it was called, or returns a cached count. Re-calculating is really easy: subtract the difference of the old bucket's count to its newer neighbour from all buckets. Then, if a hit is added, you only need to add it to the newest bucket. The total count will be held by the newest bucket and will need to be re-calculated if you ask for it after time-interval seconds since last time you called it. So, here is finally some use of cache :)

bw, bliako

[reply]
[d/l]
[select]