[Mapserver-dev] Optimizing msAddLine()

[David Turover]

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.