Optimizing msAddLine() - Githubissues

Reporter: dmorissette Date: 2003/03/28 - 13:46
There was a thread on mapserver-dev around Jan 12 discussing ways to optimize 
msAddLine().  I'm copying the conclusions of this thread below to document this 
potential enhancement.

The whole thread can be found at 
http://mapserver.gis.umn.edu/wilma/mapserver-dev/0301/threads.html#00006

-------------

I guess that could be a good idea, and since this is a simple if()
statement once we start keeping track of the allocated buffer size,
perhaps we could even consider using a macro that would hide the code
complexity and save the overhead of a function call (since we're talking
about using this in critical places in the code).

e.g. something like this:

#define MS_REALLOC_ARRAY_IF_FULL(ptr, objType, numAllocated, \
                                 numUsed, minToAlloc, funcName) \
  if (ptr == NULL) {                                         \
      (numAllocated) = (minToAlloc);                         \
      ptr = (objType *)malloc((minToAlloc)*sizeof(objType)); \
  } else if ((numUsed) == (numAllocated))                    \
      (numAllocated) *= 2;  /* realloc twice the size */     \
      ptr = (objType *)realloc(ptr, (numAllocated)*sizeof(objType));\
  }                                                          \
  if (ptr == NULL)                                           \
      msSetError(MS_MEMERR, NULL, funcName);

Note that I don't mind using a separate function either... perhaps the
macro is pushing things a bit far.  :)

Daniel

Steve Lime wrote:
> 
> What about adding a buffer size to the lineObj? If we did that to the
> various objects
> that would be prone to expansion then a generalized function would be
> very handy.
> The labelCacheObj keeps track already. Kind of a big change but could
> be implemented
> in the shapeObj's first and then applied elsewhere over time...
> 
> Steve
> 
> >>> Daniel Morissette <morissette@dmsolutions.ca> 01/10/03 09:40AM >>>
> 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@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.
> >
MapServer / MapServer-import

Optimizing msAddLine() #303
