Steel Bank Common Lisp

Akshay Srinivasan <akshaysrinivasan@...> writes:

> Hello,
> 	Does reduce have a compiler macro ?
>
> Doing this in SBCL tells me that:
> $ (compiler-macro-function 'reduce)
> nil
>
> but so does this
> $ (compiler-macro-function 'sort)
> nil
> However, I've found that optimizations and type declarations in the
> environment do have a significant effect on runtimes of sort. I'm not
> sure how this can be done without compiler macros.
>
> reduce tends to run quite slow(compared with loop) even with
> type-declarations, and optimize declarations. This does not actually
> bother me much, I'm just curious.
SBCL has more powerful ways of optimizations, e.g., transforms. In the
case of SORT it's declared inline, which allows to eliminate
type-dispatch and apply other optimizations.

reduce may be slow when using functions with arbitrary number of
arguments, e.g. +.
(reduce (lambda (x y) (+ x y)) sequence) would be faster.
But indeed, LOOP in this case becomes more readable and faster.
-- 
With best regards, Stas.

Stas Boukarev <stassats@...> writes:
> reduce may be slow when using functions with arbitrary number of
> arguments, e.g. +.
> (reduce (lambda (x y) (+ x y)) sequence) would be faster.

I'm confused by this. Do you mean faster than (reduce #'+ sequence)? In
which case, can you explain how an arbitrary number of arguments gets
involved? (Or point me at the relevant bit of source and I'll try to
work it out)

I presume this is orthogonal to things like open-coding summation of a
load of fixnums etc. (Can SBCL spot that sort of thing?)

I hope I'm not hijacking the thread with my questions!


Rupert

Rupert Swarbrick <rswarbrick@...> writes:

> Stas Boukarev <stassats@...> writes:
>> reduce may be slow when using functions with arbitrary number of
>> arguments, e.g. +.
>> (reduce (lambda (x y) (+ x y)) sequence) would be faster.
>
> I'm confused by this. Do you mean faster than (reduce #'+ sequence)? In
> which case, can you explain how an arbitrary number of arguments gets
> involved? (Or point me at the relevant bit of source and I'll try to
> work it out)
Right, faster than (reduce #'+ sequence).
Because it doesn't know the number of arguments it'll be called with.
When compiled as (+ x y), it knows that it'll be exactly two arguments
and can open-code a call to the two-argument function which actually
performs addition, instead of adding each argument one by one
(basically, performing its own reduce).

+ also has lambda-list as (&rest args) which means it conses a list of
two elements each time it's called.

You can see the difference by doing
(disassemble (lambda (x y) (+ x y)))
and
(disassemble #'+)
-- 
With best regards, Stas.

Stas Boukarev <stassats@...> writes:
> Rupert Swarbrick <rswarbrick@...> writes:
>> Stas Boukarev <stassats@...> writes:
>>> reduce may be slow when using functions with arbitrary number of
>>> arguments, e.g. +.
>>> (reduce (lambda (x y) (+ x y)) sequence) would be faster.
>>
>> I'm confused by this. Do you mean faster than (reduce #'+ sequence)? In
>> which case, can you explain how an arbitrary number of arguments gets
>> involved? (Or point me at the relevant bit of source and I'll try to
>> work it out)
> Right, faster than (reduce #'+ sequence).
> Because it doesn't know the number of arguments it'll be called with.
> When compiled as (+ x y), it knows that it'll be exactly two arguments
> and can open-code a call to the two-argument function which actually
> performs addition, instead of adding each argument one by one
> (basically, performing its own reduce).
>
> + also has lambda-list as (&rest args) which means it conses a list of
> two elements each time it's called.
>
> You can see the difference by doing
> (disassemble (lambda (x y) (+ x y)))
> and
> (disassemble #'+)

Ah, OK, I think I understand. Presumably it would be possible for SBCL
to notice that (reduce f seq) calls f with only two arguments and thus
replace (reduce #'f seq) with the two-argument version? (I'm not
necessarily arguing that this optimisation is easy to implement / worth
implementing - I just want to check it makes sense)

Rupert

Rupert Swarbrick <rswarbrick@...> writes:

> Stas Boukarev <stassats@...> writes:
>> Rupert Swarbrick <rswarbrick@...> writes:
>>> Stas Boukarev <stassats@...> writes:
>>>> reduce may be slow when using functions with arbitrary number of
>>>> arguments, e.g. +.
>>>> (reduce (lambda (x y) (+ x y)) sequence) would be faster.
>>>
>>> I'm confused by this. Do you mean faster than (reduce #'+ sequence)? In
>>> which case, can you explain how an arbitrary number of arguments gets
>>> involved? (Or point me at the relevant bit of source and I'll try to
>>> work it out)
>> Right, faster than (reduce #'+ sequence).
>> Because it doesn't know the number of arguments it'll be called with.
>> When compiled as (+ x y), it knows that it'll be exactly two arguments
>> and can open-code a call to the two-argument function which actually
>> performs addition, instead of adding each argument one by one
>> (basically, performing its own reduce).
>>
>> + also has lambda-list as (&rest args) which means it conses a list of
>> two elements each time it's called.
>>
>> You can see the difference by doing
>> (disassemble (lambda (x y) (+ x y)))
>> and
>> (disassemble #'+)
>
> Ah, OK, I think I understand. Presumably it would be possible for SBCL
> to notice that (reduce f seq) calls f with only two arguments and thus
> replace (reduce #'f seq) with the two-argument version? (I'm not
> necessarily arguing that this optimisation is easy to implement / worth
> implementing - I just want to check it makes sense)
Yes, it is possible.
-- 
With best regards, Stas.

On 07/30/2012 12:47 PM, Rupert Swarbrick wrote:
>
> Ah, OK, I think I understand. Presumably it would be possible for SBCL
> to notice that (reduce f seq) calls f with only two arguments and thus
> replace (reduce #'f seq) with the two-argument version? (I'm not
> necessarily arguing that this optimisation is easy to implement / worth
> implementing - I just want to check it makes sense)
>
> Rupert
>

But then the test for the 2-argument case would involve additional 
overhead affecting both cases. So it wouldn't be as fast as '+' alone 
and would slow down the > 2 case as well.

Jeff

Jeffrey Cunningham <jeffrey@...> writes:
> On 07/30/2012 12:47 PM, Rupert Swarbrick wrote:
>>
>> Ah, OK, I think I understand. Presumably it would be possible for SBCL
>> to notice that (reduce f seq) calls f with only two arguments and thus
>> replace (reduce #'f seq) with the two-argument version? (I'm not
>> necessarily arguing that this optimisation is easy to implement / worth
>> implementing - I just want to check it makes sense)
>>
>> Rupert
>>
>
> But then the test for the 2-argument case would involve additional
> overhead affecting both cases. So it wouldn't be as fast as '+' alone
> and would slow down the > 2 case as well.
>
> Jeff

But you would be checking for it when you compiled the form (reduce #'+
seq), not when #'+ was called, no?

Rupert