math code optimisation

math code optimisation

[P.Stephenson]

I just happened to look at mathevall() and noticed it was doing a lot
of unncecessary memory moving, as well as keeping some stack space
around when it wasn't using it.  Actual, tidying this up seems to make
the code (OSF/1 3.0, using `size') 170 bytes larger, though there's
less in data/bss, and it looked like it made about 8k difference
(using `ps') at run time (which I don't understand since it should be
about 1.5k, even with 64-bit longs; perhaps it's getting rounded up
somewhere).

*** Src/math.c.stk	Tue May 30 14:29:00 1995
--- Src/math.c	Tue May 30 15:25:03 1995
***************
*** 146,152 ****
  /* list of lvalues (variables) */
  
  static int lvc;
! static char *lvals[LVCOUNT];
  
  
  /**/
--- 146,152 ----
  /* list of lvalues (variables) */
  
  static int lvc;
! static char **lvals;
  
  
  /**/
***************
*** 463,471 ****
  struct mathvalue {
      LV lval;
      long val;
! }
  
! stack[STACKSZ];
  
  static void push _((long val, LV lval));
  
--- 463,471 ----
  struct mathvalue {
      LV lval;
      long val;
! };
  
! static struct mathvalue *stack;
  
  static void push _((long val, LV lval));
  
***************
*** 782,790 ****
      char *xptr;
      long xyyval;
      LV xyylval;
!     char *xlvals[LVCOUNT];
      int xmtok, xsp;
!     struct mathvalue xstack[STACKSZ];
      long ret;
  
      xlastbase = xnoeval = xunary = xlvc = xyyval = xyylval = xsp = xmtok = 0;
--- 782,790 ----
      char *xptr;
      long xyyval;
      LV xyylval;
!     char **xlvals = 0;
      int xmtok, xsp;
!     struct mathvalue *xstack = 0;
      long ret;
  
      xlastbase = xnoeval = xunary = xlvc = xyyval = xyylval = xsp = xmtok = 0;
***************
*** 797,811 ****
  	xptr = ptr;
  	xyyval = yyval;
  	xyylval = yylval;
! 	memcpy(xlvals, lvals, LVCOUNT * sizeof(char *));
  
  	xmtok = mtok;
  	xsp = sp;
! 	memcpy(xstack, stack, STACKSZ * sizeof(struct mathvalue));
      }
      lastbase = -1;
!     for (t0 = 0; t0 != LVCOUNT; t0++)
! 	lvals[t0] = NULL;
      lvc = 0;
      ptr = s;
      sp = -1;
--- 797,811 ----
  	xptr = ptr;
  	xyyval = yyval;
  	xyylval = yylval;
! 	xlvals = lvals;
  
  	xmtok = mtok;
  	xsp = sp;
! 	xstack = stack;
      }
+     stack = (struct mathvalue *)zalloc(STACKSZ*sizeof(struct mathvalue));
      lastbase = -1;
!     lvals = (char **)zcalloc(LVCOUNT*sizeof(char *));
      lvc = 0;
      ptr = s;
      sp = -1;
***************
*** 819,824 ****
--- 819,826 ----
  
      ret = stack[0].val;
  
+     zfree(lvals, LVCOUNT*sizeof(char *));
+     zfree(stack, STACKSZ*sizeof(struct mathvalue));
      if (--mlevel) {
  	lastbase = xlastbase;
  	noeval = xnoeval;
***************
*** 827,837 ****
  	ptr = xptr;
  	yyval = xyyval;
  	yylval = xyylval;
! 	memcpy(lvals, xlvals, LVCOUNT * sizeof(char *));
  
- 	sp = xsp;
  	mtok = xmtok;
! 	memcpy(stack, xstack, STACKSZ * sizeof(struct mathvalue));
      }
      return ret;
  }
--- 829,839 ----
  	ptr = xptr;
  	yyval = xyyval;
  	yylval = xyylval;
! 	lvals = xlvals;
  
  	mtok = xmtok;
! 	sp = xsp;
! 	stack = xstack;
      }
      return ret;
  }

-- 
Peter Stephenson <P.Stephenson@swansea.ac.uk>  Tel: +44 1792 205678 extn. 4461
WWW:  http://python.swan.ac.uk/~pypeters/      Fax: +44 1792 295324
Department of Physics, University of Wales, Swansea,
Singleton Park, Swansea, SA2 8PP, U.K.

Re: math code optimisation

[Zoltan Hidvegi]

Peter Stephenson <P.Stephenson@swansea.ac.uk> wrote:
> I just happened to look at mathevall() and noticed it was doing a lot
> of unncecessary memory moving, as well as keeping some stack space
> around when it wasn't using it.  Actual, tidying this up seems to make
> the code (OSF/1 3.0, using `size') 170 bytes larger, though there's
> less in data/bss, and it looked like it made about 8k difference
> (using `ps') at run time (which I don't understand since it should be
> about 1.5k, even with 64-bit longs; perhaps it's getting rounded up
> somewhere).

I'm quite busy recently and I had no time to response to mails. I hope it is
still not too late.

I'm not really sure that this optimisation Peter made in the quoted letter and
which is now part of beta9 is much better that the former code. While the
original code used the stack and memcpy, the current version uses
malloc/free. I agree that it should be a little faster than memcpy, but each
malloc may increase memory fragmentation and this way it may consume more
memory than necessary.

Probably that's the problem in other parts of the code, like in

% zsh -f
ktud% foo=( a{,}{,}{,}{,}{,}{,}{,}{,}{,}{,} )
ktud% ps aux $$
USER       PID %CPU %MEM SIZE  RSS TTY STAT START   TIME COMMAND
hzoli     2237  3.6  3.6  460  556 pp0 S    17:03   0:00 zsh -f
ktud% echo ${foo%?}
 
ktud% ps aux $$    
USER       PID %CPU %MEM SIZE  RSS TTY STAT START   TIME COMMAND
hzoli     2237  4.7 21.6 3168 3268 pp0 S    17:03   0:01 zsh -f
ktud% 

as you see, ${foo%?} above increases the resident size with about 2.7M the
first time it is executed (the exact reason for that is still unknown). This
happens on Linux with or wothout ZSH_MEM.

Because of this, I do not really like adding new malloc's. I think the math
code can use halloc if necessary which is safer and also does not requires
explicit free but it's probably better to use the stack and memcpy.

Zoltan