[Mapserver-dev] Optimizing msAddLine()

[Daniel Morissette]

Steve Lime wrote:
> 
> Any comments or can we go ahead and add this? Dan?
> 

My only comment was that I wished we could have a simpler solution
instead of a separate function like this, but the problem is that we
don't keep track of the current allocated buffer size in lineObj, so we
have to figure it out on every call this way.  We could also possibly
use a loop to figure the value but it would probably be as CPU
expensive.

In brief, I don't have any more comments, so you can go ahead...

Daniel

> >>> David Turover <dturover at student.santarosa.edu> 01/08/03 13:10 PM >>>
> On Mon, 6 Jan 2003, Daniel Morissette wrote:
> > Steve Lime wrote:
> > >
> > > Thanks David, lemme (and others?) look through the code and test it
> a
> > > bit. Certainly looks
> > > promising though. Wonder how much affect it has in web use...
> > >
> >
> > I think the basic idea is great (better than reallocating one item
> > at a time), but I'm worried a bit by the overhead in memory usage
> > involved in general use of the current solution, especially for things
> > like the labelcache that stores shapes for each label.
> [snip]
> > Anyway, what I wanted to propose is to start with a smaller buffer and
> > double the buffer size everytime we realloc, e.g. start with a buffer
> of
> > 8 lineObj, then realloc to 16, 32, 64, 128, ... ...
> [snip]
> 
> How does this look?
> 
> void msArrayResizeIfFull(void ** arrayPtr, int numItems, int itemSize){
>         const static int maxArraySegment = 256;
>         void * newArray;
> 
>         if(arrayPtr == NULL) return;
> 
>         /* Set newArray equal to the original array so
>         ** if newArray changes we know that malloc was called on it,
>         ** and that newArray == NULL means malloc failed. */
>         newArray = *arrayPtr;
> 
>         if(numItems < maxArraySegment){
>                 switch(numItems){
>                 case 0: /* malloc an initial array */
>                         newArray = calloc(8, itemSize);
>                         break;
>                 case 8:         /* Fall through */
>                 case 16:        /* Fall through */
>                 case 32:        /* Fall through */
>                 case 64:        /* Fall through */
>                 case 128:
>                         newArray = calloc(numItems * 2, itemSize);
>                         memcpy(newArray, *arrayPtr, numItems *
> itemSize);
>                         break;
>                 default: break;
>                 }
>         } else if(numItems % maxArraySegment == 0){
>                 newArray = calloc(numItems + maxArraySegment,itemSize);
>                 memcpy(newArray, *arrayPtr, numItems * itemSize);
>         }
> 
>         if(newArray != *arrayPtr){
>                 if(newArray == NULL)
>                         msSetError(MS_MEMERR, NULL,
> "msArrayResizeIfFull()");
>                 else{
>                         msFree(*arrayPtr);
>                         *arrayPtr = newArray;
>                 }
>         }
> 
>         return;
> }
> 
> And msAddLine() becomes:
> 
> int msAddLine(shapeObj *p, lineObj *new_line){
>         lineObj *extended_line;
> 
>         msArrayResizeIfFull((void **)&p->line, p->numlines,
> sizeof(lineObj));
> 
>         /* Update the polygon information */
>         extended_line = &p->line[p->numlines];
> 
>         /* Copy the points to the line array */
>         extended_line->numpoints = new_line->numpoints;
>         if((extended_line->point = (pointObj
> *)malloc(new_line->numpoints
>                  * sizeof(pointObj))) == NULL) {
>                 msSetError(MS_MEMERR, NULL, "msAddLine()");
>                 return(-1);
>         }
>         memcpy(extended_line->point, new_line->point,
> new_line->numpoints
> * sizeof(pointObj));
>         p->numlines++;
> 
>         return(0);
> }
> 
> This hasn't been well tested (it runs here, but I haven't tried to hit
> every branch to see what happens).
> 
> BTW: I glanced at maplabel.c and it appears the labelcache is already
> expanding by increments of 10, so that shouldn't be a problem.
>