[mapserver-dev] Labelcache potential optimization using spatial index

[thomas bonfort]

Hi there,
I had a quick go at some optimizations that could be brought to the
labelcache. My test case is very far from a real-world situation, and
consists in rendering the names of *all* the roads in the UK, and
therefore stresses the labelcache immensely as there are millions of
collision detections to be run.

Initial run: I killed the process after 30 minutes. 99% of the cpu
time was spent in the collision detection, 90% of which was spent
iterating through the labels to check if they had been rendered or not
(i.e. checking cachePtr->status);

I modified the labelcache to keep a linked list of which labels had
actually been rendered, and cut out the nested loops iterating through
the labelcacheslots. runtime after the patch: 23 seconds :) .

So in conclusion it would seem that in this extreme case, an rtree
index on the rendered labels would have actually helped alot also.
Until someone wants to investigate more, a simple linked-list hack as
I have tried seems to be pretty promising.

cheers,
thomas

On 26 February 2013 17:40, thomas bonfort <thomas.bonfort at gmail.com> wrote:
>> I wonder how many labels one would have to be dealing with for this overhead and complexity to be worth it.
> My gut feeling is also that a spatial index won't provide any
> noticeable speedup, and may potentially even slow things down. The
> reason for this is that in a typical map render, only a small number
> of labels  (i.e. in the order of the 10s, max 100s) make it into the
> rendered map, and those are the only ones that could be put in the
> spatial index. Given that these rendered labels already have a
> bounding box test before a full intersection test with subsequent
> label candidates, I suspect that this process is at least fast as what
> we could get with an index.
> Of course, if someone wants to implement such an indexing, I will be
> happy to be proved wrong if it results in a performance enhancement :)
>
> regards,
> thomas