Hi.
I've been working on a little project, and I was hoping people here
could give me some feedback. I'm especially interested in looking at
other systems with similar goals.
I do a lot of numerical scientific work. It is important that my
programs be efficient. I have found that CMUCL will give me
sufficient numerical efficiency, if I am careful about making
declarations. The system I'm building is a first attempt towards
making it easier and more natural to write efficient programs.
My system is a form of "templating" system, that allows one to
automatically construct a parametrized family of efficient
implementations with as little work as possible. For example, suppose
I need functions to scale arrays of numbers by a constant. In my
current system, I can say:
(def-templated scale-array ((a :array) (s :scalar :tied-to a))
(let* ((length (length a))
(result (make-array length :element-type '(:elt-type a))))
(declare (type fixnum length))
(dotimes (i length)
(setf (aref result i)
(* s (aref a i))))
result))
This says that a is an array parameter, and s is a scalar parameter
that is of the same type as a. Evaluating def-templated creates a
generic function for scale-array, and it also creates a macro,
instantiate-scale-array, with the following macroexpansion:
CL-USER> (macroexpand-1 '(instantiate-scale-array double-float))
(LOCALLY
(DECLARE (OPTIMIZE (SPEED 3) (SAFETY 0) (DEBUG 1)))
(DEFMETHOD SCALE-ARRAY
((A #<BUILT-IN-CLASS KERNEL::SIMPLE-ARRAY-DOUBLE-FLOAT {281B11E5}>)
(S DOUBLE-FLOAT))
(DECLARE (TYPE (SIMPLE-ARRAY DOUBLE-FLOAT (*)) A)
(TYPE DOUBLE-FLOAT S))
(LET* ((LENGTH (LENGTH A))
(RESULT (MAKE-ARRAY LENGTH :ELEMENT-TYPE 'DOUBLE-FLOAT)))
(DECLARE (TYPE FIXNUM LENGTH))
(DOTIMES (I LENGTH) (SETF (AREF RESULT I) (* S (AREF A I))))
RESULT)))
Note that the instantiation includes type declarations for the
defmethod parameters, even though the template didn't include them at
all --- since the types are known at instantation time, these type
declarations can be automatically generated.
The "unspecialized method", (scale-array (a t) (s t)), has additional
behavior. It checks to see if a is of a type it knows how to
specialize on, and if so, automatically instantiates and runs the
specialized method. With this feature, users don't have to explicitly
instantiate the template --- they just call the function, and if the
system can build a useful specialization, it will.
This system is targeting three different efficiency optimizations:
1. Taking advantage of the fact that (at least on some
implementations) numerical arrays are laid out "in place"
2. Avoiding generic arithmetic.
3. Inlining passed-in functions to avoid boxing/unboxing
(not yet implemented, but I think it's possible)
The current system is not pretty code (it's a hacked up mess) and
chock full of cargo-cult macrology (thanks for all the help on my
macro question), but it does work.
A more full-fledged (future) system will let you template over
multiple functions simultaneously (to make efficient "data structures"
such as trees, priority queues, etc.), and will probably generate two
versions of each function --- a long-name version such
scale-array<double-float>, and a generic version that calls the
long-name version. That way one can avoid the dispatching overhead
for inner loop functions as needed, but still keep genericity.
I'm not sure whether using CLOS is a good idea for this. In
particular, for the next version of the system, I'm seriously
considering just using a hash table of implementations and dispatching
myself. The reason for this is that it seems like there is a bit of
mismatch between CL's type system and CMUCL's class system. For
instance, using CLOS, I can't seem to specialize on (simple-array
double-float (*)), instead I have to actually construct such an array
(at instantiation time), get it's class, and specialize on that (see
the expansion above).
Any thoughts and comments are welcome.
Cheers,
rif
From: Wade Humeniuk
Subject: Re: Feedback (thoughts, prior art) wanted on templating system (long)
Date:
Message-ID: <iTJWd.6032$gJ3.1456@clgrps13>
Have you looked at compiler macros?
See DEFINE-COMPILER-MACRO in the Spec.
I suppose if you use compiler macros you can
define a number of straight functions like scale-array
and then define a compiler macro to handle expansion
based on the type of parameters at compile time. I suppose
you would have to give your macro a hint with statments like
(the double-float scale-factor). Perhaps you can then get rid
of any methods or reliance on CLOS.
Also should not the following inline version of scale-array
capture the type information of array and scale and perform the
proper type optimizations and any inherited compiler optimizations?
(declaim (inline scale-array))
(defun scale-array (array scale)
(let* ((length (length array))
(result (make-array length :element-type (array-element-type array))))
(declare (type fixnum length))
(dotimes (i length)
(setf (aref result i)
(* scale (aref array i))))
result))
If the compiler had trouble with optimizing access to result, you
you define scale-array to take a result array, like
(define scale-array (array scale result) ...
and the compiler would then know the type of result from
higher level declarations.
Wade
From: Wade Humeniuk
Subject: Re: Feedback (thoughts, prior art) wanted on templating system (long)
Date:
Message-ID: <U3KWd.6125$gJ3.4621@clgrps13>
Thanks for the feedback. I see what you are saying.
I was familiar with DEFINE-COMPILER-MACRO. It does some of what I
want, but not all.
Both DEFINE-COMPILER-MACRO and your inlining solution require that the
types be apparent at compile time. The inlining solution additionally
implies a willingness to inline arbitrarily large functions, and
nestings thereof. This also involves recompiling all systems that
depend on a library when the underlying library changes.
rif
rif <···@mit.edu> writes:
> I'm not sure whether using CLOS is a good idea for this. In
> particular, for the next version of the system, I'm seriously
> considering just using a hash table of implementations and dispatching
> myself. The reason for this is that it seems like there is a bit of
> mismatch between CL's type system and CMUCL's class system. For
> instance, using CLOS, I can't seem to specialize on (simple-array
> double-float (*)), instead I have to actually construct such an array
> (at instantiation time), get it's class, and specialize on that (see
> the expansion above).
Because of these problems, I have generally chosen to create my own typed
CLOS classes in my PDE toolbox Femlisp, e.g.
* (class-of #m(1.0))
#<STANDARD-CLASS |(STANDARD-MATRIX DOUBLE-FLOAT)| {58AADCED}>
Then, automatic code generation and dispatch can be done for those CLOS
classes.
Nicolas.
Ah, interesting. I see what you're saying.
I can see advantages to your suggestion. Certainly, for matrices,
where you're almost certainly going to need a class to represent,
anyways. The tradeoff is that you have to put a layer of objects
around everything, but that doesn't seem like an enormously large
price to pay.
Thanks for the tip.
Does Femlisp contain stuff pretty similar to what I was suggesting in
my post? I should take a closer look...
Cheers,
rif
rif <···@mit.edu> writes:
> Thanks for the tip.
>
> Does Femlisp contain stuff pretty similar to what I was suggesting in
> my post? I should take a closer look...
>
> Cheers,
>
> rif
I think it does. Especially, you should look in the directory
#p"femlisp:src;matlisp".
Nicolas.
From: Rahul Jain
Subject: Re: Feedback (thoughts, prior art) wanted on templating system (long)
Date:
Message-ID: <87eke2rpb7.fsf@nyct.net>
rif <···@mit.edu> writes:
> My system is a form of "templating" system, that allows one to
> automatically construct a parametrized family of efficient
> implementations with as little work as possible. For example, suppose
> I need functions to scale arrays of numbers by a constant. In my
> current system, I can say:
Have you looked at how all the numerical operators in CMUCL are
implemented? They work exactly how you want your operators to work.
Since you seem to OK with sticking to CMUCL, this might be a perfect
solution for you.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Rahul Jain <·····@nyct.net> writes:
> rif <···@mit.edu> writes:
>
> > My system is a form of "templating" system, that allows one to
> > automatically construct a parametrized family of efficient
> > implementations with as little work as possible. For example, suppose
> > I need functions to scale arrays of numbers by a constant. In my
> > current system, I can say:
>
> Have you looked at how all the numerical operators in CMUCL are
> implemented? They work exactly how you want your operators to work.
> Since you seem to OK with sticking to CMUCL, this might be a perfect
> solution for you.
>
> --
> Rahul Jain
> ·····@nyct.net
> Professional Software Developer, Amateur Quantum Mechanicist
I haven't looked. I've always been a bit scared to look into the guts
of a CL implementation. Perhaps this is the right time. Thanks for
the pointer.
rif
From: Joe Marshall
Subject: Re: Feedback (thoughts, prior art) wanted on templating system (long)
Date:
Message-ID: <acomb0ro.fsf@ccs.neu.edu>
rif <···@mit.edu> writes:
> I've always been a bit scared to look into the guts of a CL
> implementation.
And when you stare persistently into a CL implementation, the CL
implementation also stares into you.