[mapserver-dev] Labelcache potential optimization using spatial index

[Lime, Steve D (MNIT)]

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