From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Robert Boyer Newsgroups: gmane.emacs.devel Subject: Re: Some thoughts about Emacs performance Date: Fri, 16 Feb 2024 10:31:42 -0600 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000b2cb9e06118249cb" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="2483"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Emacs developers To: Simon Leinen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Feb 16 17:37:25 2024 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1rb1DH-0000OV-TI for ged-emacs-devel@m.gmane-mx.org; Fri, 16 Feb 2024 17:37:24 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rb1Ch-0008Nb-Tu; Fri, 16 Feb 2024 11:36:47 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rb18T-0007MJ-40 for emacs-devel@gnu.org; Fri, 16 Feb 2024 11:32:25 -0500 Original-Received: from mail-ej1-x62f.google.com ([2a00:1450:4864:20::62f]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1rb18Q-0002oV-7t for emacs-devel@gnu.org; Fri, 16 Feb 2024 11:32:24 -0500 Original-Received: by mail-ej1-x62f.google.com with SMTP id a640c23a62f3a-a3d0d26182dso247127066b.1 for ; Fri, 16 Feb 2024 08:32:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1708101140; x=1708705940; darn=gnu.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=ZA7BPxP7abe9/VTU7g9zKoQ1cIRNaLNy5FnW3BfyK0U=; b=koL7MSxOg3NSutNyU/1uqPJSZnBbJk2xEYBEddAIAqL23gQ4hWG881ErFp4u3V+VEc 0JuANMh4XswTvKd8oJj39MXctxeqgXehRpOzxgIcqwJHjoKvF9IA05fegjxLRXi4f1uJ 1PsGt56hUVm2IdXaTF3HTBygBz3ptg1MXyAlghVLp1ovXRVZ5fqOURRVV+/yY2VbI+cu Q61NhqkVOl84Gysp0vQzir78/gm+fI1lgsuu5zczH3mVDMhUxE9QXUmpLEHIrOE46j5L NpQHwZHJAH08dqygZp2XDMYa2DqNl5Ybgkkcvmf33xIN11IlymuvqQ8cIegJqUzsNUHc Y5lA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1708101140; x=1708705940; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=ZA7BPxP7abe9/VTU7g9zKoQ1cIRNaLNy5FnW3BfyK0U=; b=JS71JDM4xkSBGLZVrYXhPjvLoqDU8mKf+Zcry3gBG7nXoY5Erdfv4ez0xMrnl9QF5e bJPnN/+tesK5MB/xmwE2znDyBz9V9IaqHZgH2fFwbSKlf4R0WRV9eDi4k5esGX049svF +u1LSu35BD1bK4hQHExmkxzWUqDJnBPveYa6L8rrWzBvRM5sYtNZlL2bzQskm6E/KFGw WALpljHQXzWTtCX3/tD3sYzKQG+ZOBnVqrqX1rsbnTmUx6/qv48mD+Qko6vNnh+0Lynt +UKzvTUTniIrAyJwzrstnyDp959E+zFwkXmrv+FeI8MeOk3pIucG8JUtTzHClvxMDkxd 7Dig== X-Gm-Message-State: AOJu0YwMW06lE6vW9h7e6Wq6aC5uOaAT0m2pfC9aIao4bhVEbPrKr6IF utLYeIsz239ylaJgkGciynnvV5DSb0QVUrxszrv/Q+TLrsHjqxsUm9sJRSpZBBaaQMl9DcwMBbn dZaWmaWN8CsWs9WfHLxOaApTx2SiECYoqcT4= X-Google-Smtp-Source: AGHT+IFjSHEItU04sRcVRwA0Xrw/pSWU1x7pDk0Vc5Mxirz/8lp1z3aHhHcEAewH4Mp1KRNJhphUrriwjedbM2NIdoY= X-Received: by 2002:a17:906:254d:b0:a36:c466:52ea with SMTP id j13-20020a170906254d00b00a36c46652eamr3580614ejb.75.1708101140136; Fri, 16 Feb 2024 08:32:20 -0800 (PST) In-Reply-To: Received-SPF: pass client-ip=2a00:1450:4864:20::62f; envelope-from=robertstephenboyer@gmail.com; helo=mail-ej1-x62f.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-Mailman-Approved-At: Fri, 16 Feb 2024 11:36:45 -0500 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:316251 Archived-At: --000000000000b2cb9e06118249cb Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Dear Simon, You note: On the other hand when sorting it again, i.e. when the vector is already fully sorter, Emacs is quite a bit faster than SBCL=E2=80=94maybe Emacs chose to optimize for partly-sorte= d vectors at the expense of a bit of performance for random input. You are so right. 'msa' kills 'stable sort' on a few examples, namely an array that is all 0's and an array that is 1, 2, 3, ... Below is some info on sorting arrays that are 21 million long. But I should mention that I regard what my 'msa' does to catch the easy cases may be nothing in comparison to what sorting pros can do. Best, Bob Running (test-msa-0 21,000,000). Timing (MSA TEST-MSA-AR1 '< :KEY 'CAR). WARNING: redefining COMMON-LISP-USER::KEY in DEFMACRO WARNING: redefining COMMON-LISP-USER::MSA-EQUAL in DEFMACRO WARNING: redefining COMMON-LISP-USER::MSA-PREDICATE in DEFMACRO WARNING: redefining COMMON-LISP-USER::MSA-1 in DEFUN Evaluation took: 3.334 seconds of real time 3.267129 seconds of total run time (2.323391 user, 0.943738 system) [ Run times consist of 0.154 seconds GC time, and 3.114 seconds non-GC time. ] 97.99% CPU 31 forms interpreted 115 lambdas converted 5,990,145,243 processor cycles 174,860,640 bytes consed Timing (STABLE-SORT TEST-MSA-AR2 '< :KEY 'CAR). Evaluation took: 12.729 seconds of real time 12.562949 seconds of total run time (11.935063 user, 0.627886 system) [ Run times consist of 0.232 seconds GC time, and 12.331 seconds non-GC time. ] 98.70% CPU 22,870,125,432 processor cycles 168,006,352 bytes consed Running (test-msa-ascending 21,000,000). Timing (MSA TEST-MSA-AR1 '< :KEY 'CAR). WARNING: redefining COMMON-LISP-USER::KEY in DEFMACRO WARNING: redefining COMMON-LISP-USER::MSA-EQUAL in DEFMACRO WARNING: redefining COMMON-LISP-USER::MSA-PREDICATE in DEFMACRO WARNING: redefining COMMON-LISP-USER::MSA-1 in DEFUN Evaluation took: 2.525 seconds of real time 2.514507 seconds of total run time (2.471494 user, 0.043013 system) 99.60% CPU 31 forms interpreted 115 lambdas converted 4,536,551,428 processor cycles 6,823,488 bytes consed Timing (STABLE-SORT TEST-MSA-AR2 '< :KEY 'CAR). Evaluation took: 12.914 seconds of real time 12.823063 seconds of total run time (12.407732 user, 0.415331 system) [ Run times consist of 0.227 seconds GC time, and 12.597 seconds non-GC time. ] 99.30% CPU 23,203,467,086 processor cycles 168,006,128 bytes consed On Fri, Feb 16, 2024 at 8:08=E2=80=AFAM Simon Leinen wrote: > Bob, > > welcome to the emacs-devel list, and thanks a lot for *your* wonderful > contributions (theorem prover, string search, and Lisp benchmarking - > I remember boyer.lisp from RPG's reference work[1]). > > On Thu, Feb 8, 2024 at 8:15=E2=80=AFAM Robert Boyer > wrote: > > > > Emacs 27.1 has a 'sort' function that takes longer than stable-sort of > SBCL. Maybe > > by a factor of 2. See also my attached file 'ms.lisp'. > > > > There may be a lot that can be improved in Emacs' > > handling of cl-loop, setf, elt, or cl-random. > > In this case, cl-random seems to be the main culprit for the slow > initialization=E2=80=94replacing that with plain "random" speeds it up by > about a factor of ten. There was some discussion on the list recently > about cl-random vs. random. The main functional difference is that > cl-random supports a defined state. But the performance difference may > be due more to the fact that random is written in C, and cl-random in > Lisp. > > As for the sorting itself, both Emacs and SBCL seem to use mergesort > in their implementations of (stable-)sort. Emacs's implementation is > written in C, SBCL's in Lisp. Performance is quite similar=E2=80=94on my > system (Apple Macbook Air M2) Emacs takes about 35% longer to sort a > million random numbers than SBCL. (On the other hand when sorting it > again, i.e. when the vector is already fully sorter, Emacs is quite a > bit faster than SBCL=E2=80=94maybe Emacs chose to optimize for partly-sor= ted > vectors at the expense of a bit of performance for random input.) > > In general, the Emacs Lisp runtime system and compiler(s) aren't as > optimized as SBCL for general Lisp use. But it gets quite close! > > On the other hand, Emacs has editor-specific code (e.g. redisplay) and > data structures (e.g. buffers) which are highly optimized and partly > written in C. But it doesn't try to be a standalone platform for > performance-oriented Lisp developers. Of course Emacs is very > suitable as a Software Development Environment for systems such as > SBCL, and there are many good integration options=E2=80=94personally I us= e the > SLIME package these days. > > Best regards, and enjoy Lisping in Emacs! > -- > Simon. > > > ;; First some Emacs, with times on my $100 Chromebook. > > > > (setq n 6) > > (defun make-random-array (n) > > (let ((a (make-vector n 0))) > > (cl-loop for i below n do > > (setf (elt a i) (cl-random 1000000))) > > a)) > > (byte-compile 'make-random-array) > > (benchmark '(setq foo (make-random-array (expt 10 n))) 1) -- 2.3 second= s > > (benchmark '(sort foo '<) 1) -- 1 second > > > > ;; Second some Common Lisp, with times for SBCL on my $100 Chromebook. > > > > (defparameter n 6) > > (defun make-random-array (n) > > (declare (fixnum n)) > > (let ((a (make-array n))) > > (declare (type array a)) > > (loop for i fixnum below n do > > (setf (aref a i) (random most-positive-fixnum))) > > a)) > > (time (defparameter foo (make-random-array (expt 10 n)))) -- .041 > seconds > > (time (progn (stable-sort foo '<) nil)) -- .45 seconds > > > > Thanks so much for Emacs, which is so great that I cannot put it > > into words. > > > > Bob > > > [1] https://dreamsongs.com/Files/Timrep.pdf > --000000000000b2cb9e06118249cb Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Dear Simon,
You note:=C2=A0

<= /div>On the other hand when sorting it
again, i.e. when the vector is al= ready fully sorter, Emacs is quite a
bit faster than SBCL=E2=80=94maybe = Emacs chose to optimize for partly-sorted
vectors at the expense of a bi= t of performance for random input.

You are so right.= =C2=A0 'msa' kills 'stable sort' on a few examples, namely = an array
that is all 0's and an array that is 1, 2, 3, ...

Below=C2=A0 is some info on sorting arrays that are = 21 million long.

But I should mention that I regar= d what my 'msa' does to catch the easy cases may be nothing in comp= arison to what sorting pros can do.

Best,

Bob

Running (test-msa-0 21,000,00= 0).
Timing (MSA TEST-MSA-AR1 '< :KEY 'CAR).
WARNING: redef= ining COMMON-LISP-USER::KEY in DEFMACRO
WARNING: redefining COMMON-LISP-= USER::MSA-EQUAL in DEFMACRO
WARNING: redefining COMMON-LISP-USER::MSA-PR= EDICATE in DEFMACRO
WARNING: redefining COMMON-LISP-USER::MSA-1 in DEFUN=
Evaluation took:
=C2=A0 3.334 seconds of real time
=C2=A0 3.26712= 9 seconds of total run time (2.323391 user, 0.943738 system)
=C2=A0 [ Ru= n times consist of 0.154 seconds GC time, and 3.114 seconds non-GC time. ]<= br>=C2=A0 97.99% CPU
=C2=A0 31 forms interpreted
=C2=A0 115 lambdas c= onverted
=C2=A0 5,990,145,243 processor cycles
=C2=A0 174,860,640 byt= es consed
=C2=A0

Timing (STABLE-SORT TEST-MSA-AR2 '< :KEY= 'CAR).
Evaluation took:
=C2=A0 12.729 seconds of real time
= =C2=A0 12.562949 seconds of total run time (11.935063 user, 0.627886 system= )
=C2=A0 [ Run times consist of 0.232 seconds GC time, and 12.331 second= s non-GC time. ]
=C2=A0 98.70% CPU
=C2=A0 22,870,125,432 processor cy= cles
=C2=A0 168,006,352 bytes consed
=C2=A0

Running (test-msa= -ascending 21,000,000).
Timing (MSA TEST-MSA-AR1 '< :KEY 'CAR= ).
WARNING: redefining COMMON-LISP-USER::KEY in DEFMACRO
WARNING: red= efining COMMON-LISP-USER::MSA-EQUAL in DEFMACRO
WARNING: redefining COMM= ON-LISP-USER::MSA-PREDICATE in DEFMACRO
WARNING: redefining COMMON-LISP-= USER::MSA-1 in DEFUN
Evaluation took:
=C2=A0 2.525 seconds of real ti= me
=C2=A0 2.514507 seconds of total run time (2.471494 user, 0.043013 sy= stem)
=C2=A0 99.60% CPU
=C2=A0 31 forms interpreted
=C2=A0 115 lam= bdas converted
=C2=A0 4,536,551,428 processor cycles
=C2=A0 6,823,488= bytes consed
=C2=A0

Timing (STABLE-SORT TEST-MSA-AR2 '< = :KEY 'CAR).
Evaluation took:
=C2=A0 12.914 seconds of real time=C2=A0 12.823063 seconds of total run time (12.407732 user, 0.415331 syst= em)
=C2=A0 [ Run times consist of 0.227 seconds GC time, and 12.597 seco= nds non-GC time. ]
=C2=A0 99.30% CPU
=C2=A0 23,203,467,086 processor = cycles
=C2=A0 168,006,128 bytes consed
=C2=A0=C2=A0


On Fri, Feb 16, 2024 at 8:08=E2=80=AFAM Simon Leinen = <simon.leinen@gmail.com>= ; wrote:
Bob,
welcome to the emacs-devel list, and thanks a lot for *your* wonderful
contributions (theorem prover, string search, and Lisp benchmarking -
I remember boyer.lisp from RPG's reference work[1]).

On Thu, Feb 8, 2024 at 8:15=E2=80=AFAM Robert Boyer
<rober= tstephenboyer@gmail.com> wrote:
>
> Emacs 27.1 has a 'sort' function that takes longer than stable= -sort of SBCL. Maybe
> by a factor of 2. See also my attached file 'ms.lisp'.
>
> There may be a lot that can be improved in Emacs'
> handling of cl-loop, setf, elt, or cl-random.

In this case, cl-random seems to be the main culprit for the slow
initialization=E2=80=94replacing that with plain "random" speeds = it up by
about a factor of ten.=C2=A0 There was some discussion on the list recently=
about cl-random vs. random. The main functional difference is that
cl-random supports a defined state. But the performance difference may
be due more to the fact that random is written in C, and cl-random in
Lisp.

As for the sorting itself, both Emacs and SBCL seem to use mergesort
in their implementations of (stable-)sort.=C2=A0 Emacs's implementation= is
written in C, SBCL's in Lisp. Performance is quite similar=E2=80=94on m= y
system (Apple Macbook Air M2) Emacs takes about 35% longer to sort a
million random numbers than SBCL.=C2=A0 (On the other hand when sorting it<= br> again, i.e. when the vector is already fully sorter, Emacs is quite a
bit faster than SBCL=E2=80=94maybe Emacs chose to optimize for partly-sorte= d
vectors at the expense of a bit of performance for random input.)

In general, the Emacs Lisp runtime system and compiler(s) aren't as
optimized as SBCL for general Lisp use.=C2=A0 But it gets quite close!

On the other hand, Emacs has editor-specific code (e.g. redisplay) and
data structures (e.g. buffers) which are highly optimized and partly
written in C.=C2=A0 But it doesn't try to be a standalone platform for<= br> performance-oriented Lisp developers.=C2=A0 Of course Emacs is very
suitable as a Software Development Environment for systems such as
SBCL, and there are many good integration options=E2=80=94personally I use = the
SLIME package these days.

Best regards, and enjoy Lisping in Emacs!
--
Simon.

> ;; First some Emacs, with times on my $100 Chromebook.
>
> (setq n 6)
> (defun make-random-array (n)
>=C2=A0 =C2=A0(let ((a (make-vector n 0)))
>=C2=A0 =C2=A0 =C2=A0(cl-loop for i below n do
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (setf (elt a i) (cl-ra= ndom 1000000)))
>=C2=A0 =C2=A0 =C2=A0a))
> (byte-compile 'make-random-array)
> (benchmark '(setq foo (make-random-array (expt 10 n))) 1) -- 2.3 s= econds
> (benchmark '(sort foo '<) 1) -- 1 second
>
> ;; Second some Common Lisp, with times for SBCL on my $100 Chromebook.=
>
> (defparameter n 6)
> (defun make-random-array (n)
>=C2=A0 =C2=A0(declare (fixnum n))
>=C2=A0 =C2=A0(let ((a (make-array n)))
>=C2=A0 =C2=A0 =C2=A0(declare (type array a))
>=C2=A0 =C2=A0 =C2=A0(loop for i fixnum below n do
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(setf (aref a i) (random most-= positive-fixnum)))
>=C2=A0 =C2=A0 =C2=A0a))
> (time (defparameter foo (make-random-array (expt 10 n))))=C2=A0 -- .04= 1 seconds
> (time (progn (stable-sort foo '<) nil)) -- .45 seconds
>
> Thanks so much for Emacs, which is so great that I cannot put it
> into words.
>
> Bob


[1] https://dreamsongs.com/Files/Timrep.pdf
--000000000000b2cb9e06118249cb--