1 I benchmarked a build of a large wiki (my home wiki), and it was spending
2 quite a lot of time sorting; `CORE::sort` was called only 1138 times, but
3 still flagged as the #1 time sink. (I'm not sure I trust NYTProf fully
4 about that FWIW, since it also said 27238263 calls to `cmp_age` were
5 the #3 timesink, and I suspect it may not entirely accurately measure
6 the overhead of so many short function calls.)
8 `pagespec_match_list` currently always sorts *all* pages first, and then
9 finds the top M that match the pagespec. That's innefficient when M is
10 small (as for example in a typical blog, where only 20 posts are shown,
11 out of maybe thousands).
13 As [[smcv]] noted, It could be flipped, so the pagespec is applied first,
14 and then sort the smaller matching set. But, checking pagespecs is likely
15 more expensive than sorting. (Also, influence calculation complicates
16 doing that, since only influences for the M returned pages should be tracked.)
18 Another option, when there is a limit on M pages to return, might be to
19 cull the M top pages without sorting the rest. This could be done using
20 a variant of Ye Olde Bubble Sort. Take the first M pages, and (quick)sort.
21 Then for each of the rest, check if it is higher than the Mth page.
22 If it is, bubble it up so it's sorted.
23 If not, throw it out (that's the fast bit and why this is not O(N^2)).
25 This would be bad when M is very large, and particularly, of course, when
26 there is no limit and all pages are being matched on. (For example, an
27 archive page shows all pages that match a pagespec specifying a creation
28 date range.) Well, in this case, it *does* make sense to flip it, limit by
29 pagespe first, and do a (quick)sort second. (No influence complications,
32 > Flipping when there's no limit implemented, and it knocked 1/3 off
33 > the rebuild time of my blog's archive pages. --[[Joey]]
35 Adding these special cases will be more complicated, but I think the best
36 of both worlds. --[[Joey]]