StefanBruens authored Aug 27, 2018 and Albert Astals Cid committed Oct 05, 2018

For complex paths, a significant amount of time is spent in
SplashXPathScanner::computeIntersections, more specifically with
sorting the spans in y/x order.

Instead of using one large array for all spans, use a 2-dimensional
structure.  As the number of y positions is known upfront, it is
possible to create an array for the y dimension and insert the spans
directly at the appropriate position.

For Y rows with X spans per row, this reduces the complexity for sorting
from O( Y*X log Y*X) to O( Y * X log X), i.e. a reduction by log Y.

For the documents from #57 (fdo#96728) and #24 (fdo#78728), the
runtime/memory is significantly reduced (according to /usr/bin/time -v):
(1) $> pdftoppm -r 18 -aa no runsforever-poppler.pdf
(2) $> pdftoppm surf-types.pdf

Before/After
                                  runsforever-poppler |    surf-types
User time (seconds):                2979.80 / 2348.08 |  9.45 /  7.76
Maximum resident set size (kbytes):   51208 /   46288 | 18084 / 14076