I've done a bit more hacking on my Lisp code for generating the
Mandelbrot Set. I've not been working on it constantly, that's why
I'm not further along than might be expected from the last time I
posted. I'm not using rationals anymore. I'm going with ints as a
way to do fixed radix math. I've not implemented certain features
yet like adjusting the number of bits used based on zoom factor. I'm
also doing a fairly brute-force approach to calculating the pixels.
I am considering using an array to hold the escape value data so that
I can do edge detection on the set so that I don't have to calculate
pixels in the interior. Anyway, here is the Lisp that I have:
;;;; fractal.lisp -- an exploration of the Mandelbrot Set using
;;;; arbitrary sized integer math.
;;;;
;;;; By David Steuber with feedback from comp.lang.lisp
;;;;
;;;; This software is put in the public domain by David Steuber
;;;;
;;;; Just for the record, I hate global variables because they
;;;; break modularity by being non-local.
;;; global variables related to the fractional bits in our fixed radix numbers
(defvar *fractional-bits* 16
"Number of fractional bits in our number")
(defvar *escape-value* (ash 4 *fractional-bits*)
"Numbers larger than this have escaped and are not part of the Mandelbrot Set")
(defvar *my-two* (ash 2 *fractional-bits*))
(defun set-fractional-bits (fb)
"A nice way to set both *fractional-bits* and *escape-value* at the same time"
(setf *escape-value* (ash 4 fb)
*my-two* (ash 2 fb)
*fractional-bits* fb))
(defun shifted-multiply (&rest args)
"Multiplies the args as integers left-shifted by *fractional-bits* and right-shifts accordingly"
(let ((n (apply #'* args)))
(ash n (- (* (max 0 (- (list-length args) 1)) *fractional-bits*)))))
(defun mandelbrot-escape-fn (c-real c-imag &key (max-iterations 10000))
"Return iterations for c-real + c-imag i as integers left shifted by *fractional-bits*"
(loop for iterations below max-iterations
for z-imag = 0 then (+ (shifted-multiply z-real z-imag *my-two*) c-imag)
for z-real = 0 then (+ (- z-real-squared z-imag-squared) c-real)
for z-real-squared = 0 then (shifted-multiply z-real z-real)
for z-imag-squared = 0 then (shifted-multiply z-imag z-imag)
unless (< (+ z-real-squared z-imag-squared) *escape-value*) return iterations
finally (return iterations)))
(defun mandelbrot-escape-fn-pc (c-real c-imag &key (max-iterations 10000))
"Return iterations for c-real + c-imag i as integers left shifted by *fractional-bits* doing period checking"
(loop for iterations below max-iterations
for period from 1
for z-imag = 0 then (+ (shifted-multiply z-real z-imag *my-two*) c-imag)
for z-real = 0 then (+ (- z-real-squared z-imag-squared) c-real)
for z-real-squared = 0 then (shifted-multiply z-real z-real)
for z-imag-squared = 0 then (shifted-multiply z-imag z-imag)
with a-imag = 0
with a-real = 0
with check = 3
unless (< (+ z-real-squared z-imag-squared) *escape-value*) return iterations
when (and (= a-imag z-imag) (= a-real z-real) (> iterations 1)) return max-iterations
when (> period check) do (setf period 1 check (* 2 check) a-imag z-imag a-real z-real)
finally (return iterations)))
(defun numbers-to-fixed-radix (&rest nums)
"Return list of numbers converted to fixed-radix integers with *fractional-bits*"
(mapcar #'(lambda (n)
(round (* n (ash 1 *fractional-bits*))))
nums))
(defun fixed-radix-to-numbers (&rest nums)
"Almost the inverse of numbers-to-fixed-radix"
(mapcar #'(lambda (n)
(/ n (ash 1 *fractional-bits*)))
nums))
(defun mandelbrot-set (&key (x 0) (y 0) (zoom 1) (aspect 1)
(bitmap-width 100) (bitmap-height 100)
(data-file-name "mandelbrot-data.txt")
(max-iterations 1000))
"Calculate bitmap data for the Mandelbrot Set"
(let ((real-array (make-array bitmap-width)) ; to contain the real values left to right
(imag-array (make-array bitmap-height)) ; to contain the imag values top to bottom
(escape-fn #'mandelbrot-escape-fn) ; escape function to use
(data-file (make-pathname :name data-file-name))
(iterations 0) ; just another local variable
(total-iterations 0)) ; useful to know?
;; initialize real-array
(loop for i below bitmap-width
with size = (/ (* 4 aspect) zoom)
with pixelsize = (/ size bitmap-width)
with start = (- x (* (/ bitmap-width 2) pixelsize))
do (setf (svref real-array i) (car (numbers-to-fixed-radix (+ start (* i pixelsize))))))
;; initialize imag-array
(loop for i below bitmap-height
with size = (/ 4 zoom)
with pixelsize = (/ size bitmap-height)
with start = (- y (* (/ bitmap-height 2) pixelsize))
do (setf (svref imag-array i) (car (numbers-to-fixed-radix (+ start (* i pixelsize)))))
finally (nreverse imag-array)) ; this is so the first element is on the top row
;; we will start by doing this the brute force way and calculate every damn pixel
(with-open-file (stream data-file :direction :output
:if-exists :supersede)
(format stream "/* FRACTAL MANDELBROT */~%/* left top right bottom */~%") ; old format for now
(format stream "~A ~A ~A ~A~%"
(svref real-array 0) (svref imag-array 0)
(svref real-array (1- bitmap-width)) (svref imag-array (1- bitmap-height)))
(format stream "/* center_x center_y aspect zoom */~%")
(format stream "~A ~A ~A ~A~%" x y aspect zoom)
(format stream "/* width height maxitt */~%~A ~A ~A~%/* data */~%" bitmap-width bitmap-height max-iterations)
(dotimes (j bitmap-height)
(dotimes (i bitmap-width)
(setf iterations (funcall escape-fn (svref real-array i) (svref imag-array j) :max-iterations max-iterations))
(if (= iterations max-iterations)
(setf escape-fn #'mandelbrot-escape-fn-pc)
(setf escape-fn #'mandelbrot-escape-fn))
(format stream "~A " iterations)
(incf total-iterations iterations))
(format stream "~%")))
total-iterations))
Here is a test run:
CL-USER> (time (mandelbrot-set :x -3/4 :zoom 2 :bitmap-width 640 :bitmap-height 640))
(MANDELBROT-SET :X -3/4 :ZOOM 2 :BITMAP-WIDTH 640 :BITMAP-HEIGHT 640) took 126,626 milliseconds (126.626 seconds) to run.
Of that, 87,830 milliseconds (87.830 seconds) were spent in user mode
32,520 milliseconds (32.520 seconds) were spent in system mode
6,276 milliseconds (6.276 seconds) were spent executing other OS processes.
24,051 milliseconds (24.051 seconds) was spent in GC.
2,252,959,120 bytes of memory allocated.
145962887
By running this Perl script on the data written out
http://www.david-steuber.com/~david/files/fractal2image.txt
I generate an XPM file that I converted to this GIF file with Graphic
Converter:
http://www.david-steuber.com/~david/files/mandelbrot3.gif
This was all done on a PowerBook G4 12" with the 866Mhz G4 and 640MB
RAM.
--
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.
--- Ken Anderson
http://openmap.bbn.com/~kanderso/performance/java/index.html
David Steuber wrote:
> ;;;; Just for the record, I hate global variables because they
> ;;;; break modularity by being non-local.
>
> ;;; global variables related to the fractional bits in our fixed radix numbers
> (defvar *fractional-bits* 16
> "Number of fractional bits in our number")
> (defvar *escape-value* (ash 4 *fractional-bits*)
> "Numbers larger than this have escaped and are not part of the Mandelbrot Set")
> (defvar *my-two* (ash 2 *fractional-bits*))
>
> (defun set-fractional-bits (fb)
> "A nice way to set both *fractional-bits* and *escape-value* at the same time"
> (setf *escape-value* (ash 4 fb)
> *my-two* (ash 2 fb)
> *fractional-bits* fb))
>
I'll let someone with more guts tackle your program in detail, but
here's one suggestion. To avoid 'global' variables, you can create a
closure with local variables and only those functions which need access
to them. For instance:
(let* ((fractional-bits 16)
(escape-value (ash 4 fractional-bits))
(my-two (ash 2 fractional-bits)))
(defun initialize (fb)
(setf escape-value (ash 4 fb) my-two (ash 2 fb) fractional-bits fb))
...)
<Rest of program out here--can't access FRACTIONAL-BITS, etc...>
This gives you the convenience of not having to pass the 'globals' as
args to each function, yet still provides some encapsulation.
You can't change these variables directly from the top-level
interactively, but you do have a setter function--INITIALIZE (or
SET-FRACTIONAL-BITS, whatever you call it).
David Sletten
In article <··············@david-steuber.com>,
David Steuber <·············@verizon.net> wrote:
> ;;;; Just for the record, I hate global variables because they
> ;;;; break modularity by being non-local.
>
> ;;; global variables related to the fractional bits in our fixed radix numbers
> (defvar *fractional-bits* 16
> "Number of fractional bits in our number")
> (defvar *escape-value* (ash 4 *fractional-bits*)
> "Numbers larger than this have escaped and are not part of the
> Mandelbrot Set")
> (defvar *my-two* (ash 2 *fractional-bits*))
As dynamic variables go this doesn't seem too bad a usage in my
unlearned opinion. You can say:
(let* ((*fractional-bits* 64)
(*escape-value* (ash 4 *fractional-bits*))
(*my-two* (ash 2 *fractional-bits*)))
(mandelbrot-set ...))
to rebind them only for the dynamic scope of the let*. Since most
implementations treat dynamic scope as thread local, you can even have
multiple threads going at it with different parameters at the same time
with the above. I believe this should help your "breaking modularity"
concerns.
It's been a great surprise to me just how /usable/ dynamic variables
(CL's "globals") are, coming from languages where globals are greatly
feared.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Brian Downing <·············@lavos.net> writes:
> It's been a great surprise to me just how /usable/ dynamic variables
> (CL's "globals") are, coming from languages where globals are greatly
> feared.
yes, this is actually one of the most useful features of CL.
It has saved me unbelievable amounts of work.
--
(espen)
Brian Downing <·············@lavos.net> writes:
> It's been a great surprise to me just how /usable/ dynamic variables
> (CL's "globals") are, coming from languages where globals are greatly
> feared.
I am used to fearing the globals. I will probably continue to not
like them. I am using a few in this code because I think this is a
case of the lesser evil. Perhaps I overstated my disdain for globals
in the comment.
--
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.
--- Ken Anderson
http://openmap.bbn.com/~kanderso/performance/java/index.html
David Steuber <·············@verizon.net> writes:
> Brian Downing <·············@lavos.net> writes:
>
>> It's been a great surprise to me just how /usable/ dynamic variables
>> (CL's "globals") are, coming from languages where globals are greatly
>> feared.
>
> I am used to fearing the globals. I will probably continue to not
> like them. I am using a few in this code because I think this is a
> case of the lesser evil. Perhaps I overstated my disdain for globals
> in the comment.
Keep in mind that CL's special variables are not necessarily
"Global", i.e. they don't even have to have a global binding.
In fact, I do this so often I use a macro DEFVAR-UNBOUND to
declare them (and place the docstring).
In a multithreaded lisp, they'll naturally be be thread specific.
When rebound near the top of a call stack, each set of calls will
get their own value to play with. They're so much nicer than, e.g. C
globals they hardly deserve the same name.
David Steuber wrote:
> (defun shifted-multiply (&rest args)
I am no expert, but I think this forces a consing of a list. But the
code I see always calls s-m with two values or two values and *my-two*
(aside: would making some of these defvars into defconstants help?). So
perhaps some benefit can be had by creating two functions s-m and s-mx2,
where the latter expands to (s-m *my-two* (s-m x y)).
I think there was another function in there also using &rest args, but I
did not check that one out more closely. As a rule, there is a cost to
&rest, &key, and (I think) &optional.
Nice picture, btw.
kt
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Kenny Tilton <·······@nyc.rr.com> writes:
> David Steuber wrote:
> > (defun shifted-multiply (&rest args)
>
> I am no expert, but I think this forces a consing of a list.
Yes, but it's not necessary, if the argument can be declared
dynamic-extent.
> But the
> code I see always calls s-m with two values or two values and *my-two*
> (aside: would making some of these defvars into defconstants
> help?). So perhaps some benefit can be had by creating two functions
> s-m and s-mx2, where the latter expands to (s-m *my-two* (s-m x y)).
This is true, for cost reasons not necessarily related to consing
> I think there was another function in there also using &rest args, but
> I did not check that one out more closely. As a rule, there is a cost
> to &rest, &key, and (I think) &optional.
I would rate the cost of each of these as
&key: highest usually
&rest: medium to low if dynamic-extent, otherwise highest
&optional: usually extremely low - perhaps only one comparison
even when multiple optionals present.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Kenny Tilton <·······@nyc.rr.com> writes:
> David Steuber wrote:
> > (defun shifted-multiply (&rest args)
>
> I am no expert, but I think this forces a consing of a list. But the
> code I see always calls s-m with two values or two values and *my-two*
> (aside: would making some of these defvars into defconstants
> help?). So perhaps some benefit can be had by creating two functions
> s-m and s-mx2, where the latter expands to (s-m *my-two* (s-m x y)).
Defconstants won't do because I will want to be able to change them
later. Deeper zooms will require more bits.
The shifted-multiply should probably be revisited though. I tried to
make it generic like *. As I am not using it for other than 2 and 3
arg calls, that was probably not necessary. However, I didn't
realize there was an expense of any significance incurred. I will do
some experiments to see. I certainly did cons a lot to make that
image.
> I think there was another function in there also using &rest args, but
> I did not check that one out more closely. As a rule, there is a cost
> to &rest, &key, and (I think) &optional.
Converting to and from fixed radix notation is something I tried to
generalize. I think that was a mistake. I will just make them unary
functions. If nothing else, that will get rid of calling car on a
list of one element.
> Nice picture, btw.
Thanks. Hopefully that is only a beginning.
I am not certain that I can write code fast enough in Lisp to crunch
as many numbers as I have to. On the other hand, I am using a
reasonable number of Lisp functions to do this program. As it grows
and gets factored, I should be learning something.
I think I'm getting the hang of all those parens.
--
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.
--- Ken Anderson
http://openmap.bbn.com/~kanderso/performance/java/index.html
In article <··············@david-steuber.com>,
David Steuber <·············@verizon.net> wrote:
>The shifted-multiply should probably be revisited though. I tried to
>make it generic like *. As I am not using it for other than 2 and 3
>arg calls, that was probably not necessary. However, I didn't
>realize there was an expense of any significance incurred. I will do
>some experiments to see. I certainly did cons a lot to make that
>image.
You can write this simply as (* 2 (shifted-multiply x y)) and make
shifted-multiply purely binary.
>
>> I think there was another function in there also using &rest args, but
>> I did not check that one out more closely. As a rule, there is a cost
>> to &rest, &key, and (I think) &optional.
>
>Converting to and from fixed radix notation is something I tried to
>generalize. I think that was a mistake. I will just make them unary
>functions. If nothing else, that will get rid of calling car on a
>list of one element.
Yes, just make it unary, and use mapcar if you need to apply it to a list.
Brad
···@cs.purdue.edu (Bradley J Lucier) writes:
> In article <··············@david-steuber.com>,
> David Steuber <·············@verizon.net> wrote:
> >The shifted-multiply should probably be revisited though. I tried to
> >make it generic like *. As I am not using it for other than 2 and 3
> >arg calls, that was probably not necessary. However, I didn't
> >realize there was an expense of any significance incurred. I will do
> >some experiments to see. I certainly did cons a lot to make that
> >image.
>
> You can write this simply as (* 2 (shifted-multiply x y)) and make
> shifted-multiply purely binary.
More efficient, since multiplying by 2 is just shifting, would be
to have a separate function for calculating 2xy. Or, I suppose,
a single function that calculates (* (expt 2 r) x y) shifted,
where r is an optional arg defaulting to 0; but that imposes
some overhead, which might be enough that you'd care about it.
--
Gareth McCaughan
.sig under construc
Changing shifted-multiply and also adding a
shifted-multiply-and-double made a huge difference. I did some other
tweaks as well simply for clearer code. The result is nearly four
times faster and produces a fair amount less garbage. The program
still seems to be correct. I think this means I can move onto
figuring out how to do some edge detection to further reduce the
number of numbers that need to be crunched.
Here is what I have now:
;;;; fractal.lisp -- an exploration of the Mandelbrot Set using
;;;; arbitrary sized integer math.
;;;;
;;;; By David Steuber with feedback from comp.lang.lisp
;;;;
;;;; This software is put in the public domain by David Steuber
;;; global variables related to the fractional bits in our fixed radix numbers
(defvar *fractional-bits* 16
"Number of fractional bits in our number")
(defvar *escape-value* (ash 4 *fractional-bits*)
"Numbers larger than this have escaped and are not part of the Mandelbrot Set")
(defvar *fractional-bits-minus-1* (- *fractional-bits* 1))
(defun set-fractional-bits (fb)
"A nice way to set both *fractional-bits* and *escape-value* at the same time"
(setf *escape-value* (ash 4 fb)
*fractional-bits-minus-1* (- fb 1)
*fractional-bits* fb))
(defun shifted-multiply (a b)
"Multiplies a by b and then right-shifts by *fractional-bits*"
(ash (* a b) (- *fractional-bits*)))
(defun shifted-multiply-and-double (a b)
"Returns (* 2 (shifted-multiply a b))"
(ash (* a b) (- *fractional-bits-minus-1*)))
(defun mandelbrot-escape-fn (c-real c-imag &key (max-iterations 10000))
"Return iterations for c-real + c-imag i as integers left shifted by *fractional-bits*"
(loop for iterations below max-iterations
for z-imag = 0 then (+ (shifted-multiply-and-double z-real z-imag) c-imag)
for z-real = 0 then (+ (- z-real-squared z-imag-squared) c-real)
for z-real-squared = 0 then (shifted-multiply z-real z-real)
for z-imag-squared = 0 then (shifted-multiply z-imag z-imag)
unless (< (+ z-real-squared z-imag-squared) *escape-value*) return iterations
finally (return iterations)))
(defun mandelbrot-escape-fn-pc (c-real c-imag &key (max-iterations 10000))
"Return iterations for c-real + c-imag i as integers left shifted by *fractional-bits* doing period checking"
(loop for iterations below max-iterations
for period from 1
for z-imag = 0 then (+ (shifted-multiply-and-double z-real z-imag) c-imag)
for z-real = 0 then (+ (- z-real-squared z-imag-squared) c-real)
for z-real-squared = 0 then (shifted-multiply z-real z-real)
for z-imag-squared = 0 then (shifted-multiply z-imag z-imag)
with a-imag = 0
with a-real = 0
with check = 3
unless (< (+ z-real-squared z-imag-squared) *escape-value*) return iterations
when (and (= a-imag z-imag) (= a-real z-real) (> iterations 1)) return max-iterations
when (> period check) do (setf period 1 check (* 2 check) a-imag z-imag a-real z-real)
finally (return iterations)))
(defun number-to-fixed-radix (n)
"Convert a number to fixed-radix integer representation with *fractional-bits*"
(round (* n (ash 1 *fractional-bits*))))
(defun fixed-radix-to-number (n)
"Almost the inverse of number-to-fixed-radix"
(/ n (ash 1 *fractional-bits*)))
(defun mandelbrot-set (&key (x 0) (y 0) (zoom 1) (aspect 1)
(bitmap-width 100) (bitmap-height 100)
(data-file-name "mandelbrot-data.txt")
(max-iterations 1000))
"Calculate bitmap data for the Mandelbrot Set"
(let ((real-array (make-array bitmap-width)) ; to contain the real values left to right
(imag-array (make-array bitmap-height)) ; to contain the imag values top to bottom
(escape-fn #'mandelbrot-escape-fn) ; escape function to use
(data-file (make-pathname :name data-file-name))
(iterations 0) ; just another local variable
(total-iterations 0)) ; useful to know?
;; initialize real-array
(loop for i below bitmap-width
with size = (/ (* 4 aspect) zoom)
with pixelsize = (/ size bitmap-width)
with start = (- x (* (/ bitmap-width 2) pixelsize))
do (setf (svref real-array i) (number-to-fixed-radix (+ start (* i pixelsize)))))
;; initialize imag-array
(loop for i below bitmap-height
with size = (/ 4 zoom)
with pixelsize = (/ size bitmap-height)
with start = (- y (* (/ bitmap-height 2) pixelsize))
do (setf (svref imag-array i) (number-to-fixed-radix (+ start (* i pixelsize))))
finally (nreverse imag-array)) ; this is so the first element is on the top row
;; we will start by doing this the brute force way and calculate every damn pixel
(with-open-file (stream data-file :direction :output
:if-exists :supersede)
(format stream "/* FRACTAL MANDELBROT */~%/* left top right bottom */~%") ; old format for now
(format stream "~A ~A ~A ~A~%"
(svref real-array 0) (svref imag-array 0)
(svref real-array (1- bitmap-width)) (svref imag-array (1- bitmap-height)))
(format stream "/* center_x center_y aspect zoom */~%")
(format stream "~A ~A ~A ~A~%" x y aspect zoom)
(format stream "/* width height maxitt */~%~A ~A ~A~%/* data */~%" bitmap-width bitmap-height max-iterations)
(dotimes (j bitmap-height)
(dotimes (i bitmap-width)
(setf iterations (funcall escape-fn (svref real-array i) (svref imag-array j) :max-iterations max-iterations))
(if (= iterations max-iterations)
(setf escape-fn #'mandelbrot-escape-fn-pc)
(setf escape-fn #'mandelbrot-escape-fn))
(format stream "~A " iterations)
(incf total-iterations iterations))
(format stream "~%")))
total-iterations))
And a nice test run:
CL-USER> (time (mandelbrot-set :x -3/4 :zoom 2 :bitmap-width 640 :bitmap-height 640))
(MANDELBROT-SET :X -3/4 :ZOOM 2 :BITMAP-WIDTH 640 :BITMAP-HEIGHT 640) took 37,353 milliseconds (37.353 seconds) to run.
Of that, 29,550 milliseconds (29.550 seconds) were spent in user mode
5,460 milliseconds (5.460 seconds) were spent in system mode
2,343 milliseconds (2.343 seconds) were spent executing other OS processes.
2,881 milliseconds (2.881 seconds) was spent in GC.
466,543,248 bytes of memory allocated.
145962887
For this particular zoom and pixmap size, I can speed things up quite
a bit by reducing the *fractional-bits* to 12 and cutting back on the
max-iterations without degrading the image. So the other means of
getting good results in less time is to algorithmically determine
what *fractional-bits* and max-iterations should be for a give pixmap
size and zoom factor.
--
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.
--- Ken Anderson
http://openmap.bbn.com/~kanderso/performance/java/index.html
David Steuber <·············@verizon.net> writes:
> Here is what I have now:
[etc]
Some stylistic notes... You have
(defun mandelbrot-set (...)
(let (... (iterations 0) ...)
...
(dotimes (...)
(dotimes (...)
(setf iterations ...)
...))))
It would be better (and might even produce faster code, though
I doubt it) to write
(defun mandelbrot-set (...)
(let (... ...)
...
(dotimes (...)
(dotimes (...)
(let ((iterations ...))
..)))))
That way the variable ITERATIONS is declared near to where it's used
(which eases the burden on the reader's memory), it has a shorter lifetime
(which might help the compiler, though it may well be able to deduce that
anyway), and it isn't ever altered (which makes it easier to think about).
It might be good to separate calculation and output: make the
MANDELBROT-SET function return, say, a 2-dimensional array of
iteration counts, and have a separate function that writes the
array to a file. On the other hand, your file contains a pile of
extra data computed in the "calculation" part, so maybe that's
not so great an idea.
Your REAL-ARRAY and IMAG-ARRAY are calculated in essentially the
same way as each other. Pull that calculation out into a function:
(defun arange (first step i0 n &optional (converter #'identity))
(let ((result (make-array n)))
(loop repeat n for i upfrom i0 do
(setf (aref result i)
(funcall converter (+ first (* i step)))))
result))
(defun mandelbrot-set (...)
(let (...
(real-array (arange x (/ (* 4 aspect) zoom bitmap-width)
(- (/ bitmap-width 2)) bitmap-width
#'number-to-fixed-radix))
(imag-array (arange y (/ -4 zoom bitmap-height)
(/ bitmap-height 2) bitmap-height
#'number-to-fixed-radix))
...)
...))
You could (I don't know whether it would be worth it) abstract out
the notion of iterating over a rectangular array.
(defmacro for-2d-array ((i-var x-var x-values)
(j-var y-var y-values)
&body body)
(let ((x-values-sym (gensym))
(y-values-sym (gensym)))
`(let ((,x-values-sym ,x-values)
(,y-values-sym ,y-values))
(dotimes (,i-var ,(length x-values))
(let ((,x-var (aref ,x-values-sym ,i-var)))
(dotimes (,j-var ,(length y-values))
(let ((,y-var (aref ,y-values-sym ,j-var)))
,@body)))))))
(defun mandelbrot-set (...)
...
(for-2d-array (i x real-array) (j y imag-array)
... do something with (funcall escape-fn x y) ...))
I'd consider making the iteration limit a special variable.
All these changes will actually make your code slightly longer,
but they will also make it easier to change in future and easier
to reuse bits of.
--
Gareth McCaughan
.sig under construc
Gareth McCaughan <················@pobox.com> writes:
I've saved your response because it has a lot of good ideas in it I
want to try.
> It might be good to separate calculation and output: make the
> MANDELBROT-SET function return, say, a 2-dimensional array of
> iteration counts, and have a separate function that writes the
> array to a file. On the other hand, your file contains a pile of
> extra data computed in the "calculation" part, so maybe that's
> not so great an idea.
Actually, the file output is temporary because I have a Perl script
that can make an XPM out of it. I just wanted to make sure I was in
fact producing what I thought I was. So the file stuff can (and
will) be moved out of the calculation code.
Of course if I ever want to make a GUI for this that shows the
progress of the calculation, I will have to work out something
different.
Thanks.
--
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.
--- Ken Anderson
http://openmap.bbn.com/~kanderso/performance/java/index.html
David Steuber <·············@verizon.net> writes:
> Gareth McCaughan <················@pobox.com> writes:
>
> I've saved your response because it has a lot of good ideas in it I
> want to try.
>
>> It might be good to separate calculation and output: make the
>> MANDELBROT-SET function return, say, a 2-dimensional array of
>> iteration counts, and have a separate function that writes the
>> array to a file. On the other hand, your file contains a pile of
>> extra data computed in the "calculation" part, so maybe that's
>> not so great an idea.
>
> Actually, the file output is temporary because I have a Perl script
> that can make an XPM out of it. I just wanted to make sure I was in
> fact producing what I thought I was. So the file stuff can (and
> will) be moved out of the calculation code.
>
> Of course if I ever want to make a GUI for this that shows the
> progress of the calculation, I will have to work out something
> different.
>
> Thanks.
I think the ray-tracer example in Paul Graham's "ANSI Common
Lisp" (or possibly "On Lisp") includes code for generating XPM output.
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
From: John Thingstad
Subject: Re: Code Feedback Wanted (Generating more garbage)
Date:
Message-ID: <opr5houflzxfnb1n@news.chello.no>
Just thought I would mention that the chaos algorithm is more efficient
than escape time.
On Wed, 24 Mar 2004 15:58:31 GMT, Kenny Tilton <·······@nyc.rr.com> wrote:
>
>
> David Steuber wrote:
>> (defun shifted-multiply (&rest args)
>
> I am no expert, but I think this forces a consing of a list. But the
> code I see always calls s-m with two values or two values and *my-two*
> (aside: would making some of these defvars into defconstants help?). So
> perhaps some benefit can be had by creating two functions s-m and s-mx2,
> where the latter expands to (s-m *my-two* (s-m x y)).
>
> I think there was another function in there also using &rest args, but I
> did not check that one out more closely. As a rule, there is a cost to
> &rest, &key, and (I think) &optional.
>
> Nice picture, btw.
>
> kt
>
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
John Thingstad <··············@chello.no> writes:
> Just thought I would mention that the chaos algorithm is more
> efficient than escape time.
I'm not familiar with that one. Can you point me to it or show a
simple Lisp version of it? Would I still be able to map colors
outside the set? The nice thing about the escape time is that with
the right pallet mapping, I can make some very pretty pictures.
I am looking at how I can use standard graphics techniques to locate
the edge/boundry of the set and then work my way around that so that
I do not have to calculate too many points in the interior.
Naturally with escape time and no period checking, points in the set
will consume the max-iterations.
--
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.
--- Ken Anderson
http://openmap.bbn.com/~kanderso/performance/java/index.html
Avant:
> CL-USER> (time (mandelbrot-set :x -3/4 :zoom 2 :bitmap-width 640 :bitmap-height 640))
> (MANDELBROT-SET :X -3/4 :ZOOM 2 :BITMAP-WIDTH 640 :BITMAP-HEIGHT 640) took 126,626 milliseconds (126.626 seconds) to run.
> Of that, 87,830 milliseconds (87.830 seconds) were spent in user mode
> 32,520 milliseconds (32.520 seconds) were spent in system mode
> 6,276 milliseconds (6.276 seconds) were spent executing other OS processes.
> 24,051 milliseconds (24.051 seconds) was spent in GC.
> 2,252,959,120 bytes of memory allocated.
Apres:
> CL-USER> (time (mandelbrot-set :x -3/4 :zoom 2 :bitmap-width 640 :bitmap-height 640))
> (MANDELBROT-SET :X -3/4 :ZOOM 2 :BITMAP-WIDTH 640 :BITMAP-HEIGHT 640) took 37,353 milliseconds (37.353 seconds) to run.
> Of that, 29,550 milliseconds (29.550 seconds) were spent in user mode
> 5,460 milliseconds (5.460 seconds) were spent in system mode
> 2,343 milliseconds (2.343 seconds) were spent executing other OS processes.
> 2,881 milliseconds (2.881 seconds) was spent in GC.
> 466,543,248 bytes of memory allocated.
Roughly:
Bef Aft
User 88 30
System 33 5
GC 24 3
Mem(gb) 2.3 0.5
Wow. Does anyone know why? Was it the &rest -> non-&rest switch? Duane
said the switch would be faster but for a different reason, without
specifying the latter. He also said &rest was efficient if it was (or
was not?) "dynamic extent". Hunh? Whassat? Examples, plz, I really am
just an apps guy.
> For this particular zoom and pixmap size, I can speed things up quite
> a bit by reducing the *fractional-bits* to 12 and cutting back on the
> max-iterations without degrading the image. So the other means of
> getting good results in less time is to algorithmically determine
> what *fractional-bits* and max-iterations should be for a give pixmap
> size and zoom factor.
>
I am still curious what effect changing the defvars to defconstant would
do. I do not see those changing during the run. I understand you want to
make those into parameters eventually. Just curious.
kt
>>>>> "KT" == Kenny Tilton <·······@nyc.rr.com> writes:
KT> ... He also said
KT> &rest was efficient if it was (or was not?) "dynamic
KT> extent". Hunh? Whassat? Examples, plz, I really am just an
KT> apps guy. ...
He must have said "if it was." Dynamic extent (as opposed to indefinite
extent you are used to) means the data is not alive once the function
returns. That means you don't return pointers to it, you don't assign it
to a dynamic var etc. Fancy name for 'can be allocated on the stack.'
You use a declaration for this and the implementation is allowed to
ignore it. Nasal daemons if you lie. Hyperspec is calling you...
cheers,
BM
Bulent Murtezaoglu wrote:
>>>>>>"KT" == Kenny Tilton <·······@nyc.rr.com> writes:
>
>
> KT> ... He also said
> KT> &rest was efficient if it was (or was not?) "dynamic
> KT> extent". Hunh? Whassat? Examples, plz, I really am just an
> KT> apps guy. ...
>
> He must have said "if it was." Dynamic extent (as opposed to indefinite
> extent you are used to) means the data is not alive once the function
> returns. That means you don't return pointers to it, you don't assign it
> to a dynamic var etc. Fancy name for 'can be allocated on the stack.'
> You use a declaration for this and the implementation is allowed to
> ignore it. Nasal daemons if you lie. Hyperspec is calling you...
I generally cannot understand technical doc written any less clearly
than K&R, which leaves a pretty short list. Most tech docs read like
mathematical proofs, and make sense to me only if I already know what
they are trying to say.
"once the function returns"? But rest args are on the way in. The
example was:
(my-multiply 1 2 3)
and (defun my-multiply (&rest factors)...
Now the body of my multiply is looking at a list. Where'd it come from?
(this is the way apps-guys think).
Does the compiler see that my-multiply does not do something such as
return the list it receives, in which case it would have indefinite
extent, and so cooks up at compile time a reusable three-cons allocation
to be used each time that particular invocation of my-multiply gets hit?
Makes sense.
So why did the consing drop from 2.3gb to 0.5gb? I'm getting ready to
start tracking down every occurrence of &rest in Cello.
:)
kt
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
From: Joe Marshall
Subject: Re: Code Feedback Wanted (Generating more garbage)
Date:
Message-ID: <fzbwsxku.fsf@ccs.neu.edu>
Kenny Tilton <·······@nyc.rr.com> writes:
> I generally cannot understand technical doc written any less clearly
> than K&R, which leaves a pretty short list. Most tech docs read like
> mathematical proofs, and make sense to me only if I already know what
> they are trying to say.
>
> "once the function returns"? But rest args are on the way in. The
> example was:
>
> (my-multiply 1 2 3)
>
> and (defun my-multiply (&rest factors)...
>
> Now the body of my multiply is looking at a list. Where'd it come
> from? (this is the way apps-guys think).
The caller generally pushes a bunch of arguments on the stack. When
my-multiply is entered, before it gets to the code inside, it sees
that it was handed a bunch of arguments, but that it is supposed to
treat them like a list of arguments. It therefore conses up a list.
In the absence of any other information, that list might last
indefinitely, so it is consed in the heap. But if the author of
my-multiply knows that none of the cons cells that are used to create
the list will need to survive beyond the call, he can tell the
compiler to stack allocate them.
Joe Marshall wrote:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>
>>I generally cannot understand technical doc written any less clearly
>>than K&R, which leaves a pretty short list. Most tech docs read like
>>mathematical proofs, and make sense to me only if I already know what
>>they are trying to say.
>>
>>"once the function returns"? But rest args are on the way in. The
>>example was:
>>
>> (my-multiply 1 2 3)
>>
>>and (defun my-multiply (&rest factors)...
>>
>>Now the body of my multiply is looking at a list. Where'd it come
>>from? (this is the way apps-guys think).
>
>
> The caller generally pushes a bunch of arguments on the stack. When
> my-multiply is entered, before it gets to the code inside, it sees
> that it was handed a bunch of arguments, but that it is supposed to
> treat them like a list of arguments. It therefore conses up a list.
>
> In the absence of any other information, that list might last
> indefinitely, so it is consed in the heap. But if the author of
> my-multiply knows that none of the cons cells that are used to create
> the list will need to survive beyond the call, he can tell the
> compiler to stack allocate them.
And a good compiler could look at:
(defun my-summer (&rest addends) (loop for n in adddends summing n))
and stack-allocate? I am still trying to understand why the latest
version of David's fractal generator used so much less memory. Was it
unrelated to eliminating the rest args? Was his compiler not smart
enough? Would declaring dynamic extent have allowed him to leave the
code otherwise as it was, with &rest args.
kt
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
From: Joe Marshall
Subject: Re: Code Feedback Wanted (Generating more garbage)
Date:
Message-ID: <wu57bdr0.fsf@comcast.net>
Kenny Tilton <·······@nyc.rr.com> writes:
> And a good compiler could look at:
>
> (defun my-summer (&rest addends) (loop for n in adddends summing n))
>
> and stack-allocate?
Yep.
> I am still trying to understand why the latest
> version of David's fractal generator used so much less memory. Was it
> unrelated to eliminating the rest args? Was his compiler not smart
> enough? Would declaring dynamic extent have allowed him to leave the
> code otherwise as it was, with &rest args.
I'm afraid I didn't study the code in detail. I'll do that and see
what I can figure out.
--
~jrm
From: Joe Marshall
Subject: Re: Code Feedback Wanted (Generating more garbage)
Date:
Message-ID: <n060bwvg.fsf@comcast.net>
Joe Marshall <·············@comcast.net> writes:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>> And a good compiler could look at:
>>
>> (defun my-summer (&rest addends) (loop for n in adddends summing n))
>>
>> and stack-allocate?
>
> Yep.
>
>> I am still trying to understand why the latest
>> version of David's fractal generator used so much less memory. Was it
>> unrelated to eliminating the rest args? Was his compiler not smart
>> enough? Would declaring dynamic extent have allowed him to leave the
>> code otherwise as it was, with &rest args.
>
> I'm afraid I didn't study the code in detail. I'll do that and see
> what I can figure out.
I looked at it. The big issue was the call to shifted multiply and by
declaring the &rest arg to be dynamic extent I saw the amount of list
consing drop from 162,145,430 to 1,232,699 (two orders of magnitude!)
But this doesn't necessarily make things two orders of magnitude
faster. The total time, on my machine, was 139 seconds without the
dynamic extent and 121 seconds with. The gc time dropped from 5.6
seconds to 3.2 seconds. So in this case, it was worth the effort to
declare it dynamic extent, but barely.
Since shifted-multiply is only called with 2 or 3 arguments,
replacing it with this version:
(defun shifted-multiply (arg0 arg1 &optional arg2)
(if arg2
(ash (* arg0 arg1 arg2) (- (* 2 *fractional-bits*)))
(ash (* arg0 arg1) (- *fractional-bits*))))
cut the time down to 73 seconds.
--
~jrm
Kenny Tilton <·······@nyc.rr.com> writes:
> Bulent Murtezaoglu wrote:
>
> >>>>>>"KT" == Kenny Tilton <·······@nyc.rr.com> writes:
> > KT> ... He also said
>
> > KT> &rest was efficient if it was (or was not?) "dynamic
> > KT> extent". Hunh? Whassat? Examples, plz, I really am just an
> > KT> apps guy. ...
> > He must have said "if it was." Dynamic extent (as opposed to
Actually, I said "if it can be". If an &rest argument is captured
and survives the function call, then it is not dynamic-extent
and this can't be declared as such without lying to the compiler.
> > indefinite extent you are used to) means the data is not alive once
> > the function returns. That means you don't return pointers to it,
> > you don't assign it to a dynamic var etc. Fancy name for 'can be
> > allocated on the stack.' You use a declaration for this and the
> > implementation is allowed to ignore it. Nasal daemons if you lie.
> > Hyperspec is calling you...
>
>
> I generally cannot understand technical doc written any less clearly
> than K&R, which leaves a pretty short list. Most tech docs read like
> mathematical proofs, and make sense to me only if I already know what
> they are trying to say.
>
>
> "once the function returns"? But rest args are on the way in. The
> example was:
>
>
> (my-multiply 1 2 3)
>
> and (defun my-multiply (&rest factors)...
>
> Now the body of my multiply is looking at a list. Where'd it come
> from? (this is the way apps-guys think).
The my-multiply function creates it, on the way in. Where it
creates it depends on what the compiler knows about how it will be
used. The default tends to be "on the heap".
> Does the compiler see that my-multiply does not do something such as
> return the list it receives, in which case it would have indefinite
> extent, and so cooks up at compile time a reusable three-cons
> allocation to be used each time that particular invocation of
> my-multiply gets hit?
Returning the list is only one of the ways to violate
dynamic-extentness. Setting global state will also violate
dynamic-extenness, as others have noted. An example might help:
CL-USER(1): (defvar *x*)
*X*
CL-USER(2): (defun foo (&rest x)
(declare (optimize speed) (dynamic-extent x))
(setq *x* x)
(break "x: ~s" x))
FOO
CL-USER(3): (compile *)
FOO
NIL
NIL
CL-USER(4): (foo 1 2 3 4 5)
Break: x: (1 2 3 4 5)
Restart actions (select using :continue):
0: return from break.
1: Return to Top Level (an "abort" restart).
2: Abort entirely from this process.
[1c] CL-USER(5): *x*
(1 2 3 4 5)
[1c] CL-USER(6): :cont
NIL
CL-USER(7): *x*
(#<STRING-OUTPUT-SIMPLE-STREAM "" pos 0 @ #x717833ca>
. #<Closure (:INTERNAL EXCL::DEFRESOURCE-1 1) @ #x711ea4f2>)
CL-USER(8):
Note: your last result will probably vary :-)
> Makes sense.
>
> So why did the consing drop from 2.3gb to 0.5gb?
The consing didn't drop, only the heap-consing dropped. The time
macro doesn't track stack-consing, because it's generally considered
to be "free", and it is, at least wrt GC.
> I'm getting ready to
> start tracking down every occurrence of &rest in Cello.
>
>
> :)
The smiley shouldn't be necessary; people do seriously go through
their sources and do precisely that.
If this isn't enough for your apps-guy mind to absorb ;-) -
One other optimization we provide automatically is that if a
&rest argument is used only as the last argument of one or more
apply statements, then the &rest list isn't even consed on the
stack at all; instead the apply is turned into what we call
"applyn", which takes the appropriate arguments from the call
site itself, and copies the arguments down from the parent, where
they were left alone, and makes the larger call without even consing
on the stack; both approaces do no heap consing, but the applyn
style doesn't even run through extra code to build up a list on
the stack, since it is obvious that the &rest list is only being
used to pass down to the next function.
For example,
(defun foo (x y &rest z)
(if y
(apply x :extra y z)
(apply x z)))
In this code, z is never used as a list, really, and is thus
only intended to provide the arguments to the next function.
So regardless of whether the list is dynamic-extent, it need
not be consed up at all, even on the stack. Instead, the arguments
to foo are copied down directly to whatever is going to be called
as the value of x.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig wrote:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>
>>Bulent Murtezaoglu wrote:
>>
>>
> CL-USER(2): (defun foo (&rest x)
> (declare (optimize speed) (dynamic-extent x))
> (setq *x* x)
> (break "x: ~s" x))
> FOO
> CL-USER(3): (compile *)
> FOO
> NIL
> NIL
> CL-USER(4): (foo 1 2 3 4 5)
> Break: x: (1 2 3 4 5)
>
> Restart actions (select using :continue):
> 0: return from break.
> 1: Return to Top Level (an "abort" restart).
> 2: Abort entirely from this process.
> [1c] CL-USER(5): *x*
> (1 2 3 4 5)
> [1c] CL-USER(6): :cont
> NIL
> CL-USER(7): *x*
> (#<STRING-OUTPUT-SIMPLE-STREAM "" pos 0 @ #x717833ca>
> . #<Closure (:INTERNAL EXCL::DEFRESOURCE-1 1) @ #x711ea4f2>)
Cool! :)
>>So why did the consing drop from 2.3gb to 0.5gb?
>
>
> The consing didn't drop, only the heap-consing dropped. The time
> macro doesn't track stack-consing, because it's generally considered
> to be "free", and it is, at least wrt GC.
Aha!
But this was the original:
(defun shifted-multiply (&rest args)
(let ((n (apply #'* args)))
(ash n (- (* (max 0 (- (list-length args) 1)) *fractional-bits*)))))
And the compiler heap-consed because...it does not analyze the function
to determine if could go with dynamic extent? One has to make the
declaration to get the tuning? Or because it /did/ analyze but could not
be bothered to check the function value behind the first arg to var to
see if it was a known function which would be cool with dynamic-extent?
Maybe it just sees (list-length args) and thinks "game up"?
Thanks, Duane, but....Throw me a bone, people! Why did v2 heap-cons
less?!!! (And why would (sm x1 (sm x2 x3)) would be faster, but not
because of the rest args?)
:)
kt
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
Kenny Tilton <·······@nyc.rr.com> writes:
> But this was the original:
>
> (defun shifted-multiply (&rest args)
> (let ((n (apply #'* args)))
> (ash n (- (* (max 0 (- (list-length args) 1)) *fractional-bits*)))))
>
> And the compiler heap-consed because...it does not analyze the
> function to determine if could go with dynamic extent?
Knowing that a function _can_ be compiled assuming dynamic-extent
and actually taking advantage of such optimizations are two different
things. Sometimes the optimizations which just seem obvious to you
might not be so obvious to someone else (or to a compiler). So you
have equated the answer "This is dynamic-extent" with the related, but
different answer "I can stack-allocate this", and further have concluded
"I want to stack-allocate this". As a compiler writer, I have to be sure
that the three statements are virtually equivalent (or if they are not,
the user has to have a way to disable the automation) before I would
agree to making such automatic compilation. The major disincentive
there is to stack-allocation is a reduction of debuggability in
the face of multiprocessing - you may be debugging a stack-allocated
object which is still in scope, but which is unavailable due to the
virtual nature of the stacks themselves.
> One has to make
> the declaration to get the tuning? Or because it /did/ analyze but
> could not be bothered to check the function value behind the first arg
> to var to see if it was a known function which would be cool with
> dynamic-extent?
Having said what I said, it is in fact true that we do extensive
analysis for dynamic-extent _functions_ (flets, labels), which
follow this kind of reasoning. So, for example, a construct
like
(flet ((foo (...) ...))
...
#'foo
...
would normally kill the possibility that foo is stack-allocated,
_unless_ the usage of #'foo is to a function with known dynamic-extent
usage of its function-argument. So (mapcar #'foo ...) would
still allow foo to be stack-allocated, becase mapcar never captures
the functional argument.
> Maybe it just sees (list-length args) and thinks "game
> up"?
Yes.
> Thanks, Duane, but....Throw me a bone, people! Why did v2 heap-cons
> less?!!! (And why would (sm x1 (sm x2 x3)) would be faster, but not
> because of the rest args?)
I actually haven't been following this thread as closely as I'd
like, so I'm not sure what you mean by v2, and the sm form you reference.
Perhaps you can reword this question without any assumption that I
know the context.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Stepping into the Wayback Machine, this was version one ("v1"):
>>
>> (defun shifted-multiply (&rest args)
>> (let ((n (apply #'* args)))
>> (ash n (- (* (max 0 (- (list-length args) 1)) *fractional-bits*)))))
>>
Then ....
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>
>>> David Steuber wrote:
>>
>>>> > (defun shifted-multiply (&rest args)
>>
>>>
>>> I am no expert, but I think this forces a consing of a list.
>
>
> Yes, but it's not necessary, if the argument can be declared
> dynamic-extent.
>
...which I mistook to be a comment on v1, and further took to be
indicating that in v1's case rest was not a problem. ie, I was just
thinking about v1, and you were (I am guessing) stepping in to correct
an over-generalization (aka "mistake") on my part. The moral being I do
not have to abandon the use of &rest in compute-intensive code where it
is the most elegant tool, as long as I can guarantee in my own mind that
dynamic extent is safe, in which case I make a declaration to that
effect rather than stare at the code and try to guess if the compiler
will be able to figure out what I already know, with the understanding
that when I hastily make a change just before the demo to potential
investors and screw up that promise....
I then continued:
>
>>> But the
>>> code I see always calls s-m with two values or two values and *my-two*
>>> (aside: would making some of these defvars into defconstants
>>> help?). So perhaps some benefit can be had by creating two functions
>>> s-m and s-mx2, where the latter expands to (s-m *my-two* (s-m x y)).
>
...and you offered:
>
> This is true, for cost reasons not necessarily related to consing
>
...without dropping the other shoe.
btw, it certainly is a hoot having a top guy from a top compiler hanging
out here on CL using all those big words and dispensing insight, even if
most of it leaves me with that stunned-cow look.
Much appreciated.
kt
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
Kenny Tilton <·······@nyc.rr.com> writes:
> Stepping into the Wayback Machine, this was version one ("v1"):
> >>
> >> (defun shifted-multiply (&rest args)
> >> (let ((n (apply #'* args)))
> >> (ash n (- (* (max 0 (- (list-length args) 1)) *fractional-bits*)))))
> >>
>
> Then ....
>
> > Kenny Tilton <·······@nyc.rr.com> writes:
> >
>
> >>> David Steuber wrote:
> >>
> >>>> > (defun shifted-multiply (&rest args)
> >>
> >>> I am no expert, but I think this forces a consing of a list.
>
> > Yes, but it's not necessary, if the argument can be declared
> > dynamic-extent.
> >
>
>
> ...which I mistook to be a comment on v1, and further took to be
> indicating that in v1's case rest was not a problem. ie, I was just
> thinking about v1, and you were (I am guessing) stepping in to correct
> an over-generalization (aka "mistake") on my part.
Yes. The "it" in this case referred to consing, not &rest arguments.
I see, now; we never really saw v2, but only talked about it.
> The moral being I
> do not have to abandon the use of &rest in compute-intensive code
> where it is the most elegant tool, as long as I can guarantee in my
> own mind that dynamic extent is safe, in which case I make a
> declaration to that effect rather than stare at the code and try to
> guess if the compiler will be able to figure out what I already know,
> with the understanding that when I hastily make a change just before
> the demo to potential investors and screw up that promise....
Well, of course you know that the demo-syndrome is an inevitability...
> I then continued:
>
> >
>
> >>> But the
> >>> code I see always calls s-m with two values or two values and *my-two*
> >>> (aside: would making some of these defvars into defconstants
> >>> help?). So perhaps some benefit can be had by creating two functions
> >>> s-m and s-mx2, where the latter expands to (s-m *my-two* (s-m x y)).
> >
>
>
> ...and you offered:
>
> > This is true, for cost reasons not necessarily related to consing
>
> >
>
>
> ...without dropping the other shoe.
I think if you had understood my "it's not necessary" as dealing with
consing, you would have recognized the other shoe, and that I did not
let it drop, but set it down very gently (you didn't even hear it!)
The shoe consisted of three parts, an assessment of costs (other than
consing) of each of &key, &rest, and &optional argument receiving
in functions. To see what I mean, create some trivial functions of
each type of argument, each by itself, and compile and disassemble
them; I think you'll see what I mean, even if you don't know the
disassembler or the architecture. Don't forget to also disassemble
a function with only required arguments, for comparison.
> btw, it certainly is a hoot having a top guy from a top compiler
> hanging out here on CL using all those big words and dispensing
> insight, even if most of it leaves me with that stunned-cow look.
Thanks. And of course, the first thought in my mind here was:
Got Milk?
> Much appreciated.
Your welcome. But you're the hoot in this ng; I always enjoy reading
your posts. If only we could harness all that energy ...
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig wrote:
> But you're the hoot in this ng;
Nah, just trying to keep up with Bradshaw and Gilham...
> If only we could harness all that energy ...
Jeez, give them a portable CL gui with constraints and they
want....what? What else can the open source fairy leave under your pillow?
You know, I had a scary thought. If Cello is platform-agnostic, all we
gotta do is the plug-in glue and we have that CL Web plug-in.* Curl
found out no one wanted a thick web client, but if the open source fairy
leaves one under your pillow....?
kt
* As long as users will sit still long enough for the installer to pipe
in all fifteen libraries Cello de... on which Cello depends.
k
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
Kenny Tilton <·······@nyc.rr.com> writes:
> btw, it certainly is a hoot having a top guy from a top compiler
> hanging out here on CL using all those big words and dispensing
> insight, even if most of it leaves me with that stunned-cow look.
Yes it is a hoot. I honestly would not have considered &rest to be a
problem. Or &key. And those are both useful things to have.
One thing I think may be a factor (I don't know how major) in the
speed up of the code is the total amount of bignum arithmetic being
performed:
CL-USER> (set-fractional-bits 12)
12
CL-USER> (time (mandelbrot-set :x -3/4 :zoom 2 :bitmap-width 640 :bitmap-height 640))
(MANDELBROT-SET :X -3/4 :ZOOM 2 :BITMAP-WIDTH 640 :BITMAP-HEIGHT 640) took 14,759 milliseconds (14.759 seconds) to run.
Of that, 13,980 milliseconds (13.980 seconds) were spent in user mode
310 milliseconds (0.310 seconds) were spent in system mode
469 milliseconds (0.469 seconds) were spent executing other OS processes.
83,864 bytes of memory allocated.
Two 12 bit quantities multiplied together will not exceed 24 bits,
even with overflow. In OpenMCL, a fixnum is 29 bits (I guess that
three bits carry type information). So when I multiply two 16 bit
numbers, I get a 32 bit result which puts me in bignum territory. I
can really slow down the above function call by going with 64 bits.
Enough so that I don't want to do a run while I am typing this post
;-)
Also the period checking code is less likely to detect periodicity
with bigger numbers because of the time it takes to get attracted to
some value.
So just looking at &rest does not give a complete picture. The code
changes reduced the actual number of calculations required to produce
the result. Good algorithms rule.
However, I now have more things to think about when the time does
come to try optimization. I think that this is also a demonstration
of the proverb that it is easy to write slow Lisp code.
--
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.
--- Ken Anderson
http://openmap.bbn.com/~kanderso/performance/java/index.html
> One thing I think may be a factor (I don't know how major) in the
> speed up of the code is the total amount of bignum arithmetic being
> performed:
I hear performance-wise bignums are the end of the world as we know it.
> can really slow down the above function call by going with 64 bits.
> Enough so that I don't want to do a run while I am typing this post
> ;-)
Pardon a Deep Thought from a phys ed major in the fractal herd, but if
fractals manifest the same shape no matter how deep you go, why go any
deeper than 96dpi? 1440dpi for print? or is that bignum turf?
mmmooooooo....
kt
ps. could someone get that horsefly off my ass?
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
From: Paul Wallich
Subject: Re: Code Feedback Wanted (Generating more garbage)
Date:
Message-ID: <c41jqs$o6c$2@reader1.panix.com>
Kenny Tilton wrote:
>> One thing I think may be a factor (I don't know how major) in the
>> speed up of the code is the total amount of bignum arithmetic being
>> performed:
>
>
> I hear performance-wise bignums are the end of the world as we know it.
>
>> can really slow down the above function call by going with 64 bits.
>> Enough so that I don't want to do a run while I am typing this post
>> ;-)
>
>
> Pardon a Deep Thought from a phys ed major in the fractal herd, but if
> fractals manifest the same shape no matter how deep you go, why go any
> deeper than 96dpi? 1440dpi for print? or is that bignum turf?
Self-_similar_. Not self-duplicated. (at least not all of them)
pqul
Kenny Tilton <·······@nyc.rr.com> writes:
> Pardon a Deep Thought from a phys ed major in the fractal herd, but if
> fractals manifest the same shape no matter how deep you go, why go any
> deeper than 96dpi? 1440dpi for print? or is that bignum turf?
He's zooming! (I am not aware that the complex plane has dot-per-inch units).
--
__Pascal_Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he doesn't
want merely because you think it would be good for him.--Robert Heinlein
http://www.theadvocates.org/
From: Tim Daly Jr.
Subject: Re: Code Feedback Wanted (Generating more garbage)
Date:
Message-ID: <873c7vg83p.fsf@hummer.intern>
Kenny Tilton <·······@nyc.rr.com> writes:
> Pardon a Deep Thought from a phys ed major in the fractal herd, but if
> fractals manifest the same shape no matter how deep you go, why go any
> deeper than 96dpi? 1440dpi for print? or is that bignum turf?
Fractals like the Mandelbrot set exhibit self-similarity, which means
that parts of them are similar to the whole. It doesn't mean that
there are no variations on the theme. That lobe-y thingy with the
point on it will twist to one side or the other, get hairier, etc., as
you zoom. That's what makes it so trippy. :)
--
-Tim
Check out the new PHP compiler: www.roadsend.com
In article <···················@twister.nyc.rr.com>,
Kenny Tilton <·······@nyc.rr.com> wrote:
> Pardon a Deep Thought from a phys ed major in the fractal herd, but if
> fractals manifest the same shape no matter how deep you go, why go any
> deeper than 96dpi? 1440dpi for print? or is that bignum turf?
It's not completely similar. You just can't find strange crap like this
without zooming in:
http://home.insightbb.com/~bdowning0/horizontal-hold.png
That area is at
#C(-1.999999999999999999999999999999999999999999999999999999999999999...
999999999999999999999999999999999999999999999999999999999999999999999...
999999999999999999998895836912417836217316527999933164430805531612097...
027084085942478631470944179784765553302325289533320961898109921686419...
831529734837424289096210971806586916814 0), and the magnification is set
to 1e306. A Windows program (Ultra Fractal, evaluation version), took
2.5 hours to render the 640x480 image with the above parameters and
80000 iterations on an Athlon 1900+. 311 decimals of arbitrary
precision were used. Periodicity checking was off, because it was
screwing up at that depth.
(I believe that time only represents rendering the upper half of the
image, and the lower half was duplicated from the upper, since the
imaginary origin runs through the middle of the image.)
This can be used by the OP and anyone else who is interested as a guide
to the speed of (probably) hand-optimized assembly for this task. (I
was using the built-in "fast" Mandelbrot, not the normal one compiled
from a user-specified formula.)
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Kenny Tilton <·······@nyc.rr.com> writes:
> Pardon a Deep Thought from a phys ed major in the fractal herd, but if
> fractals manifest the same shape no matter how deep you go, why go any
> deeper than 96dpi? 1440dpi for print? or is that bignum turf?
As other's have said, zooms get interesting. Check this out:
http://www.david-steuber.com/~david/fractal-movie/
You need QuickTime to play it back. This zoom is not all that deep.
There are still a couple of digits left in IEEE 764 double. That is,
each pixel still has a unique coordinate value within the available
precision.
There is complexity there.
I churned out those frames with sub-optimal C code. What I would
like to do is churn out even more frames in less time with a better
algorithm. However, I am stuck with the need to go with bignums once
I pass a certain zoom factor.
The last frame in the movie was calculated with the following call to
my little C program:
./fractal -m9999999 -z39999999999997.3 -x-0.7488480795599556927300 -y0.0416808596456499994010 > frames/frame1800.txt
-m is max-iterations
-z is zoom
-x is the x coordinate
-y is the y coordinate
The fractal program just sends its output to STDOUT. I used a Perl
script to generate two simple shell scripts. One shell script was
for calculating the even frames, the other for the odd frames. In
this way, I kept two CPUs busy for several days.
I probably went overboard with the max-iterations. There was no
period checking. There were no other optimizations. Each pixel was
calculated for each frame.
The fact that the Mandelbrot Set is symetrical about the real axis
very quickly didn't matter.
The movie Contact (based on that fine novel by Carl Sagan) opened up
with a very nice zoom out. I would sooooo like to be able to top
that with the Mandelbrot Set in a reasonable time frame. My current
fractal movie is sort of a first cut at that. The full set would
still fit in the solar system at the final magnification. The edges
are flying apart from each other at a rate much faster than the speed
of light. It kind of makes Hubble's Law interesting, if you know
what I mean.
Anyway, using my prior experience with the first fractal zoom movie,
I should be able to cut way down on the number of calculations I need
to do for an equal result. At the same time, I am learning to
program in C with Lisp :-/
Heh. Well not quite. I am liking the Lisp and I expect to
transition over to a Lispy style along the way.
--
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.
--- Ken Anderson
http://openmap.bbn.com/~kanderso/performance/java/index.html