[mapserver-dev] Labelcache potential optimization using spatial index

[thomas bonfort]

I was hoping to work on that and other labelcache optimizations during
the codesprint. Namely:

- cutting down on memory allocations:
 - use references to styleObjs and labelObjs instead of copies when
there are no bindings at stake
 - defer creation of labelcache shapeObj/rectObj to only allocate
memory for them if the label is effectively rendered
 - slim down our shapeObj object (cut into featureObj/geometryObj) so
that the bounding polys of our labels don't have to carry useless
information

- speeding up some collision detections, there's a shortcut we can use
when the label's bounding poly is the same as the label bounding box
(i.e. only do a bbox test, not an intersection test). This is a very
common occurence (i.e. when the label is not rotated), and would also
cut down on the need for allocating a shapeObj for the label.

On 4 March 2013 19:03, Lime, Steve D (MNIT) <Steve.Lime at state.mn.us> wrote:
> Pretty cool! What's that, an 3900%+ improvement? Probably simplifies the code a good bit too. Any reason not to at least put the hack in place?
>
> Steve
>
> -----Original Message-----
> From: thomas bonfort [mailto:thomas.bonfort at gmail.com]
> Sent: Monday, March 04, 2013 8:51 AM
> To: Lime, Steve D (MNIT)
> Cc: Stephen Woodbridge; mapserver-dev at lists.osgeo.org
> Subject: Re: [mapserver-dev] Labelcache potential optimization using spatial index
>
> 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
>