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?
> 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;
}
I do see that it is not as elegant as the small_vec solution, but if
this vector is reserved as above, it should almost retain the favorable
properties our your proposed solution without the Boost dependency.
Best regards, Adam.
> 3) New with std::vector<small_vector<4, Intersection>>
> As above, but the allocation for the outer vector (size 1200) also allocates
> space for the intersections in *one contigous allocation*. Just one
> allocation
> is needed.
> Sorting is as as above
>
> | allocs | sorting
> 1) old (array) | 7 | O(N log N), N = 2400
> 2) new (vector<vector<T>>) | 1201 | O(M * N log N), M = 1200, N = 2
> 3) new (vector<small_vector<4, T>>) | 1 | O(M * N log N), M = 1200, N = 2
>
> So, (1) is slow because sorting is slow, (2) is slow because it it spends
> most
> of the time allocating. (3) is faster for allocations and sorting.
>
> 1) runsforever-poppler.pdf: 50 minutes
> 2) runsforever-poppler.pdf: 60 minutes
> 3) runsforever-poppler.pdf: 30 minutes
>
> When increasing the resolution, (2) and (3) slow down linearly, while (1)
> slows down super-linear.
>
>
>
>
> _______________________________________________
> poppler mailing list
> [email protected]
> https://lists.freedesktop.org/mailman/listinfo/poppler
>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ poppler mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/poppler
