[patch] generator function optimizations

[patch] generator function optimizations

[Paul Pogonyshev]

[-- Attachment #1: Type: text/plain, Size: 851 bytes --]

Generator functions are translated into a set of closures
that work together. While documentation says that they are
"somewhat less efficient than conventional elisp routines",
that seems to be an understatement.

In my real code (a very large function used as a co-routine)
with 60 yields, generator function has over 1000 lambdas.
I see several ways to improve this at least somewhat.

The patch below improves transformation of `progn' forms.
Here it results in 30 lambdas in the generator function fewer.
Not great (~ -3%), but I guess in other cases it can give a
larger improvement.

All unit-tests pass.

If this patch is accepted, I can work on some other ideas
I have.

Paul


* lisp/emacs-lisp/generator.el (cps--transform-1): When
transforming `progn' form with several atomic forms at the
beginning, create only one state for all of them.

[-- Attachment #2: generators.diff --]
[-- Type: text/plain, Size: 2090 bytes --]

diff --git a/lisp/emacs-lisp/generator.el b/lisp/emacs-lisp/generator.el
index 2ab01404ba..a3462971f8 100644
--- a/lisp/emacs-lisp/generator.el
+++ b/lisp/emacs-lisp/generator.el
@@ -286,19 +286,25 @@ don't yield.")
     ;; Process `progn' and `inline': they are identical except for the
     ;; name, which has some significance to the byte compiler.
 
-    (`(inline) (cps--transform-1 nil next-state))
-    (`(inline ,form) (cps--transform-1 form next-state))
-    (`(inline ,form . ,rest)
-      (cps--transform-1 form
-                        (cps--transform-1 `(inline ,@rest)
-                                          next-state)))
-
-    (`(progn) (cps--transform-1 nil next-state))
-    (`(progn ,form) (cps--transform-1 form next-state))
-    (`(progn ,form . ,rest)
-      (cps--transform-1 form
-                        (cps--transform-1 `(progn ,@rest)
-                                          next-state)))
+    (`(,(or 'inline 'progn)) (cps--transform-1 nil next-state))
+    (`(,(or 'inline 'progn) ,form) (cps--transform-1 form next-state))
+    (`(,(and (or 'inline 'progn) progn-type) ,form . ,rest)
+      (let (atomic-head)
+        ;; When there are several atomic (i.e. without `iter-yield')
+        ;; forms at the beginning, don't create a separate state for
+        ;; each of them, but rather one for all.
+        (unless cps-inhibit-atomic-optimization
+          (when (cps--atomic-p form)
+            (setf atomic-head (list form))
+            (while (and rest (cps--atomic-p (car rest)))
+              (push (pop rest) atomic-head))))
+        (if atomic-head
+            (cps--make-atomic-state `(,progn-type ,@(nreverse atomic-head))
+                                    (cps--transform-1 `(,progn-type ,@rest)
+                                                      next-state))
+          (cps--transform-1 form
+                            (cps--transform-1 `(,progn-type ,@rest)
+                                              next-state)))))
 
     ;; Process `let' in a helper function that transforms it into a
     ;; let* with temporaries.

Re: [patch] generator function optimizations

[Stefan Monnier]

> In my real code (a very large function used as a co-routine)
> with 60 yields, generator function has over 1000 lambdas.
> I see several ways to improve this at least somewhat.
>
> The patch below improves transformation of `progn' forms.
> Here it results in 30 lambdas in the generator function fewer.
> Not great (~ -3%), but I guess in other cases it can give a
> larger improvement.

Hmm... I don't think anyone should really care about the number of
lambdas, right?  So what is the actual problem (caused by this large
number of lambdas) that you're trying to improve?  Code size?
Run time?  Both?  Something else?

Have you tried to measure the impact of your patch on the actual problem?

> If this patch is accepted, I can work on some other ideas
> I have.

Indeed, there's probably a lot of opportunity for improvement.
E.g. cconv.el was designed based on the assumption that there wouldn't
be many different lambdas within the same scope (i.e. we don't try to
share the data part of various related closures).


        Stefan

Re: [patch] generator function optimizations

[Paul Pogonyshev]

[please keep me on CC, I'm not subscribed to the list]

> > In my real code (a very large function used as a co-routine)
> > with 60 yields, generator function has over 1000 lambdas.
> > [...]
>
> Hmm... I don't think anyone should really care about the number of
> lambdas, right?  So what is the actual problem (caused by this large
> number of lambdas) that you're trying to improve?  Code size?
> Run time?  Both?  Something else?

Both. This huge function takes a lot of time to compile, produces
lots of bytecode and is fairly slow. Of course it is difficult to compare
with non-generator routine: it is so large and complicated I won't try
to rewrite it just for speed comparisons, not to mention that it is run
by a "master" that can pause at any yield-point to resolve
dependencies with other code.

However, note that there are 60 points where it can yield and thus
lose control. But, there are over 1000 generator states. Meaning
that even between this points it switches many generator states, in
a sense pointlessly, because intermediate states have predetermined
successor (some of them have several, if they are branching points).

Lambda calls are not free and it is certainly faster not to call them
if you don't have to. Basically, this patch eliminates some intermediate
states and makes generator form transformer generate a single lambda
where it would previously create several.

> Have you tried to measure the impact of your patch on the actual problem?

I mentioned 3%. Yes, it is practically negligible, but this is a first
small patch and I'm willing to work on improving generators further.

> > If this patch is accepted, I can work on some other ideas
> > I have.
>
> Indeed, there's probably a lot of opportunity for improvement.
> E.g. cconv.el was designed based on the assumption that there wouldn't
> be many different lambdas within the same scope (i.e. we don't try to
> share the data part of various related closures).

There are also, unfortunately, bugs. I have found and submitted two
already (in the normal bug tracker), for one I attached a fix.

Paul

Re: [patch] generator function optimizations

[Stefan Monnier]

>> Have you tried to measure the impact of your patch on the actual problem?
> I mentioned 3%.

That's the percentage impact on the number of lambdas.  I'm curious
about its impact on actual problematic aspects, such as speed and code
size (and compilation time, I guess).

> Yes, it is practically negligible, but this is a first small patch and
> I'm willing to work on improving generators further.

Of course.


        Stefan

Re: [patch] generator function optimizations

[Andreas Politz]

Paul Pogonyshev <pogonyshev@gmail.com> writes:

> Generator functions are translated into a set of closures
> that work together. [...]

Can you please also make the expansion of these generators edebuggable,
by giving all variables distinct names, if you haven't already ?

-ap

Re: [patch] generator function optimizations

[Noam Postavsky]

On Sun, Mar 12, 2017 at 6:26 PM, Andreas Politz
<politza@hochschule-trier.de> wrote:
>
> Can you please also make the expansion of these generators edebuggable,
> by giving all variables distinct names

Since the fix for #23660 was merged, you can already edebug the
expansion if you set print-circle and print-gensym. Of course,
distinct names are a bit easier for a human to read.

https://debbugs.gnu.org/cgi/bugreport.cgi?bug=23660#17

Re: [patch] generator function optimizations

[Andreas Politz]

Noam Postavsky <npostavs@users.sourceforge.net> writes:

> Since the fix for #23660 was merged, you can already edebug the
> expansion if you set print-circle and print-gensym. 

Ah, ok.

> Of course, distinct names are a bit easier for a human to read.

Yes, and I would add, way more easy to follow the execution path.

-ap