Sod will_paginate library

visible_page_numbers will take a very long time if the number of pages you have is large, say if you are returning web search results that have millions of pages.

Here is the offending code:

  visible   = (1..total_pages).to_a <<< O(n)
  left_gap  = (2 + outer_window)...window_from
  right_gap = (window_to + 1)...(total_pages - outer_window) <<< Again
  visible  -= left_gap.to_a  if left_gap.last - left_gap.first > 1
  visible  -= right_gap.to_a if right_gap.last - right_gap.first > 1

Here is a potential fix that only depend on the size of inner+outer window:

# these are always visible
visible   = (window_from..window_to).to_a

# left window
if window_from > (outer_window + 1) # fully visible
  visible = ((1..(outer_window+1)).to_a + visible)
else # runs into visible pages
  visible = (1...window_from).to_a + visible
end

# right window
if window_to < (total_pages - outer_window) # fully visible
  visible = (visible + (total_pages - outer_window..total_pages).to_a)
else # runs into visible pages
  visible = visible + ((window_to+1)..total_pages).to_a
end