Suppose I have a "color" class in a graphics package that supports
various color formats, e.g. 32-bit colors (8 bits of red, green, blue,
and alpha), 16-bit colors (e.g 5 bits red, 6 bits green, 5 bits blue),
HSV, and so on.
Obviously, I want to be able to convert between the various types. A
first cut would be to define something like:
(defgeneric convert-color (old-color new-type)
...)
so one might write:
(let ((hsv = convert-color(some-color 'color-hsv)))
...
convert-color would make an instance of new-type, fill in the slots, and
return the instance.
The problem with this is that it can be very, very slow since color
conversion always creates a new instance. Code I wrote two years ago to
check RGB888 -> HSV conversion for all possible RGB values, without
using classes, took about 30 seconds to run on my laptop. The
class-based code using the above technique took over 10 times longer.
So, take #2. Change the color conversion routines to be:
(defgeneric convert-color (old-color new-color)
...)
convert-color then does setf's on the slots of new-color.
With this implementation, the code to test RGB888->HSV conversion takes
30 seconds, since I only need to create one instance of an HSV and
converted RGB color, instead of 2^24 instances.
But somehow the paradigm of this type of function side effect is too
"C-ish" and just doesn't feel "Lisp-ish".
Any other techniques I might consider?
On Mar 1, 2:37 pm, ····@stablecross.com (Bob Felts) wrote:
> Suppose I have a "color" class in a graphics package that supports
> various color formats, e.g. 32-bit colors (8 bits of red, green, blue,
> and alpha), 16-bit colors (e.g 5 bits red, 6 bits green, 5 bits blue),
> HSV, and so on.
>
> Obviously, I want to be able to convert between the various types. A
> first cut would be to define something like:
>
> (defgeneric convert-color (old-color new-type)
> ...)
>
> so one might write:
>
> (let ((hsv = convert-color(some-color 'color-hsv)))
> ...
>
> convert-color would make an instance of new-type, fill in the slots, and
> return the instance.
>
> The problem with this is that it can be very, very slow since color
> conversion always creates a new instance. Code I wrote two years ago to
> check RGB888 -> HSV conversion for all possible RGB values, without
> using classes, took about 30 seconds to run on my laptop. The
> class-based code using the above technique took over 10 times longer.
>
> So, take #2. Change the color conversion routines to be:
>
> (defgeneric convert-color (old-color new-color)
> ...)
>
> convert-color then does setf's on the slots of new-color.
>
> With this implementation, the code to test RGB888->HSV conversion takes
> 30 seconds, since I only need to create one instance of an HSV and
> converted RGB color, instead of 2^24 instances.
>
> But somehow the paradigm of this type of function side effect is too
> "C-ish" and just doesn't feel "Lisp-ish".
>
> Any other techniques I might consider?
You don't end up with all of your colors being the last color that you
converted?
I'm a little confused how this is supposed to work. Are we interested
in *actually* converting a bunch of colors, or converting it, using it
and throwing it away?
If you are going to use the same color over and over again,
(As in an actual application of converting one thing to another rather
than a benchmark),
you could do some memoization (ex. with a 3D array).
ex.:
(setf *hsv-lookup* (make-array '(256 256 256)) :initial-element nil)
;with whatever array optimization stuff... i believe initial-
element is the right thing
pseudocode:
(defun RGB->HSV ()
(get the rgb values)
(let ((hsv (aref *hsv-lookup* rgb-values-go-here)))
(if hsv
hsv
(otherwise we create the hsv instance and set it in the array at
the rgb values and stuff), and return it)))
Just iterating through it would be same speed as your original... but
how often do you use every color available in a .jpeg (not bloody
often).
So, I guess what I'm saying is that if you are just benchmarking
iterating through 256 256 256,
Your solution is probably as fast (perhaps optimal) as you will get,
but you might want to do something kind of in-between if you expect to
reuse colors.
anyway, hth...
On Mar 1, 3:49 pm, ··················@gmail.com wrote:
> On Mar 1, 2:37 pm, ····@stablecross.com (Bob Felts) wrote:
>
>
>
> > Suppose I have a "color" class in a graphics package that supports
> > various color formats, e.g. 32-bit colors (8 bits of red, green, blue,
> > and alpha), 16-bit colors (e.g 5 bits red, 6 bits green, 5 bits blue),
> > HSV, and so on.
>
> > Obviously, I want to be able to convert between the various types. A
> > first cut would be to define something like:
>
> > (defgeneric convert-color (old-color new-type)
> > ...)
>
> > so one might write:
>
> > (let ((hsv = convert-color(some-color 'color-hsv)))
> > ...
>
> > convert-color would make an instance of new-type, fill in the slots, and
> > return the instance.
>
> > The problem with this is that it can be very, very slow since color
> > conversion always creates a new instance. Code I wrote two years ago to
> > check RGB888 -> HSV conversion for all possible RGB values, without
> > using classes, took about 30 seconds to run on my laptop. The
> > class-based code using the above technique took over 10 times longer.
>
> > So, take #2. Change the color conversion routines to be:
>
> > (defgeneric convert-color (old-color new-color)
> > ...)
>
> > convert-color then does setf's on the slots of new-color.
>
> > With this implementation, the code to test RGB888->HSV conversion takes
> > 30 seconds, since I only need to create one instance of an HSV and
> > converted RGB color, instead of 2^24 instances.
>
> > But somehow the paradigm of this type of function side effect is too
> > "C-ish" and just doesn't feel "Lisp-ish".
>
> > Any other techniques I might consider?
>
> You don't end up with all of your colors being the last color that you
> converted?
>
> I'm a little confused how this is supposed to work. Are we interested
> in *actually* converting a bunch of colors, or converting it, using it
> and throwing it away?
>
> If you are going to use the same color over and over again,
> (As in an actual application of converting one thing to another rather
> than a benchmark),
> you could do some memoization (ex. with a 3D array).
>
> ex.:
> (setf *hsv-lookup* (make-array '(256 256 256)) :initial-element nil)
> ;with whatever array optimization stuff... i believe initial-
> element is the right thing
>
> pseudocode:
> (defun RGB->HSV ()
> (get the rgb values)
> (let ((hsv (aref *hsv-lookup* rgb-values-go-here)))
> (if hsv
> hsv
> (otherwise we create the hsv instance and set it in the array at
> the rgb values and stuff), and return it)))
>
> Just iterating through it would be same speed as your original... but
> how often do you use every color available in a .jpeg (not bloody
> often).
>
> So, I guess what I'm saying is that if you are just benchmarking
> iterating through 256 256 256,
> Your solution is probably as fast (perhaps optimal) as you will get,
> but you might want to do something kind of in-between if you expect to
> reuse colors.
>
> anyway, hth...
(defun RGB->HSV (RGB)
(get the rgb values)
(let ((hsv (aref *hsv-lookup* rgb-values-go-here)))
(if hsv
hsv
(otherwise we create the hsv instance and set it in the array at
the rgb values and stuff), and return it)))
in before i get the 'your pseudocode doesn't run!' replies
<··················@gmail.com> wrote:
> On Mar 1, 3:49 pm, ··················@gmail.com wrote:
> > On Mar 1, 2:37 pm, ····@stablecross.com (Bob Felts) wrote:
> >
> >
> >
> > > Suppose I have a "color" class in a graphics package that supports
> > > various color formats, e.g. 32-bit colors (8 bits of red, green, blue,
> > > and alpha), 16-bit colors (e.g 5 bits red, 6 bits green, 5 bits blue),
> > > HSV, and so on.
> >
> > > Obviously, I want to be able to convert between the various types. A
> > > first cut would be to define something like:
> >
> > > (defgeneric convert-color (old-color new-type)
> > > ...)
> >
> > > so one might write:
> >
> > > (let ((hsv = convert-color(some-color 'color-hsv)))
> > > ...
> >
> > > convert-color would make an instance of new-type, fill in the slots, and
> > > return the instance.
> >
> > > The problem with this is that it can be very, very slow since color
> > > conversion always creates a new instance. Code I wrote two years ago to
> > > check RGB888 -> HSV conversion for all possible RGB values, without
> > > using classes, took about 30 seconds to run on my laptop. The
> > > class-based code using the above technique took over 10 times longer.
> >
> > > So, take #2. Change the color conversion routines to be:
> >
> > > (defgeneric convert-color (old-color new-color)
> > > ...)
> >
> > > convert-color then does setf's on the slots of new-color.
> >
> > > With this implementation, the code to test RGB888->HSV conversion takes
> > > 30 seconds, since I only need to create one instance of an HSV and
> > > converted RGB color, instead of 2^24 instances.
> >
> > > But somehow the paradigm of this type of function side effect is too
> > > "C-ish" and just doesn't feel "Lisp-ish".
> >
> > > Any other techniques I might consider?
> >
> > You don't end up with all of your colors being the last color that you
> > converted?
No. In one case, 2^24 RGB triplets are being converted to their HSV
equivalents, then back to RGB to ensure that the conversion is working
correctly. But there will be a lot of other instances where I have to
convert from one color representation to another.
> >
> > I'm a little confused how this is supposed to work. Are we interested
> > in *actually* converting a bunch of colors, or converting it, using it
> > and throwing it away?
Typically converting, using, and throwing away.
> >
> > If you are going to use the same color over and over again,
> > (As in an actual application of converting one thing to another rather
> > than a benchmark),
> > you could do some memoization (ex. with a 3D array).
> >
Memoization is too expensive in terms of memory in this instance.
I was wondering if someone was going to perhaps metion setf'able
functions as a more Lisp-like way of setting the value of the converted
color. I may try to figure that bit out, anyway.
>[...]
>
> in before i get the 'your pseudocode doesn't run!' replies
I wouldn't do that. I'm grateful for the time folks are taking to try
to help.
Bob Felts wrote:
> Suppose I have a "color" class in a graphics package that supports
> various color formats, e.g. 32-bit colors (8 bits of red, green, blue,
> and alpha), 16-bit colors (e.g 5 bits red, 6 bits green, 5 bits blue),
> HSV, and so on.
>
> Obviously, I want to be able to convert between the various types. A
> first cut would be to define something like:
...
What do ch-image or imago do?
> convert-color would make an instance of new-type, fill in the slots, and
> return the instance.
>
> The problem with this is that it can be very, very slow since color
> conversion always creates a new instance. Code I wrote two years ago to
> check RGB888 -> HSV conversion for all possible RGB values, without
> using classes, took about 30 seconds to run on my laptop. The
> class-based code using the above technique took over 10 times longer.
>
> So, take #2. Change the color conversion routines to be:
>
> (defgeneric convert-color (old-color new-color)
> ...)
>
> convert-color then does setf's on the slots of new-color.
>
> With this implementation, the code to test RGB888->HSV conversion takes
> 30 seconds, since I only need to create one instance of an HSV and
> converted RGB color, instead of 2^24 instances.
>
> But somehow the paradigm of this type of function side effect is too
> "C-ish" and just doesn't feel "Lisp-ish".
>
> Any other techniques I might consider?
I would have two sets of function
(convert-color old-color new-color) ; destructively modifies new-color
(convert-color old-color 'new-type) ; returns an equivalent color of
new-type
The second function simply wraps the first, something like
;; warning: untested pseudocode; written in email editor. YMMV.
(defmethod convert-color (old-color (eql 'hsv))
(let ((tmp (make-instance 'hsv)))
(convert-color old-color tmp)
tmp))
Then you have efficient in-place modification (e.g. for marching
through an array) and a more functional interface when speed isn't so
critical.
For absolute speed (i.e. with poor CLOS implementations), you may need
to start with raw routines (e.g. convert-rgb-to-hsv) and wrap them in
CLOS calls.
Just a few random thoughts,
Daniel
P.S. In addition to representation, sometimes you want pixels packed
RGBRGB and other times you want separate color planes RRR...GGG...BBB...
On Mar 1, 8:37 pm, ····@stablecross.com (Bob Felts) wrote:
> Suppose I have a "color" class in a graphics package that supports
> various color formats, e.g. 32-bit colors (8 bits of red, green, blue,
> and alpha), 16-bit colors (e.g 5 bits red, 6 bits green, 5 bits blue),
> HSV, and so on.
>
> Obviously, I want to be able to convert between the various types. A
> first cut would be to define something like:
[...]
> Any other techniques I might consider?
The good thing about CL is that you can postpone decisions about
representations for quite a while. So, instead of going off some
optimization tangent, first let's have a look how that goes.
Explanations come in #||# comments. (Caveat lector: I know little
about colors, so the algorithms I used might be wrong.)
Code follows.
#|| A color is a color is a color. No idea yet how to represent it. ||
#
(defclass color ()
())
#|| We know the operations we want to support, and we will mostly work
with all color parameters at once. We have access to them in all
representations, so we are not forced to create throw-away
representations just to query them. ||#
;;; The COLOR Protocol
;; * For all COLORs, primary methods must be implemented on these
;; functions.
(defgeneric color/hsv (color)
(:documentation
"Returns hue (in range [0,6]), saturation, and value of COLOR as
three values, in this order.
For class COLOR, the standard implementation calls COLOR/RGB."))
(defgeneric color/rgb (color)
(:documentation
"Returns red, gree, and blue portions of COLOR as three values in
range [0,1], in this order.
For class COLOR, the standard implementation calls COLOR/HSV."))
#|| Not sure yet whether we need to allocate fresh instances, let's
keep a loop hole for optimizations open: ||#
(defgeneric color-convert (repr-type color)
(:documentation
"Returns color COLOR, but represented as class REPR-TYPE.
It is unspecified whether the returned instance is freshly
allocated."))
#|| We implement RGB<->HSV conversion. These functions need thorough
testing. We don't have to know anything about the concrete
representation of colors to implement them. ||#
;;; COLOR Protocol (Default Implementations)
;; Mutually recursive default implementations, implementors must
;; ensure there is a ground case.
(defconstant +undefined+ 'undefined)
;; From "The HSV-RGB Transform Pair", Alvy Ray Smith,
;; <http://www.alvyray.com/Papers/hsv2rgb.htm>
(defmethod color/hsv ((color color))
(multiple-value-bind (r g b) (color/rgb color)
(let ((x (min r g b))
(v (max r g b)))
(when (= x v)
(return-from color/hsv (values +undefined+ 0 v)))
(let ((f (cond ((= r x) (- g b))
((= g x) (- b r))
(t
(- r g))))
(i (cond ((= r x) 3)
((= g x) 5)
(t
1))))
(values (- i (/ f (- v x)))
(/ (- v x) v)
v)))))
(defmethod color/rgb ((color color))
(multiple-value-bind (h s v) (color/hsv color)
(when (eql +undefined+ h)
(return-from color/rgb (values v v v)))
(let* ((i (floor h))
(f (if (evenp i)
(- 1 (- h i))
(- h i)))
(m (* v (- 1 s)))
(n (* v (- 1 (* s f)))))
(ecase i
((0 6) (values v n m))
(1 (values n v m))
(2 (values m v n))
(3 (values m n v))
(4 (values n m v))
(5 (values v m n))))))
#|| For convenience, we want to get at one color parameter at a time.
Still haven't chosen a concrete representation of colors. ||#
;; Base-Level Functions
;; * For representations which are not subclasses of COLOR, primary
;; methods must be implemented.
;;
;; * For user-defined subclasses of COLOR, more specific primary
;; methods may be implemented, the standard ones call COLOR/HSV and
;; COLOR/RGB, respectively.
(defgeneric hsv-h (color)
(:method ((color color))
(nth-value 0 (color/hsv color))))
(defgeneric hsv-s (color)
(:method ((color color))
(nth-value 1 (color/hsv color))))
(defgeneric hsv-v (color)
(:method ((color color))
(nth-value 2 (color/hsv color))))
(defgeneric rgb-r (color)
(:method ((color color))
(nth-value 0 (color/rgb color))))
(defgeneric rgb-g (color)
(:method ((color color))
(nth-value 1 (color/rgb color))))
(defgeneric rgb-b (color)
(:method ((color color))
(nth-value 2 (color/rgb color))))
#|| Time to get serious: we want to store HSV-style colors and RGB-
style colors. ||#
;;; Concrete Color Representations
(defclass color/hsv (color)
((%hue :reader hsv-h :initarg :h)
(%saturation :reader hsv-s :initarg :s)
(%value :reader hsv-v :initarg :v)))
(defclass color/rgb (color)
((%red :reader rgb-r :initarg :r)
(%green :reader rgb-g :initarg :g)
(%blue :reader rgb-b :initarg :b)))
;;; Printing COLOR instances
(defmethod print-object ((color color/rgb) stream)
(print-unreadable-object (color stream :type t)
(with-accessors ((r rgb-r)
(g rgb-g)
(b rgb-b)) color
(format stream "R:~A G:~A B:~A" r g b))))
(defmethod print-object ((color color/hsv) stream)
(print-unreadable-object (color stream :type t)
(with-accessors ((h hsv-h)
(s hsv-s)
(v hsv-v)) color
(format stream "H:~A S:~A V:~A" h s v))))
#|| The conversion functions are just thin wrappers around what we
have so far. Better to test the real work horses (COLOR/...) than
this. ||#
;;; Color Conversions
;; (these could be generated, thanks to class/function name spaces)
(defmethod color-convert ((repr-type (eql 'color/hsv)) (color color))
(multiple-value-bind (h s v) (color/hsv color)
(make-instance 'color/hsv :h h :s s :v v)))
(defmethod color-convert ((repr-type (eql 'color/rgb)) (color color))
(multiple-value-bind (r g b) (color/rgb color)
(make-instance 'color/rgb :r r :g g :b b)))
;;; Ground Cases
(defmethod color/hsv ((color color/hsv))
(values (hsv-h color) (hsv-s color) (hsv-v color)))
(defmethod color/rgb ((color color/rgb))
(values (rgb-r color) (rgb-g color) (rgb-b color)))
#|| Obviously, we want to do as little work as possible. Here's a
generic optimization which returns the color if it's of the right
representation already. (More interesting ones like caching could
also go here.) ||#
;;; Optimization
(defmethod color-convert :around (repr-type (color color))
;; Only convert if it's not the right representation already
(if (eql repr-type (type-of color))
color
(call-next-method)))
#|| Done. Now let's add another representation to see how much work
that is. ||#
;;; Example Extension: RGB888
(defclass color/rgb888 (color)
((%red :reader rgb888-r :initarg :r :type (unsigned-byte 8))
(%green :reader rgb888-g :initarg :g :type (unsigned-byte 8))
(%blue :reader rgb888-b :initarg :b :type (unsigned-byte 8))))
#|| No need to redo the HSV conversion work, unless profiling show
this is the bottleneck. COLOR/RGB is reused for any color
representation, but no throw-away instances are created. ||#
(defmethod color/hsv ((color color/rgb888))
(call-next-method))
#|| We pick the easiest way to connect to the rest of the
functionality. ||#
(defmethod color/rgb ((color color/rgb888))
(with-accessors ((r rgb888-r)
(g rgb888-g)
(b rgb888-b)) color
(values (/ r 255.0) (/ g 255.0) (/ b 255.0))))
#|| The rest is not strictly needed but nice to have: ||#
(defgeneric color/rgb888 (color)
(:documentation
"Returns red, gree, and blue portions of COLOR as three integer
values in range [0,255], in this order.
For class COLOR, the standard implementation calls COLOR/RGB.")
(:method ((color color))
(multiple-value-bind (r g b) (color/rgb color)
(values (truncate (* r 255))
(truncate (* g 255))
(truncate (* b 255)))))
(:method ((color color/rgb888))
(values (rgb888-r color) (rgb888-g color) (rgb888-b color))))
(defmethod print-object ((color color/rgb888) stream)
(print-unreadable-object (color stream :type t)
(with-accessors ((r rgb888-r)
(g rgb888-g)
(b rgb888-b)) color
(format stream "R:~A G:~A B:~A" r g b))))
(defmethod color-convert ((repr-type (eql 'color/rgb888)) (color
color))
(multiple-value-bind (r8 g8 b8) (color/rgb888 color)
(make-instance 'color/rgb888 :r r8 :g g8 :b b8)))
(defmethod rgb888-r ((color color))
(nth-value 0 (color/rgb888 color)))
(defmethod rgb888-g ((color color))
(nth-value 1 (color/rgb888 color)))
(defmethod rgb888-b ((color color))
(nth-value 2 (color/rgb888 color)))
#|| Some naive benchmarking:
(defun test ()
(dotimes (r 255)
(dotimes (g 255)
(dotimes (b 255)
(color/hsv (make-instance 'color/rgb888 :r r :g g :b b))))))
COLORS> (time (test))
Evaluation took:
12.021 seconds of real time
11.929973 seconds of total run time (11.675793 user, 0.254180
system)
[ Run times consist of 1.972 seconds GC time, and 9.958 seconds non-
GC time. ]
99.24% CPU
25,981,233,772 processor cycles
2,255,062,136 bytes consed
NIL
||#
Bob Felts wrote:
> Suppose I have a "color" class in a graphics package that supports
> various color formats, e.g. 32-bit colors (8 bits of red, green, blue,
> and alpha), 16-bit colors (e.g 5 bits red, 6 bits green, 5 bits blue),
> HSV, and so on.
>
> Obviously, I want to be able to convert between the various types. A
> first cut would be to define something like:
>
> (defgeneric convert-color (old-color new-type)
> ...)
>
> so one might write:
>
> (let ((hsv = convert-color(some-color 'color-hsv)))
> ...
>
> convert-color would make an instance of new-type, fill in the slots, and
> return the instance.
>
> The problem with this is that it can be very, very slow since color
> conversion always creates a new instance. Code I wrote two years ago to
> check RGB888 -> HSV conversion for all possible RGB values, without
> using classes, took about 30 seconds to run on my laptop. The
> class-based code using the above technique took over 10 times longer.
>
> So, take #2. Change the color conversion routines to be:
>
> (defgeneric convert-color (old-color new-color)
> ...)
>
> convert-color then does setf's on the slots of new-color.
>
> With this implementation, the code to test RGB888->HSV conversion takes
> 30 seconds, since I only need to create one instance of an HSV and
> converted RGB color, instead of 2^24 instances.
>
> But somehow the paradigm of this type of function side effect is too
> "C-ish" and just doesn't feel "Lisp-ish".
>
> Any other techniques I might consider?
+ Measure the overall effect of this in the big picture: Does this
overhead really matter? Maybe it gets lost in the noise, and you
shouldn't really worry about it.
+ Use defstruct instead of defclass.
+ Use lazy evaluation - only create the new instances when absolutely
needed (depends on your concrete needs).
+ Use an object pool. (Google for it.)
+ Depending on your needs, you could use change-class (see change-class
and update-instance-for-different-class in the HyperSpec).
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza <··@p-cos.net> wrote:
> Bob Felts wrote:
> > Suppose I have a "color" class in a graphics package that supports
> > various color formats, e.g. 32-bit colors (8 bits of red, green, blue,
> > and alpha), 16-bit colors (e.g 5 bits red, 6 bits green, 5 bits blue),
> > HSV, and so on.
> >
[...]
> >
> > But somehow the paradigm of this type of function side effect is too
> > "C-ish" and just doesn't feel "Lisp-ish".
> >
> > Any other techniques I might consider?
>
> + Measure the overall effect of this in the big picture: Does this
> overhead really matter? Maybe it gets lost in the noise, and you
> shouldn't really worry about it.
>
This is as much a learning exercise for me in learning good Lisp style
as it is in optimizing performance. I'm looking to see if I'm missing
anything in my Lisp-bag-o-tricks.
> + Use defstruct instead of defclass.
>
But I want the power that multimethods gives me, which I lose with
structures. Besides, even if I switch to a structure, I still have the
paradigm of
(convert... input-structure output-structure)
where output-structure is modified by the function. That seems wrong to
me. Maybe I need to explore defsetf.
[...]
> + Depending on your needs, you could use change-class (see change-class
> and update-instance-for-different-class in the HyperSpec).
>
Never heard of those before. Thanks, I'll look them up.
On Mar 1, 4:20 pm, ····@stablecross.com (Bob Felts) wrote:
[...]
> But I want the power that multimethods gives me, which I lose with
> structures.
With structs, you lose multiple *inheritance*, not multiple
*dispatch*. Multiple dispatch works with any Lisp classes, whether
they're standard classes, structure classes or built-in classes.
(defmethod something-mathematical ((x integer) (y double-float))
...)
is also perfectly legit.
Cheers,
Pillsy
Pillsy wrote:
> (defmethod something-mathematical ((x integer) (y double-float))
> ...)
>
> is also perfectly legit.
Check again... Param specializers are a symbol (naming a class), a
class, or an eql form. The numeric types are not necessarily classes
(some implementations support this, but its not required). IIRC,
Clisp does not support numeric specializers.
- Daniel
P.S. This is one of the things which should have been fixed in the
past 10 years...
D Herring <········@at.tentpost.dot.com> wrote:
+---------------
| Pillsy wrote:
| > (defmethod something-mathematical ((x integer) (y double-float))
| > ...)
| > is also perfectly legit.
|
| Check again... Param specializers are a symbol (naming a class), a
| class, or an eql form. The numeric types are not necessarily classes
| (some implementations support this, but its not required).
+---------------
Hmmm... I think you're somewhat less than half right here. True, the
CLHS does not define a System Class for DOUBLE-FLOAT per se [or any
of the other various precisions of floats], but it *does* for FLOAT:
http://www.lispworks.com/documentation/HyperSpec/Body/t_float.htm
System Class FLOAT
Class Precedence List:
float, real, number, t
and, of course, also for INTEGER:
http://www.lispworks.com/documentation/HyperSpec/Body/t_intege.htm
System Class INTEGER
Class Precedence List:
integer, rational, real, number, t
In fact, AFAICT a conforming CL *must* provide a System Class for -- and
thus be able to dispatch on -- at least INTEGER, RATIO, FLOAT, COMPLEX
and all of their their superclasses (e.g., RATIONAL, REAL, NUMBER).
The reason [again, AFAICT] that a conforming CL need not provide
System Classes for the ${PRECISION}-FLOAT subtypes of FLOAT is that
the ANSI Standard permits them to be degenerate, see:
http://www.lispworks.com/documentation/HyperSpec/Body/t_short_.htm
Type SHORT-FLOAT, SINGLE-FLOAT, DOUBLE-FLOAT, LONG-FLOAT
Supertypes:
short-float: short-float, float, real, number, t
single-float: single-float, float, real, number, t
double-float: double-float, float, real, number, t
long-float: long-float, float, real, number, t
...
There can be fewer than four internal representations for floats.
...
- If there is only one, it is the type single-float. In this
representation, an object is simultaneously of types
single-float, double-float, short-float, and long-float.
...
Given that, the standard *can't* mandate that (say) SINGLE-FLOAT and
DOUBLE-FLOAT dispatch differently, since they might be identical types.
+---------------
| IIRC, Clisp does not support numeric specializers.
+---------------
Again, only half-correct. Older CLISPs did not allow specializers
of the ${PRECISION}-FLOAT subtypes of FLOAT [newer versions may be
more liberal, I dunno], but certainly *did* allow numeric types
which are system classes:
$ clisp -q
[1]> (defmethod types ((x integer) (y float))
(list (list x 'is (type-of x)) (list y 'is (type-of y))))
#<STANDARD-METHOD (#<BUILT-IN-CLASS INTEGER> #<BUILT-IN-CLASS FLOAT>)>
[2]> (types 3 4.0)
((3 IS FIXNUM) (4.0 IS SINGLE-FLOAT))
[3]> (types 3 4d0)
((3 IS FIXNUM) (4.0d0 IS DOUBLE-FLOAT))
[4]>
Other CLs also do allow some degree of ${PRECISION}-FLOAT specializers,
e.g., CMUCL-19e on x86 permits specializing on SINGLE-FLOAT & DOUBLE-FLOAT
[and provides System Classes for those], but *not* on either SHORT-FLOAT
or LONG-FLOAT [which are degenerate with SINGLE-FLOAT & DOUBLE-FLOAT,
respectively].
+---------------
| P.S. This is one of the things which should have been fixed in the
| past 10 years...
+---------------
See above for why it's not "broken". (IMHO, YMMV.)
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> D Herring <········@at.tentpost.dot.com> wrote:
> +---------------
> | Pillsy wrote:
> | > (defmethod something-mathematical ((x integer) (y double-float))
> | > ...)
> | > is also perfectly legit.
> |
> | Check again... Param specializers are a symbol (naming a class), a
> | class, or an eql form. The numeric types are not necessarily classes
> | (some implementations support this, but its not required).
> +---------------
>
> Hmmm... I think you're somewhat less than half right here. True, the
> CLHS does not define a System Class for DOUBLE-FLOAT per se [or any
> of the other various precisions of floats], but it *does* for FLOAT:
...
> and, of course, also for INTEGER:
...
> In fact, AFAICT a conforming CL *must* provide a System Class for -- and
> thus be able to dispatch on -- at least INTEGER, RATIO, FLOAT, COMPLEX
> and all of their their superclasses (e.g., RATIONAL, REAL, NUMBER).
>
> The reason [again, AFAICT] that a conforming CL need not provide
> System Classes for the ${PRECISION}-FLOAT subtypes of FLOAT is that
> the ANSI Standard permits them to be degenerate, see:
...
> Given that, the standard *can't* mandate that (say) SINGLE-FLOAT and
> DOUBLE-FLOAT dispatch differently, since they might be identical types.
>
> +---------------
> | IIRC, Clisp does not support numeric specializers.
> +---------------
>
> Again, only half-correct. Older CLISPs did not allow specializers
> of the ${PRECISION}-FLOAT subtypes of FLOAT [newer versions may be
> more liberal, I dunno], but certainly *did* allow numeric types
> which are system classes:
...
> Other CLs also do allow some degree of ${PRECISION}-FLOAT specializers,
> e.g., CMUCL-19e on x86 permits specializing on SINGLE-FLOAT & DOUBLE-FLOAT
> [and provides System Classes for those], but *not* on either SHORT-FLOAT
> or LONG-FLOAT [which are degenerate with SINGLE-FLOAT & DOUBLE-FLOAT,
> respectively].
>
> +---------------
> | P.S. This is one of the things which should have been fixed in the
> | past 10 years...
> +---------------
>
> See above for why it's not "broken". (IMHO, YMMV.)
Good stuff. Thanks for the summary. I had bumped into this with bad
specializers for double-float and fixnum on CLISP, but didn't dig
beyond the CLHS sections saying they weren't required.
Why couldn't they have simply treated specializations on aliases the
same as repeated methods with the same specializations? (i.e. last
defmethod wins)
IMHO allowing double-float to alias with single-float is no longer
justifiable (post IEEE-754 world). If it ever was, I wish the
standard had said that a conforming impl was free to not provide
double-float rather than alias it down to single-float.
Floating-point algorithms need certain guarantees of range and
precision... the standard does not provide the necessary information
(merely a table of recommended minimum sizes). And why was
short/single-float *or* single/double-float a good idea?
Thanks for the insight,
Daniel
D Herring <········@at.tentpost.dot.com> wrote:
+---------------
| Rob Warnock wrote:
| > In fact, AFAICT a conforming CL *must* provide a System Class for -- and
| > thus be able to dispatch on -- at least INTEGER, RATIO, FLOAT, COMPLEX
| > and all of their their superclasses (e.g., RATIONAL, REAL, NUMBER).
| >
| > The reason [again, AFAICT] that a conforming CL need not provide
| > System Classes for the ${PRECISION}-FLOAT subtypes of FLOAT is that
| > the ANSI Standard permits them to be degenerate, see:
| ...
| > Given that, the standard *can't* mandate that (say) SINGLE-FLOAT and
| > DOUBLE-FLOAT dispatch differently, since they might be identical types.
...
| Why couldn't they have simply treated specializations on aliases the
| same as repeated methods with the same specializations? (i.e. last
| defmethod wins)
+---------------
Individual implementations *might* choose to do so,
say on SHORT-FLOAT and SINGLE-FLOAT, but only if
(EQL (FIND-CLASS 'SHORT-FLOAT) (FIND-CLASS 'SINGLE-FLOAT))
returned T. [Think about why that must be the case.]
But the CLHS doesn't even require that the types
{SHORT,SINGLE,DOUBLE,LONG}-FLOAT *be* classes, so
it certainly doesn't require the kind of aliasing
you request.
+---------------
| IMHO allowing double-float to alias with single-float is no longer
| justifiable (post IEEE-754 world). If it ever was, I wish the
| standard had said that a conforming impl was free to not provide
| double-float rather than alias it down to single-float.
+---------------
CL was not defined in a "post IEEE-754 world". While the X3J13
Commmittee was certainly quite aware of IEEE-754 [e.g., see CLHS
"Issue IEEE-ATAN-BRANCH-CUT" and its reference to consultations
with Kahan], there were still numerous other floating-point formats
quite active at the time [e.g., DEC PDP-10, DEC VAX, IBM 360/370,
CDC (?), Motorola 68k, etc.]. They were obligated to provide a spec
that accommodated *all* of them as best as possible. That it is not
worse than it is is almost a miracle! ;-}
+---------------
| Floating-point algorithms need certain guarantees of range and
| precision... the standard does not provide the necessary information
| (merely a table of recommended minimum sizes). And why was
| short/single-float *or* single/double-float a good idea?
+---------------
See above. I wasn't there but I'd suspect that there would have
been an irreconcilable split had both not been allowed. Also,
see Section 3.4 "Numerical Facilities" in this classic:
http://dreamsongs.com/NewFiles/Hopl2.pdf
"The Evolution of Lisp", Guy Steele & Peter Gabriel, HOPL 1992
which contains many details about the context of the design of
the arithmetic [including floating point] in CL [e.g., the four
FLOAT precisions were driven by the needs of the S-1 project,
the (ATANH -2) quick test, other amusing snippets].
But perhaps one of those who were there might want to give a (short!)
recap of the technical and/or political issues of the day... ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Bob Felts wrote:
> Pascal Costanza <··@p-cos.net> wrote:
>> + Use defstruct instead of defclass.
>>
>
> But I want the power that multimethods gives me, which I lose with
> structures.
No, you don't. You can specialize methods on structure types.
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Juliusz Chroboczek wrote:
>> + Use an object pool. (Google for it.)
>
> Intern your colour objects. Additional benefit -- you can test colour
> equality using eq.
>
> Juliusz
what if he is iterating over possible colors? Then there is
approximately zero reason to allocate new structure on each iteration.
Have you people ever actually programmed a computer?
hth,k
Kenneth Tilton <·········@gmail.com> writes:
> Juliusz Chroboczek wrote:
>>> + Use an object pool. (Google for it.)
>> Intern your colour objects. Additional benefit -- you can test
>> colour
>> equality using eq.
>> Juliusz
>
> what if he is iterating over possible colors? Then there is
> approximately zero reason to allocate new structure on each iteration.
>
> Have you people ever actually programmed a computer?
So you never used an object pool?
Have you otherwise actually programmed a computer?
--
__Pascal Bourguignon__
Pascal J. Bourguignon wrote:
> Kenneth Tilton <·········@gmail.com> writes:
>> Juliusz Chroboczek wrote:
>>>> + Use an object pool. (Google for it.)
>>> Intern your colour objects. Additional benefit -- you can test
>>> colour
>>> equality using eq.
>>>
>> what if he is iterating over possible colors? Then there is
>> approximately zero reason to allocate new structure on each iteration.
>
> So you never used an object pool?
?!?
I parsed this as
1) Use object pool
2) Intern objects
3) Use object pool or single variable
4) Use object pool
- Daniel
D Herring <········@at.tentpost.dot.com> writes:
> Pascal J. Bourguignon wrote:
>> Kenneth Tilton <·········@gmail.com> writes:
>>> Juliusz Chroboczek wrote:
>>>>> + Use an object pool. (Google for it.)
>>>> Intern your colour objects. Additional benefit -- you can test
>>>> colour
>>>> equality using eq.
>>>>
>>> what if he is iterating over possible colors? Then there is
>>> approximately zero reason to allocate new structure on each iteration.
>> So you never used an object pool?
>
> ?!?
>
> I parsed this as
> 1) Use object pool
> 2) Intern objects
> 3) Use object pool or single variable
> 4) Use object pool
Interning objects and object pools are not contradictory.
When you have an objet pool, you can unify with existing objects, so
you can use EQ and avoid duplicates, in addition to the other resource
management features of object pools.
--
__Pascal Bourguignon__
Pascal J. Bourguignon <···@informatimago.com> wrote:
> Kenneth Tilton <·········@gmail.com> writes:
>
> > Juliusz Chroboczek wrote:
> >>> + Use an object pool. (Google for it.)
> >> Intern your colour objects. Additional benefit -- you can test
> >> colour
> >> equality using eq.
> >> Juliusz
> >
> > what if he is iterating over possible colors? Then there is
> > approximately zero reason to allocate new structure on each iteration.
> >
> > Have you people ever actually programmed a computer?
>
> So you never used an object pool?
> Have you otherwise actually programmed a computer?
Yes to both in my case.
For this particular problem, the conversion overhead really isn't much
more than what it would take to do a lookup in an object pool. And
since the possible space of colors can be >= 2^32, it's just as easy to
do the conversion as it is to manage a pool.
It really comes down to this:
1) The overhead of allocating an object instance for each conversion is
too high.
2) => the conversion functions work on previously allocated things,
3) => the conversion function ends up changing an input argument.
Step 3 doesn't seem "Lisp-like" to me. Perhaps I'm just being overly
fussy. Maybe I'll explore playing with defsetf(), which I haven't used
yet. But I really do need the flexibility that multi-methods and
inheritance provides.
Bob Felts wrote:
> Any other techniques I might consider?
If you use the colors for representing images, use a fast native library,
like ImageMagick and then use different image types, instead of pixel
types.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> wrote:
> Bob Felts wrote:
>
> > Any other techniques I might consider?
>
> If you use the colors for representing images, use a fast native library,
> like ImageMagick and then use different image types, instead of pixel
> types.
I want this to be a pure Lisp solution, since it's as much a learning
exercise as it is a lab bench (I'm duplicating some functionality in an
embedded system so that I can do things on my laptop before porting to
the embedded system in C).
····@stablecross.com (Bob Felts) writes:
> Obviously, I want to be able to convert between the various types.
This is not obvious to me. Why not keep the color in some canonical
representation, and just have methods to convert to the needed
representation as needed?
Something like (assuming rgba as the canonical representation)
(defmethod color-values ((color color) (type (eql :rgba)))
(values (slot-value color 'red)
(slot-value color 'green)
(slot-value color 'blue)
(slot-value color 'alpha)))
(defmethod color-values ((color color) (type (eql :hsv)))
(values <whatever the values of a hsv representation looks like>))
etc.
If the conversion from the canonical representation is too heavy to do
every time, you can use the color object as a cache, just add extra
slots for the alternative representations, and do the conversion on
first access.
This way, you only ever have one object per color. I don't do much
graphics programming, so there may be downsides I haven't seen, but
this was the approach I considered obvious. Have you considered and
discarded something like this?
...Peder...
--
I wish a new life awaited _me_ in some off-world colony.
On Tue, 03 Mar 2009 20:08:36 +0100, ·····@news.klingenberg.no (Peder
O. Klingenberg) wrote:
>····@stablecross.com (Bob Felts) writes:
>
>> Obviously, I want to be able to convert between the various types.
>
>This is not obvious to me. Why not keep the color in some canonical
>representation, and just have methods to convert to the needed
>representation as needed?
You obviously haven't done much image processing.
There isn't any canon representation of color. Conversion between
color spaces (RGB, CMYK, HSI/HSV, YUV, etc.) is not exact and, in
general, is not reversible. Additionally, there are multiple
conversion equations for any pair of color spaces - for example to
preserve hue at the expense of intensity or vice versa.
You use the representation and conversion equations that best fit your
needs.
George
George Neuner <········@comcast.net> writes:
> You obviously haven't done much image processing.
True.
> There isn't any canon representation of color. Conversion between
> color spaces (RGB, CMYK, HSI/HSV, YUV, etc.) is not exact and, in
> general, is not reversible. Additionally, there are multiple
> conversion equations for any pair of color spaces - for example to
> preserve hue at the expense of intensity or vice versa.
Sounds horrible. But I guess those may be reasons enough to have
different objects for different representations. Thanks for the
explanation.
...Peder...
--
I wish a new life awaited _me_ in some off-world colony.
Peder O. Klingenberg wrote:
> ····@stablecross.com (Bob Felts) writes:
>
>> Obviously, I want to be able to convert between the various types.
>
> This is not obvious to me. Why not keep the color in some canonical
> representation, and just have methods to convert to the needed
> representation as needed?
>
> Something like (assuming rgba as the canonical representation)
>
> (defmethod color-values ((color color) (type (eql :rgba)))
> (values (slot-value color 'red)
> (slot-value color 'green)
> (slot-value color 'blue)
> (slot-value color 'alpha)))
>
> (defmethod color-values ((color color) (type (eql :hsv)))
> (values <whatever the values of a hsv representation looks like>))
>
> etc.
>
> If the conversion from the canonical representation is too heavy to do
> every time, you can use the color object as a cache, just add extra
> slots for the alternative representations, and do the conversion on
> first access.
Or put everything in an alist or plist, to avoid wasting space in case
the additional representations are not needed...
> This way, you only ever have one object per color. I don't do much
> graphics programming, so there may be downsides I haven't seen, but
> this was the approach I considered obvious. Have you considered and
> discarded something like this?
>
> ...Peder...
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/