The responses to my recent post about a randomized COND got me
thinking..
In general, if one has an ordinary COND block with lots of clauses,
we're looking at O(n) comparisons to find the first clause to fire
on.
How could we make a system which allows for optimization of the COND
clauses by placing the most-often fired rules up top? Obviously, there
would be a huge penalty to try and do this at run-time constantly..
but..
My approach would be to have a macro which checks a special variable
(*COND-CHECK*) if it is T, the macro spits out the clauses in the
order they have been given and inserts an expression in the body of
each clause to increment a counter for that clause (in an array,
somewhere). If it is NIL, the macro spits out a COND block with the
clauses re-ordered according to the values in the array.
I guess I'd also need to have an additional argument to my macro which
names the block so that multiple COND's can be profiled / optimized in
this way.
So, one could write their code using this hypothetical macr with *COND-
CHECK* set to T.
Run some test data through it, maybe even 'go live' and after a
fashion, set *COND-CHECK* to NIL and re-load the code. Now the COND
blocks are optimized, and you could compile it up.
Obviously, this technique could only be used for COND blocks where the
order doens't matter. Thoughts?
On Aug 8, 2:19 pm, "Mike G." <···············@gmail.com> wrote:
> How could we make a system which allows for optimization of the COND
> clauses by placing the most-often fired rules up top? Obviously, there
> would be a huge penalty to try and do this at run-time constantly..
> but..
>
You might be interested in the following paper by H�lzle and Ungar:
"Optimizing Dynamically-Dispatched Calls with Run-Time Type
Feedback" (http://www.cs.ucsb.edu/~urs/oocsb/papers/type-
feedback.html)
They do basically the same thing for method dispatch, which you can
think of a TYPECASE. (Which relates back to what Pascal was talking
about regarding specialized versions of COND since there isn't much
you can do about COND in the general case.)
"Mike G." <···············@gmail.com> writes:
> The responses to my recent post about a randomized COND got me
> thinking..
>
> In general, if one has an ordinary COND block with lots of clauses,
> we're looking at O(n) comparisons to find the first clause to fire
> on.
>
> How could we make a system which allows for optimization of the COND
> clauses by placing the most-often fired rules up top? Obviously, there
> would be a huge penalty to try and do this at run-time constantly..
> but..
I can imagine two possibilities:
1. When writing the program, the programmer can figure out which rules
give t (here I mean non-nil) most often, and put them in front. You
can do this with cond now.
2. The probability distribution of the result of the rules is unknown
at the time of writing the program. Yes, one can imagine a smart cond
that would keep track of which rules give t, and try to predict the
results and rearrange the order. However, this would require a
probabilistic model (is the distribution iid? or not? etc) which can
be quite complex (think nonlinear Bayesian filtering), a hassle to
implement and provide very little actual gain unless the test are very
slow.
Best,
Tamas
On Aug 8, 3:09 pm, Tamas Papp <······@gmail.com> wrote:
> I can imagine two possibilities:
>
> 1. When writing the program, the programmer can figure out which rules
> give t (here I mean non-nil) most often, and put them in front. You
> can do this with cond now.
Well, yes. If there are only a few rules the programmer can do all
this in her head.
I don't believe anyone would use a technique like the one I imagine
for such simple cases.
>
> 2. The probability distribution of the result of the rules is unknown
> at the time of writing the program. Yes, one can imagine a smart cond
> that would keep track of which rules give t, and try to predict the
> results and rearrange the order. However, this would require a
> probabilistic model (is the distribution iid? or not? etc) which can
> be quite complex (think nonlinear Bayesian filtering), a hassle to
> implement and provide very little actual gain unless the test are very
> slow.
I don't see why one would necessarily need such complex techniques. It
seems to me that simply counting the number of times the rules fire
would be sufficient. Once enough data has passed through the code, you
flip a switch and re-load the code. The macro now (instead of
generating rule-counting code) re-orders the cond rules and spits out
an optimized block.
Yes, you need a lot of rules (or very time-consuming tests) for this
to become a real win. Surely there are production rule systems where
something like this could help.
"Tamas Papp" <······@gmail.com> wrote:
> 2. The probability distribution of the result of the rules is unknown
> at the time of writing the program. Yes, one can imagine a smart cond
> that would keep track of which rules give t, and try to predict the
> results and rearrange the order. However, this would require a
> probabilistic model (is the distribution iid? or not? etc) which can
> be quite complex (think nonlinear Bayesian filtering), a hassle to
> implement and provide very little actual gain unless the test are very
> slow.
Huh ?
Such techniques were already studied in the context of dynamic optimization
for OO languages ("type feedback" if I recall). You may look here:
http://citeseer.ist.psu.edu/247663.html
Cheers,
Pummelo
Mike G. wrote:
> The responses to my recent post about a randomized COND got me
> thinking..
>
> In general, if one has an ordinary COND block with lots of clauses,
> we're looking at O(n) comparisons to find the first clause to fire
> on.
>
> How could we make a system which allows for optimization of the COND
> clauses by placing the most-often fired rules up top? Obviously, there
> would be a huge penalty to try and do this at run-time constantly..
> but..
>
> My approach would be to have a macro which checks a special variable
> (*COND-CHECK*) if it is T, the macro spits out the clauses in the
> order they have been given and inserts an expression in the body of
> each clause to increment a counter for that clause (in an array,
> somewhere). If it is NIL, the macro spits out a COND block with the
> clauses re-ordered according to the values in the array.
>
> I guess I'd also need to have an additional argument to my macro which
> names the block so that multiple COND's can be profiled / optimized in
> this way.
>
> So, one could write their code using this hypothetical macr with *COND-
> CHECK* set to T.
> Run some test data through it, maybe even 'go live' and after a
> fashion, set *COND-CHECK* to NIL and re-load the code. Now the COND
> blocks are optimized, and you could compile it up.
>
> Obviously, this technique could only be used for COND blocks where the
> order doens't matter. Thoughts?
This last remark is unfortunately very crucial: Since in the general
case you cannot automatically decide whether two predicates trigger on
overlapping sets of values, such optimizations work only on very simple
cases. If the predicates additionally have side effects, then you get an
additional hard nut to crack - and in Lisp, any function may have side
effects.
That's why there are a number of specialized constructs for which such
optimizations are far easier to achieve, like case, typecase and the
method dispatch performed by generic functions, to name just a few.
That's why I also tend to describe the latter as "glorified" cond forms.
The advantage of such specialized constructs is typically indeed "just"
that they are generally more efficient. [1] The disadvantage is that you
always lose some degree of expressiveness: Nothing can be as precise as
a cond form in which an exact sequence of predicate tests is encoded. No
internal machinery is necessary to determine a "good" sequence for such
tests, the human programmer can just specify it. So a cond is indeed the
most general form of dispatch.
This is in fact a testimony of the simplicity and brilliance of this
particular invention of John McCarthy. [2]
Pascal
[1] Although in the case of generic functions, you additionally get the
advantage that otherwise unrelated parts of your code can contribute to
the definition of a generic function. This is in fact the reason why
there is a recurring interest in making predicate dispatch work: It
would give you both the advantage of the generality of a cond form
together with the possibility that otherwise unrelated parts of a
program can contribute to the same dispatch. Unfortunately, because of
the very fact that you generally cannot determine the "interesting"
characteristics of predicates, a most general form of predicate dispatch
is simply not possible.
Jim Newton has presented a paper at this year's European Lisp Workshop
with a very simple idea to make predicate dispatch work nonetheless: He
just makes it part of the metaobject protocol for generic functions to
decide how predicate dispatch is performed in detail. I think this is a
very worthwhile idea to explore further.
[2] I am not joking here. I sincerely think it is amazing what a great
step forward the cond form was in the 1950's.
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Aug 8, 9:18 pm, Pascal Costanza <····@p-cos.net> wrote:
> So a cond is indeed the
> most general form of dispatch.
>
> This is in fact a testimony of the simplicity and brilliance of this
> particular invention of John McCarthy. [2]
[...]
> [2] I am not joking here. I sincerely think it is amazing what a great
> step forward the cond form was in the 1950's.
Tsk-tsk, this in response to a poster whose previous topic was about
trying to turn COND into Fortran's computed GOTO! It was computed
GOTO's kissing cousin, three-way IF, that was COND's primary
competitor! How can you argue with the unbridled power of those two
constructs!
[ I am, of course, joking here. The n-way conditional branch
expression is still shockingly more elegant and powerful than what's
available in most *modern* languages, much less what it had to compete
with. ]
On Aug 8, 2:19 pm, "Mike G." <···············@gmail.com> wrote:
> The responses to my recent post about a randomized COND got me
> thinking..
Here is my solution to this, coded this morning on my train ride to
work.
Not heavily tested, but seems to work fine.
(declaim (special *KOND-CHECK* *KOND-COUNTS*))
(defvar *KOND-CHECK* T)
(defvar *KOND-COUNTS* NIL)
(defmacro kond (name &rest clauses)
"KOND - a self-optimizing COND
(KOND :keyword-name
(test1 body1)
(test2 body2)
...)
The :keyword-name is used as a key into the *KOND-COUNTS* a-list
where it is
paired with an array. This array holds the counts of how many times
each rule
fired.
KOND is controlled by the *KOND-CHECK* special variable. When it is
T, KOND
rewrites the bodies of the clauses, including an expression to
increment the
required array element. When it is NIL, KOND references the arrays
and re-orders
the clauses so that the most commonly used clauses are given first.
Typically, one will run realistic test data through the KOND block,
then set
*KOND-CHECK* to NIL, and re-load/re-compile the Lisp source so that
the KOND
macro optimizes the KOND block.
If :keyword-name is omitted, or if :keyword-name isn't found in the
A-LIST,
and *KOND-CHECK* is NIL, an ordinary COND block is written."
(if (keywordp name)
(let ((foo (assoc name *KOND-COUNTS*))
(num -1))
(if *KOND-CHECK*
(progn
(if (null foo)
(let* ((n -1)
(v (map 'vector #'(lambda (x)
(declare (ignore x))
(incf n)
(cons 0 n))
(make-array (length clauses)))))
(setf *KOND-COUNTS* (nconc *KOND-COUNTS* (list (cons name v)))))
`(let ((ary (cdr (assoc ,name *KOND-COUNTS*))))
,(cons 'cond
(map 'list #'(lambda (cl)
(incf num)
(apply #'list
(first cl)
`(incf (car (elt ary ,num)))
(rest cl)))
clauses)))))
(progn
(if (null foo)
(cons 'cond
(map 'list #'(lambda (x) x) clauses))
(let ((ary (sort (cdr foo) #'(lambda (x y)
(> (car x) (car y))))))
`(cond
,(map 'list #'(lambda (x)
(elt clauses (cdr x)))
ary)))))))
(progn
(format t "ERROR: No name supplied to KOND. Using COND structure.")
(cons 'cond
(map 'list #'(lambda (x) x) (apply #'list name clauses)))))