Subject: Re: Implementation limits when accessing circular lists
From: rpw3@rpw3.org (Rob Warnock)
Date: Mon, 30 Jun 2003 03:59:07 -0500
Newsgroups: comp.lang.lisp
Message-ID: <S92cnZzM-rVGZmKjXTWc-w@speakeasy.net>
Adam Warner  <usenet@consulting.net.nz> wrote:
+---------------
| Paul F. Dietz:
| > I'm not going to add a test for it to ansi-tests, though, since it
| > would take too long to run.
| 
| Thanks for the reply Paul. At the moment it's an instantaneous failure on
| CLISP, CMUCL and SBCL. ...
...
| And even if it wasn't an instantaneous failure we're talking about
| approximate a second when running interpreted on modest 32-bit hardware.
| $ cat /proc/cpuinfo | grep 'MHz'
| cpu MHz         : 530.046
| 
| CLISP:
| (time (nth most-positive-fixnum '#1=(t . #1#)))
| 
| Real time: 0.394791 sec.
| Run time: 0.39 sec.
| Space: 0 Bytes
+---------------

On CMUCL-18e, using (1- most-positive-fixnum), it's *far* faster than that!!

	cmu> (time (nth (1- most-positive-fixnum) '#1=(t . #1#)))
	; Compiling LAMBDA NIL: 
	; Compiling Top-Level Form: 

	; Evaluation took:
	;   0.0 seconds of real time
	;   5.0e-6 seconds of user run time
	;   7.0e-6 seconds of system run time
	;   3,212 CPU cycles
	;   0 page faults and
	;   64 bytes consed.
	; 
	T
	cmu> 

Now, granted, I have a 1.4 GHz Athlon ("1600+"), but it's not *that*
much faster than Adam's machine. Hmmm... Let's try it on a lowly 133 MHz
Pentium II:

	cmu> (time (nth (1- most-positive-fixnum) '#1=(t . #1#)))
	; Compiling LAMBDA NIL: 
	; Compiling Top-Level Form: 

	; Evaluation took:
	;   0.0 seconds of real time
	;   6.6e-5 seconds of user run time
	;   10.0e-7 seconds of system run time
	;   922 CPU cycles
	;   0 page faults and
	;   64 bytes consed.
	; 
	T
	cmu> 

Now that's *really* weird! Is CMUCL's *compiler* somehow detecting that
the circularity implies a constant result?

Answer: No! Looks like some artifact with the TIME macro instead.
When you run it this way you get *much* more reasonable results:

	cmu> (defun foo (x)
	       (declare (fixnum x) (optimize (speed 3)))
	       (nth x '#1=(t . #1#)))

	FOO
	cmu> (compile 'foo)
	; Compiling LAMBDA (X): 
	; Compiling Top-Level Form: 

	FOO
	NIL
	NIL
	cmu> (time (foo (1- most-positive-fixnum)))
	; Compiling LAMBDA NIL: 
	; Compiling Top-Level Form: 

	; Evaluation took:
	;   1.59 seconds of real time
	;   1.572572 seconds of user run time
	;   0.013583 seconds of system run time
	;   2,234,478,100 CPU cycles
	;   0 page faults and
	;   64 bytes consed.
	; 
	T
	cmu> 

on the 1.4 GHz Athlon, and:

	cmu> (time (foo (1- most-positive-fixnum)))
	; Compiling LAMBDA NIL: 
	; Compiling Top-Level Form: 

	; Evaluation took:
	;   25.19 seconds of real time
	;   24.542253 seconds of user run time
	;   0.047189 seconds of system run time
	;   3,317,991,740 CPU cycles
	;   0 page faults and
	;   64 bytes consed.
	; 
	T
	cmu> 

on the 133 MHz Pentium.


-Rob

-----
Rob Warnock, PP-ASEL-IA		<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607