[Python-checkins] CVS: python/dist/src/Objects longobject.c,1.84,1.85

[Tim Peters]

Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv27050/python/dist/src/objects

Modified Files:
	longobject.c 
Log Message:
long_format():  Easy speedup for output bases that aren't a power of 2 (in
particular, str(long) and repr(long) use base 10, and that gets a factor
of 4 speedup).  Another factor of 2 can be gotten by refactoring divrem1 to
support in-place division, but that started getting messy so I'm leaving
that out.


Index: longobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/longobject.c,v
retrieving revision 1.84
retrieving revision 1.85
diff -C2 -r1.84 -r1.85
*** longobject.c	2001/07/12 11:21:17	1.84
--- longobject.c	2001/07/13 02:59:26	1.85
***************
*** 812,831 ****
  	}
  	else {
  		Py_INCREF(a);
  		do {
  			digit rem;
! 			PyLongObject *temp = divrem1(a, (digit)base, &rem);
  			if (temp == NULL) {
- 				Py_DECREF(a);
  				Py_DECREF(str);
  				return NULL;
  			}
- 			if (rem < 10)
- 				rem += '0';
- 			else
- 				rem += 'A'-10;
- 			assert(p > PyString_AS_STRING(str));
- 			*--p = (char) rem;
- 			Py_DECREF(a);
  			a = temp;
  			SIGCHECK({
--- 812,838 ----
  	}
  	else {
+ 		/* Not 0, and base not a power of 2.  Divide repeatedly by
+ 		   base, but for speed use the highest power of base that
+ 		   fits in a digit. */
+ 		digit powbase = base;  /* powbase == base ** power */
+ 		int power = 1;
+ 		for (;;) {
+ 			unsigned long newpow = powbase * (unsigned long)base;
+ 			if (newpow >> SHIFT)  /* doesn't fit in a digit */
+ 				break;
+ 			powbase = (digit)newpow;
+ 			++power;
+ 		}
+ 		
  		Py_INCREF(a);
  		do {
+ 			int ntostore = power;
  			digit rem;
! 			PyLongObject *temp = divrem1(a, powbase, &rem);
! 			Py_DECREF(a);
  			if (temp == NULL) {
  				Py_DECREF(str);
  				return NULL;
  			}
  			a = temp;
  			SIGCHECK({
***************
*** 834,837 ****
--- 841,854 ----
  				return NULL;
  			})
+ 			while (--ntostore >= 0) {
+ 				digit nextrem = (digit)(rem / base);
+ 				char c = (char)(rem - nextrem * base);
+ 				assert(p > PyString_AS_STRING(str));
+ 				c += (c < 10) ? '0' : 'A'-10;
+ 				*--p = c;
+ 				rem = nextrem;
+ 				if (a->ob_size == 0 && rem == 0)
+ 					break;  /* skip leading zeroes */
+ 			}
  		} while (ABS(a->ob_size) != 0);
  		Py_DECREF(a);