[Qgis-developer] Parallel Development

[Martin Dobias]

On Mar 4, 2013 11:38 PM, "Matthias Kuhn" <matthias.kuhn at gmx.ch> wrote:
>
> Hi Benjamin,
>
> Thank you for your interest in the project.
> I was looking at a problem today and thought of your mail to the list.
> In case you still would like to contribute to QGIS with a task concerning
parallelisation, I would have a place, where I can imagine a true benefit
of this.
> QGIS makes use of the PAL library, which allows for automated placement
of labels [1] using collision detection. To my knowledge (pardon me if I'm
wrong), this library is not widely used outside of QGIS. Unfortunately it
can be really time consuming, as it compares each possible label position
to each other. I think that this job could greatly profit from being split
between different cores.
> While I'm not the author of this library, my understanding is that the
loop on line 579 in pal.cpp [2] could be a place to start. If this loop
could be split up into chunks being worked on by different threads, overall
performance would benefit.

Hi Matthias

>From what I remember the main source of PAL speed issues were the
underlying geometry algorithms, especially when working with polygons
(instead of the label placement algorithm as one would expect). The routine
for searching overlapping candidates uses R-tree, so usually it walks
thrugh just few other candidates (though in case of dense layers even that
may be a lot - we should probably skip candidates if they intersect more
than a certain number of features to save processing time of hopeless
candidates).

Parallelization always comes at a cost of more complex code and the
possibility of deadlocks and subtle errors from run conditions. Worst of
all, algorithms sometimes do not scale well and running them in parallel
actually takes longer due to waiting on locks. That's why I think the
parallelization should be a only used as last resort (unless the task is
trivially parallelizable).

Regards
Martin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/qgis-developer/attachments/20130305/c5fad966/attachment.html>