Bug 17941 - CanBookBeRenewed is very inefficient/slow
Summary: CanBookBeRenewed is very inefficient/slow
Status: Pushed to Master
Alias: None
Product: Koha
Classification: Unclassified
Component: Hold requests (show other bugs)
Version: master
Hardware: All All
: P5 - low major (vote)
Assignee: Francesco Rivetti
QA Contact: Testopia
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2017-01-19 13:28 UTC by Petter Goksøyr Åsen
Modified: 2017-04-02 16:50 UTC (History)
7 users (show)

See Also:
Change sponsored?: ---
Patch complexity: ---
Bot Control: ---
When did the bot last check this:
Who signed the patch off:
Text to go in the release notes:


Attachments
Try to recreate CanBookBeRenewed perf issue (2.35 KB, patch)
2017-02-01 13:10 UTC, Jonathan Druart
Details | Diff | Splinter Review
local transformation that will greatly improve the performance (2.47 KB, patch)
2017-02-14 10:32 UTC, Francesco Rivetti
Details | Diff | Splinter Review
BZ 17941 typo (812 bytes, patch)
2017-02-14 11:02 UTC, Francesco Rivetti
Details | Diff | Splinter Review
BZ 17941 don't compute priority more than needed (993 bytes, patch)
2017-02-14 11:02 UTC, Francesco Rivetti
Details | Diff | Splinter Review
BZ 17941 avoid scanning the full cartesian product (2.19 KB, patch)
2017-02-14 11:02 UTC, Francesco Rivetti
Details | Diff | Splinter Review
Bug 17941 Adding PureFunctions functionality (20.35 KB, patch)
2017-02-14 11:16 UTC, Francesco Rivetti
Details | Diff | Splinter Review
Bug 17941 avoid scanning the full cartesian product (2.20 KB, patch)
2017-02-14 11:18 UTC, Francesco Rivetti
Details | Diff | Splinter Review
Bug 17941 don't compute priority more than needed (994 bytes, patch)
2017-02-14 11:18 UTC, Francesco Rivetti
Details | Diff | Splinter Review
Bug 17941 typo (813 bytes, patch)
2017-02-14 11:18 UTC, Francesco Rivetti
Details | Diff | Splinter Review
Bug 19741 more typos (987 bytes, patch)
2017-02-14 11:18 UTC, Francesco Rivetti
Details | Diff | Splinter Review
Bug 17941 add tests to cover the optimization of the nested loop (4.92 KB, patch)
2017-02-20 10:19 UTC, Francesco Rivetti
Details | Diff | Splinter Review
Bug 17941 avoid scanning the full cartesian product (2.24 KB, patch)
2017-02-20 16:10 UTC, M. Tompsett
Details | Diff | Splinter Review
Bug 17941 don't compute priority more than needed (1.02 KB, patch)
2017-02-20 16:10 UTC, M. Tompsett
Details | Diff | Splinter Review
Bug 17941 add tests to cover the optimization of the nested loop (4.97 KB, patch)
2017-02-20 16:10 UTC, M. Tompsett
Details | Diff | Splinter Review
Bug 17941 avoid scanning the full cartesian product (2.31 KB, patch)
2017-02-22 11:08 UTC, Jonathan Druart
Details | Diff | Splinter Review
Bug 17941 don't compute priority more than needed (1.09 KB, patch)
2017-02-22 11:08 UTC, Jonathan Druart
Details | Diff | Splinter Review
Bug 17941 add tests to cover the optimization of the nested loop (5.07 KB, patch)
2017-02-22 11:08 UTC, Jonathan Druart
Details | Diff | Splinter Review

Note You need to log in before you can comment on or make changes to this bug.
Description Petter Goksøyr Åsen 2017-01-19 13:28:25 UTC
I started investigating why populating the checkout list in the patron view sometimes took ages (minutes), and on occations even causing the system to almost halt because of DB overload. It turned out that reason is calls to C4::Circulation::CanBookBeRenewed. The critical factor is whether an item has many holds on it, and if there are many items that can fill the hold.

Briefly looking at the code it seems obvious that the time spent grows exponentially with the number of holds and items.

As one example, checking if an item with 111 holds (and 12 items on the biblio) can be renewed takes around 25 sec and generates over 18,000 SQL queries. 

I can't help to think there must be some missed "early returns" opportunities in the loops somewhere. For example, if there are more unfulfilled holds than available items, can the item ever be renewed? If no, return before even begin to calculate.. However, I know holds are full of complexities and things I probably haven't thought about so I need to dig into the code more.

I would be very gratefull if anyone knowledgeable about this part of the code could help me find some ways to optimize this!
Comment 1 Jonathan Druart 2017-02-01 13:10:12 UTC
Created attachment 59740 [details] [review]
Try to recreate CanBookBeRenewed perf issue
Comment 2 Jonathan Druart 2017-02-01 13:12:05 UTC
Hi Petter,
I'd be interested to recreate the perf issue.
I have written this quick script, it generates 20 items, 200 patrons and generate a hold for each patron.

On the second run, I comment everything but the last 2 lines and execute again the script. It is executed in 1.5s
Comment 3 Petter Goksøyr Åsen 2017-02-01 13:58:48 UTC
Hi Jonathan. Thanks for looking into this!
We were actually working on this problem right now, so I have some information.
The code in question is quite complicated, so I'm not sure I understand it, but it seems that the pathological cases are when most of the items are checked out, so it needs to check every permutation of item, hold, and borrower to check if it can be renewed. But I'm not 100% sure about it.

Rather than trying to understand how all the holds logic work in order to fix this properly, we have made a patch now, that greatly improves the speed. This is done by memoizing idempotent DB calls (GetItem, GetMembers and so on), during the scope of CanBookBeRenewed. It helps a lot, because sometimes the same item is fetched again and again, 100s to even 1000s of times from the DB!

In one case, by using the patch, the display of checkout tab with 5 items goes from around 20 seconds to 3 seconds, 

We do belive this patch is a good step forward, but we will test it extensivly in staging environment before we submit it.

I'll try see if I can get some interesting result from your script.
Comment 4 Jonathan Druart 2017-02-01 14:11:35 UTC
(In reply to Petter Goksøyr Åsen from comment #3)
> We do belive this patch is a good step forward, but we will test it
> extensivly in staging environment before we submit it.

No do not wait, release as soon as you can :)
Comment 5 Petter Goksøyr Åsen 2017-02-01 14:24:40 UTC
(In reply to Jonathan Druart from comment #4)

> No do not wait, release as soon as you can :)

OK, for the adventurous:
https://gist.github.com/boutros/c3a63904c788d0a6336023042ce22cde

We recently hired a very experienced Perl guy, so he's behind this, not me:) But it's very simple actually: just by decorating subroutines with ": PureFunction" - you get memoization for free!

The actuall PureFunctions module is maybe not for the faint of heart, but it's very small, and I do belive it works out very beautifull. And as this is not a persistent cache, but only valid during the scope of the request, we don't have to deal with cache invalidation and such problems.

The solution can easily be extended to other Getter-methods, as long as they are idempotent (which they should be).
Comment 6 Jonathan Druart 2017-02-01 14:50:59 UTC
Hum, are you sure this is Plack-compatible?
Comment 7 Petter Goksøyr Åsen 2017-02-01 17:39:37 UTC
(In reply to Jonathan Druart from comment #6)
> Hum, are you sure this is Plack-compatible?

It should be. I've been testing under Plack today without experiencing any issues, and it certainly seems to work fine. But I haven't profiled for memory leaks yet.
Comment 8 Francesco Rivetti 2017-02-01 21:24:01 UTC
Hi! I can't think of any issue with plack or apache.

The only problem I had implementing it is the race with Exporter:

Attribute::Handlers apply attributes at CHECK time, while Exporter at BEGIN time. I found a easy way to convince A::H to replace the methods at BEGIN time, but I believe the order in the @ISA must be preserved.

But I don't consider this a proper fix, I just lack the experience to understand the whole logic behind it yet.
Comment 9 Petter Goksøyr Åsen 2017-02-07 11:01:17 UTC
Some adittional evidence from testings Fransesco's patch:

Here are the stats of cache hits/misses from one call to /svc/checkouts (on a patron with 5 checkouts, 2 of them which has many holds)

                                              hit   miss
C4::Circulation::GetBranchItemRule            4537  21
C4::Reserves::_OnShelfHoldsAllowed            13    116
C4::Reserves::IsAvailableForItemLevelRequest  0     129
C4::Circulation::CanBookBeRenewed             0     5
C4::Items::GetItem                            4845  33
C4::Members::GetMember                        4075  584
C4::Reserves::CheckReserves                   0     53
C4::Reserves::CanItemBeReserved               0     129
C4::Reserves::IsItemOnHoldAndFound            24    239

As you can see, we save almost 15 thousand DB-queries here!

We are most probably pushing this into production today.
Comment 10 Alex Sassmannshausen 2017-02-08 11:58:22 UTC
Hello,

This looks like a really interesting hack! Thanks for sharing :-)

In terms of using it in Koha, I have some questions:

- Documentation for Attributes mentions it is experimental and the internal API may change.  We may need to consider whether this is a risk for Koha?  Does anyone know what the status is on that?
(http://perldoc.perl.org/attributes.html)

- I too, like Jonathan, worry slightly about Plack implications.  It may just be that I don't quite understand how long the cache exists — but it seems to me that in a Plack context the cache that is created by memoization here would not be busted.  This would be problematic as follows:

 + GetMember memoizes a call to a specific borrowernumber
 + Another user in Plack updates the borrower details
 + Next call to GetMember returns memoized result, not the updated result.

How is the cache expired?

It could be that Plack in CGI compatibility mode does the expiring for us, so it might work well in practice — Petter could you confirm whether you tested this kind of use-case or similar ones?

To be specific, some of the calls that are Memoized are only Idempotent in the context of no other db updates happening.  In CGI context, this is no problem.  In long-living Plack processes this *may* be a problem.

Anyway, like I say — love the optimization! :-D

Alex
Comment 11 Francesco Rivetti 2017-02-08 12:15:36 UTC
(In reply to Alex Sassmannshausen from comment #10)
> - Documentation for Attributes mentions it is experimental and the internal
> API may change.  We may need to consider whether this is a risk for Koha? 
> Does anyone know what the status is on that?
> (http://perldoc.perl.org/attributes.html)

yes, I read it as some attributes might change, or added. I used uppercase naming to avoid future conflicts.

> - I too, like Jonathan, worry slightly about Plack implications.  It may
> just be that I don't quite understand how long the cache exists — but it
> seems to me that in a Plack context the cache that is created by memoization
> here would not be busted.  This would be problematic as follows:
> 
>  + GetMember memoizes a call to a specific borrowernumber
>  + Another user in Plack updates the borrower details
>  + Next call to GetMember returns memoized result, not the updated result.
> 
> How is the cache expired?

I'm working on documenting that hack a bit better, but the whole system relies on:

local $CACHE = $CACHE//{};

this is a bit of perl trickery here, because the "local" will make a new "version" of $CACHE while the scope it is in is still alive.

on the other end, the new "version" will use the same "instance" if available, which means that you can be sure that only one cache is shared but it won't live longer than the life of the first pure function life.

in other words, when the { local $CACHE = $CACHE//{}; .... } block goes out of scope, it will revert to the previous version of CACHE, which will (and MUST be) undef at plack time.

> To be specific, some of the calls that are Memoized are only Idempotent in
> the context of no other db updates happening.  In CGI context, this is no
> problem.  In long-living Plack processes this *may* be a problem.

You are absolutely right, and it is designed to be safe in this case.

you can actually push even further.

sub hybrid {
  pure(); # all happening inside this function will be memoized _temporary_
  db_change();
  pure(); # a new cache will be used here, with new data from db
}

or, in case you need it you could:

sub hybrid {

  K::U::PF::pure { # start a new cache
    for (...) {
      pure($_);
    }
  }; # cache is destroyed

  db_change();

  pure(); # new cache
}

I'm also adding another attribute which will throw an error in case like this

sub db_changes : ImpureFunction {
  ...
}

sub pure : PureFunction {
  db_changes(); # db_changes is marked as not pure, and will complain
}

and while we are in topic, any suggestions for the "Impure" function?
Comment 12 Francesco Rivetti 2017-02-14 10:32:44 UTC
Created attachment 60181 [details] [review]
local transformation that will greatly improve the performance
Comment 13 Francesco Rivetti 2017-02-14 10:35:04 UTC
I found few more spot where some optimization was easy to add, and should definitely make it faster. I still think using pure functions helps in general, but this is probably a better and easier fix.
Comment 14 Francesco Rivetti 2017-02-14 11:02:11 UTC
Created attachment 60184 [details] [review]
BZ 17941 typo
Comment 15 Francesco Rivetti 2017-02-14 11:02:24 UTC
Created attachment 60185 [details] [review]
BZ 17941 don't compute priority more than needed
Comment 16 Francesco Rivetti 2017-02-14 11:02:35 UTC
Created attachment 60186 [details] [review]
BZ 17941 avoid scanning the full cartesian product

when a item match a borrower, there is no point in checking the
other borrowers
Comment 17 Francesco Rivetti 2017-02-14 11:03:25 UTC
as per Joubu request on irc, sending the patches again via git-bz
Comment 18 Francesco Rivetti 2017-02-14 11:16:45 UTC
Created attachment 60188 [details] [review]
Bug 17941 Adding PureFunctions functionality
Comment 19 Francesco Rivetti 2017-02-14 11:18:10 UTC
Created attachment 60189 [details] [review]
Bug 17941 avoid scanning the full cartesian product

when a item match a borrower, there is no point in checking the
other borrowers
Comment 20 Francesco Rivetti 2017-02-14 11:18:25 UTC
Created attachment 60190 [details] [review]
Bug 17941 don't compute priority more than needed
Comment 21 Francesco Rivetti 2017-02-14 11:18:36 UTC
Created attachment 60191 [details] [review]
Bug 17941 typo
Comment 22 Francesco Rivetti 2017-02-14 11:18:47 UTC
Created attachment 60192 [details] [review]
Bug 19741 more typos
Comment 23 M. Tompsett 2017-02-15 00:30:25 UTC
Comment on attachment 60189 [details] [review]
Bug 17941 avoid scanning the full cartesian product

Review of attachment 60189 [details] [review]:
-----------------------------------------------------------------

Love the optimization, but two tiny code changes would improve readability.

::: C4/Circulation.pm
@@ +2683,5 @@
> +            ITEM: foreach my $i (@itemnumbers) {
> +                my $item = GetItem($i);
> +                next if IsItemOnHoldAndFound($i);
> +                for my $b (@borrowernumbers) {
> +                    my $borr = $borrowers{$b}//= C4::Members::GetMember(borrowernumber => $_);

Could we avoid $_? It is harder to read. Here it should be $b.

@@ +2687,5 @@
> +                    my $borr = $borrowers{$b}//= C4::Members::GetMember(borrowernumber => $_);
> +                    next unless IsAvailableForItemLevelRequest($item, $borr);
> +                    next unless CanItemBeReserved($b,$i);
> +
> +                    push @reservable;

The old code is pushing item numbers into the reservable array. This seems to be using an implicit $_ type behaviour, which I believe is $b. This isn't code equivalent, and explicit is always easier for debugging later. Though, I don't think it will matter, which is probably why it was optimized this way. Still, could we be explicit? It's easier to read.
Comment 24 M. Tompsett 2017-02-15 00:31:53 UTC
Comment on attachment 60191 [details] [review]
Bug 17941 typo

Review of attachment 60191 [details] [review]:
-----------------------------------------------------------------

::: C4/Circulation.pm
@@ +2688,4 @@
>                      next unless IsAvailableForItemLevelRequest($item, $borr);
>                      next unless CanItemBeReserved($b,$i);
>  
> +                    push @reservable, $i;

Ah, you caught it. Great!
Comment 25 M. Tompsett 2017-02-15 00:32:20 UTC
Comment on attachment 60192 [details] [review]
Bug 19741 more typos

Review of attachment 60192 [details] [review]:
-----------------------------------------------------------------

::: C4/Circulation.pm
@@ +2684,4 @@
>                  my $item = GetItem($i);
>                  next if IsItemOnHoldAndFound($i);
>                  for my $b (@borrowernumbers) {
> +                    my $borr = $borrowers{$b}//= C4::Members::GetMember(borrowernumber => $b);

Sweet! Let's get some sign off. :)
Comment 26 M. Tompsett 2017-02-15 05:36:41 UTC
(In reply to M. Tompsett from comment #25)
> Sweet! Let's get some sign off. :)

t/db_dependent/Circulation.t does a good job of testing the revision, except for one case!

2675             # If the count of the union of the lists of reservable items for each borrower
2676             # is equal or greater than the number of borrowers, we know that all reserves
2677             # can be filled with available items. We can get the union of the sets simply
2678             # by pushing all the elements onto an array and removing the duplicates.
2679             my @reservable;
2680             my %borrowers;
2681             print STDERR "check 1\n";
2682             ITEM: foreach my $i (@itemnumbers) {
2683             print STDERR "check 2\n";
2684                 my $item = GetItem($i);
2685                 next if IsItemOnHoldAndFound($i);
2686             print STDERR "check 3\n";
2687                 for my $b (@borrowernumbers) {
2688             print STDERR "check 4\n";
2689                     my $borr = $borrowers{$b}//= C4::Members::GetMember(borrowernumber => $b);
2690                     next unless IsAvailableForItemLevelRequest($item, $borr);
2691             print STDERR "check 5\n";
2692                     next unless CanItemBeReserved($b,$i);
2693             print STDERR "check 6\n";
2694
2695                     push @reservable, $i;
2696                     if (@reservable >= @borrowernumbers) {
2697             print STDERR "check 7\n";
2698                         $resfound = 0;
2699                         last ITEM;
2700                     }
2701             print STDERR "check 8\n";
2702                     last;
2703                 }
2704             }

As you can see, I added print statements, "check 8" is not triggered.

$ git checkout -b bug_17941 origin/master
$ git bz apply 17941
-- add in the STDERR's above.
$ sudo koha-shell -c bash kohadev
K$ prove -v t/db_dependent/Circulation.t 2>&1 | grep check | sort -u
-- output has check 1 through check 7, but not check 8.

So, if you could add a test which triggers check 8, that would be good.
Comment 27 Francesco Rivetti 2017-02-15 09:05:51 UTC
(In reply to M. Tompsett from comment #26)
> As you can see, I added print statements, "check 8" is not triggered.

oh great, got it. Will do asap and add a new patch

F
Comment 28 Francesco Rivetti 2017-02-20 10:19:59 UTC
Created attachment 60457 [details] [review]
Bug 17941 add tests to cover the optimization of the nested loop

the new code skip testing for more borrowers if the item can't be renewed
this require more tests for the case where 2+ items are reserved.

I tried to add 1 more reserve to the main test suit, but too many other tests
rely on specific holds, and I couldn't get around it.

Instead, I added a subtest that consider the specific simple case and leave the
other test cases exactly has they were designed.
Comment 29 Francesco Rivetti 2017-02-20 10:24:05 UTC
(In reply to M. Tompsett from comment #26)
> So, if you could add a test which triggers check 8, that would be good.

done, sorry it took a while!

I ended up adding a new subtest for this, since the complexity of the other tests made it a bit too hard for me to integrate it. It should cover all the cases of the new algorithm.
Comment 30 M. Tompsett 2017-02-20 16:10:23 UTC
Created attachment 60472 [details] [review]
Bug 17941 avoid scanning the full cartesian product

when a item match a borrower, there is no point in checking the
other borrowers

Signed-off-by: Mark Tompsett <mtompset@hotmail.com>
Comment 31 M. Tompsett 2017-02-20 16:10:30 UTC
Created attachment 60473 [details] [review]
Bug 17941 don't compute priority more than needed

Signed-off-by: Mark Tompsett <mtompset@hotmail.com>
Comment 32 M. Tompsett 2017-02-20 16:10:37 UTC
Created attachment 60474 [details] [review]
Bug 17941 add tests to cover the optimization of the nested loop

the new code skip testing for more borrowers if the item can't be renewed
this require more tests for the case where 2+ items are reserved.

I tried to add 1 more reserve to the main test suit, but too many other tests
rely on specific holds, and I couldn't get around it.

Instead, I added a subtest that consider the specific simple case and leave the
other test cases exactly has they were designed.

Signed-off-by: Mark Tompsett <mtompset@hotmail.com>
Comment 33 M. Tompsett 2017-02-20 16:12:35 UTC
The test cases cover the changes now. Thank you, Francesco Rivetti.
Comment 34 Jonathan Druart 2017-02-22 11:08:29 UTC
Created attachment 60544 [details] [review]
Bug 17941 avoid scanning the full cartesian product

when a item match a borrower, there is no point in checking the
other borrowers

Signed-off-by: Mark Tompsett <mtompset@hotmail.com>

Signed-off-by: Jonathan Druart <jonathan.druart@bugs.koha-community.org>
Comment 35 Jonathan Druart 2017-02-22 11:08:33 UTC
Created attachment 60545 [details] [review]
Bug 17941 don't compute priority more than needed

Signed-off-by: Mark Tompsett <mtompset@hotmail.com>

Signed-off-by: Jonathan Druart <jonathan.druart@bugs.koha-community.org>
Comment 36 Jonathan Druart 2017-02-22 11:08:37 UTC
Created attachment 60546 [details] [review]
Bug 17941 add tests to cover the optimization of the nested loop

the new code skip testing for more borrowers if the item can't be renewed
this require more tests for the case where 2+ items are reserved.

I tried to add 1 more reserve to the main test suit, but too many other tests
rely on specific holds, and I couldn't get around it.

Instead, I added a subtest that consider the specific simple case and leave the
other test cases exactly has they were designed.

Signed-off-by: Mark Tompsett <mtompset@hotmail.com>

Signed-off-by: Jonathan Druart <jonathan.druart@bugs.koha-community.org>
Amended-patch: Just fix 3 indendations
Comment 37 Kyle M Hall 2017-03-03 16:52:04 UTC
Pushed to master for 17.05, thanks Francesco!
Comment 38 Petter Goksøyr Åsen 2017-03-06 14:24:52 UTC
> Pushed to master for 17.05, thanks Francesco!

It does not appear to be pushed:
http://git.koha-community.org/gitweb/?p=koha.git;a=shortlog
Comment 39 Petter Goksøyr Åsen 2017-03-06 14:25:45 UTC
(In reply to Petter Goksøyr Åsen from comment #38)
> > Pushed to master for 17.05, thanks Francesco!
> 
> It does not appear to be pushed:
> http://git.koha-community.org/gitweb/?p=koha.git;a=shortlog

Forget it, I'm blind!
Comment 40 Katrin Fischer 2017-03-12 22:26:14 UTC
This seems to use some new constructs, is this safe for backporting to 16.11.x?
Comment 41 Jonathan Druart 2017-03-14 13:31:16 UTC
(In reply to Katrin Fischer from comment #40)
> This seems to use some new constructs, is this safe for backporting to
> 16.11.x?

That would need to be tested, I only tested against master.
Comment 42 Katrin Fischer 2017-03-14 16:38:32 UTC
I will watch this a bit longer and consider pushing it to the next 16.11.x release.
Comment 43 Francesco Rivetti 2017-03-27 14:21:16 UTC
(In reply to Jonathan Druart from comment #41)
> (In reply to Katrin Fischer from comment #40)
> > This seems to use some new constructs, is this safe for backporting to
> > 16.11.x?
> 
> That would need to be tested, I only tested against master.

Agreed. I don't see why it shouldn't work, but that should be tested before.

F
Comment 44 Katrin Fischer 2017-04-02 16:50:02 UTC
If someone would be willing to test and sign-off for 16.11.x, I am willing to push this :)