gcl-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Gcl-devel] Re: possible dotimes enhancement


From: Camm Maguire
Subject: Re: [Gcl-devel] Re: possible dotimes enhancement
Date: 01 Aug 2003 15:15:20 -0400
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2

Greetings, Paul, and thanks as always for this!

Your negativity check suggestion works, but leaves at least one
generic integer comparison at the head (outside) of each loop
(i.e. inside the second and outside the third loop in a matrix
multiply).  This is good, but I think we can do better.  

There are three instances which ideally could be caught:

1) (some scope (declare (fixnum n)) (dotimes (i n) ...)) ->
        declaration of i, n and gensym'ed temp to fixnum in loop body 

2) (dotimes (i n) (declare (fixnum n)) ...) ->
        declaration of i, n and gensym'ed temp to fixnum in loop body 

3) (dotimes (i n) (declare (fixnum i)) ...) ->
        declaration of i, n and gensym'ed temp to fixnum in loop body 
        after one eval of n to check for positivity or equivalent

In general, there are two regions in which we could address this, in
the compiler, or at macro expansion time.  Likewise there are three
levels we could address: dotimes, do*, and let*.

2) is the easiest, and can be simply addressed at macro expansion.
   The idea is to declare the gensym'ed temp in the same manner as the
   loop count-form may be declared, if in fact it remains constant in
   the loop body.  Modifying dotimes is straightforward, as it is
   known that ,temp is bound only once to ,form.  The let* level would
   be tricky (i.e. parsing the body looking for unchanged variables).

   I think the intermediate do* level could be handled as follows.
   This presumes that the control variables are not set in the loop
   body, which might have to be scanned for this possibility.

=============================================================================
(defmacro do* (control (test . result) &rest body
               &aux (decl nil) (const nil) (label (gensym)) (vl nil) (step nil))
  
  (dolist (c control)
    (declare (object c))
    (if(symbolp  c) (setq c (list c)))
        (push (list (car c) (cadr c)) vl)
    (if (endp (cddr c))
;;
;; new code
;; push unchanged control variables onto a list
        (progn
          (format t "pushing ~S onto ~S~%" c const)
          (push (car c) const)
          (push (cadr c) const))
;; end new code
      (progn
        (push (car c) step)
        (push (caddr c) step))))
  (do ()
      ((or (endp body)
           (not (consp (car body)))
           (not (eq (caar body) 'declare))))
      (push (car body) decl)
;;
;; new code
;; add any unchanging control variables bound to variables in
;; this declaration to the declaration list
;;
      (dolist (c (cdadar decl))
        (format t "c is ~S decl is ~S const is ~S~%" c decl const)
        (cond ((setq tt (member c const))
               (nconc (last (cdadar decl)) (list (cadr tt)))))
        (format t "decl is now~%" (cdadar decl))
                      )
;;
;; end new code
;;
      (pop body))
  `(block nil
          (let* ,(reverse vl)
                ,@decl
                (tagbody
                 ,label (if ,test (return (progn ,@result)))
                        (tagbody ,@body)
                        (setq ,@(reverse step))
                        (go ,label))))
  )
=============================================================================
Is this too add hoc?  I think so -- the proper level would appear to
    be at let* after scanning the body for setq et.al.  I don't
    suppose there is a convenient way to identify the possible
    operations setq, incf, etc. which would be pertinent.

In any case, 1) should work, but I cannot see any way to do this
outside of reference to compiler functions -- in short I don't know
how to access declarations in the surrounding scope outside of the
compiler.  (Clueless me thought that &env might work, or some such).

Below is a fragment to show how this might be done at the dotimes
level:

=============================================================================
(defmacro dotimes ((var form &optional (val nil)) &rest body
                                                  &aux (temp (gensym)))
  (format t "c1vref is ~S~%" (if (symbolp form) (compiler::var-type (caaddr 
(compiler::c1var form))) `(compiler::c1var ,form)))
  `(do* ((,temp ,form) (,var 0 (1+ ,var)))
        ((>= ,var ,temp) ,val)
        
        ,@body))
=============================================================================
But this is very ugly and obviously not right.

3) Can be addressed as we discussed before, but I want to avoid the
   generic integer negativity evaluation if 1) or 2) kick in.

Anyway, thoughts most welcome!

Take care,




"Paul F. Dietz" <address@hidden> writes:

> Camm Maguire wrote:
> > Greetings!  I was just looking at how gcl compiles a matrix
> > multiplication today.  In short, once one makes sure all the
> > declarations are kicking in, it appears as if it can get as fast as
> > native C.
> > There does appear to be a curent inefficiency in our dotimes
> > definition, as compared with do and do*.  The existing definition is:
> > (defmacro dotimes ((var form &optional (val nil)) &rest body
> >                                                   &aux (temp (gensym)))
> >   `(do* ((,temp ,form) (,var 0 (1+ ,var)))
> >         ((>= ,var ,temp) ,val)
> >         ,@body))
> > If one declares the type of var, optimizations still do not kick in
> > because the gensym'd temp has no declared type. I'm proposing the
> > following:
> > (defmacro dotimes ((var form &optional (val nil)) &rest body
> >                                                   &aux (temp (gensym)) 
> > temp1 temp2 temp3 temp4)
> >   `(do* ((,temp ,form) (,var 0 (1+ ,var)))
> >         ((>= ,var ,temp) ,val)
> >     ,(dolist (temp1 body temp4)          (when (eq (car temp1)
> > 'declare)          (let ((temp2 (cadr temp1)))
> >              (dolist (temp3 (cdr temp2))
> >                (when (eq temp3 var)
> >                  (setq temp4 `(declare (,(car temp2) ,temp))))))))
> >         ,@body))
> > This basically will extend the user's possible declaration of var to
> > that of the integer evaluation of form stored in temp, as would appear
> > to make sense, as var has to count up to this value in any case.
> > With this enhancement in my preliminary testing, all loops of the
> > form
> > '(dotimes (i form) (declare (fixnum i)) ...) have the counting variable
> > incrementation and comparison fully optimized, i.e. avoiding the
> > generic number_compare, etc.
> > So what do the lisp experts think?  Am I getting into trouble?
> 
> 
> This goes wrong when FORM is negative:
> 
>     (dotimes (i (1- most-negative-fixnum) i)
>       (declare (type fixnum i))
>       (error "shouldn't happen"))
>     ==> 0
> 
> You could test the count form for negativity first, then bind it to
> another variable of the same type as the index variable.
> 
> 
> 
> > Separately, at some point we have to figure out why the optimizer
> > cannot currently optimize
> > (declare (fixnum i)) (aref a (+ i 1))
> > but only
> > (let ((m 0)) (declare (fixnum m i)) (setq m (+ i 1)) (aref a m))
> 
> AREF requires each of its indices be a fixnum, so it's legal to
> treat
> 
>    (aref a i j ... k)
> 
> as
> 
>    (aref (the fixnum i) (the fixnum j) ... (the fixnum k))
> 
>       Paul
> 
> 
> 
> 
> _______________________________________________
> Gcl-devel mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/gcl-devel
> 
> 
> 

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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]