Opened 16 years ago

Closed 16 years ago

#2422 closed enhancement (fixed)

force_palette could be optimized

Reported by: tbonfort Owned by: tbonfort
Priority: normal Milestone: 5.2 release
Component: MapServer C Library Version: unspecified
Severity: normal Keywords:
Cc: assefa, zjames, jmckenna

Description

the caching strategy when using a forced palette isn't optimal and results in substantial slowdowns, especially for large images

Attachments (2)

plot-small.png (3.5 KB ) - added by tbonfort 16 years ago.
same plot for small image sizes. allocation cost doesn't seem too important
plot-large.png (5.2 KB ) - added by tbonfort 16 years ago.
paletting time in ms. x is image size. red is current. green is high mem. blue is with a hash

Download all attachments as: .zip

Change History (8)

comment:1 by tbonfort, 16 years ago

I propose a more agressive caching of paletted images

static int msImageCopyForcePaletteGD2(gdImagePtr src, gdImagePtr dst) 
{
  
/* snip */

  cache=(short*)calloc(16777216,sizeof(short));

  for (y = 0; (y < h); y++) {
    for (x = 0; (x < w); x++) {
        int index;
        c = gdImageGetPixel(src, x, y);    
        index=c&0xFFFFFF;
      if(!cache[index]) {
          r =  gdTrueColorGetRed(c);
          g = gdTrueColorGetGreen(c);
          b = gdTrueColorGetBlue(c);
          color = gdImageColorClosest(dst, r, g, b);
          cache[index]=color+1;
          dst->pixels[y][x] = color;
      }
      else
          dst->pixels[y][x] = cache[index]-1;
    }
  }
  free(cache);
  return MS_SUCCESS;
}

which is substantially faster, but allocates 3MB of memory on the heap.

attaching some benchmark graphs

by tbonfort, 16 years ago

Attachment: plot-small.png added

same plot for small image sizes. allocation cost doesn't seem too important

comment:2 by tbonfort, 16 years ago

from my benchmarking, it seems the cost of allocating the cache is marginal, therefore this method could be used whatever the image size being renderered.

However, there might be some situations where this large memory allocation may not be wanted. We could add a new

FORMATOPTION "PALETTE_METHOD=conserve_mem"

that would revert to using the current method.

comment:3 by tbonfort, 16 years ago

Someone got their math horribly wrong here ;)

a full 32MB are allocated, not 3

by tbonfort, 16 years ago

Attachment: plot-large.png added

paletting time in ms. x is image size. red is current. green is high mem. blue is with a hash

comment:4 by tbonfort, 16 years ago

I added an intermediate caching strategy. On my test map, 6000*6000, approx 4MB was allocated.

static int msImageCopyForcePaletteGD6(gdImagePtr src, gdImagePtr dst) 
{
  int x, y;
  int w, h;
  int c, r, g, b,color;
  if(!src || !dst) return MS_FAILURE;
  if(gdImageSX(src) != gdImageSX(dst) || gdImageSY(src) != gdImageSY(dst)) return MS_FAILURE;
  if(!gdImageTrueColor(src) || gdImageTrueColor(dst)) return MS_FAILURE; /* 24-bit to 8-bit */
  w = gdImageSX(src);
  h = gdImageSY(src);
  
  unsigned short ***cols=(unsigned short***)calloc(256,sizeof(unsigned short**));
  unsigned short **data=(unsigned short**)calloc(256*256,sizeof(unsigned short*));
  for(r=0;r<256;r++) {
      cols[r]=&(data[r*256]);
  }
  
  for (y = 0; (y < h); y++) {
    for (x = 0; (x < w); x++) {
      int index;
      c = gdImageGetPixel(src, x, y);    
      index=c&0xFFFFFF;
      r =  gdTrueColorGetRed(c);
      g = gdTrueColorGetGreen(c);
      b = gdTrueColorGetBlue(c);
      
      if(cols[r][g]==NULL) {
          cols[r][g]=(unsigned short*)calloc(256,sizeof(unsigned short));
      }
      
      if(!cols[r][g][b]) {
          color = gdImageColorClosest(dst, r, g, b);
          dst->pixels[y][x] = color;
          cols[r][g][b]=color+1;
      }
      else {
          dst->pixels[y][x] = cols[r][g][b]-1;
      }
    }
  }
  for(r=0;r<256;r++) 
      for(g=0;g<256;g++) 
          if(cols[r][g]) 
              free(cols[r][g]);
  free(data);
  free(cols);
  return MS_SUCCESS;
}

plot-large.png shows the updated banchmarking.

comment:5 by assefa, 16 years ago

Tomas,

I had similar results testing with 6000/6000 with the latest function. I think it is the best compromise. I like the fact that the old way is still there with an option parameter so that if for some reason someone is currently using it and find an issue he can still have the old behavior. Personally I think you should go with the commit. Great work. Thanks

comment:6 by tbonfort, 16 years ago

Resolution: fixed
Status: newclosed

commited in r7154.

closing.

documentation isn't done yet but #2096 is already open for that.

Note: See TracTickets for help on using tickets.