[patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Ami Fischman]

[-- Attachment #1: Type: text/plain, Size: 2270 bytes --]

Following up on a couple of recent threads, I decided to add caching to the
X Color lookup code in emacs.  The way I ended up doing it was creating a
general purpose cache linked-list, and wrapping each of XAllocColor,
XQueryColor, and XQueryColors in a function that first looks for the
requested data in the linked list before issuing the X call.  Results are
quite good.  Some arbitrary timings follow.  All times over an ssh -XC link
with lbxproxy running on the remote end.  The "stock" emacs has a version
string of:  GNU Emacs 21.1.1 (i686-pc-linux-gnu, X toolkit, Xaw3d scroll
bars) of 2001-10-22 on zion.  Times are presented for this stock emacs and
for a current CVS emacs configured --without-xim and with color caching,
and for each of those, with and without my ~/.emacs file (which loads a
whole bunch of libraries).

without ~/.emacs (-q):
Std emacs 21.1
    0.24user 0.05system 0:45.31elapsed
emacs-cvs --without-xim, with color caching:
    0.25user 0.03system 0:29.80elapsed

with ~/.emacs:
emacs-21.1:
    0.96user 0.22system 1:04.65elapsed
emacs-cvs --without-xim, with color caching:
    0.94user 0.15system 0:32.40elapsed

As you can see, the big improvement is in the loading of libraries -- where
the stock emacs goes from 45s to 69s, the caching emacs goes up less than 3
seconds.  

Another obvious thing to cache would be the font data that emacs can
request, although it is much less clear to me how to cache the XExtData
list that is potentially contained in an XFontStruct (namely, how do you
know how big the private data is?  If anyone has any suggestions here, I'd
like to hear them).

This new functionality is provided via two new files (xcache.[ch]), adding
xcache.o to the XOBJ variable in src/Makefile, adding -DUSE_XCACHE to the
ALL_CFLAGS in the Makefile, and the following small patch to xterm.c:

Index: xterm.h
===================================================================
RCS file: /cvsroot/emacs/emacs/src/xterm.h,v
retrieving revision 1.136
diff -r1.136 xterm.h
36c36,39
< #endif
---
> #ifdef USE_XCACHE
> #include "xcache.h"
> #endif /* USE_XCACHE */
> #endif /* USE_X_TOOLKIT */

xcache.[ch] are attached.  

I'd be interested to hear any feedback you might have on this.

-- 
  Ami Fischman
  usenet@fischman.org


[-- Attachment #2: xcache.c --]
[-- Type: application/octet-stream, Size: 10641 bytes --]

#define XCACHE_C

#include "xcache.h"

#define DEBUG_AC 0
#define DEBUG_QC 0
#define DEBUG_LF 0
#define DEBUG_LQF 0

/*****************************************************************************
 Definitions of main xcache structure & access functions
 *****************************************************************************/
struct _xcache_record {
  unsigned int keylen, datalen;
  char *key;
  char *data;
  struct _xcache_record *nextrec;
};

struct _xcache {
  unsigned int numrecs;
  unsigned int cachesize;
  struct _xcache_record *first;
};

static struct _xcache xcache = {0, 0, NULL};

struct _xcache_record *xcache_store(unsigned int keylen, char *key, unsigned int datalen, char *data) {
  struct _xcache_record *newrec=(struct _xcache_record*)xmalloc(sizeof(struct _xcache_record));
  newrec->keylen=keylen; newrec->datalen=datalen;
  newrec->key=(char*)xmalloc(keylen);
  newrec->data=(char*)xmalloc(datalen);
  memcpy(newrec->key, key, keylen);
  memcpy(newrec->data, data, datalen);
  newrec->nextrec=xcache.first;
  xcache.first=newrec;
  xcache.numrecs++;
  xcache.cachesize+=keylen+datalen+(sizeof(unsigned int)*2);
  return newrec;
}

struct _xcache_record *xcache_find(unsigned int keylen, char *key) {
  char *ret=0;
  struct _xcache_record *recptr = xcache.first;
  while (recptr) {
    if ((recptr->keylen==keylen) && !memcmp(key, recptr->key, keylen)) {
      return recptr;
    }
    recptr=recptr->nextrec;
  }
  return NULL;
}


/*****************************************************************************
 XAllocColor
 *****************************************************************************/
/* Status is just an int, at least on XFree86 */
Status xcache_AllocColor(Display *display, Colormap colormap, XColor *screen_in_out) {
  unsigned int keylen=strlen(DisplayString(display))+sizeof(Colormap)+sizeof(XColor), datalen=0;
  unsigned char *key=(unsigned char*)xmalloc(keylen);
  unsigned char *data=NULL;
  struct _xcache_record *recptr=NULL;
  Status ret=1;

  memset(key, 0, keylen);
  screen_in_out->pad=0;   screen_in_out->flags=0;

  memcpy(key, DisplayString(display), strlen(DisplayString(display)));
  memcpy(key+strlen(DisplayString(display)), &colormap, sizeof(Colormap));
  memcpy(key+strlen(DisplayString(display))+sizeof(Colormap), screen_in_out, sizeof(XColor));

  if (recptr=xcache_find(keylen, key)) {
    memcpy(screen_in_out, recptr->data, recptr->datalen);
#if DEBUG_AC
    TIMELOG("AllocColor hit!");
#endif
  } else {
    ret=XAllocColor(display, colormap, screen_in_out);
    if (ret) {
      xcache_store(keylen, key, sizeof(XColor), (char*)screen_in_out);
    }
#if DEBUG_AC
    TIMELOG("AllocColor miss!");
    {
      static char s[1024];
      sprintf(s, "  %lu %hu %hu %hu %hhd %hhd", 
	      screen_in_out->pixel, screen_in_out->red, screen_in_out->blue, screen_in_out->green, screen_in_out->pad, screen_in_out->flags);
      TIMELOG(s);
    }
#endif
  }  
  return ret;
}


/*****************************************************************************
 XListFonts
 *****************************************************************************/
// Forward decl's.  See below for definitions.
static char **data2nameset(char *data, unsigned int datalen, int *count);
static char *nameset2data(char **nameset, int count, unsigned int *datalenp);

char **xcache_ListFonts(Display *display, char *pattern, int maxnames, int *actual_count_return) {
  unsigned int keylen=strlen(DisplayString(display))+sizeof(int)+strlen(pattern), datalen=0;
  unsigned char *key=(unsigned char*)xmalloc(keylen);
  unsigned char *data=NULL;
  struct _xcache_record *recptr=NULL;
  char **ret=NULL;

  memset(key, 0, keylen);

  /* Make key: */
  memcpy(key, DisplayString(display), strlen(DisplayString(display)));
  memcpy(key+strlen(DisplayString(display)), pattern, strlen(pattern));
  memcpy(key+strlen(DisplayString(display))+strlen(pattern), &maxnames, sizeof(int));

  if (recptr=xcache_find(keylen, key)) {
    ret=data2nameset(recptr->data, recptr->datalen, actual_count_return);
#if DEBUG_LF
    TIMELOG("ListFonts hit!");
#endif
  } else {
    ret=XListFonts(display, pattern, maxnames, actual_count_return);
    data=nameset2data(ret, *actual_count_return, &datalen);
    xcache_store(keylen, key, sizeof(datalen), data);
#if DEBUG_LF
    TIMELOG("ListFonts miss!");
    {
      static char s[1024];
      sprintf(s, "  [%s] %d",
	      pattern, maxnames);
      TIMELOG(s);
    }
#endif
  }  
  return ret;
}

char **data2nameset(char *data, unsigned int datalen, int *count) {
  char **ret=NULL;
  char *nextstr=NULL, *retspace;
  unsigned int i=0;

  memcpy(count, data, sizeof(int));
  assert(*count>0);
  data+=sizeof(int);
  ret=(char**)xmalloc(sizeof(char*)*(*count));
  datalen-=sizeof(int);
  retspace=(char*)xmalloc(sizeof(char)*datalen);
  memcpy(retspace, data, datalen);
  nextstr=data;
  for(i=0; i<*count; ++i) {
    ret[i]=nextstr;
    nextstr=strchr(nextstr,0)+(char*)1;
  }
  return ret;
}

char *nameset2data(char **nameset, int count, unsigned int *datalenp) {
  unsigned int datalen=0, i=0;
  char *data, *datap;

  datalen=sizeof(int);
  for(i=0; i< count; ++i) {
    datalen+=strlen(nameset[i])+1;
  }
  data=(char*)xmalloc(sizeof(char)*datalen);
  *datalenp=datalen;

  memcpy(data, &count, sizeof(int));

  datap=data+sizeof(int);
  for(i=0; i<count; ++i) {
    unsigned int llen=strlen(nameset[i])+1;
    memcpy(datap, nameset[i], llen);
    datap+=llen;
  }

  return data;  
}

#ifdef USE_XCACHE_LFQ
/*****************************************************************************
 XLoadQueryFont
 *****************************************************************************/


  /* XXX TODO XXX There is a big woopsie here in that I don't see how to
   * XXX TODO XXX cache the ext_data member of the XFontStruct (which is a
   * XXX TODO XXX linked list of arbitrary data bits, the size of which is
   * XXX TODO XXX not known).  Let's try just dropping the member and seeing
   * XXX TODO XXX what happens */

char *fontstruct2data(XFontStruct *f, unsigned int *datalenp);
XFontStruct *data2fontstruct(char *data, unsigned int datalen);

XFontStruct *xcache_LoadQueryFont(Display *display, char *name) {
  unsigned int keylen=strlen(DisplayString(display))+strlen(name)+1, datalen=0;
  unsigned char *key=(unsigned char*)xmalloc(keylen);
  unsigned char *data=NULL;
  struct _xcache_record *recptr=NULL;
  XFontStruct *ret=NULL;

  memset(key, 0, keylen);

  memcpy(key, DisplayString(display), strlen(DisplayString(display)));
  memcpy(key+strlen(DisplayString(display)), name, strlen(name));
  if (recptr=xcache_find(keylen, key)) {
    ret=data2fontstruct(recptr->data, recptr->datalen);
#if DEBUG_LQF
    TIMELOG("LoadQueryFont hit!");
#endif
  } else {
    ret=XLoadQueryFont(display, name);
    data=fontstruct2data(ret, &datalen);
    if (ret) {
      xcache_store(keylen, key, datalen, data);
    }
#if DEBUG_LQF
    TIMELOG("LoadQueryFont miss!");
    {
      static char s[1024];
      sprintf(s, "  [%s]", name);
      TIMELOG(s);
    }
#endif
  }  
  return ret;
}

XFontStruct *data2fontstruct(char *data, unsigned int datalen) {
  XFontStruct *ret=(XFontStruct*)xmalloc(sizeof(XFontStruct));
  XFontProp *retprop=(XFontProp*)xmalloc(sizeof(XFontProp));
  XCharStruct *retcs=(XCharStruct*)xmalloc(sizeof(XCharStruct));

  memcpy(ret, data, sizeof(XFontStruct));
  memcpy(retprop, data+sizeof(XFontStruct), sizeof(XFontProp));
  memcpy(retcs,  data+sizeof(XFontStruct)+sizeof(XFontProp), sizeof(XCharStruct));
  ret->properties=retprop;
  ret->per_char=retcs;

  return ret;
}

char *fontstruct2data(XFontStruct *f, unsigned int *datalenp) {
  unsigned int datalen, datac;
  char *data;
  XFontStruct tmp;
  
  memcpy(&tmp, f, sizeof(XFontStruct));

  tmp.ext_data=NULL;

  datalen=sizeof(XFontStruct)+sizeof(XFontProp)+sizeof(XCharStruct);
  data=(char*)xmalloc(datalen);

  memcpy(data, &tmp, sizeof(XFontStruct));
  datac+=sizeof(XFontStruct);
  /* Also the properties member is an array that should be dealt with */
  memcpy(data+datac, tmp.properties, sizeof(XFontProp));
  datac+=sizeof(XFontProp);
  memcpy(data+datac, tmp.per_char, sizeof(XCharStruct));
  
  *datalenp=datalen;
  return data;
}
#endif /* USE_XCACHE_LFQ */

/*****************************************************************************
 XGetFontProperty
 *****************************************************************************/
#if 0
/* Again, same problem here... */
Bool xcache_GetFontProperty(XFontStruct *f, Atom atom, unsigned long *ret_val) {
}
#endif

/*****************************************************************************
 XQueryColor
 *****************************************************************************/
void xcache_QueryColor(Display *display, Colormap colormap, XColor *xc) {
  unsigned int keylen=strlen(DisplayString(display))+sizeof(Colormap)+sizeof(XColor), datalen=0;
  unsigned char *key=(unsigned char*)xmalloc(keylen);
  unsigned char *data=NULL;
  struct _xcache_record *recptr=NULL;

  memset(key, 0, keylen);
  xc->pad=0; xc->flags=0; xc->red=xc->blue=xc->green=0;

  memcpy(key, DisplayString(display), strlen(DisplayString(display)));
  memcpy(key+strlen(DisplayString(display)), &colormap, sizeof(Colormap));
  memcpy(key+strlen(DisplayString(display))+sizeof(Colormap), xc, sizeof(XColor));

  if (recptr=xcache_find(keylen, key)) {
    memcpy(xc, recptr->data, recptr->datalen);
#if DEBUG_QC
    TIMELOG("QueryColor hit!");
#endif
  } else {
    XQueryColor(display, colormap, xc);
    xcache_store(keylen, key, sizeof(XColor), (char*)xc);
#if DEBUG_QC
    TIMELOG("QueryColor miss!");
    {
      static char s[1024];
      sprintf(s, "  %lu %hu %hu %hu %hhd %hhd", 
	      xc->pixel, xc->red, xc->blue, xc->green, xc->pad, xc->flags);
      TIMELOG(s);
    }
#endif
  }  

}



/*****************************************************************************
 XQueryColors
 *****************************************************************************/
void xcache_QueryColors(Display *display, Colormap colormap, XColor xc[], int ncolors) {
  int i=0;
  for(i=0; i<ncolors; ++i) {
    xcache_QueryColor(display, colormap, &xc[i]);
  }
}

/*****************************************************************************

 *****************************************************************************/

#ifdef USE_XLOG

void timerlog(char *s, unsigned int c, char *extra) {
  static FILE *logfile = NULL;
  static time_t now = 0;
  if (logfile==NULL) logfile=fopen("/tmp/timelog", "a");
  now=time(NULL);
  fprintf(logfile, "%s:%u %s %s", s, c, extra, ctime(&now));
  fflush(logfile);
}
#endif /* USE_XLOG */

[-- Attachment #3: xcache.h --]
[-- Type: application/octet-stream, Size: 1584 bytes --]

/* The xcache structure allows caching of arbitrary information.  
   We use it to save color and font information so that the X server 
   doesn't need to be queried more than once for the same question.

*/

#ifndef XCACHE_H_INCLUDED
#define XCACHE_H_INCLUDED

#ifdef USE_XCACHE

#include <X11/X.h>
#include <X11/Xlib.h>
#include <assert.h>
#include <X11/Xatom.h>

#ifdef USE_XLOG
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TIMELOG(extra) do { \
  timerlog(__FILE__, __LINE__, extra); \
} while (0);

void timerlog(char *s, unsigned int c, char *extra);
#else
#define TIMELOG(extra) do { ; } while(0);
#endif /* USE_XLOG */

#ifndef XCACHE_C /* So that the real calls don't get messed up */
#define XAllocColor xcache_AllocColor
#define XListFonts xcache_ListFonts
/* #define XListQueryFonts xcache_ListQueryFonts NOT DONE YET! */
/* #define XGetFontProperty xcache_GetFontProperty NOT DONE YET! */
#define XQueryColor xcache_QueryColor
#define XQueryColors xcache_QueryColors
#endif /* ! XCACHE_C */

Status xcache_AllocColor(Display *display, Colormap colormap, XColor *screen_in_out);
char **xcache_ListFonts(Display *display, char *pattern, int maxnames, int *actual_count_return);
/* XFontStruct *xcache_LoadQueryFont(Display *display, char *name); */
/* Bool xcache_GetFontProperty(XFontStruct *f, Atom atom, unsigned long *ret_val); */
void xcache_QueryColor(Display *display, Colormap colormap, XColor *xc);
void xcache_QueryColors(Display *display, Colormap colormap, XColor *xc, int ncolors);

#endif /* USE_XCACHE */

#endif /* XCACHE_H_INCLUDED */

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Miles Bader]

On Sat, Oct 05, 2002 at 05:21:48PM -0700, Ami Fischman wrote:
> This new functionality is provided via two new files (xcache.[ch]), adding
> xcache.o to the XOBJ variable in src/Makefile, adding -DUSE_XCACHE to the
> ALL_CFLAGS in the Makefile, and the following small patch to xterm.c:

I like the approach of having a general `X cache' and wrapping individual
functions -- it may not be the best thing in all cases, but it seems very
simple to add/maintain (and if necessary revert).

There are some problems with your implementation though --

  The C code doesn't following GNU coding standards (and is a bit hard to read)

  It seems to have unnecessary overhead, even in the `cached' case -- it does
  malloc and memory copying for _every_ call, which seems silly just to pass
  to a compare function.  Something that supported multiple keys in the cache
  entries, so that the wrapper functions could just directly pass their
  arguments to the cache lookup function, seems preferable.

  It's going to leak memory like crazy, since the above-mentioned mallocs
  don't ever appear to be freed...

BTW, I thought someone experimented with caching calls to X color functions
before (Kim?) and for some reason that code was never merged, so perhaps
there's a deeper problem with doing this.

-Miles
-- 
Suburbia: where they tear out the trees and then name streets after them.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Ami Fischman]

[-- Attachment #1: Type: text/plain, Size: 1984 bytes --]

Miles Bader raised some valid points.  Attached are updated versions of
xcache.[ch].  Some comments:

- Changed the bracing, line width, and some other formatting to be more
  GNU'ish.  Please let me know if there are other formatting issues lacking.

- The keys were being xmalloc'ed (unnecessarily) and then leaked.  Instead
  each of the wrapper functions now has a static buffer (of a #define'able
  size) to store the transient keys.  

- I decided to stay w/ the memory copying for the keys (instead of writing
  custom compare functions for each query type and then storing the cached
  data's type in the _xcache_record) because it is a cheap, local
  operation.  A typical emacs startup session might take on the order of
  magnitude of 900 X requests which incurs net lag, but 900 calls to a
  wrapper function that get executed locally are completely negligible.
  Custom compare functions would introduce a level of complexity that I
  think is unwarranted.

Using static buffers seems to speed up the whole thing even more!  With my
.emacs it's down to 30s and without (emacs -q) it's down to 28s.  

I'd be interested to hear from anyone about:
1) Have you tested this?  What sort of speed improvements do you see?
2) Am I doing anything else very stupidly (such as leaking every call :))?
3) Do you have any ideas on caching XFontStruct's?  Specifically, the
   XExtData* list has private_data members whose size is unknown (as far as
   I can see).
4) Adding an option to configure.in to enable a (default=off) switch for
   USE_XCACHE.  I don't feel like learning autoconf for this one thing.
5) Miles mentioned someone else took a crack at this at some point.  I'd be
   very interested to hear about this experience.  There is something 
   morally wrong about caching this info, but I'm willing to be a little
   naughty to cut out the ridiculous lag delays in remote X emacsen... 
6) Any other thoughts on this.

Cheers,
-- 
  Ami Fischman
  usenet@fischman.org


[-- Attachment #2: xcache.c --]
[-- Type: application/octet-stream, Size: 11352 bytes --]

#define XCACHE_C

#include "xcache.h"
#include "config.h"
#include "lisp.h"

#define MAXKEYLENSIZE 2048

#define DEBUG_AC 0
#define DEBUG_QC 0
#define DEBUG_LF 0
#define DEBUG_LQF 0

/*****************************************************************************
 Definitions of main xcache structure & access functions
 *****************************************************************************/
struct _xcache_record
{
  unsigned int keylen, datalen;
  char *key;
  char *data;
  struct _xcache_record *nextrec;
};

struct _xcache 
{
  unsigned int numrecs;
  unsigned int cachesize;
  struct _xcache_record *first;
};

static struct _xcache xcache = {0, 0, NULL};

struct _xcache_record *
xcache_store(unsigned int keylen, char *key, unsigned int datalen, char *data)
{
  struct _xcache_record *newrec=
   (struct _xcache_record*)xmalloc(sizeof(struct _xcache_record));

  newrec->keylen=keylen; newrec->datalen=datalen;
  newrec->key=(char*)xmalloc(keylen);
  newrec->data=(char*)xmalloc(datalen);
  memcpy(newrec->key, key, keylen);
  memcpy(newrec->data, data, datalen);
  newrec->nextrec=xcache.first;
  xcache.first=newrec;
  xcache.numrecs++;
  xcache.cachesize+=keylen+datalen+(sizeof(unsigned int)*2);

  return newrec;
}

struct _xcache_record *
xcache_find(unsigned int keylen, char *key) 
{
  struct _xcache_record *recptr = xcache.first;
  while (recptr) 
    {
      if ((recptr->keylen==keylen) && !memcmp(key, recptr->key, keylen)) 
       return recptr;
      recptr=recptr->nextrec;
    }
  return NULL;
}


/*****************************************************************************
 XAllocColor
 *****************************************************************************/
/* Status is just an int, at least on XFree86 */
Status 
xcache_AllocColor(Display *display, Colormap colormap, XColor *screen_in_out) 
{
  unsigned int keylen=
   strlen(DisplayString(display))+sizeof(Colormap)+sizeof(XColor);
  static unsigned char key[MAXKEYLENSIZE];
  struct _xcache_record *recptr=NULL;
  Status ret=1;

  if (keylen > MAXKEYLENSIZE) 
    return XAllocColor(display, colormap, screen_in_out);

  memset(key, 0, keylen);
  screen_in_out->pad=0;   screen_in_out->flags=0;

  memcpy(key, DisplayString(display), strlen(DisplayString(display)));
  memcpy(key+strlen(DisplayString(display)), &colormap, sizeof(Colormap));
  memcpy(key+strlen(DisplayString(display))+sizeof(Colormap), screen_in_out, 
	 sizeof(XColor));

  if ((recptr=xcache_find(keylen, key)))
    {
      memcpy(screen_in_out, recptr->data, recptr->datalen);
#if DEBUG_AC
      TIMELOG("AllocColor hit!");
#endif
    } 
  else 
    {
      ret=XAllocColor(display, colormap, screen_in_out);
      if (ret) 
        xcache_store(keylen, key, sizeof(XColor), (char*)screen_in_out);
#if DEBUG_AC
      TIMELOG("AllocColor miss!");
      {
	static char s[1024];
	sprintf(s, "  %lu %hu %hu %hu %hhd %hhd", 
		screen_in_out->pixel, screen_in_out->red, screen_in_out->blue, 
		screen_in_out->green, screen_in_out->pad, screen_in_out->flags);
	TIMELOG(s);
      }
#endif
    }  
  return ret;
}


/*****************************************************************************
 XListFonts
 *****************************************************************************/
// Forward decl's.  See below for definitions.
static char **data2nameset(char *data, unsigned int datalen, int *count);
static char *nameset2data(char **nameset, int count, unsigned int *datalenp);

char **
xcache_ListFonts(Display *display, char *pattern, int maxnames, 
		 int *actual_count_return) 
{
  unsigned int keylen=
   strlen(DisplayString(display)) + sizeof(int) + strlen(pattern);
  unsigned int datalen=0;
  static unsigned char key[MAXKEYLENSIZE];
  unsigned char *data=NULL;
  struct _xcache_record *recptr=NULL;
  char **ret=NULL;

  if (keylen >= MAXKEYLENSIZE) 
    return XListFonts(display, pattern, maxnames, actual_count_return);

  memset(key, 0, keylen);

  /* Make key: */
  memcpy(key, DisplayString(display), strlen(DisplayString(display)));
  memcpy(key+strlen(DisplayString(display)), pattern, strlen(pattern));
  memcpy(key+strlen(DisplayString(display))+strlen(pattern), &maxnames, 
	 sizeof(int));

  if ((recptr=xcache_find(keylen, key)))
    {
      ret=data2nameset(recptr->data, recptr->datalen, actual_count_return);
#if DEBUG_LF
      TIMELOG("ListFonts hit!");
#endif
    } 
  else 
    {
      ret=XListFonts(display, pattern, maxnames, actual_count_return);
      data=nameset2data(ret, *actual_count_return, &datalen);
      xcache_store(keylen, key, sizeof(datalen), data);
#if DEBUG_LF
      TIMELOG("ListFonts miss!");
      {
	static char s[1024];
	sprintf(s, "  [%s] %d",
		pattern, maxnames);
	TIMELOG(s);
      }
#endif
    }  
  return ret;
}

char **
data2nameset(char *data, unsigned int datalen, int *count) 
{
  char **ret=NULL;
  char *nextstr=NULL, *retspace;
  unsigned int i=0;

  memcpy(count, data, sizeof(int));
  assert(*count>0);
  data+=sizeof(int);
  ret=(char**)xmalloc(sizeof(char*)*(*count));
  datalen-=sizeof(int);
  retspace=(char*)xmalloc(sizeof(char)*datalen);
  memcpy(retspace, data, datalen);
  nextstr=data;
  for(i=0; i<*count; ++i) 
    {
      ret[i]=nextstr;
      nextstr=strchr(nextstr,0)+1;
    }
  return ret;
}

char *
nameset2data(char **nameset, int count, unsigned int *datalenp) 
{
  unsigned int datalen=0, i=0;
  char *data, *datap;

  datalen=sizeof(int);
  for(i=0; i< count; ++i) 
    datalen+=strlen(nameset[i])+1;
  data=(char*)xmalloc(sizeof(char)*datalen);
  *datalenp=datalen;

  memcpy(data, &count, sizeof(int));

  datap=data+sizeof(int);
  for(i=0; i<count; ++i) 
    {
      unsigned int llen=strlen(nameset[i])+1;
      memcpy(datap, nameset[i], llen);
      datap+=llen;
    }

  return data;  
}

#ifdef USE_XCACHE_LFQ
/*****************************************************************************
 XLoadQueryFont
 *****************************************************************************/


  /* XXX TODO XXX There is a big woopsie here in that I don't see how to
   * XXX TODO XXX cache the ext_data member of the XFontStruct (which is a
   * XXX TODO XXX linked list of arbitrary data bits, the size of which is
   * XXX TODO XXX not known).  Let's try just dropping the member and seeing
   * XXX TODO XXX what happens */

char *fontstruct2data(XFontStruct *f, unsigned int *datalenp);
XFontStruct *data2fontstruct(char *data, unsigned int datalen);

XFontStruct *
xcache_LoadQueryFont(Display *display, char *name) 
{
  unsigned int keylen=strlen(DisplayString(display))+strlen(name)+1;
  unsigned int datalen=0;
  static unsigned char key[MAXKEYLENSIZE];
  unsigned char *data=NULL;
  struct _xcache_record *recptr=NULL;
  XFontStruct *ret=NULL;

  if (keylen >= MAXKEYLENSIZE) 
    return XLoadQueryFont(display, name);

  memset(key, 0, keylen);

  memcpy(key, DisplayString(display), strlen(DisplayString(display)));
  memcpy(key+strlen(DisplayString(display)), name, strlen(name));
  if (recptr=xcache_find(keylen, key)) 
    {
      ret=data2fontstruct(recptr->data, recptr->datalen);
#if DEBUG_LQF
      TIMELOG("LoadQueryFont hit!");
#endif
    } 
  else 
    {
      ret=XLoadQueryFont(display, name);
      data=fontstruct2data(ret, &datalen);
      if (ret) 
        xcache_store(keylen, key, datalen, data);
#if DEBUG_LQF
      TIMELOG("LoadQueryFont miss!");
      {
	static char s[1024];
	sprintf(s, "  [%s]", name);
	TIMELOG(s);
      }
#endif
    }  
  return ret;
}

XFontStruct *
data2fontstruct(char *data, unsigned int datalen) 
{
  XFontStruct *ret=(XFontStruct*)xmalloc(sizeof(XFontStruct));
  XFontProp *retprop=(XFontProp*)xmalloc(sizeof(XFontProp));
  XCharStruct *retcs=(XCharStruct*)xmalloc(sizeof(XCharStruct));

  memcpy(ret, data, sizeof(XFontStruct));
  memcpy(retprop, data+sizeof(XFontStruct), sizeof(XFontProp));
  memcpy(retcs,  data+sizeof(XFontStruct)+sizeof(XFontProp), 
	 sizeof(XCharStruct));
  ret->properties=retprop;
  ret->per_char=retcs;

  return ret;
}

char *
fontstruct2data(XFontStruct *f, unsigned int *datalenp) 
{
  unsigned int datalen, datac;
  char *data;
  XFontStruct tmp;
  
  memcpy(&tmp, f, sizeof(XFontStruct));

  tmp.ext_data=NULL;

  datalen=sizeof(XFontStruct)+sizeof(XFontProp)+sizeof(XCharStruct);
  data=(char*)xmalloc(datalen);

  memcpy(data, &tmp, sizeof(XFontStruct));
  datac+=sizeof(XFontStruct);
  /* Also the properties member is an array that should be dealt with */
  memcpy(data+datac, tmp.properties, sizeof(XFontProp));
  datac+=sizeof(XFontProp);
  memcpy(data+datac, tmp.per_char, sizeof(XCharStruct));
  
  *datalenp=datalen;
  return data;
}
#endif /* USE_XCACHE_LFQ */

/*****************************************************************************
 XGetFontProperty
 *****************************************************************************/
#if 0
/* Again, same problem here... */
Bool xcache_GetFontProperty(XFontStruct *f, Atom atom, unsigned long *ret_val) {
}
#endif

/*****************************************************************************
 XQueryColor
 *****************************************************************************/
void 
xcache_QueryColor(Display *display, Colormap colormap, XColor *xc) 
{
  unsigned int keylen=strlen(DisplayString(display))+
   sizeof(Colormap)+sizeof(XColor);
  static unsigned char key[MAXKEYLENSIZE];
  struct _xcache_record *recptr=NULL;

  if (keylen >= MAXKEYLENSIZE)
    return XQueryColor(display, colormap, xc);

  memset(key, 0, keylen);
  xc->pad=0; xc->flags=0; xc->red=xc->blue=xc->green=0;

  memcpy(key, DisplayString(display), strlen(DisplayString(display)));
  memcpy(key+strlen(DisplayString(display)), &colormap, sizeof(Colormap));
  memcpy(key+strlen(DisplayString(display))+sizeof(Colormap), xc, 
	 sizeof(XColor));

  if ((recptr=xcache_find(keylen, key)))
    {
      memcpy(xc, recptr->data, recptr->datalen);
#if DEBUG_QC
      TIMELOG("QueryColor hit!");
#endif
    } 
  else 
    {
      XQueryColor(display, colormap, xc);
      xcache_store(keylen, key, sizeof(XColor), (char*)xc);
#if DEBUG_QC
      TIMELOG("QueryColor miss!");
      {
	static char s[1024];
	sprintf(s, "  %lu %hu %hu %hu %hhd %hhd", 
		xc->pixel, xc->red, xc->blue, xc->green, xc->pad, xc->flags);
	TIMELOG(s);
      }
#endif
    }  
  
}



/*****************************************************************************
 XQueryColors
 *****************************************************************************/
void 
xcache_QueryColors(Display *display, Colormap colormap, 
		   XColor xc[], int ncolors) 
{
  int i=0;
  for(i=0; i<ncolors; ++i) 
    xcache_QueryColor(display, colormap, &xc[i]);
}

/*****************************************************************************
 Generic logging mechanism -- this will simply log the file and source line 
 where the TIMELOG(s) macro was called, noting the string s passed to the macro
 and timestamping the line in /tmp/timelog.  Obviously this should never be 
 enabled in a non-testing environment.
 *****************************************************************************/

#ifdef USE_XLOG

void 
timerlog(char *s, unsigned int c, char *extra) 
{
  static FILE *logfile = NULL;
  static time_t now = 0;
  if (logfile==NULL) logfile=fopen("/tmp/timelog", "a");
  now=time(NULL);
  fprintf(logfile, "%s:%u %s %s", s, c, extra, ctime(&now));
  fflush(logfile);
}
#endif /* USE_XLOG */

[-- Attachment #3: xcache.h --]
[-- Type: application/octet-stream, Size: 1584 bytes --]

/* The xcache structure allows caching of arbitrary information.  
   We use it to save color and font information so that the X server 
   doesn't need to be queried more than once for the same question.

*/

#ifndef XCACHE_H_INCLUDED
#define XCACHE_H_INCLUDED

#ifdef USE_XCACHE

#include <X11/X.h>
#include <X11/Xlib.h>
#include <assert.h>
#include <X11/Xatom.h>

#ifdef USE_XLOG
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TIMELOG(extra) do { \
  timerlog(__FILE__, __LINE__, extra); \
} while (0);

void timerlog(char *s, unsigned int c, char *extra);
#else
#define TIMELOG(extra) do { ; } while(0);
#endif /* USE_XLOG */

#ifndef XCACHE_C /* So that the real calls don't get messed up */
#define XAllocColor xcache_AllocColor
#define XListFonts xcache_ListFonts
/* #define XListQueryFonts xcache_ListQueryFonts NOT DONE YET! */
/* #define XGetFontProperty xcache_GetFontProperty NOT DONE YET! */
#define XQueryColor xcache_QueryColor
#define XQueryColors xcache_QueryColors
#endif /* ! XCACHE_C */

Status xcache_AllocColor(Display *display, Colormap colormap, XColor *screen_in_out);
char **xcache_ListFonts(Display *display, char *pattern, int maxnames, int *actual_count_return);
/* XFontStruct *xcache_LoadQueryFont(Display *display, char *name); */
/* Bool xcache_GetFontProperty(XFontStruct *f, Atom atom, unsigned long *ret_val); */
void xcache_QueryColor(Display *display, Colormap colormap, XColor *xc);
void xcache_QueryColors(Display *display, Colormap colormap, XColor *xc, int ncolors);

#endif /* USE_XCACHE */

#endif /* XCACHE_H_INCLUDED */

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Miles Bader]

On Sat, Oct 05, 2002 at 10:31:07PM -0700, Ami Fischman wrote:
> - The keys were being xmalloc'ed (unnecessarily) and then leaked.  Instead
>   each of the wrapper functions now has a static buffer (of a #define'able
>   size) to store the transient keys.  

Note that you could also use `alloca', which is almost as cheap as a static
buffer, and doesn't require you to free anything.

-Miles
-- 
P.S.  All information contained in the above letter is false,
      for reasons of military security.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Jan D.]

>
> without ~/.emacs (-q):
> Std emacs 21.1
>     0.24user 0.05system 0:45.31elapsed
> emacs-cvs --without-xim, with color caching:
>     0.25user 0.03system 0:29.80elapsed
>
> with ~/.emacs:
> emacs-21.1:
>     0.96user 0.22system 1:04.65elapsed
> emacs-cvs --without-xim, with color caching:
>     0.94user 0.15system 0:32.40elapsed

Do you know how much speedup that results from --without-xim and how much 
is due to caching?

	Jan D.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Ami Fischman]

"Jan D." <jan.h.d@swipnet.se> writes:

> Do you know how much speedup that results from --without-xim and how much is
> due to caching?

In fact I thought that it was almost all from the caching (I had a vague
memory of having attempted to use --without-xim in the past and being
disappointed with the speed delta).  Since you asked, I re-ran some tests,
and realized that most of the speedup is coming from the --without-xim.
The caching now makes about 5-7s difference on different runs, although I
suspect the difference would be more pronounced as the emacs session got
longer.  Right now I'm just doing a:
time emacs -f save-buffers-kill-emacs
with and without -q.  Is there a standard way to time emacs sessions?
(other than using gprof, which I suspect would not be very useful, given
the X delays).

-- 
  Ami Fischman
  usenet@fischman.org

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Jan D.]

> 3) Do you have any ideas on caching XFontStruct's?  Specifically, the
>    XExtData* list has private_data members whose size is unknown (as far 
> as
>    I can see).

Talking about pango, they have a font cache for X11 fonts in their X11 
specific code.  May be worthwhile to check out.

	Jan D.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Ami Fischman]

[-- Attachment #1: Type: text/plain, Size: 517 bytes --]

I was making an assumption before, which was that the keys I was using would
not overlap between the functions.  This was mistaken, as I have now
observed (a symptom was that sometimes the mode-line of the active buffer
would be gray-on-gray (instead of black-on-gray), so unreadable).  I've
added a type char to the key.  Also, took out the beginnings of the font
caching functions, since they are broken and were just cluttering things up.
Attaching the updated versions.

-- 
  Ami Fischman
  usenet@fischman.org


[-- Attachment #2: xcache.c --]
[-- Type: application/octet-stream, Size: 5990 bytes --]

#define XCACHE_C

#include "xcache.h"
#include "config.h"
#include "lisp.h"

#define MAXKEYLENSIZE 2048

/* This gets prepended to the key to insure cached data doesn't 
 * get confused between the different wrappers (necessary) 
 */
static unsigned char XAC=1;
static unsigned char XQC=2;
static unsigned char XQCS=3;

#define DEBUG_AC 0
#define DEBUG_QC 0
#define DEBUG_LF 0
#define DEBUG_LQF 0

/*****************************************************************************
 Definitions of main xcache structure & access functions
 *****************************************************************************/
struct _xcache_record
{
  unsigned int keylen, datalen;
  char *key;
  char *data;
  struct _xcache_record *nextrec;
};

struct _xcache 
{
  unsigned int numrecs;
  unsigned int cachesize;
  struct _xcache_record *first;
};

static struct _xcache xcache = {0, 0, NULL};

struct _xcache_record *
xcache_store(unsigned int keylen, char *key, unsigned int datalen, char *data)
{
  struct _xcache_record *newrec=
   (struct _xcache_record*)xmalloc(sizeof(struct _xcache_record));

  newrec->keylen=keylen; newrec->datalen=datalen;
  newrec->key=(char*)xmalloc(keylen);
  newrec->data=(char*)xmalloc(datalen);
  memcpy(newrec->key, key, keylen);
  memcpy(newrec->data, data, datalen);
  newrec->nextrec=xcache.first;
  xcache.first=newrec;
  xcache.numrecs++;
  xcache.cachesize+=keylen+datalen+(sizeof(unsigned int)*2);

  return newrec;
}

struct _xcache_record *
xcache_find(unsigned int keylen, char *key) 
{
  struct _xcache_record *recptr = xcache.first;
  while (recptr) 
    {
      if ((recptr->keylen==keylen) && !memcmp(key, recptr->key, keylen)) 
       return recptr;
      recptr=recptr->nextrec;
    }
  return NULL;
}


/*****************************************************************************
 XAllocColor
 *****************************************************************************/
/* Status is just an int, at least on XFree86 */
Status 
xcache_AllocColor(Display *display, Colormap colormap, XColor *screen_in_out) 
{
  unsigned int keylen=sizeof(unsigned char) +
   strlen(DisplayString(display))+sizeof(Colormap)+sizeof(XColor);
  static unsigned char key[MAXKEYLENSIZE];
  struct _xcache_record *recptr=NULL;
  Status ret=1;

  if (keylen > MAXKEYLENSIZE) 
    return XAllocColor(display, colormap, screen_in_out);

  memset(key, 0, keylen);
  screen_in_out->pad=0;   screen_in_out->flags=0;

  memcpy(key, &XAC, sizeof(unsigned char));
  memcpy(key+sizeof(unsigned char), DisplayString(display), 
	 strlen(DisplayString(display)));
  memcpy(key+sizeof(unsigned char) +strlen(DisplayString(display)), 
	 &colormap, sizeof(Colormap));
  memcpy(key+sizeof(unsigned char)+strlen(DisplayString(display))
	 +sizeof(Colormap), screen_in_out, sizeof(XColor));

  if ((recptr=xcache_find(keylen, key)))
    {
      memcpy(screen_in_out, recptr->data, recptr->datalen);
#if DEBUG_AC
      TIMELOG("AllocColor hit!");
#endif
    } 
  else 
    {
      ret=XAllocColor(display, colormap, screen_in_out);
      if (ret) 
        xcache_store(keylen, key, sizeof(XColor), (char*)screen_in_out);
#if DEBUG_AC
      TIMELOG("AllocColor miss!");
      {
	static char s[1024];
	sprintf(s, "  %lu %hu %hu %hu %hhd %hhd", 
		screen_in_out->pixel, screen_in_out->red, screen_in_out->blue, 
		screen_in_out->green, screen_in_out->pad, screen_in_out->flags);
	TIMELOG(s);
      }
#endif
    }  
  return ret;
}


/*****************************************************************************
 XQueryColor
 *****************************************************************************/
void 
xcache_QueryColor(Display *display, Colormap colormap, XColor *xc) 
{
  unsigned int keylen=sizeof(unsigned char)+strlen(DisplayString(display))+
   sizeof(Colormap)+sizeof(XColor);
  static unsigned char key[MAXKEYLENSIZE];
  struct _xcache_record *recptr=NULL;

  if (keylen >= MAXKEYLENSIZE)
    return XQueryColor(display, colormap, xc);

  memset(key, 0, keylen);
  xc->pad=0; xc->flags=0; xc->red=xc->blue=xc->green=0;

  memcpy(key, &XQC, sizeof(unsigned char));
  memcpy(key+sizeof(unsigned char), DisplayString(display), 
	 strlen(DisplayString(display)));
  memcpy(key+sizeof(unsigned char)+strlen(DisplayString(display)), 
	 &colormap, sizeof(Colormap));
  memcpy(key+sizeof(unsigned char)+strlen(DisplayString(display))
	 +sizeof(Colormap), xc, sizeof(XColor));

  if ((recptr=xcache_find(keylen, key)))
    {
      memcpy(xc, recptr->data, recptr->datalen);
#if DEBUG_QC
      TIMELOG("QueryColor hit!");
#endif
    } 
  else 
    {
      XQueryColor(display, colormap, xc);
      xcache_store(keylen, key, sizeof(XColor), (char*)xc);
#if DEBUG_QC
      TIMELOG("QueryColor miss!");
      {
	static char s[1024];
	sprintf(s, "  %lu %hu %hu %hu %hhd %hhd", 
		xc->pixel, xc->red, xc->blue, xc->green, xc->pad, xc->flags);
	TIMELOG(s);
      }
#endif
    }  
  
}



/*****************************************************************************
 XQueryColors
 *****************************************************************************/
void 
xcache_QueryColors(Display *display, Colormap colormap, 
		   XColor xc[], int ncolors) 
{
  int i=0;
  for(i=0; i<ncolors; ++i) 
    xcache_QueryColor(display, colormap, &xc[i]);
}

/*****************************************************************************
 Generic logging mechanism -- this will simply log the file and source line 
 where the TIMELOG(s) macro was called, noting the string s passed to the macro
 and timestamping the line in /tmp/timelog.  Obviously this should never be 
 enabled in a non-testing environment.
 *****************************************************************************/

#ifdef USE_XLOG

void 
timerlog(char *s, unsigned int c, char *extra) 
{
  static FILE *logfile = NULL;
  static time_t now = 0;
  if (logfile==NULL) logfile=fopen("/tmp/timelog", "a");
  now=time(NULL);
  fprintf(logfile, "%s:%u %s %s", s, c, extra, ctime(&now));
  fflush(logfile);
}
#endif /* USE_XLOG */

[-- Attachment #3: xcache.h --]
[-- Type: application/octet-stream, Size: 1590 bytes --]

/* The xcache structure allows caching of arbitrary information.  
   We use it to save color and font information so that the X server 
   doesn't need to be queried more than once for the same question.

*/

#ifndef XCACHE_H_INCLUDED
#define XCACHE_H_INCLUDED

#ifdef USE_XCACHE

#include <X11/X.h>
#include <X11/Xlib.h>
#include <assert.h>
#include <X11/Xatom.h>

#ifdef USE_XLOG
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TIMELOG(extra) do { \
  timerlog(__FILE__, __LINE__, extra); \
} while (0);

void timerlog(char *s, unsigned int c, char *extra);
#else
#define TIMELOG(extra) do { ; } while(0);
#endif /* USE_XLOG */

#ifndef XCACHE_C /* So that the real calls don't get messed up */
#define XAllocColor xcache_AllocColor
/* #define XListFonts xcache_ListFonts */
/* #define XListQueryFonts xcache_ListQueryFonts NOT DONE YET! */
/* #define XGetFontProperty xcache_GetFontProperty NOT DONE YET! */
#define XQueryColor xcache_QueryColor
#define XQueryColors xcache_QueryColors
#endif /* ! XCACHE_C */

Status xcache_AllocColor(Display *display, Colormap colormap, XColor *screen_in_out);
char **xcache_ListFonts(Display *display, char *pattern, int maxnames, int *actual_count_return);
/* XFontStruct *xcache_LoadQueryFont(Display *display, char *name); */
/* Bool xcache_GetFontProperty(XFontStruct *f, Atom atom, unsigned long *ret_val); */
void xcache_QueryColor(Display *display, Colormap colormap, XColor *xc);
void xcache_QueryColors(Display *display, Colormap colormap, XColor *xc, int ncolors);

#endif /* USE_XCACHE */

#endif /* XCACHE_H_INCLUDED */

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Ami Fischman]

"Jan D." <jan.h.d@swipnet.se> writes:

> Talking about pango, they have a font cache for X11 fonts in their X11
> specific code.  May be worthwhile to check out.

Checked it out.  The way pango does it is by only caching the pointer to
the returned XFontStruct, and maintaining a reference count for each
structure (in order to handle the freeing of these structures later).  That
could work here as well, if we wrap the XFree.*Font.* calls as well.  

However, my cursory tracing/sniffing seems to indicate that not that many
packets get wasted on redundant calls to the font functions, so I'm not
sure this is worth doing.

-- 
  Ami Fischman
  usenet@fischman.org

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Stefan Monnier]

> - The keys were being xmalloc'ed (unnecessarily) and then leaked.  Instead
>   each of the wrapper functions now has a static buffer (of a #define'able
>   size) to store the transient keys.

Yuck!  At least use alloca.  Disallowing re-entrance is always a bad idea.

By the way, is the cached answer always the same as the one we would have
goten without the cache ?  IF not, what is the potential impact ?
Can/should we invalidate the cache sometimes to avoid/reduce those
problems ?


	Stefan

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Richard Stallman]

    Another obvious thing to cache would be the font data that emacs can
    request, although it is much less clear to me how to cache the XExtData
    list that is potentially contained in an XFontStruct (namely, how do you
    know how big the private data is?  If anyone has any suggestions here, I'd
    like to hear them).

Maybe the thing to do is to copy and cache just the data that Emacs
actually looks at in that code.

For fonts that are actually being used for display, Emacs already has
a cache.  So I suspect (though I'm partly guessing) that this is for
some other part of Emacs which is just thinking about fonts and not
actually using them.  If that is true, I suspect that the parts of the
font data it uses are rather limited.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Richard Stallman]

It looks like you've done a good job.

    4) Adding an option to configure.in to enable a (default=off) switch for
       USE_XCACHE.  I don't feel like learning autoconf for this one thing.

Such a feature would be a bad idea--useless complexity.
Using a configure option to control something is a last resort.

What would be both simpler and more useful is a feature at run time to
turn the cache use on and off.  A Lisp variable forwarded with
DEFVAR_BOOL to a C int variable could control it.  The entry points
could avoid checking the cache if the C variable is 0.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Ami Fischman]

"Stefan Monnier" <monnier+gnu/emacs@rum.cs.yale.edu> writes:

[...]

> Yuck!  At least use alloca.  Disallowing re-entrance is always a bad idea.

I agree with the first and third statements.  But, I was unaware that emacs
had threading support (in fact, I was under the impression that it was
highly NON re-entrant, which is why, for instance, running lisp routines in
the background of an emacs session is not possible).  I've converted to use
alloca (it's just the two buffers), and it works just as well.  

But, if there's a possibility that these routines will be used in a
re-entrant manner, I should add a mutex lock to the cache.  Is this really a
possibility, or were you just expressing a distaste for non-re-entrant code
on principle?

> By the way, is the cached answer always the same as the one we would have
> goten without the cache ?  

For AllocColor, yes.  For XQueryColor{,s}, no.

> IF not, what is the potential impact ?  

The worst that can happen is that an old RGB set would be returned for a
pixel value (rather than the new one), and thus that the wrong color will
be shown in emacs.

> Can/should we invalidate the cache sometimes to avoid/reduce those
> problems ?

"should" -> yes.  "Can" is trickier.  In order for an old cache entry to be
"wrong", the X server will have to allocate a colormap entry once, then
dealloc it, then allocate another color in that space.  Which really comes
down to the X server having very few colormap entries and an app that asks
for a lot.  I don't think emacs will be running into this problem soon
(although, testing with xpms/pngs might be instructive here).  

-- 
  Ami Fischman
  usenet@fischman.org

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Stefan Monnier]

> re-entrant manner, I should add a mutex lock to the cache.  Is this really a
> possibility, or were you just expressing a distaste for non-re-entrant code
> on principle?

It was on principle.  It saves you from having to think about
whether or not re-entrance can happen.

> > By the way, is the cached answer always the same as the one we would have
> > goten without the cache ?  
> For AllocColor, yes.  For XQueryColor{,s}, no.

For AllocColor ?
How come ?  Can't Emacs dealloc the color and re-allocate it again and
get a different result (because the color cell was allocated to some other
color in the mean time) ?

> > Can/should we invalidate the cache sometimes to avoid/reduce those
> > problems ?
> "should" -> yes.  "Can" is trickier.  In order for an old cache entry to be
> "wrong", the X server will have to allocate a colormap entry once, then
> dealloc it, then allocate another color in that space.  Which really comes
> down to the X server having very few colormap entries and an app that asks
> for a lot.  I don't think emacs will be running into this problem soon
> (although, testing with xpms/pngs might be instructive here).

As someone whose colormap is full about 95% of the time, I can
assure you that tose things happen ;-)
Maybe we can flush the cache whenever Emacs deallocates a color
(that shouldn't happen too often, right?).  BTW shouldn't we cache
DeAllocColor as well since the server normally keeps a counter
and each AllocColor should have a matching DeAllocColor ?


	Stefan

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Ami Fischman]

[-- Attachment #1: Type: text/plain, Size: 1081 bytes --]

"Stefan Monnier" <monnier+gnu/emacs@rum.cs.yale.edu> writes:

[...]

> As someone whose colormap is full about 95% of the time, I can
> assure you that tose things happen ;-)

Really?  I guess I've been spoiled by my video card (which is a not very
respectable 4M matrox) and more respectable lack of use of colors :)

The shame of not caching the XFreeColors has caught up with me, so I added
a refcount and a wrapper for XFreeColors that takes advantage of the
refcount (so the X server only sees the Free request once per cached color,
and upon final Free'ing, the cache entry is removed).  This ensures there
are no stale entries in the cache.  The performance hit is negligible in my
tests.

The newest versions of xcache.[ch] reflect:
- Reformatted function calls to K&R style
- Added a lot of comments to explain what's going on
- Added refcounting & XFreeColors caching

Note that in order to take advantage of the XFreeColors caching, you need
to add the xcache.h header to other files.  Included is also a patch that
does that.

-- 
  Ami Fischman
  usenet@fischman.org


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: add-xcache.patch --]
[-- Type: text/x-patch, Size: 1063 bytes --]

Index: xfaces.c
===================================================================
RCS file: /cvsroot/emacs/emacs/src/xfaces.c,v
retrieving revision 1.264
diff -r1.264 xfaces.c
587a588,592
> 
> #ifdef USE_XCACHE
> #include "xcache.h"
> #endif /* USE_XCACHE */
> 
Index: xfns.c
===================================================================
RCS file: /cvsroot/emacs/emacs/src/xfns.c,v
retrieving revision 1.562
diff -r1.562 xfns.c
121a122,125
> #ifdef USE_XCACHE
> #include "xcache.h"
> #endif /* USE_XCACHE */
> 
Index: xrdb.c
===================================================================
RCS file: /cvsroot/emacs/emacs/src/xrdb.c,v
retrieving revision 1.48
diff -r1.48 xrdb.c
68a69,72
> #ifdef USE_XCACHE
> #include "xcache.h"
> #endif /* USE_XCACHE */
> 
Index: xterm.h
===================================================================
RCS file: /cvsroot/emacs/emacs/src/xterm.h,v
retrieving revision 1.136
diff -r1.136 xterm.h
36c36,39
< #endif
---
> #ifdef USE_XCACHE
> #include "xcache.h"
> #endif /* USE_XCACHE */
> #endif /* USE_X_TOOLKIT */

[-- Attachment #3: xcache.h --]
[-- Type: text/plain, Size: 1782 bytes --]

/* The xcache structure allows caching of arbitrary information.  
   We use it to save color and font information so that the X server 
   doesn't need to be queried more than once for the same question.

*/

#ifndef XCACHE_H_INCLUDED
#define XCACHE_H_INCLUDED

#ifdef USE_XCACHE

#include <X11/X.h>
#include <X11/Xlib.h>
#include <assert.h>
#include <X11/Xatom.h>

#ifdef USE_XLOG
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TIMELOG(extra) do { \
  timerlog(__FILE__, __LINE__, extra); \
} while (0);

void timerlog(char *s, unsigned int c, char *extra);
#else
#define TIMELOG(extra) do { ; } while(0);
#endif /* USE_XLOG */

#ifndef XCACHE_C /* So that the real calls don't get messed up */
#define XAllocColor xcache_AllocColor
/* #define XListFonts xcache_ListFonts */
/* #define XListQueryFonts xcache_ListQueryFonts NOT DONE YET! */
/* #define XGetFontProperty xcache_GetFontProperty NOT DONE YET! */
#define XQueryColor xcache_QueryColor
#define XQueryColors xcache_QueryColors
#define XFreeColors xcache_FreeColors
#endif /* ! XCACHE_C */

Status xcache_AllocColor(Display *display, Colormap colormap, 
			 XColor *screen_in_out);
char **xcache_ListFonts(Display *display, char *pattern, int maxnames, 
			int *actual_count_return);
/* XFontStruct *xcache_LoadQueryFont(Display *display, char *name); */
/* Bool xcache_GetFontProperty(XFontStruct *f, Atom atom, unsigned long *ret_val); */
void xcache_QueryColor(Display *display, Colormap colormap, XColor *xc);
void xcache_QueryColors(Display *display, Colormap colormap, XColor *xc, 
			int ncolors);

void xcache_FreeColors(Display *display, Colormap colormap, 
		       unsigned long pixels[], int npixels, 
		       unsigned long planes);

#endif /* USE_XCACHE */

#endif /* XCACHE_H_INCLUDED */

[-- Attachment #4: xcache.c --]
[-- Type: text/plain, Size: 9603 bytes --]

#define XCACHE_C

#include "xcache.h"
#include "config.h"
#include "lisp.h"

/* General comments: 
 *
 * - Each of the wrapper functions (xcache_[A-Z][A-z]*) goes through a similar
 *   routine: allocate & build the key, search for the key in the cache, if 
 *   found, return that data, else execute the underlying X function and store 
 *   the result in the cache for future use.
 *
 * - The keys are basically a concatenation of the data type (XAC, XQC) with 
 *   the arguments to the wrapper function.
 */

/* The size of the largest key we bother to cache */
#define MAXKEYLENSIZE 2048

/* This gets prepended to the key to insure cached data doesn't 
 * get confused between the different wrappers (necessary) 
 */
static unsigned char XAC=1;
static unsigned char XQC=2;

/* For debugging purposes; should be 0 unless you want hit/miss info */
#define DEBUG_AC 0
#define DEBUG_QC 0
#define DEBUG_LF 0
#define DEBUG_LQF 0

/*****************************************************************************
 Definitions of main xcache structure & access functions
 The cache structure consists of a linked list of cache records.  Each record
 consists of key and data pointers, and lengths for each of those.  
 xcache_find(keylen, key) locates a cache record by its key and returns it,
 whereas xcache_store(keylen, key, datalen, data) creates and stores a new 
 record in the cache list (at the head of the list).
 *****************************************************************************/
struct _xcache_record
{
  unsigned int keylen, datalen;   /* Lengths of the key and data binary strings */
  char *key;
  char *data;                     
  unsigned int refcount;          /* How many times is this data being used? */
  struct _xcache_record *nextrec; /* next record in the list */
};

struct _xcache 
{
  unsigned int numrecs;           /* Length of the list */
  unsigned int cachesize;         /* In bytes */
  struct _xcache_record *first;   /* Head of the list */
};

static struct _xcache xcache = {0, 0, NULL};  /* This is the actual _xcache object */

/* Store a new record into the cache */
struct _xcache_record *
xcache_store(keylen, key, datalen, data)
     unsigned int keylen;
     char *key;
     unsigned int datalen;
     char *data;
{
  struct _xcache_record *newrec=
   (struct _xcache_record*)xmalloc(sizeof(struct _xcache_record));

  newrec->keylen=keylen; newrec->datalen=datalen;
  newrec->key=(char*)xmalloc(keylen);
  newrec->data=(char*)xmalloc(datalen);
  memcpy(newrec->key, key, keylen);
  memcpy(newrec->data, data, datalen);
  newrec->nextrec=xcache.first;
  xcache.first=newrec;
  xcache.numrecs++;
  newrec->refcount=1;
  xcache.cachesize+=keylen+datalen+(sizeof(unsigned int)*2);

  return newrec;
}

/* Find a cache record in the cache */
struct _xcache_record *
xcache_find(keylen, key)
     unsigned int keylen;
     char *key;
{
  struct _xcache_record *recptr = xcache.first;
  while (recptr) 
    {
      if ((recptr->keylen==keylen) && !memcmp(key, recptr->key, keylen)) 
       return recptr;
      recptr=recptr->nextrec;
    }
  return NULL;
}

/* Remove a cache record from the cache */
unsigned char
xcache_remove(keylen, key)
     unsigned int keylen;
     char *key;
{
  struct _xcache_record *recptr = xcache.first, *prevptr=NULL;
  while (recptr) 
    {
      if ((recptr->keylen==keylen) && !memcmp(key, recptr->key, keylen)) 
        {
	  if (prevptr==NULL) 
	    xcache.first=xcache.first->nextrec;
	  else
	    prevptr->nextrec=recptr->nextrec;
	      
	  xcache.numrecs--; 
	  xcache.cachesize -= recptr->keylen + recptr->datalen 
	   + (sizeof(unsigned int)*2);
	  xfree(recptr->key); xfree(recptr->data); xfree(recptr);
	  return 1;
	}
      prevptr=recptr;
      recptr=recptr->nextrec;
    }
  return 0;
}


/*****************************************************************************
 XAllocColor
 *****************************************************************************/
/* Status is just an int, at least on XFree86 */
Status 
xcache_AllocColor(display, colormap, screen_in_out)
     Display *display;
     Colormap colormap;
     XColor *screen_in_out;
{
  unsigned int keylen=sizeof(unsigned char) +
   strlen(DisplayString(display))+sizeof(Colormap)+sizeof(XColor);
  unsigned char *key=alloca(sizeof(char)*MAXKEYLENSIZE);
  struct _xcache_record *recptr=NULL;
  Status ret=1;

  if (keylen >= MAXKEYLENSIZE) 
    return XAllocColor(display, colormap, screen_in_out);

  memset(key, 0, keylen);
  screen_in_out->pad=0;   screen_in_out->flags=0;

  memcpy(key, &XAC, sizeof(unsigned char));
  memcpy(key+sizeof(unsigned char), DisplayString(display), 
	 strlen(DisplayString(display)));
  memcpy(key+sizeof(unsigned char) +strlen(DisplayString(display)), 
	 &colormap, sizeof(Colormap));
  memcpy(key+sizeof(unsigned char)+strlen(DisplayString(display))
	 +sizeof(Colormap), screen_in_out, sizeof(XColor));

  if ((recptr=xcache_find(keylen, key)))
    {
      recptr->refcount++;
      memcpy(screen_in_out, recptr->data, recptr->datalen);
#if DEBUG_AC
      TIMELOG("AllocColor hit!");
#endif
    } 
  else 
    {
      ret=XAllocColor(display, colormap, screen_in_out);
      if (ret) 
        xcache_store(keylen, key, sizeof(XColor), (char*)screen_in_out);
#if DEBUG_AC
      TIMELOG("AllocColor miss!");
      {
	static char s[1024];
	sprintf(s, "  %lu %hu %hu %hu %hhd %hhd", 
		screen_in_out->pixel, screen_in_out->red, screen_in_out->blue, 
		screen_in_out->green, screen_in_out->pad, screen_in_out->flags);
	TIMELOG(s);
      }
#endif
    }  
  return ret;
}

/* A utility function that finds a cache record of type XAC
 * with a certain pixel value.  Used for XFreeColors wrapping. 
 */
struct _xcache_record *
xcache_AC_findpixel(pixel)
     unsigned int pixel;
{
  struct _xcache_record *recptr=xcache.first;
  XColor *xc=NULL;

  while (recptr)
    {
      if (memcmp(recptr->key, &XAC, sizeof(unsigned short)))
        recptr=recptr->nextrec;
      else
        {
	  xc=(XColor*)recptr->key+recptr->keylen-sizeof(XColor);
	  if (xc->pixel == pixel)
  	    return recptr;
	  recptr=recptr->nextrec;
	}
    }
  return NULL;
}


/*****************************************************************************
 XQueryColor
 *****************************************************************************/
void 
xcache_QueryColor(display, colormap, xc)
     Display *display;
     Colormap colormap;
     XColor *xc;
{
  unsigned int keylen=sizeof(unsigned char)+strlen(DisplayString(display))+
   sizeof(Colormap)+sizeof(XColor);
  unsigned char *key=alloca(sizeof(char)*MAXKEYLENSIZE);
  struct _xcache_record *recptr=NULL;

  if (keylen >= MAXKEYLENSIZE)
    {
      XQueryColor(display, colormap, xc);
      return;
    }

  memset(key, 0, keylen);
  xc->pad=0; xc->flags=0; xc->red=xc->blue=xc->green=0;

  memcpy(key, &XQC, sizeof(unsigned char));
  memcpy(key+sizeof(unsigned char), DisplayString(display), 
	 strlen(DisplayString(display)));
  memcpy(key+sizeof(unsigned char)+strlen(DisplayString(display)), 
	 &colormap, sizeof(Colormap));
  memcpy(key+sizeof(unsigned char)+strlen(DisplayString(display))
	 +sizeof(Colormap), xc, sizeof(XColor));

  if ((recptr=xcache_find(keylen, key)))
    {
      recptr->refcount++;
      memcpy(xc, recptr->data, recptr->datalen);
#if DEBUG_QC
      TIMELOG("QueryColor hit!");
#endif
    } 
  else 
    {
      XQueryColor(display, colormap, xc);
      xcache_store(keylen, key, sizeof(XColor), (char*)xc);
#if DEBUG_QC
      TIMELOG("QueryColor miss!");
      {
	static char s[1024];
	sprintf(s, "  %lu %hu %hu %hu %hhd %hhd", 
		xc->pixel, xc->red, xc->blue, xc->green, xc->pad, xc->flags);
	TIMELOG(s);
      }
#endif
    }  
  
}



/*****************************************************************************
 XQueryColors
 *****************************************************************************/
void 
xcache_QueryColors(display, colormap, xc, ncolors)
     Display *display;
     Colormap colormap;
     XColor xc[];
     int ncolors;
{
  int i=0;
  for(i=0; i<ncolors; ++i) 
    xcache_QueryColor(display, colormap, &xc[i]);
}

/*****************************************************************************
 XFreeColors
 *****************************************************************************/
void
xcache_FreeColors(display, colormap, pixels, npixels, planes)
     Display *display;
     Colormap colormap;
     unsigned long pixels[];
     int npixels;
     unsigned long planes;
{
  unsigned int i=0;
  struct _xcache_record *recptr=NULL;
  XColor *xc;

  memset(&xc, 0, sizeof(XColor));

  for(i=0; i<npixels; ++i) 
    {
      recptr=xcache_AC_findpixel(pixels[i]);
      eassert(recptr);
      if (recptr->refcount > 1) 
        recptr->refcount--;
      else 
        {
	  XFreeColors(display, colormap, &pixels[i], 1, planes);
	  xcache_remove(recptr->keylen, recptr->key);
	}
    }
}


/*****************************************************************************
 Generic logging mechanism -- this will simply log the file and source line 
 where the TIMELOG(s) macro was called, noting the string s passed to the macro
 and timestamping the line in /tmp/timelog.  Obviously this should never be 
 enabled in a non-testing environment.
 *****************************************************************************/

#ifdef USE_XLOG

void 
timerlog(char *s, unsigned int c, char *extra) 
{
  static FILE *logfile = NULL;
  static time_t now = 0;
  if (logfile==NULL) logfile=fopen("/tmp/timelog", "a");
  now=time(NULL);
  fprintf(logfile, "%s:%u %s %s", s, c, extra, ctime(&now));
  fflush(logfile);
}
#endif /* USE_XLOG */

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Ami Fischman]

Richard Stallman <rms@gnu.org> writes:

[...]

> What would be both simpler and more useful is a feature at run time to
> turn the cache use on and off.  A Lisp variable forwarded with
> DEFVAR_BOOL to a C int variable could control it.  The entry points
> could avoid checking the cache if the C variable is 0.

True.  A command-line option would also be in order, to save the delay at
startup before the lisp variable is eval'd.  Anyone feel like adding these
(cmd line opt & lisp var)?  

-- 
  Ami Fischman
  usenet@fischman.org

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Jan D.]

måndagen den 7 oktober 2002 kl 18.49 skrev Ami Fischman:

> "Stefan Monnier" <monnier+gnu/emacs@rum.cs.yale.edu> writes:
>
> [...]
>
>> As someone whose colormap is full about 95% of the time, I can
>> assure you that tose things happen ;-)
>
> Really?  I guess I've been spoiled by my video card (which is a not very
> respectable 4M matrox) and more respectable lack of use of colors :)

You can listen for XColormapEvent and invalidate the cache if the colormap
changes.  I think Emacs just uses one colormap.

> The shame of not caching the XFreeColors has caught up with me, so I added
> a refcount and a wrapper for XFreeColors that takes advantage of the
> refcount (so the X server only sees the Free request once per cached color,
> and upon final Free'ing, the cache entry is removed).  This ensures there
> are no stale entries in the cache.  The performance hit is negligible in 
> my
> tests.
>
> The newest versions of xcache.[ch] reflect:
> - Reformatted function calls to K&R style
> - Added a lot of comments to explain what's going on
> - Added refcounting & XFreeColors caching
>
> Note that in order to take advantage of the XFreeColors caching, you need
> to add the xcache.h header to other files.  Included is also a patch that
> does that.


Or, for gcc, do
make CC='gcc -include xcache.h'

	Jan D.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Jan D.]

> For AllocColor ?
> How come ?  Can't Emacs dealloc the color and re-allocate it again and
> get a different result (because the color cell was allocated to some other
> color in the mean time) ?

In principle, yes.  But if Emacs runs on the default visual, it uses the
default colormap, otherwise, it creates its own.  It would not be nice
by an application to change the default colormap or one created by Emacs.

It can happen, but I consider that a bug in the application that does
such a thing.

> As someone whose colormap is full about 95% of the time, I can
> assure you that tose things happen ;-)

What should happen is that when the colormap is full, a new one is
created and then the window manager switches colormap depending on
which application has the focus.

> Maybe we can flush the cache whenever Emacs deallocates a color
> (that shouldn't happen too often, right?).  BTW shouldn't we cache
> DeAllocColor as well since the server normally keeps a counter
> and each AllocColor should have a matching DeAllocColor ?

True, a counter is needed for proper allocate/free operation.

	Jan D.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Stefan Monnier]

> 
> > For AllocColor ?
> > How come ?  Can't Emacs dealloc the color and re-allocate it again and
> > get a different result (because the color cell was allocated to some other
> > color in the mean time) ?
> 
> In principle, yes.  But if Emacs runs on the default visual, it uses the
> default colormap, otherwise, it creates its own.  It would not be nice
> by an application to change the default colormap or one created by Emacs.
> 
> It can happen, but I consider that a bug in the application that does
> such a thing.

My "default" colormap has never behaved in that way.  It just contains
whichever colors have been requested by applications, i.e. it is changed
by applications like ExMH, Netscape, Emacs, ...

> > As someone whose colormap is full about 95% of the time, I can
> > assure you that tose things happen ;-)
> 
> What should happen is that when the colormap is full, a new one is
> created and then the window manager switches colormap depending on
> which application has the focus.

I hate colormap switching.  I much prefer what happens with Emacs:
when XAllocColor fails, Emacs looks for the nearest color in the map
and uses it.  After all I generally don't care that much about the
exact color.


	Stefan

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Jan D.]

>> In principle, yes.  But if Emacs runs on the default visual, it uses the
>> default colormap, otherwise, it creates its own.  It would not be nice
>> by an application to change the default colormap or one created by Emacs.
>>
>> It can happen, but I consider that a bug in the application that does
>> such a thing.
>
> My "default" colormap has never behaved in that way.  It just contains
> whichever colors have been requested by applications, i.e. it is changed
> by applications like ExMH, Netscape, Emacs, ...

You are right, I didn't read the question properly.  If an application
allocates a color not in the colormap and there are free cells, these
cells change.  But Emacs should not be using cells (i.e. pixels) that
it has freed.    I don't think it does, I'll check that.

>
>>> As someone whose colormap is full about 95% of the time, I can
>>> assure you that tose things happen ;-)
>>
>> What should happen is that when the colormap is full, a new one is
>> created and then the window manager switches colormap depending on
>> which application has the focus.
>
> I hate colormap switching.  I much prefer what happens with Emacs:
> when XAllocColor fails, Emacs looks for the nearest color in the map
> and uses it.  After all I generally don't care that much about the
> exact color.

If the exact color isn't important, and the nearest color is ok, that is
easier on the user.  But sometimes the exact color is important, and
then you have no choise but to do switching.  Anyway, in about a year
or two, we will all be running 16 or 24 bit color and this problem
goes away :-)

	Jan D.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Richard Stallman]

    "should" -> yes.  "Can" is trickier.  In order for an old cache entry to be
    "wrong", the X server will have to allocate a colormap entry once, then
    dealloc it, then allocate another color in that space.

Do most PCs nowadays have color maps, or do they store the actual
color values in the pixel?  In another context recently someone said
it was the latter.  If the latter, we could turn off the caching code
on the occasional displays that really have a color map.

Re: [patch] cache color info for remote X sessions [Was: Emacs 21/X11 generating unbelieveable network traffic]

[Richard Stallman]

    > What would be both simpler and more useful is a feature at run time to
    > turn the cache use on and off.  A Lisp variable forwarded with
    > DEFVAR_BOOL to a C int variable could control it.  The entry points
    > could avoid checking the cache if the C variable is 0.

    True.  A command-line option would also be in order, to save the delay at
    startup before the lisp variable is eval'd.  Anyone feel like adding these
    (cmd line opt & lisp var)?  

If the caching works reliably and if it does not cause problems
when the color map is full, there may be no need ever to turn it off.
Or just having a C variable that you can set with GDB could be enough
for debugging purposes.