unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
* [patch] generator function optimizations
@ 2017-03-12 10:59 Paul Pogonyshev
  2017-03-12 17:21 ` Stefan Monnier
  2017-03-12 22:26 ` Andreas Politz
  0 siblings, 2 replies; 7+ messages in thread
From: Paul Pogonyshev @ 2017-03-12 10:59 UTC (permalink / raw)
  To: Emacs developers

[-- 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.

^ permalink raw reply related	[flat|nested] 7+ messages in thread

* Re: [patch] generator function optimizations
  2017-03-12 10:59 [patch] generator function optimizations Paul Pogonyshev
@ 2017-03-12 17:21 ` Stefan Monnier
  2017-03-12 22:26 ` Andreas Politz
  1 sibling, 0 replies; 7+ messages in thread
From: Stefan Monnier @ 2017-03-12 17:21 UTC (permalink / raw)
  To: emacs-devel

> 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




^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [patch] generator function optimizations
@ 2017-03-12 19:12 Paul Pogonyshev
  2017-03-12 21:53 ` Stefan Monnier
  0 siblings, 1 reply; 7+ messages in thread
From: Paul Pogonyshev @ 2017-03-12 19:12 UTC (permalink / raw)
  To: Emacs developers, Stefan Monnier

[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



^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [patch] generator function optimizations
  2017-03-12 19:12 Paul Pogonyshev
@ 2017-03-12 21:53 ` Stefan Monnier
  0 siblings, 0 replies; 7+ messages in thread
From: Stefan Monnier @ 2017-03-12 21:53 UTC (permalink / raw)
  To: emacs-devel

>> 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




^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [patch] generator function optimizations
  2017-03-12 10:59 [patch] generator function optimizations Paul Pogonyshev
  2017-03-12 17:21 ` Stefan Monnier
@ 2017-03-12 22:26 ` Andreas Politz
  2017-03-12 22:33   ` Noam Postavsky
  1 sibling, 1 reply; 7+ messages in thread
From: Andreas Politz @ 2017-03-12 22:26 UTC (permalink / raw)
  To: Paul Pogonyshev; +Cc: Emacs developers

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



^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [patch] generator function optimizations
  2017-03-12 22:26 ` Andreas Politz
@ 2017-03-12 22:33   ` Noam Postavsky
  2017-03-12 22:44     ` Andreas Politz
  0 siblings, 1 reply; 7+ messages in thread
From: Noam Postavsky @ 2017-03-12 22:33 UTC (permalink / raw)
  To: Andreas Politz; +Cc: Paul Pogonyshev, Emacs developers

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



^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [patch] generator function optimizations
  2017-03-12 22:33   ` Noam Postavsky
@ 2017-03-12 22:44     ` Andreas Politz
  0 siblings, 0 replies; 7+ messages in thread
From: Andreas Politz @ 2017-03-12 22:44 UTC (permalink / raw)
  To: Noam Postavsky; +Cc: Paul Pogonyshev, Emacs developers

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



^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, other threads:[~2017-03-12 22:44 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-03-12 10:59 [patch] generator function optimizations Paul Pogonyshev
2017-03-12 17:21 ` Stefan Monnier
2017-03-12 22:26 ` Andreas Politz
2017-03-12 22:33   ` Noam Postavsky
2017-03-12 22:44     ` Andreas Politz
  -- strict thread matches above, loose matches on Subject: below --
2017-03-12 19:12 Paul Pogonyshev
2017-03-12 21:53 ` Stefan Monnier

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).