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!
Created attachment 59740 [details] [review] Try to recreate CanBookBeRenewed perf issue
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
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.
(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 :)
(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).
Hum, are you sure this is Plack-compatible?
(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.
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.
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.
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
(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?
Created attachment 60181 [details] [review] local transformation that will greatly improve the performance
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.
Created attachment 60184 [details] [review] BZ 17941 typo
Created attachment 60185 [details] [review] BZ 17941 don't compute priority more than needed
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
as per Joubu request on irc, sending the patches again via git-bz
Created attachment 60188 [details] [review] Bug 17941 Adding PureFunctions functionality
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
Created attachment 60190 [details] [review] Bug 17941 don't compute priority more than needed
Created attachment 60191 [details] [review] Bug 17941 typo
Created attachment 60192 [details] [review] Bug 19741 more typos
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 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 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. :)
(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.
(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
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.
(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.
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>
Created attachment 60473 [details] [review] Bug 17941 don't compute priority more than needed Signed-off-by: Mark Tompsett <mtompset@hotmail.com>
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>
The test cases cover the changes now. Thank you, Francesco Rivetti.
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>
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>
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
Pushed to master for 17.05, thanks Francesco!
> 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
(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!
This seems to use some new constructs, is this safe for backporting to 16.11.x?
(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.
I will watch this a bit longer and consider pushing it to the next 16.11.x release.
(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
If someone would be willing to test and sign-off for 16.11.x, I am willing to push this :)
3 months - closing this now.