[Mapserver-dev] Speed Improvement Fix.

[Alan Steremberg]

This is slightly ugly, because every node has a tail pointer in it, but it
would be hard to keep all of them up to date.. So i just update the head
pointer, and try to keep the rest of them NULL.

Here is the piece of code (I just wrote and tested it a little bit):

in map.h add:
// FEATURE LIST OBJECT - for inline features, shape caches and queries
#ifndef SWIG
typedef struct listNode {
  shapeObj shape;
  struct listNode *next;
/* this is the tail node in the list, if this is the head element,
otherwise NULL */
  struct listNode *tailifhead;
} featureListNodeObj;


In insertFeatureList:


remove the old list code, and replace it with:

/* AJS - alans at wunderground.com O(n^2) -> O(n) conversion, keep a pointer
to the end */

    /* set the tailifhead to NULL, since it is only set for the head of
the list */
    node->tailifhead=NULL;
    node->next=NULL;
    /* if we are at the head of the list, we need to set the list to node,
before
        pointing tailifhead somewhere */
    if (*list==NULL)
    {
        *list=node;
    }
    else
    {
        /* this should never be NULL, but I hate crashing */
        if ((*list)->tailifhead!=NULL)
        {
            /* put the node at the end of the list */
            (*list)->tailifhead->next=node;
        }
    }
    /* repoint the head of the list to the end  - our new element */
    /* this causes a loop if we are at the head, be careful not to walk in
a loop */
    (*list)->tailifhead=node;
    //node->next=*list;
    //*list=node;


----------------------------
 Alan Steremberg
 415-543-5021 x 103
 http://www.wunderground.com

On Thu, 6 Nov 2003, Steve Lime wrote:

> Excellent- we like speed increases. Actually someone suggested a similar
> modification a long time ago but I lost the email and code change and it
> never got put in place. I'll make sure this time the code is commited to
> the 4.1 source tree! I don't think the order is relevant, but I'll have
> to think about it since this is used not just with inline features. Do
> you know/have the mod needed to keep things in order?
>
> Steve
>
> >>> Alan Steremberg <alans at wunderground.com> 11/5/2003 9:31:20 PM >>>
>
> Hi,
>
> I am not sure if this changes the drawing behaviour, but I was able to
> speed up one of the layers I was drawing by a factor of 4-6.
>
> Here is the issue:
>   When drawing Overlay symbols, mapdraw caches everything using
> 'insertFeatureList'.  insertFeaturelist is a linked list with a tail
> insertion. This is n*log(n).  I switched the algorithm to a head
> insertion
> which is time n.  It is possible that the lines will now draw
> backwards
> (not sure if this is a problem) if it is, we should change the linked
> list
> structure to have a last pointer that we can keep updated.
>
> here is my modification:
>
> mapfile.c:
>
> /* AJS -- link the list the other way?? */
> /* BEFORE --> */
> #if 0
>   node->next = NULL;
>
>   previous = NULL;
>   current = *list;
>   while(current != NULL) {
>     previous = current;
>     current = current->next;
>     i++;
>   }
>
>   if(previous == NULL) {
>     *list = node;
>   } else
>     previous->next = node;
> #endif
> /* AJS */
> /* AFTER, two lines of code */
>     node->next=*list;
>     *list=node;
>
>
> Thoughts?
>
>
> Alan
>
> ----------------------------
>  Alan Steremberg
>  415-543-5021 x 103
>  http://www.wunderground.com
> _______________________________________________
> Mapserver-dev mailing list
> Mapserver-dev at lists.gis.umn.edu
> http://lists.gis.umn.edu/mailman/listinfo/mapserver-dev
> _______________________________________________
> Mapserver-dev mailing list
> Mapserver-dev at lists.gis.umn.edu
> http://lists.gis.umn.edu/mailman/listinfo/mapserver-dev
>