Compiler macro for apply-partially

Compiler macro for apply-partially

[Adam Porter]

Hi,

I wondered if using apply-partially had a significant runtime cost, so I
did a little benchmark using my bench-multi-lexical macro.[0]  I found
that it seems to be much slower than writing a lambda form directly,
which the byte-compiler can optimize more effectively.  It also conses,
so it can contribute to earlier GC.  Whether it has a noticable effect
depends on the application, I suppose.

Anyway, I came up with a simple compiler-macro declaration that seems to
help.  In these benchmarks, the version with the compiler-macro is named
`apply-partially*': it's roughly twice as fast as `apply-partially' and
produces about half as much garbage.

I was curious to see if it could be further optimized for cases in which
the partially applied function is called with only one argument, which
is the most common case for me, so I also made a version that does that,
here named `apply-partially**', and it's virtually identical in
performance to writing a lambda directly.

Please see the benchmark code and results below.  If any of these
enhancements would be useful, I'd be glad to submit a patch.  Please let
me know.

Thanks,
Adam

0: https://github.com/alphapapa/emacs-package-dev-handbook#bench-multi-lexical

#+BEGIN_SRC elisp :exports code :results silent
  (defun apply-partially* (fun &rest args)
    "Return a function that is a partial application of FUN to ARGS.
  ARGS is a list of the first N arguments to pass to FUN.  The
  result is a new function which does the same as FUN, except that
  the first N arguments are fixed at the values with which this
  function was called."
    (declare (compiler-macro (lambda (exp)
                               `(lambda (&rest args2)
                                  (apply ,fun ,@args args2)))))
    (lambda (&rest args2)
      (apply fun (append args args2))))

  (defun apply-partially** (fun &rest args)
    "Return a function that is a partial application of FUN to ARGS.
  ARGS is a list of the first N arguments to pass to FUN.  The
  result is a new function which does the same as FUN, except that
  the first N arguments are fixed at the values with which this
  function was called, and it only accepts one additional
  argument."
    (declare (compiler-macro (lambda (exp)
                               `(lambda (arg2)
                                  ,(pcase fun
                                     (`(function ,fun)
                                      `(,fun ,@args arg2))
                                     (_ `(,fun ,@args arg2)))))))
    (lambda (arg2)
      (apply fun (append args (list arg2)))))
#+END_SRC

* With one applied argument

#+BEGIN_SRC elisp :exports both
  (bench-multi-lexical :times 100000 :ensure-equal t
    :forms (("lambda" (let* ((foo 'FOO)
                             (fn (lambda (arg)
                                   (eq arg foo))))
                        (cl-loop for i below 100
                                 do (funcall fn foo))))
            ("apply-partially" (let* ((foo 'FOO)
                                      (fn (apply-partially #'eq foo)))
                                 (cl-loop for i below 100
                                          do (funcall fn foo))))
            ("apply-partially*" (let* ((foo 'FOO)
                                       (fn (apply-partially* #'eq foo)))
                                  (cl-loop for i below 100
                                           do (funcall fn foo))))
            ("apply-partially**" (let* ((foo 'FOO)
                                        (fn (apply-partially** #'eq foo)))
                                   (cl-loop for i below 100
                                            do (funcall fn foo))))))
#+END_SRC

#+RESULTS:
| Form              | x faster than next | Total runtime | # of GCs | Total GC runtime |
|-------------------+--------------------+---------------+----------+------------------|
| lambda            |               1.02 |      0.446226 |        0 |                0 |
| apply-partially** |               5.11 |      0.456534 |        0 |                0 |
| apply-partially*  |               1.99 |      2.331980 |        5 |         1.476272 |
| apply-partially   |            slowest |      4.629640 |       11 |         3.257624 |

* With two applied arguments

#+BEGIN_SRC elisp :exports both
  (bench-multi-lexical :times 100000 :ensure-equal t
    :forms (("lambda" (let* ((n 0)
                             (m 1)
                             (fn (lambda (x y z)
                                   (< x y z))))
                        (cl-loop for i below 100
                                 do (funcall fn n m i))))
            ("apply-partially" (let* ((n 0)
                                      (m 1)
                                      (fn (apply-partially #'< n m)))
                                 (cl-loop for i below 100
                                          do (funcall fn i))))
            ("apply-partially*" (let* ((n 0)
                                       (m 1)
                                       (fn (apply-partially* #'< n m)))
                                  (cl-loop for i below 100
                                           do (funcall fn i))))
            ("apply-partially**" (let* ((n 0)
                                        (m 1)
                                        (fn (apply-partially** #'< n m)))
                                   (cl-loop for i below 100
                                            do (funcall fn i))))))
#+END_SRC

#+RESULTS:
| Form              | x faster than next | Total runtime | # of GCs | Total GC runtime |
|-------------------+--------------------+---------------+----------+------------------|
| apply-partially** |               1.00 |      0.551158 |        0 |                0 |
| lambda            |               4.38 |      0.551878 |        0 |                0 |
| apply-partially*  |               2.75 |      2.415262 |        5 |         1.485259 |
| apply-partially   |            slowest |      6.640960 |       17 |         5.059900 |

* With two applied arguments and two called arguments

#+BEGIN_SRC elisp :exports both
  (bench-multi-lexical :times 100000 :ensure-equal t
    :forms (("lambda" (let* ((n 0)
                             (m 1)
                             (fn (lambda (x y z a)
                                   (< x y z a))))
                        (cl-loop for i below 100
                                 do (funcall fn n m i i))))
            ("apply-partially" (let* ((n 0)
                                      (m 1)
                                      (fn (apply-partially #'< n m)))
                                 (cl-loop for i below 100
                                          do (funcall fn i i))))
            ("apply-partially*" (let* ((n 0)
                                       (m 1)
                                       (fn (apply-partially* #'< n m)))
                                  (cl-loop for i below 100
                                           do (funcall fn i i))))))
#+END_SRC

#+RESULTS:
| Form             | x faster than next | Total runtime | # of GCs | Total GC runtime |
|------------------+--------------------+---------------+----------+------------------|
| lambda           |               7.06 |      0.629179 |        0 |                0 |
| apply-partially* |               1.87 |      4.441770 |       11 |         3.310380 |
| apply-partially  |            slowest |      8.323220 |       22 |         6.596604 |

Re: Compiler macro for apply-partially

[Adam Porter]

Unfortunately some of the lines in the results tables were wrapped, but
they should still be readable enough.

[ If there's a way to stop Gnus from hard-wrapping lines for just one
  message, please let me know for future reference.  :) ]

Re: Compiler macro for apply-partially

[Andreas Schwab]

On Aug 24 2021, Adam Porter wrote:

> Unfortunately some of the lines in the results tables were wrapped, but
> they should still be readable enough.
>
> [ If there's a way to stop Gnus from hard-wrapping lines for just one
>   message, please let me know for future reference.  :) ]

I don't see any wrapping.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: Compiler macro for apply-partially

[Adam Porter]

Andreas Schwab <schwab@linux-m68k.org> writes:

> On Aug 24 2021, Adam Porter wrote:
>
>> Unfortunately some of the lines in the results tables were wrapped, but
>> they should still be readable enough.
>>
>> [ If there's a way to stop Gnus from hard-wrapping lines for just one
>>   message, please let me know for future reference.  :) ]
>
> I don't see any wrapping.

Oh, it must be something Mailman does in the Web archive.  Thanks.

Re: Compiler macro for apply-partially

[Stefan Monnier]

>   (defun apply-partially* (fun &rest args)
>     "Return a function that is a partial application of FUN to ARGS.
>   ARGS is a list of the first N arguments to pass to FUN.  The
>   result is a new function which does the same as FUN, except that
>   the first N arguments are fixed at the values with which this
>   function was called."
>     (declare (compiler-macro (lambda (exp)
>                                `(lambda (&rest args2)
>                                   (apply ,fun ,@args args2)))))
>     (lambda (&rest args2)
>       (apply fun (append args args2))))

Looks OK to me.

FWIW, I never added such a compiler macro for the following reason: it's
almost always preferable to use an explicit `lambda` where you can
specify how many args are expected and hence avoid the `&rest` and the
`apply`, leading to significantly more efficient code.

IOW if you care about performance use `lambda` rather than
`apply-partially`.  `apply-partially` was a hack to make it easy to
build closures back when we didn't have `lexical-binding`.
Adding a compiler macro to it makes it a bit less slow, but the real
gain can only come after the authors provide a more complete calling
convention as is the case when using `lambda`.

>   (defun apply-partially** (fun &rest args)

This is an example of the more efficient code I'm talking about and it
requires the programmer to tell us that the returned function will be
called only with exactly 1 argument, so it can't be just a compiler-macro.


        Stefan

Re: Compiler macro for apply-partially

[Eric Abrahamsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>   (defun apply-partially* (fun &rest args)
>>     "Return a function that is a partial application of FUN to ARGS.
>>   ARGS is a list of the first N arguments to pass to FUN.  The
>>   result is a new function which does the same as FUN, except that
>>   the first N arguments are fixed at the values with which this
>>   function was called."
>>     (declare (compiler-macro (lambda (exp)
>>                                `(lambda (&rest args2)
>>                                   (apply ,fun ,@args args2)))))
>>     (lambda (&rest args2)
>>       (apply fun (append args args2))))
>
> Looks OK to me.
>
> FWIW, I never added such a compiler macro for the following reason: it's
> almost always preferable to use an explicit `lambda` where you can
> specify how many args are expected and hence avoid the `&rest` and the
> `apply`, leading to significantly more efficient code.

For us slower kids, this explicit approach might look like:

(cl-flet ((curried (arg3)
		   (function-to-apply-partially arg1 arg2 arg3)))
  (curried "arg3"))

Either that or just plain `let' a lambda, and then `funcall' it?

Re: Compiler macro for apply-partially

[Stefan Monnier]

> For us slower kids, this explicit approach might look like:
>
> (cl-flet ((curried (arg3)
> 		   (function-to-apply-partially arg1 arg2 arg3)))
>   (curried "arg3"))
>
> Either that or just plain `let' a lambda, and then `funcall' it?

I just meant that instead of writing

    (apply-partially #'foo arg1 arg2)

you write

    (lambda (arg3 &optional arg4 ...)
      (foo arg1 arg2 arg3 arg4 ...))

A compiler macro can't easily do it for you because it's between hard
and impossible to automatically guess the (arg3 &optional arg4 ...)
part.


        Stefan

Re: Compiler macro for apply-partially

[Eric Abrahamsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> For us slower kids, this explicit approach might look like:
>>
>> (cl-flet ((curried (arg3)
>> 		   (function-to-apply-partially arg1 arg2 arg3)))
>>   (curried "arg3"))
>>
>> Either that or just plain `let' a lambda, and then `funcall' it?
>
> I just meant that instead of writing
>
>     (apply-partially #'foo arg1 arg2)
>
> you write
>
>     (lambda (arg3 &optional arg4 ...)
>       (foo arg1 arg2 arg3 arg4 ...))
>
> A compiler macro can't easily do it for you because it's between hard
> and impossible to automatically guess the (arg3 &optional arg4 ...)
> part.

Gotcha, thanks.