Re: [Sbcl-devel] performance issues vs. CMU CL

[Christophe R. <cs...@ca...>]

On Tue, Apr 23, 2002 at 01:23:29PM +0100, Christophe Rhodes wrote:
> (defun foo (x)
>   (declare (type #+cmu kernel:index #+sbcl sb-int:index x))
>   (declare (optimize (speed 3) (safety 1)))
>     (let ((y (truncate (the #+cmu kernel:index #+sbcl sb-int:index
>                          (+ x 32 -1))
>                        32)))
>       (declare (optimize (speed 3) (safety 0))
>                (type #+cmu kernel:index #+sbcl sb-int:index y))
>       y))
> 
> Compiling the above file gives a note about CHECK-FIXNUM in sbcl, but
> not in cmucl.

I've thought some more about this, and I believe I understand what's
going on.  

[ Most of this message is also relevant to cmucl, so I hope
  that those cmucl hackers on this list will forward relevant
  thoughts to the other cmucl developers... ]

Firstly, why the difference between cmucl's and sbcl's behaviour? This
derives from a discussion we had on sbcl-devel about LET and IR1
conversion in the dark days of January 2002 (see
<http://www.geocrawler.com/mail/thread.php3?subject=%5BSbcl-devel%5D+strange+LET+translator&list=1663>
and
<http://www.geocrawler.com/archives/3/1663/2002/1/0/7664170/>
for the details). The problem that we attempted to fix was along the
lines of:

  (let ((x (foo y)))
    (declare (inline foo))
    (foo x))

and having the initialization of x being made by a bogusly-inlined foo.
So SBCL currently doesn't run the bindings in the environment augmented
by the inner declarations, whereas CMUCL does. This explains the
difference in the above code derived from the bit-vector transforms in
compiler/generic/vm-tran.lisp; for cmucl, the THE in the initialization
form is a TRULY-THE with no type checking, as it is in an environment
with (SPEED 3) (SAFETY 0), but for SBCL we get weak type checking as it
is in (SPEED 3) (SAFETY 1).

Having now reread the section of the CLHS cited in the previous
discussion (section 3.3.4, "Declaration scope"), I believe that both
behaviours (CMUCL and SBCL) are in error :-/

Section 3.3.4 draws a distinction between "bound declarations" and "free
declarations"; I'll give an example of what I think is meant:

(let ((y 10))
  (declare (optimize (safety 3) (speed 0)))
  (let ((x (foo y)))
    (declare (type fixnum x))
    (declare (type fixnum y))
    (declare (inline foo))
    (declare (optimize (speed 3) (safety 0)))
    ...))

Here, I believe that the declaration of x's type is a "bound
declaration", as it is a declaration of a variable bound in the
corresponding let form. All of the others are "free declarations". This
means, I believe, that (foo y) should be not inline, y in that execution
is not necessarily a fixnum, and that it should return a fixnum, but
this should be checked as it is executing and the binding is in an
environment with (SAFETY 3) (SPEED 0). Within the "...", calls to FOO
should be inline, X and Y should be fixnums and the code should be
compiled for speed. So, in other words, I think we need to do a little
bit more work in the IR1-translator for LET to be fully ANSI compliant.

But, this isn't all I've discovered, as it turns out that there's a bug
in the bit-vector optimizations in both SBCL and CMUCL.

Consider the heart of the transforms:

  (do ((index sb!vm:vector-data-offset (1+ index))
       (end (+ sb!vm:vector-data-offset
               (truncate (the index (+ (length bit-array-1)
                                       sb!vm:n-word-bits
                                       -1))
                         sb!vm:n-word-bits))))
      ((= index	end) result-bit-array)
    (declare (optimize (speed 3) (safety 0))
             (type index index end))
    (setf (%raw-bits result-bit-array index)
          (,',wordfun (%raw-bits bit-array-1 index)
                      (%raw-bits bit-array-2 index))))))))

If the length of bit-array-1 is close to ARRAY-DIMENSION-LIMIT, then the
THE assertion is in error, as adding 31 to it will make it go over the
index bounds, resulting in a type assertion error for SBCL and an
infinite loop for CMUCL (as for CMUCL END is negative, so the
termination test is never true) -- see the attached file for a test
case.

I believe that a fix is to have a loop epilogue; so, changing the
initialization of END to
(+ sb!vm:vector-data-offset
If the length of bit-array-1 is close to ARRAY-DIMENSION-LIMIT, then the
THE assertion is in error, as adding 31 to it will make it go over the
index bounds, resulting in a type assertion error for SBCL and an
infinite loop for CMUCL (as for CMUCL END is negative, so the
termination test is never true) -- see the attached file for a test
case.

I believe that a fix is to have a loop epilogue; so, changing the
initialization of END to 

  (end-1 (+ sb!vm:vector-data-offset
            (truncate (the index (+ (length bit-array-1) -1))
                      sb!vm:n-word-bits)))

[ with TRULY-THE substituted for THE if my reasoning about LET
  conversion is accepted and implemented ]

and having (untested)

  ((= index end-1)
   (setf (%raw-bits result-bit-array index)
         (,',wordfun (%raw-bits bit-array-1 index)
		     (%raw-bits bit-array-2 index)))
   result-bit-array)

as the termination clause.

And who says performance benchmarks aren't useful? :-)

Cheers,

Christophe
-- 
Jesus College, Cambridge, CB5 8BL                           +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/                  (defun pling-dollar 
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)