[poppler] [PATCH 4/4] SplashXPathScanner: Reduce complexity of sorting spans

[Stefan Brüns]

On Samstag, 26. Mai 2018 19:06:02 CEST Adam Reichold wrote:
> Am 26.05.2018 um 17:48 schrieb Stefan Brüns:
> > On Samstag, 26. Mai 2018 17:11:41 CEST Adam Reichold wrote:
> >> Hello again,
> >> 
> >> Am 26.05.2018 um 16:22 schrieb Stefan Brüns:
> >>> Unfortunately, it gives only a 100% speed increase (i.e. 30 minutes with
> >>> small_vector, 60 minutes with std::vector), so probably I should stop
> >>> here.
> >> 
> >> I am unsure about the level of irony involved, but I also do not fully
> >> understand the numbers: In your previous mail you wrote
> > 
> > 30 minutes with std::vector<small_vector<...>>, 60 minutes with
> > std::vector<std::vector<...>>. I was only referring to the option of not
> > using boost here.
> > 
> >>> Before:
> >>> - User time (seconds): 2979.80
> >>> - Maximum resident set size (kbytes): 51208
> >>> 
> >>> After:
> >>> - User time (seconds): 1773.53
> >>> - Maximum resident set size (kbytes): 45896
> >> 
> >> i.e. ca. 60 minutes without your changes (algorithm + allocations) and
> >> ca. 30 minutes with them. Now you write that changing only algorithm but
> >> not changing the allocation brings you back to 60 minutes? Does this
> >> mean that basically all of the speed-up is due to the use of small_vec
> >> instead vector?
> >> 
> >> If I misunderstood that and you meant the 100% w.r.t. changing algorithm
> >> + allocations, then producing a measurement where just vector instead of
> >> small_vec is used would probably be interesting. And it would be another
> >> reason to break out that part of the patch.
> > 
> > Assuming just drawing one simple convex polygon with height 1200 scanlines
> > (300px with 4xAA):
> > 
> > 1) Old with Intersection[]:
> > Uses one large vector/array for all scanline intersections of a polygon.
> > There is on scanline for each output pixel, or (typically) 4 when using
> > Antialiasing. I.e. for the simple polygon, you have 2400 intersections.
> > The
> > size of the array grows by 2 each time (starting with 32), so the array is
> > realloced 7 times until it has space for 4096 elements.
> > After filling the array, it is sorted in y/x order, i.e. O(N log N), N =
> > 2400.
> So a first measure to reserve the intersection array based on the number
> of scanlines and small_vec size, e.g. 4  * scanlines to get this down to
> one allocation as well?

One vs. 7 allocations is insignifant.

> > 2) New with std::vector<std::vector<Intersection>>
> > The outer vector is set to size=1200 (number of scanlines is known
> > a-priori). Each time an intersection is added, the inner vector grows,
> > eventually forcing a reallocation. 1201 allocations are needed.
> > After filling the array, each row is sorted, i.e. O(M * N log N), M =
> > 1200, N = 2.
> 
> Couldn't this also be realized using std::vector<Intersection> and a
> separate std::vector<std::size_t> which keeps track of how many
> intersections are within each scanline to keep everything within a
> contiguous buffer? E.g.
> 
> auto first = intersections.begin();
> for (y for all scanlines) {
>    const auto last = first + intersections_per_scanline[y];
>    std::sort(first, first + count, IntersectionCmp());
>    first = last;
> }

Sorting is not the problem with this solution, but inserting at the 
appropriate place.

As long as intersections_per_scanline is < 4, you can insert in the contigous 
array. As soon as you overflow, you have to allocate a new buffer, move the 
old contents to the new place, and store a pointer and the allocation size 
somewhere (preferably in the contigous array, to avoid another storage space).

If you have done that, you have reinvented small_vector.

Regards,

Stefan

-- 
Stefan Brüns  /  Bergstraße 21  /  52062 Aachen
home: +49 241 53809034     mobile: +49 151 50412019
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 195 bytes
Desc: This is a digitally signed message part.
URL: <https://lists.freedesktop.org/archives/poppler/attachments/20180526/24724b54/attachment.sig>