shapeObj buffer resize algorithm
Kovacs Baldvin
baldvin at CS.ELTE.HU
Tue Jul 26 20:04:24 EDT 2005
Hi!
According to profiling data a lot of time was spent in msAddLine
when having pretty much lines. One of the reasons was the extremely
inefficient way of pushing data onto the vector p->line: for every
new item the whole content of the vector was copied to a newly
allocated memory area.
I attached a patch that makes shapeObj use the convetional heuristic
to double its buffer size every time it fills up. Naturally I had
to introduce a new member of shapeObj for holding the actual buffer
size.
So this is actually a speed for memory tradeoff. I really do think
that it worth it: the running time decreased pretty much.
Please consider the patch for inclusion.
Best regards,
Baldvin Kovacs
-------------- next part --------------
Index: map.h
===================================================================
RCS file: /data2/cvsroot/mapserver/map.h,v
retrieving revision 1.419
diff -u -r1.419 map.h
--- map.h 16 Jul 2005 19:07:38 -0000 1.419
+++ map.h 26 Jul 2005 23:20:10 -0000
@@ -240,6 +240,7 @@
#include <stdlib.h>
#include <string.h>
#include <math.h>
+#include <assert.h>
#if defined(_WIN32) && !defined(__CYGWIN__)
#include <direct.h>
Index: mapgeos.cpp
===================================================================
RCS file: /data2/cvsroot/mapserver/mapgeos.cpp,v
retrieving revision 1.12
diff -u -r1.12 mapgeos.cpp
--- mapgeos.cpp 14 Jun 2005 16:03:33 -0000 1.12
+++ mapgeos.cpp 26 Jul 2005 23:20:10 -0000
@@ -338,6 +338,7 @@
shape->type = MS_SHAPE_POINT;
shape->line = (lineObj *) malloc(sizeof(lineObj));
+ shape->bufsize = 1;
shape->numlines = 1;
shape->line[0].point = (pointObj *) malloc(sizeof(pointObj));
shape->line[0].numpoints = 1;
@@ -372,6 +373,7 @@
shape->type = MS_SHAPE_POINT;
shape->line = (lineObj *) malloc(sizeof(lineObj));
shape->numlines = 1;
+ shape->bufsize = 1;
shape->line[0].point = (pointObj *) malloc(sizeof(pointObj)*numPoints);
shape->line[0].numpoints = numPoints;
shape->geometry = g;
@@ -410,6 +412,7 @@
shape->type = MS_SHAPE_LINE;
shape->line = (lineObj *) malloc(sizeof(lineObj));
+ shape->bufsize = 1;
shape->numlines = 1;
shape->line[0].point = (pointObj *) malloc(sizeof(pointObj)*numPoints);
shape->line[0].numpoints = numPoints;
@@ -451,6 +454,7 @@
shape->type = MS_SHAPE_LINE;
shape->line = (lineObj *) malloc(sizeof(lineObj)*numLines);
shape->numlines = numLines;
+ shape->bufsize = numLines;
shape->geometry = g;
for(j=0; j<numLines; j++) {
Index: mapgraticule.c
===================================================================
RCS file: /data2/cvsroot/mapserver/mapgraticule.c,v
retrieving revision 1.13
diff -u -r1.13 mapgraticule.c
--- mapgraticule.c 8 Jun 2005 23:57:43 -0000 1.13
+++ mapgraticule.c 26 Jul 2005 23:20:10 -0000
@@ -306,6 +306,7 @@
}
shape->numlines = 1;
+ shape->bufsize = 1;
shape->type = MS_SHAPE_LINE;
shape->line = (lineObj *) malloc( sizeof( lineObj ) );
@@ -327,6 +328,7 @@
{
pInfo->ilabelstate++;
shape->numlines = 0;
+ shape->bufsize = 0;
return MS_SUCCESS;
}
@@ -352,6 +354,7 @@
{
pInfo->ilabelstate++;
shape->numlines = 0;
+ shape->bufsize = 0;
return MS_SUCCESS;
}
@@ -410,6 +413,7 @@
{
pInfo->ilabelstate++;
shape->numlines = 0;
+ shape->bufsize = 0;
return MS_SUCCESS;
}
@@ -435,6 +439,7 @@
{
pInfo->ilabelstate++;
shape->numlines = 0;
+ shape->bufsize = 0;
return MS_SUCCESS;
}
Index: maplegend.c
===================================================================
RCS file: /data2/cvsroot/mapserver/maplegend.c,v
retrieving revision 1.54
diff -u -r1.54 maplegend.c
--- maplegend.c 14 Jun 2005 16:03:33 -0000 1.54
+++ maplegend.c 26 Jul 2005 23:20:10 -0000
@@ -80,6 +80,7 @@
/* initialize the box used for polygons and for outlines */
box.line = (lineObj *)malloc(sizeof(lineObj));
+ box.bufsize = 1;
box.numlines = 1;
box.line[0].point = (pointObj *)malloc(sizeof(pointObj)*5);
box.line[0].numpoints = 5;
@@ -136,6 +137,7 @@
break;
case MS_LAYER_LINE:
zigzag.line = (lineObj *)malloc(sizeof(lineObj));
+ zigzag.bufsize = 1;
zigzag.numlines = 1;
zigzag.line[0].point = (pointObj *)malloc(sizeof(pointObj)*4);
zigzag.line[0].numpoints = 4;
Index: mapprimitive.c
===================================================================
RCS file: /data2/cvsroot/mapserver/mapprimitive.c,v
retrieving revision 1.53
diff -u -r1.53 mapprimitive.c
--- mapprimitive.c 14 Jun 2005 16:03:34 -0000 1.53
+++ mapprimitive.c 26 Jul 2005 23:20:11 -0000
@@ -101,6 +101,7 @@
/* spatial component */
shape->line = NULL;
shape->numlines = 0;
+ shape->bufsize = 0;
shape->type = MS_SHAPE_NULL;
shape->bounds.minx = shape->bounds.miny = -1;
shape->bounds.maxx = shape->bounds.maxy = -1;
@@ -251,38 +252,50 @@
return(list);
}
-int msAddLine(shapeObj *p, lineObj *new_line)
-{
- int c;
- lineObj *extended_line;
+int msShapeObjIncBuffer(shapeObj *p) {
- /* Create an extended line array */
- if((extended_line = (lineObj *)malloc((p->numlines + 1) * sizeof(lineObj))) == NULL) {
- msSetError(MS_MEMERR, NULL, "msAddLine()");
- return(MS_FAILURE);
+ if ( p->line ) {
+ assert(p->bufsize > 0);
+ p->bufsize *= 2;
+ /* We could use an even more agressive heuristic...:
+ p->bufsize = p->bufsize == 1 ? 2 : p->bufsize * p->bufsize;
+ */
+ p->line = realloc(p->line, p->bufsize * sizeof(lineObj));
+ if ( p->line == NULL ) {
+ msSetError(MS_MEMERR, NULL, "msShapeObjIncBuffer()");
+ return(MS_FAILURE);
+ }
+ } else {
+ p->bufsize = 1;
+ if((p->line = (lineObj *)malloc(sizeof(lineObj))) == NULL) {
+ msSetError(MS_MEMERR, NULL, "msShapeObjIncBuffer()");
+ return(MS_FAILURE);
+ }
}
- /* Copy the old line into the extended line array */
- for (c= 0; c < p->numlines; c++)
- extended_line[c]= p->line[c];
+ return MS_SUCCESS;
+}
+
+int msAddLine(shapeObj *p, lineObj *new_line)
+{
+ if ( p->numlines >= p->bufsize ) {
+ if ( msShapeObjIncBuffer(p) != MS_SUCCESS ) {
+ return MS_FAILURE;
+ }
+ }
/* Copy the new line onto the end of the extended line array */
- c= p->numlines;
- extended_line[c].numpoints = new_line->numpoints;
- if((extended_line[c].point = (pointObj *)malloc(new_line->numpoints * sizeof(pointObj))) == NULL) {
+ p->line[p->numlines].numpoints = new_line->numpoints;
+ if((p->line[p->numlines].point = (pointObj *)malloc(new_line->numpoints * sizeof(pointObj))) == NULL) {
msSetError(MS_MEMERR, NULL, "msAddLine()");
return(MS_FAILURE);
}
- memcpy( extended_line[c].point, new_line->point,
+ memcpy( p->line[p->numlines].point, new_line->point,
sizeof(pointObj) * new_line->numpoints );
- /* Dispose of the old line */
- if(p->line) free(p->line);
-
/* Update the polygon information */
p->numlines++;
- p->line = extended_line;
return(MS_SUCCESS);
}
@@ -293,34 +306,20 @@
*/
int msAddLineDirectly(shapeObj *p, lineObj *new_line)
{
- int c;
- lineObj *extended_line;
-
- /* Create an extended line array */
- if((extended_line = (lineObj *)malloc((p->numlines + 1) * sizeof(lineObj))) == NULL) {
- msSetError(MS_MEMERR, NULL, "msAddLine()");
- return(MS_FAILURE);
+ if ( p->numlines >= p->bufsize ) {
+ if ( msShapeObjIncBuffer(p) != MS_SUCCESS ) {
+ return MS_FAILURE;
+ }
}
- /* Copy the old line into the extended line array */
- for (c= 0; c < p->numlines; c++)
- extended_line[c]= p->line[c];
-
- /* Copy the new line onto the end of the extended line array */
- c= p->numlines;
- extended_line[c].numpoints = new_line->numpoints;
- extended_line[c].point = new_line->point;
+ p->line[p->numlines].numpoints = new_line->numpoints;
+ p->line[p->numlines].point = new_line->point;
/* strip points reference off the passed in lineObj */
new_line->point = NULL;
new_line->numpoints = 0;
- /* Dispose of the old line */
- if(p->line) free(p->line);
-
- /* Update the polygon information */
p->numlines++;
- p->line = extended_line;
return(MS_SUCCESS);
}
@@ -511,6 +510,7 @@
shape->line = tmp.line;
shape->numlines = tmp.numlines;
+ shape->bufsize = tmp.bufsize;
}
/*
@@ -666,6 +666,7 @@
shape->line = tmp.line;
shape->numlines = tmp.numlines;
+ shape->bufsize = tmp.bufsize;
return;
}
Index: mapprimitive.h
===================================================================
RCS file: /data2/cvsroot/mapserver/mapprimitive.h,v
retrieving revision 1.18
diff -u -r1.18 mapprimitive.h
--- mapprimitive.h 14 Jun 2005 16:03:34 -0000 1.18
+++ mapprimitive.h 26 Jul 2005 23:20:11 -0000
@@ -86,6 +86,7 @@
#endif
int numlines;
int numvalues;
+ int bufsize;
lineObj *line;
char **values;
#ifdef SWIG
More information about the mapserver-dev
mailing list