From: Michael A. Koerber
Subject: Why is this function CONSing so much?
Date:
Message-ID: <3BBDC116.FCA621B3@ll.mit.edu>
This is a multi-part message in MIME format.
--------------64BC8259EA831F777F68B064
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Can someone help me understand what I've done wrong
in the below code that is causing (what seems to me) to
be too much CONSing. This function is the "long pole"
in a simulation being called 100's of times on data sets
of consisting of several matricies with 250,000 entries.
tnx in advance...
mike
--
-------------------------------------------------------------------
Dr Michael A. Koerber We child proofed our home 3 years ago
MIT/Lincoln Laboratory and they're still getting in!
···@ll.mit.edu
--------------64BC8259EA831F777F68B064
Content-Type: text/plain; charset=us-ascii;
name="tmp.lisp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="tmp.lisp"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Here is the offending function...
(defun array-indicies (test &rest arrays)
"
STYNTAX
======
(ARRAY-INDICIES TEST ARRAYS ...)
INPUT
-----
TEST A boolean valued function taking as many arguments as there are ARRAYS
provided to this command.
ARRAYS One or more arrays. If more than one array, they must all have the same
dimensions.
OUTPUT
------
INDEX-LIST A list of indicies for which the test was passed.
PURPOSE
=======
Find a complete list of indices for which the TEST is passed. The command
(ROW-MAJOR-AREF ARRAY (CAR INDEX-LIST)) would provide the first element
that passed the test."
(declare (type function test) (type list arrays))
;; Check input array dimensions
(unless (= 1 (length (remove-duplicates (mapcar #'array-dimensions arrays) :test #'equal)))
(error "All arrays must be the same rank"))
(let* ((narrays (length arrays))
(nsize (array-total-size (car arrays)))
(args (make-list (length arrays)))
(return-list '()))
(declare (type fixnum narrays nsize)
(type list args return-list))
;; loop over all array entries
(dotimes (nentry nsize)
(declare (type fixnum nentry))
;; and for each entry collect the value of each array
(dotimes (ndim narrays)
(setf (elt args ndim) (row-major-aref (elt arrays ndim) nentry)))
;; use these values as arguments to the test function and
;; if the TEST passes store the results
(if (apply test args)
(push nentry return-list)))
;; Reverse and return this list
(reverse return-list)))
(compile 'array-indicies)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Here is a simple test set up to filter random numbers > 0.5
(defparameter test #'(lambda(x) (> x 0.5d0)))
(defparameter ar (make-sequence '(vector double-float) 250000))
(dotimes (n (length ar)) (setf (aref ar n) (random 1.0d0)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Run the profiler and cry...
(gc)
;;---profile (profile:unprofile)
;;---profile (profile:reset-time)
;;---profile (profile:profile-all)
(load "/home/mak/src/clocc/src/tools/metering/metering")
(mon:unmonitor)
(mon:reset-all-monitoring)
(mon:monitor-all)
(defparameter ans (array-indicies test ar))
;;---profile (profile:report-time)
(mon:report)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; RESULTS OF THE TWO PROFILERS
;;;
;;---RESULTS Seconds | Consed | Calls | Sec/Call | Name:
;;---RESULTS ------------------------------------------------------
;;---RESULTS 2.740 | 23,944,872 | 1 | 2.74000 | ARRAY-INDICIES
;;---RESULTS ------------------------------------------------------
;;---RESULTS 2.740 | 23,944,872 | 1 | | Total
;;---RESULTS
;;---RESULTS Estimated total profiling overhead: 0.00 seconds
;;---RESULTS
;;---RESULTS
;;---RESULTS Cons
;;---RESULTS % % Per Total Total
;;---RESULTS Function Time Cons Calls Sec/Call Call Time Cons
;;---RESULTS -----------------------------------------------------------------------------------
;;---RESULTS ARRAY-INDICIES: 100.00 100.00 1 2.739998 23944872 2.740 23944872
;;---RESULTS -----------------------------------------------------------------------------------
;;---RESULTS TOTAL: 100.00 100.00 1 2.740 23944872
;;---RESULTS Estimated monitoring overhead: 0.00 seconds
;;---RESULTS Estimated total monitoring overhead: 0.00 seconds
--------------64BC8259EA831F777F68B064--
Michael A. Koerber wrote:
> Can someone help me understand what I've done wrong
> in the below code that is causing (what seems to me) to
> be too much CONSing. This function is the "long pole"
> in a simulation being called 100's of times on data sets
> of consisting of several matricies with 250,000 entries.
>
> tnx in advance...
> mike
>
The mapcar in the dimension check will cons as will pushing the results on
the results list. To set the elements of a list to doubles, in most
implementations, requires you to box the double, again consing. This last
is probably where the issue is. You would do better to encapsulate your
testing to a function that took an array as input because then, you could
declare the type of the array inside the test function and obviate the
boxing / unboxing in the test.
faa
From: Michael A. Koerber
Subject: Re: Why is this function CONSing so much?
Date:
Message-ID: <3BC2F93E.5B95D858@ll.mit.edu>
I rcv'd hints here as well as private e-mails...tnx. The answer is
that ARRAY-INDICIES is _not_ the problem. The problem is hidden
in the statement
(defparameter test #'(lambda(x) (> x 0.5d0)))
The simple expedient in this case (though not my application) was to
write
(defparameter test (compile nil #'(lambda(x) (> x 0.5d0))))
This will clear up about 20,000,000 of the CONS' and provide
about a 10x speed up.
tnx again
mike
From: Barry Margolin
Subject: Re: Why is this function CONSing so much?
Date:
Message-ID: <alEw7.6$vN6.321@burlma1-snr2>
In article <·················@ll.mit.edu>,
Michael A. Koerber <···@ll.mit.edu> wrote:
>I rcv'd hints here as well as private e-mails...tnx. The answer is
>that ARRAY-INDICIES is _not_ the problem. The problem is hidden
>in the statement
>
>(defparameter test #'(lambda(x) (> x 0.5d0)))
>
>The simple expedient in this case (though not my application) was to
>write
>
>(defparameter test (compile nil #'(lambda(x) (> x 0.5d0))))
>
>This will clear up about 20,000,000 of the CONS' and provide
>about a 10x speed up.
Why are you using defparameter for a function in the first place? Why not:
(defun test (x)
(> x 0.5d0))
Then just reference #'test instead of test.
BTW, there are only two I's in "indices".
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Michael A. Koerber
Subject: Re: Why is this function CONSing so much?
Date:
Message-ID: <3BC5A3F1.4CA78DC8@ll.mit.edu>
Barry Margolin wrote:
>
> Why are you using defparameter for a function in the first place? Why not:
>
> (defun test (x)
> (> x 0.5d0))
It was precisely the DEFUN form that lead me to the problem. The reason
for
the DEFPARAMETER form was to emulated more closely the actually
application in which ARRAY-INDICES appeared to be the problem. In lieu
of using LAMBDA to build the needed filter functions (in a non-null
lexical environment) on the fly, I now use a (DEFUN ... #'(LAMBDA...))
form that avoids this problem. I.e.,
(DEFPARAMETER TST #'(LAMBDA (X) (> X VARIABLE-IN-LEXICAL-ENVIRONMENT))
is replaced with
(DEFUN MK-FILT (VAR) #'(LAMBDA (X) (> X VAR))
followed later by
(DEFPARAMETER TST (MK-FILT VARIALBE-IN-LEXICAL-ENVIRONMENT))
> BTW, there are only two I's in "indices".
Thanks...one of the characteristic features of much of my code is the
poor spelling...it wasn't so noticable in FORTRAN :-)
--
-------------------------------------------------------------------
Dr Michael A. Koerber We child proofed our home 3 years ago
MIT/Lincoln Laboratory and they're still getting in!
···@ll.mit.edu