[mapserver-dev] Labelcache potential optimization using spatial index

[Daniel Morissette]

Very nice to see the numbers that came out of your tests and the other 
potential enhancements. That would be one nice outcome for the sprint 
for sure.

Daniel

On 13-03-05 5:36 AM, thomas bonfort wrote:
> 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
>>
> _______________________________________________
> mapserver-dev mailing list
> mapserver-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/mapserver-dev
>


-- 
Daniel Morissette
http://www.mapgears.com/
Provider of Professional MapServer Support since 2000