WillPaginate::LinkRenderer#visible_page_numbers is O(N^2)

[chaptastic]

The method used to generate the list of visible page numbers is wildly inefficient if you have a large number of pages. I've reworked the algorithm to run in constant time. A patch with the update is available here: https://gist.github.com/f2f3869f01f0fbb1554d

[mislav]

You wrote this against a fairly old version of will_paginate. If you check the latest master (which is also the latest stable release) you'll see that the calculation is much more optimized. I welcome you to try and improve that ;)

[chaptastic]

The code for visible_page_numbers is unchanged between the current master and the version I patched against.

[chaptastic]

I realize I was a bit flip in my original posting, but I do think this is a rather serious issue for the case of a large number of pages. visible_page_numbers generates an array for the range (1..total_pages) then subtracts arrays for the two gaps. When the starting array and the gaps are large this is an O(N^2) operation. I found this in production and it was having a significant impact on page speed.

[mislav]

I'm sorry, I told you false information. The optimization is not in master yet; it is in the "agnostic" branch in this commit: c5d532f

I've been certain that I cherry-picked this into master and made a new stable release, but I forgot. The agnostic branch is preparation for will_paginate 3.0, but I won't expect everyone to upgrade right away so I want this optimization in 2.3.x version, too.

You can check this optimization and see if yours is better, then improve the agnostic branch, then I will cherry-pick the whole thing back into master.