<p dir="ltr"><br>
On Mar 4, 2013 11:38 PM, "Matthias Kuhn" <<a href="mailto:matthias.kuhn@gmx.ch">matthias.kuhn@gmx.ch</a>> wrote:<br>
><br>
> Hi Benjamin,<br>
><br>
> Thank you for your interest in the project.<br>
> I was looking at a problem today and thought of your mail to the list.<br>
> 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.<br>
> 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.<br>

> 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.</p>

<p dir="ltr">Hi Matthias</p>
<p dir="ltr">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).</p>

<p dir="ltr">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).</p>

<p dir="ltr">Regards<br>
Martin</p>