Execution speed

Execution speed

[Stefan Monnier]

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

Someone on SO reported a surprising behavior where a recursive
implementation of `gcd` turned out faster than the iterative version:

    http://stackoverflow.com/questions/42792988/

The more surprising thing is that when I try it I get the
opposite result, even though it's basically on the same kind of system
(GNU/Linx x86).

I'm curious where the difference might come from.  Could you guys try
out the test?

Just do `emacs -Q --batch -l .../ir-test.el`.  Here's what I got:

    % emacs24 -Q --batch -l ~/tmp/ir-test.el
    Interpreted:  Iterative=1.770s; Recursive=1.937s
    Bytecompiled: Iterative=1.187s; Recursive=1.496s
    % .../src/emacs -Q --batch -l ~/tmp/ir-test.el
    Interpreted:  Iterative=4.496s; Recursive=4.595s
    Bytecompiled: Iterative=2.471s; Recursive=2.983s

where `emacs24` is Debian's whereas the other one is my locally
built&hacked version with debugging assertions and stuff.


        Stefan

[-- Attachment #2: ir-test.el --]
[-- Type: application/emacs-lisp, Size: 992 bytes --]

Re: Execution speed

[Mark Oteiza]

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

> Someone on SO reported a surprising behavior where a recursive
> implementation of `gcd` turned out faster than the iterative version:
>
>     http://stackoverflow.com/questions/42792988/
>
> The more surprising thing is that when I try it I get the
> opposite result, even though it's basically on the same kind of system
> (GNU/Linx x86).
>
> I'm curious where the difference might come from.  Could you guys try
> out the test?
>
> Just do `emacs -Q --batch -l .../ir-test.el`.  Here's what I got:
>
>     % emacs24 -Q --batch -l ~/tmp/ir-test.el
>     Interpreted:  Iterative=1.770s; Recursive=1.937s
>     Bytecompiled: Iterative=1.187s; Recursive=1.496s
>     % .../src/emacs -Q --batch -l ~/tmp/ir-test.el
>     Interpreted:  Iterative=4.496s; Recursive=4.595s
>     Bytecompiled: Iterative=2.471s; Recursive=2.983s
>
> where `emacs24` is Debian's whereas the other one is my locally
> built&hacked version with debugging assertions and stuff.

Interesting.  Arch Linux's repo emacs 25:

$ emacs -Q --batch -l ir-test.el
Interpreted:  Iterative=2.302s; Recursive=1.956s
Bytecompiled: Iterative=1.349s; Recursive=1.214s

Re: Execution speed

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Sun, 19 Mar 2017 11:12:59 -0400
> 
> Just do `emacs -Q --batch -l .../ir-test.el`.  Here's what I got:
> 
>     % emacs24 -Q --batch -l ~/tmp/ir-test.el
>     Interpreted:  Iterative=1.770s; Recursive=1.937s
>     Bytecompiled: Iterative=1.187s; Recursive=1.496s
>     % .../src/emacs -Q --batch -l ~/tmp/ir-test.el
>     Interpreted:  Iterative=4.496s; Recursive=4.595s
>     Bytecompiled: Iterative=2.471s; Recursive=2.983s
> 
> where `emacs24` is Debian's whereas the other one is my locally
> built&hacked version with debugging assertions and stuff.

My results:

 . Emacs 24.5 (optimized, 32-bit):

    Interpreted:  Iterative=1.047s; Recursive=1.140s
    Bytecompiled: Iterative=0.704s; Recursive=0.875s

 . Emacs 25.2-rc2 (optimized, 32-bit --with-wide-int):

    Interpreted:  Iterative=2.500s; Recursive=2.281s
    Bytecompiled: Iterative=1.328s; Recursive=1.281s

 . Current emacs-25 branch (unoptimized, 32-bit --with-wide-int):

    Interpreted:  Iterative=29.328s; Recursive=23.953s
    Bytecompiled: Iterative=12.719s; Recursive=13.422s

 . Current master (unoptimized, 32-bit --with-wide-int):

    Interpreted:  Iterative=26.937s; Recursive=25.500s
    Bytecompiled: Iterative=7.468s; Recursive=12.953s

Re: Execution speed

[Tino Calancha]

On Sun, 19 Mar 2017, Stefan Monnier wrote:

> Just do `emacs -Q --batch -l .../ir-test.el`.  Here's what I got:
>
>    % emacs24 -Q --batch -l ~/tmp/ir-test.el
>    Interpreted:  Iterative=1.770s; Recursive=1.937s
>    Bytecompiled: Iterative=1.187s; Recursive=1.496s
>    % .../src/emacs -Q --batch -l ~/tmp/ir-test.el
>    Interpreted:  Iterative=4.496s; Recursive=4.595s
>    Bytecompiled: Iterative=2.471s; Recursive=2.983s
>
> where `emacs24` is Debian's whereas the other one is my locally
> built&hacked version with debugging assertions and stuff.

I got the following (Debian 9):

                           Emacs-24.5 (s)   Emacs-25 (s)  Emacs-26 (s)
Iterative-interpreted     1.42             1.78          1.67
Iterative-Compiled        0.74             1.02          0.63
----------------------------------------------------------------------
Recursive-interpreted     1.45             1.41          1.67
Recursive-Compiled        1.03             0.90          1.02

Re: Execution speed

[Andreas Politz]

emacs-git -Q --batch -l ~/tmp/ir-test.el
Interpreted:  Iterative=1.609s; Recursive=1.644s
Bytecompiled: Iterative=0.577s; Recursive=0.920s

Re: Execution speed

[Teemu Likonen]

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

Stefan Monnier [2017-03-19 11:12:59-04] wrote:

> Just do `emacs -Q --batch -l .../ir-test.el`.

My Emacs is from commit emacs-25.2-rc2-16-gd71e071 and it gives this:

Interpreted:  Iterative=1.269s; Recursive=0.977s
Bytecompiled: Iterative=0.635s; Recursive=0.531s

-- 
/// Teemu Likonen   - .-..   <https://keybase.io/tlikonen> //
// PGP: 4E10 55DC 84E9 DFF6 13D7 8557 719D 69D3 2453 9450 ///

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 454 bytes --]

Re: Execution speed

[npostavs]

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

On Sun, Mar 19, 2017 at 11:12 AM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> the other one is my locally built&hacked version with debugging
> assertions and stuff.

Is that the one that sets lexical-binding always?  According to my
measurements, the iterative case is slower on Emacs 25 when using
dynamic binding.  With lexical binding, the recursive case is always
slower.

(Note the measurements below are using unoptimized -O0 builds, with
extra checking enabled)

GNU Emacs 24.5.5 (x86_64-unknown-linux-gnu, X toolkit) of 2017-02-12 on zony

| DYNAMIC   | interpreted | compiled |
|-----------+-------------+----------|
| recursive | 7.64s       | 5.61s    |
| iterative | 7.91s       | 4.24s    |

| LEXICAL   | interpreted                | compiled               |
|-----------+----------------------------+------------------------|
| recursive | 21.82s (12.20s in 470 GCs) | 4.73s (0.15s in 6 GCs) |
| iterative |  8.87s  (0.54s in  21 GCs) | 3.14s (0.15s in 6 GCs) |

GNU Emacs 25.2.6 (x86_64-unknown-linux-gnu, X toolkit) of 2017-03-01

| DYNAMIC   | interpreted | compiled |
|-----------+-------------+----------|
| recursive | 10.58s      | 6.39s    |
| iterative | 14.05s      | 6.72s    |

| LEXICAL   | interpreted                | compiled               |
|-----------+----------------------------+------------------------|
| recursive | 35.44s (20.56s in 448 GCs) | 4.35s (0.28s in 6 GCs) |
| iterative | 13.20s ( 0.92s in  20 GCs) | 2.96s (0.23s in 5 GCs) |



[-- Attachment #2: benchmarking code --]
[-- Type: application/emacs-lisp, Size: 1579 bytes --]

[-- Attachment #3: benchmarking lexical code --]
[-- Type: application/emacs-lisp, Size: 1609 bytes --]

Re: Execution speed

[Phil Sainty]

$ emacs-24.4 -Q --batch -l /tmp/ir-test.el
Interpreted:  Iterative=2.001s; Recursive=2.219s
Bytecompiled: Iterative=1.266s; Recursive=1.569s

$ emacs-24.5 -Q --batch -l /tmp/ir-test.el
Interpreted:  Iterative=1.807s; Recursive=2.094s
Bytecompiled: Iterative=1.151s; Recursive=1.564s

$ emacs-25.1 -Q --batch -l /tmp/ir-test.el
Interpreted:  Iterative=2.378s; Recursive=1.936s
Bytecompiled: Iterative=1.340s; Recursive=1.197s

$ emacs-25.2 -Q --batch -l /tmp/ir-test.el
Interpreted:  Iterative=2.134s; Recursive=1.936s
Bytecompiled: Iterative=1.334s; Recursive=1.193s


FWIW, those are:
GNU Emacs 24.4.2 (x86_64-unknown-linux-gnu, X toolkit, Xaw3d scroll bars)
GNU Emacs 24.5.1 (x86_64-unknown-linux-gnu, X toolkit, Xaw3d scroll bars)
GNU Emacs 25.1.1 (x86_64-pc-linux-gnu, X toolkit, Xaw3d scroll bars)
GNU Emacs 25.2.1 (x86_64-pc-linux-gnu, X toolkit, Xaw3d scroll bars)

In all cases compiled via:
./autogen.sh && ./configure --with-x-toolkit=lucid --without-sound && make

Re: Execution speed

[Phil Sainty]

Using npostavs's code:

     | DYNAMIC   | interpreted              | compiled
--------------------------------------------------------------------
25.2 | recursive | 1.55s                    | 0.94s
     | iterative | 1.70s                    | 1.06s
--------------------------------------------------------------------
25.1 | recursive | 1.53s                    | 0.95s
     | iterative | 1.87s                    | 1.06s
--------------------------------------------------------------------
24.5 | recursive | 1.65s                    | 1.24s
     | iterative | 1.43s                    | 0.95s
--------------------------------------------------------------------
24.4 | recursive | 1.78s                    | 1.25s
     | iterative | 1.59s                    | 1.02s
--------------------------------------------------------------------


     | LEXICAL   | interpreted              | compiled
--------------------------------------------------------------------
25.2 | recursive | 4.27s (2.22s in 506 GCs) | 0.64s (0.03s in 6 GCs)
     | iterative | 1.56s (0.10s in 23 GCs)  | 0.49s (0.03s in 6 GCs)
--------------------------------------------------------------------
25.1 | recursive | 4.26s (2.21s in 506 GCs) | 0.64s (0.03s in 6 GCs)
     | iterative | 1.58s (0.10s in 23 GCs)  | 0.50s (0.03s in 6 GCs)
--------------------------------------------------------------------
24.5 | recursive | 4.11s (2.14s in 507 GCs) | 0.92s (0.03s in 6 GCs)
     | iterative | 1.57s (0.09s in 22 GCs)  | 0.84s (0.03s in 7 GCs)
--------------------------------------------------------------------
24.4 | recursive | 4.20s (2.08s in 506 GCs) | 0.91s (0.03s in 6 GCs)
     | iterative | 1.65s (0.10s in 23 GCs)  | 0.82s (0.03s in 6 GCs)
--------------------------------------------------------------------


Running as:

emacs -Q --batch -l /tmp/gcd-benchmark-dynamic.el --eval '(progn
(gcd-dynamic-benchmarks) (princ (buffer-string)))'

emacs -Q --batch -l /tmp/gcd-benchmark-lexical.el --eval '(progn
(gcd-lexical-benchmarks) (princ (buffer-string)))'





On 20/03/17 08:09, npostavs@users.sourceforge.net wrote:
> On Sun, Mar 19, 2017 at 11:12 AM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> 
>> the other one is my locally built&hacked version with debugging
>> assertions and stuff.
> 
> Is that the one that sets lexical-binding always?  According to my
> measurements, the iterative case is slower on Emacs 25 when using
> dynamic binding.  With lexical binding, the recursive case is always
> slower.
> 
> (Note the measurements below are using unoptimized -O0 builds, with
> extra checking enabled)
> 
> GNU Emacs 24.5.5 (x86_64-unknown-linux-gnu, X toolkit) of 2017-02-12 on zony
> 
> | DYNAMIC   | interpreted | compiled |
> |-----------+-------------+----------|
> | recursive | 7.64s       | 5.61s    |
> | iterative | 7.91s       | 4.24s    |
> 
> | LEXICAL   | interpreted                | compiled               |
> |-----------+----------------------------+------------------------|
> | recursive | 21.82s (12.20s in 470 GCs) | 4.73s (0.15s in 6 GCs) |
> | iterative |  8.87s  (0.54s in  21 GCs) | 3.14s (0.15s in 6 GCs) |
> 
> GNU Emacs 25.2.6 (x86_64-unknown-linux-gnu, X toolkit) of 2017-03-01
> 
> | DYNAMIC   | interpreted | compiled |
> |-----------+-------------+----------|
> | recursive | 10.58s      | 6.39s    |
> | iterative | 14.05s      | 6.72s    |
> 
> | LEXICAL   | interpreted                | compiled               |
> |-----------+----------------------------+------------------------|
> | recursive | 35.44s (20.56s in 448 GCs) | 4.35s (0.28s in 6 GCs) |
> | iterative | 13.20s ( 0.92s in  20 GCs) | 2.96s (0.23s in 5 GCs) |
> 
> 

Re: Execution speed

[Ivan Kanis]

March, 19 at 11:12 Stefan wrote:

> I'm curious where the difference might come from.  Could you guys try
> out the test?
>
> Just do `emacs -Q --batch -l .../ir-test.el`.  Here's what I got:

Interpreted:  Iterative=1.591s; Recursive=1.392s
Bytecompiled: Iterative=0.855s; Recursive=0.863s

GNU Emacs 25.2.1 (rc2 candidate) on Debian 9.

Performance of lexical closures in interpreted code? (was Re: Execution speed)

[Phil Sainty]

Tangentially, that performance hit on the interpreted recursive
code with lexical-binding enabled is pretty severe!  From well under
2 seconds (with dynamic binding) to well over 4 seconds (with lexical
binding) in all my results.

Is this a known/accepted trade-off for the better byte-compiled
performance?  I'm assuming it's to do with overheads of lexical
closures.

The output npostavs generates indicates that it's largely (if
not solely) on account of a vast quantity of garbage collection.
Perhaps that is all the lexical environments being cleaned up?
(Although I would have thought that was a requirement for the
byte-compiled code as well, so I'm very much guessing.)

Can that be improved, or is this most likely to remain this way?




On 20/03/17 11:49, Phil Sainty wrote:
> Using npostavs's code:
> 
>      | DYNAMIC   | interpreted              | compiled
> --------------------------------------------------------------------
> 25.2 | recursive | 1.55s                    | 0.94s
>      | iterative | 1.70s                    | 1.06s
> --------------------------------------------------------------------
> 25.1 | recursive | 1.53s                    | 0.95s
>      | iterative | 1.87s                    | 1.06s
> --------------------------------------------------------------------
> 24.5 | recursive | 1.65s                    | 1.24s
>      | iterative | 1.43s                    | 0.95s
> --------------------------------------------------------------------
> 24.4 | recursive | 1.78s                    | 1.25s
>      | iterative | 1.59s                    | 1.02s
> --------------------------------------------------------------------
> 
> 
>      | LEXICAL   | interpreted              | compiled
> --------------------------------------------------------------------
> 25.2 | recursive | 4.27s (2.22s in 506 GCs) | 0.64s (0.03s in 6 GCs)
>      | iterative | 1.56s (0.10s in 23 GCs)  | 0.49s (0.03s in 6 GCs)
> --------------------------------------------------------------------
> 25.1 | recursive | 4.26s (2.21s in 506 GCs) | 0.64s (0.03s in 6 GCs)
>      | iterative | 1.58s (0.10s in 23 GCs)  | 0.50s (0.03s in 6 GCs)
> --------------------------------------------------------------------
> 24.5 | recursive | 4.11s (2.14s in 507 GCs) | 0.92s (0.03s in 6 GCs)
>      | iterative | 1.57s (0.09s in 22 GCs)  | 0.84s (0.03s in 7 GCs)
> --------------------------------------------------------------------
> 24.4 | recursive | 4.20s (2.08s in 506 GCs) | 0.91s (0.03s in 6 GCs)
>      | iterative | 1.65s (0.10s in 23 GCs)  | 0.82s (0.03s in 6 GCs)
> --------------------------------------------------------------------

Re: Execution speed

[Philippe Vaucher]

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

Looks this behavior appeared around 25.1:

$ for version in 24.3 24.4 24.5 25.1 25.2-rc2 master; do echo "-----
$version -----"; docker run -it -v $(pwd):/rootfs:ro --rm
silex/emacs:$version -Q --batch -l ir-test.el; done
----- 24.3 -----
Interpreted:  Iterative=1.104s; Recursive=0.966s
Bytecompiled: Iterative=0.482s; Recursive=0.633s
----- 24.4 -----
Interpreted:  Iterative=1.096s; Recursive=1.081s
Bytecompiled: Iterative=0.499s; Recursive=0.695s
----- 24.5 -----
Interpreted:  Iterative=1.083s; Recursive=1.087s
Bytecompiled: Iterative=0.497s; Recursive=0.694s
----- 25.1 -----
Interpreted:  Iterative=1.553s; Recursive=1.149s
Bytecompiled: Iterative=0.707s; Recursive=0.590s
----- 25.2-rc2 -----
Interpreted:  Iterative=1.521s; Recursive=1.159s
Bytecompiled: Iterative=0.698s; Recursive=0.602s
----- master -----
Interpreted:  Iterative=1.412s; Recursive=1.357s
Bytecompiled: Iterative=0.439s; Recursive=0.718s

[-- Attachment #2: Type: text/html, Size: 1186 bytes --]

Re: Performance of lexical closures in interpreted code? (was Re: Execution speed)

[Stefan Monnier]

> Tangentially, that performance hit on the interpreted recursive
> code with lexical-binding enabled is pretty severe!  From well under
> 2 seconds (with dynamic binding) to well over 4 seconds (with lexical
> binding) in all my results.
> Is this a known/accepted trade-off for the better byte-compiled
> performance?

Yes and no: I consider the performance of interpreted code to be
basically irrelevant, so I haven't paid any attention to it when
introducing the lexical-binding functionality: when performance matters,
the code should be compiled.

> I'm assuming it's to do with overheads of lexical closures.

As you can guess from the above, I don't really know.  But I'd be
surprised if it's the case.  A more likely reason is the handling of the
lexical environment (e.g. all the let-rebinding of the dynamically-scoped
var which holds the lexical environment).

> The output npostavs generates indicates that it's largely (if
> not solely) on account of a vast quantity of garbage collection.
> Perhaps that is all the lexical environments being cleaned up?

Quite likely, yes.

> (Although I would have thought that was a requirement for the
> byte-compiled code as well, so I'm very much guessing.)

The lexical environment is mostly "compiled away".  In the bytecode, new
lexical vars are just pushed on the stack, whereas in interpreted code
a new lexical var means adding a new element to an alist (i.e. 2 `cons`).

> Can that be improved, or is this most likely to remain this way?

Of course it can be improved.  It might take a fair bit of effort, tho
(e.g. I think to be more efficient, you'll likely want to pass the
lexical-env as an additional argument rather than by storing it in
a global (dynamically-scoped) var, but this will require changes to all
the special forms (grep for UNEVALLED)).


        Stefan

Re: Performance of lexical closures in interpreted code? (was Re: Execution speed)

[Stefan Monnier]

> Yes and no: I consider the performance of interpreted code to be
> basically irrelevant, so I haven't paid any attention to it when
> introducing the lexical-binding functionality: when performance matters,
> the code should be compiled.

BTW, the above could give the impression that I wrote that code, but
really the credit is due to Miles Bader (similarly, the changes in the
byte-compiler were written by Igor Kuzmin (as part of a summer project
under my supervision) rather than by me (Miles Bader had started on that
front as well, but using another approach which did not lend itself to
a summer project)).

What I did do is "the finishing touches", so I basically only claim
responsibility for the bugs, not the features.


        Stefan

Re: Execution speed

[Filipp Gunbin]

My results:

Interpreted:  Iterative=2.094s; Recursive=2.032s
Bytecompiled: Iterative=1.135s; Recursive=1.199s

macOS 10.12.3, tag emacs-25.2-rc2 built locally with ./autogen.sh &&
./configure --without-all --without-x --without-ns --with-xml2
--with-gnutls --with-zlib && make

Filipp