force_palette could be optimized

[tbonfort]

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

[tbonfort]

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

[tbonfort]

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

[tbonfort]

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.

[tbonfort]

Someone got their math horribly wrong here ;)

a full 32MB are allocated, not 3

[tbonfort]

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

[tbonfort]

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.

[assefa]

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

[tbonfort]

commited in r7154.

closing.

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