Quote:

> that is a reasonable thing to hope for, but unfortunately, there is no

> substitute for experience and testing. the experience you get varies

> from version to version of each implementation and may be completely

> useless from implementation to implementation. the best you can hope for

> is to understand the major factor for the time and space consumption of a

> function. e.g., the function = (with n > 2 arguments) will return false

> as soon as two neighboring arguments are unequal, which means the running

> time is proportional to n, while the function /= (with n > 2 arguments)

> will return false as soon as one argument is equal to any other argument,

> which means the running time of each test is proportional to n, and of

> the whole function proportional to n*(n/2), or n2, for brevity.

> however, just how much time is involved can vary tremendously. suppose

> the numbers are all fixnums and declared as such. you would probably

> expect the complexity of = to be such that the compiler can inline the

> tests completely and produce very efficient machine code. the complexity

> of /=, however, is such that you would face geometric expansion of the

> generated machine code were it done inline,

Not geometric. Just quadratic. That's still painful, though.

Quote:

> so it would be a function

> call away. that function would most probably be more generic (not in the

> CLOS sense) and not be able to benefit from the declaration of the

> fixnums, so it would do type tests or more generic number comparisons.

> so even though = and /= would differ by n/2 in theoretical execution

> time, you could very easily wind up with a large constant factor on top

> of that difference that for most practical purposes (reasonably small

> values of n) would dwarf n and even n2.

Just for information: doing

(declaim (optimize (speed 3)))

(defun f (a b c d e)

(declare (fixnum a b c d e))

(/= a b c d e))

in CMU CL produces code that does lots of individual comparisons.

It does the same thing even with 10 fixnum arguments. I presume

it would do the same even with 100.

In ACL, even with only three args it's a function call, and as

you say the code doesn't change at all if you take out the fixnum

declarations.

It would be possible, if anyone cared about /= with large numbers

of arguments, to do it more efficiently-in-the-worst-case by

sorting the numbers first. Unsurprisingly, ACL doesn't appear

to do this (judginf from timing figures).

CMU CL's code is much faster for n=10 and n=30 than ACL's on my

machine -- more than 10 times faster for n=10. On the other hand,

it takes a little while about compiling the n=30 code. For n=100,

compilation was *painful*; I gave up and killed it when its

allocated memory size was about 56MB. :-)

Does anyone actually ever call /= with large numbers of values?

--

sig under construction