[Gcl-devel] Re: Improvement to GCL's EXPT?

[Camm Maguire]

Greetings!

Matt Kaufmann <address@hidden> writes:

> Thanks; the code generated by disassemble for the following does use the shift
> operator, both in GCL 2.6.5 and GCL 2.6.6 as built at UT, which is great.
> 

Great!  I trust this mod does not conflict otherwise with acl2.

>   >(disassemble (defun foo (x) (declare ((integer 0 31) x)) (the fixnum (expt 
> 2 (the
>   fixnum x)))))
> 
>   Compiling gazonk0.lsp.
>   ; (DEFUN FOO ...) is being compiled.
>   ;; Warning: Type mismatch was found in (THE FIXNUM X).
>   ;; Warning: The type of the form (THE FIXNUM X) is not T.
>   End of Pass 1.  
>   End of Pass 2.  
> 
> The warning kind of surprised me, though.

Traditional GCL, including 2.6.x, has no support for ranged numeric
type declarations.  This is being fixed in 2.7.0.  Just drop the
declare and all should be quiet.

In 2.7.0, we're expanding the expt inliner as follows so far (not yet 
committed):

(expt x y)  ->

x<<y  -- x==2 & y positive integer in range
1/x<<y -- x==2 && y negative integer in range
(* x (..)) -- y positive integer less than something around 4 (strength 
reduction)
(ratio analog of above for negative y)
exp(y*log(x)) -- x positive real, y real
(expt (abs x) y) -- x negative, y even integer
(- (expt (abs x) y)) -- x negative, y odd integer

Of course, constant ranges get compiled to constants automatically
(now) by the compiler, so these are all the opts I can think of.  One
could try to factor out the phase of a general complex number, but I'm
unsure of the gains here.  In general, we have a lot of room for
complex improvements given the development of complex arithmetic in
external libs of late.

Paul, how does one instruct your random tester to zero in on a
particular function like expt?

Take care,

> 
> -- Matt
>    Cc: address@hidden, address@hidden
>    From: Camm Maguire <address@hidden>
>    Date: 05 Apr 2005 19:40:19 -0400
>    User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2
>    Content-Type: text/plain; charset=us-ascii
>    X-SpamAssassin-Status: No, hits=-2.6 required=5.0
>    X-UTCS-Spam-Status: No, hits=-282 required=180
> 
>    Greetings!
> 
>    You are of course correct -- wrote the previous too quickly.
> 
>    In 2.6.6, the only way at present that I can see is to define foo as
>    follows:
> 
>    (defun foo (x) (declare ((integer 0 31) x)) (the fixnum (expt 2 (the
>    fixnum x))))
> 
>    This will work out of the box in 2.6.6 due to the following optimizer:
> 
> 
>    (push '((fixnum fixnum) fixnum #.(flags)(LAMBDA (LOC1 LOC2)
>                                            (IF
>                                             (AND (CONSP LOC1)
>                                              (EQ (CAR LOC1) 'FIXNUM-LOC)
>                                              (CONSP (CADR LOC1))
>                                              (EQ (CAADR LOC1)
>                                               'FIXNUM-VALUE)
>                                              (EQUAL (CADDR (CADR LOC1))
>                                               2))
>                                             (WT "(1<<(" LOC2 "))")
>                                             (WT "fixnum_expt(" LOC1 #\,
>                                              LOC2 #\)))))
>       (get 'expt 'inline-always))
> 
> 
>    This crude use of fixnum is limiting and imprecise of course.  2.7.0
>    is the first GCL to introduce integer range type inferencing, so in
>    this version one can simply eval in the compiler package:
> 
>    (push '(((integer 2 2) (integer 0 #.(integer-length
>       most-positive-fixnum))) fixnum #.(flags rfa) "(1<<(#1))") (get
>       'expt 'inline-always))
> 
>    Depending on how nfix is declared, your existing code will likely not
>    have to be modified.
> 
>    Analogs of course can be added for the other special cases, including
>    making a ratio from a shifted fixnum in the case of a negative second
>    arg in range, etc.  I don't see any other special first args other
>    than -2 -1 0 1 2.  2.7.0 also has the ability to pass situations like
>    this off to a special inliner so that only one entry in the table is
>    needed. 
> 
>    Will try to finalize this and the boxed version enhancement.  If all
>    passes through Paul's random tester, can then commit.
> 
>    Take care,
> 
>    Matt Kaufmann <address@hidden> writes:
> 
>    > Howdy --
>    > 
>    > Interesting.... But this seems to break when the exponent is not an 
> integer.
>    > An example transcript is below, showing that (expt 2 3/2) works fine 
> until
>    > after we adopt your modification.
>    > 
>    > -- Matt
>    >   sundance:~> gcl
>    >   GCL (GNU Common Lisp)  2.6.5 CLtL1    Aug 18 2004 10:07:03
>    >   Source License: LGPL(gcl,gmp), GPL(unexec,bfd)
>    >   Binary License:  GPL due to GPL'ed components: (BFD UNEXEC)
>    >   Modifications of this banner must retain notice of a compatible license
>    >   Dedicated to the memory of W. Schelter
>    > 
>    >   Use (help) to get some basic information on how to use GCL.
>    > 
>    >   >(in-package 'compiler)
>    > 
>    >   #<"COMPILER" package>
>    > 
>    >   COMPILER>(defun foo (x)  (expt 2 x))
>    > 
>    >   FOO
>    > 
>    >   COMPILER>(foo 3/2)
>    > 
>    >   2.8284271247461898
>    > 
>    >   COMPILER>(compile 'foo)
>    > 
>    >   Compiling gazonk0.lsp.
>    >   End of Pass 1.  
>    >   End of Pass 2.  
>    >   OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
>    >   Finished compiling gazonk0.lsp.
>    >   Loading gazonk0.o
>    >   start address -T 0x848a8d0 Finished loading gazonk0.o
>    >   #<compiled-function FOO>
>    > 
>    >   COMPILER>(foo 3/2)
>    > 
>    >   2.8284271247461898
>    > 
>    >   COMPILER>(defun expt-2-to-ash (form env)
>    >    (declare (ignore env))
>    >    (if (eql (cadr form) 2) `(ash 1 ,(caddr form)) form))
>    > 
>    >   EXPT-2-TO-ASH
>    > 
>    >   COMPILER>(si::putprop 'expt (function expt-2-to-ash) 'compiler-macro)
>    > 
>    >   (LAMBDA-BLOCK EXPT-2-TO-ASH (FORM ENV)
>    >     (DECLARE (IGNORE ENV))
>    >     (IF (EQL (CADR FORM) 2) (LIST 'ASH 1 (CADDR FORM)) FORM))
>    > 
>    >   COMPILER>(defun foo (x)  (expt 2 x))
>    > 
>    >   FOO
>    > 
>    >   COMPILER>(foo 3/2)
>    > 
>    >   2.8284271247461898
>    > 
>    >   COMPILER>(compile 'foo)
>    > 
>    >   Compiling gazonk0.lsp.
>    >   End of Pass 1.  
>    >   End of Pass 2.  
>    >   OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
>    >   Finished compiling gazonk0.lsp.
>    >   Loading gazonk0.o
>    >   start address -T 0x83d3660 Finished loading gazonk0.o
>    >   #<compiled-function FOO>
>    > 
>    >   COMPILER>(foo 3/2)
>    > 
>    >   Error: 3/2 is not of type INTEGER.
>    >   Fast links are on: do (si::use-fast-links nil) for debugging
>    >   Error signalled by FOO.
>    >   Broken at FOO.  Type :H for Help.
>    >   COMPILER>>
>    > 
>    > 
>    > 
> 
>    -- 
>    Camm Maguire                                               address@hidden
>    ==========================================================================
>    "The earth is but one country, and mankind its citizens."  --  Baha'u'llah
> 
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah