From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: =?UTF-8?B?Sm/Do28gVMOhdm9yYQ==?= Newsgroups: gmane.emacs.devel Subject: Re: [Emacs-diffs] master b0e318d 2/2: Score flex-style completions according to match tightness Date: Wed, 20 Mar 2019 23:25:08 +0000 Message-ID: References: <20190213212413.868.40960@vcs0.savannah.gnu.org> <20190213212415.148B9209D7@vcs0.savannah.gnu.org> <0ba3ca47-c7d6-a608-536e-94784ba3384b@yandex.ru> <4f4e9ccd-b152-2b37-cad2-6c96b0a64d84@yandex.ru> <646c8d35-89a7-b12f-8a78-b05e6d8f781c@yandex.ru> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="0000000000006ecb5b05848eefe0" Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="237421"; mail-complaints-to="usenet@blaine.gmane.org" Cc: Stefan Monnier , emacs-devel To: Dmitry Gutov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Mar 21 00:25:33 2019 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1h6kaS-000zd0-2j for ged-emacs-devel@m.gmane.org; Thu, 21 Mar 2019 00:25:32 +0100 Original-Received: from localhost ([127.0.0.1]:56524 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h6kaR-0002uF-27 for ged-emacs-devel@m.gmane.org; Wed, 20 Mar 2019 19:25:31 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:45621) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h6kaJ-0002tk-7q for emacs-devel@gnu.org; Wed, 20 Mar 2019 19:25:24 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1h6kaI-0007o5-51 for emacs-devel@gnu.org; Wed, 20 Mar 2019 19:25:23 -0400 Original-Received: from mail-qt1-x82f.google.com ([2607:f8b0:4864:20::82f]:39525) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1h6kaH-0007lV-Lw for emacs-devel@gnu.org; Wed, 20 Mar 2019 19:25:22 -0400 Original-Received: by mail-qt1-x82f.google.com with SMTP id t28so4684846qte.6 for ; Wed, 20 Mar 2019 16:25:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=schZm2wyFN1xC+x9JuhZTN4l1GsOGj7AYGDxahln4+k=; b=MBUC8ayQG9Ua2H8HWi3doB0xEE9WssOLigQS3C6JkNzyItJ4iJ1grRhUXuXbdvYlec tyI9MNVEylO4jhYy1f3EDro2jjbHvtC855Rk1KpmM+T9zYsSMVlSZnZPPNRHSmZaRPZe OZISwE2LRfkPHAZtVZCK/zkvX4LIRRaFhgK2ZSgd5wpjFPWrA6Wpy/5TV8lujNwA4rlM iAMdsI9i99qkk9GxWInmy8HwsAl4DVXUDeMb2KSDd4DYXIHINmk2L+8oP6XtMh+xVIln ylfY5BYX2II5XBzn8U7JnYkBDPrqB3rL3D9NYZwp7+yE7XrFlEUBmmXy4GBjW81QUH9C IMHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=schZm2wyFN1xC+x9JuhZTN4l1GsOGj7AYGDxahln4+k=; b=gIK6YW9QItuF7G0TuuI8wp3g1aHum4lu7BZOHVuF63DyhlCzDZlsnaBz5t7NRQIV+Q Kj+CLcVKIVSolj/i8qqTwhO6Puxji0cxkXI3v8izr4ZOOg3Ss9w81t7bTFS9ueeUjRnW IinYTuog/eUCaLH4d1Bg18EdJefk/RGy5j2n+tsUZZfkOTdSW1mbXFdrFE8wY/cirY8c 31nZHpmGGvzLu0sgBpRy++qnfPDeIL1E9SQayKKJeC5Z0YaeJ7RFoXlZlekraeP5xaSi 95CRR789er/mER8ij6Dren8PvYVINpgSPVAImW3J9ca/V1c+cx/m0kizFIVWLj7/r5qM F3Xg== X-Gm-Message-State: APjAAAVReb72Jq0HBn3/ZVog3HHYhMnwF+O4kDXtHKZdV0Vy/mHtq7LW mGf8516IHVympxM0haJOu1Pj1JErq7uoeto9MQA= X-Google-Smtp-Source: APXvYqyXFzP2tFGS+rThZWugjkFaC6FlWtatI9Vk6YrwxxKvhgu6j3bPn17E/UOdO+dwN89VI4m0TtVk8zgKPdByc5w= X-Received: by 2002:aed:302f:: with SMTP id 44mr442878qte.178.1553124320790; Wed, 20 Mar 2019 16:25:20 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4864:20::82f X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 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.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:234436 Archived-At: --0000000000006ecb5b05848eefe0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable [Again, sorry for the double email Dmitry] On Wed, Mar 20, 2019 at 9:58 PM Dmitry Gutov wrote: > On 20.03.2019 23:00, Jo=C3=A3o T=C3=A1vora wrote: > > but I do think that flex can be > > made faster so that it is only, say 1.2x, slower than basic in the wors= t > > case > > When collection contains very long strings (e.g. a list of project files > with VCR cassettes, if you know what I mean), flex can unavoidably > become noticeably slower. > Yes, but we've established that it's 2x slower than "basic" in the worse cases of flex, at least for the collection in Emacs's obarray, which is a nice benchmark: (benchmark-run-compiled 5 (let ((completion-styles '(flex))) (completion-all-completions "" obarray nil 0))); (6.105048999999999 15 3.9362529999999936) (benchmark-run-compiled 5 (let ((completion-styles '(basic))) (completion-all-completions "" obarray nil 0))); (3.322738 10 2.0635609999999787) So it doesn't seem like an impossible task to make it as fast as "basic" is now, especially for these cases of short input strings. For example, since (equal (let ((completion-styles '(flex))) (completion-all-completions "" obarray nil 0)) (let ((completion-styles '(basic))) (completion-all-completions "" obarray nil 0))) is t, the null-string case, which is probably trivial to optimize ;-), would bring a noticeable improvement to icomplete's UI, and probably company's. Of course for pathological (but reasonable) input, it will often be much much slower, because by nature flex matches much more candidates and manages around much more data. (benchmark-run-compiled 5 (let ((completion-styles '(flex))) (completion-all-completions "eeee" obarray nil 0))); (2.068143 5 1.151679999999999) (benchmark-run-compiled 5 (let ((completion-styles '(basic))) (completion-all-completions "eeee" obarray nil 0))); (0.333021 0 0.0) (benchmark-run-compiled 5 (let ((completion-styles '(flex))) (completion-all-completions "kill" obarray nil 0))); (0.7081639999999999 1 0.26370900000000574) (benchmark-run-compiled 5 (let ((completion-styles '(basic))) (completion-all-completions "kill" obarray nil 0))); (0.444207 0 0.0) So while the slowdown due to a larger amount of candidates is something we probably won't get around easily, a significant part of the slowdown seems to be the matching logic, and that can probably be optimized, with nice user-visible consequences. Jo=C3=A3o --0000000000006ecb5b05848eefe0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
[Again, sorry for the double email D= mitry]

O= n Wed, Mar 20, 2019 at 9:58 PM Dmitry Gutov <dgutov@yandex.ru> wrote:
=
On 20.03.2019 23:00, Jo=C3=A3o T=C3=A1vora wrote= :
> but I do think that flex can be
> made faster so that it is only, say 1.2x, slower than basic in the wor= st
> case

When collection contains very long strings (e.g. a list of project files with VCR cassettes, if you know what I mean), flex can unavoidably
become noticeably slower.

Yes, b= ut we've established that it's 2x slower than "basic" in = the
worse cases of flex, at least for the collection in Emacs= 9;s
obarray, which is a nice benchmark:

(benchmark-run-compiled 5
=C2=A0 (let ((completion-styles '= (flex)))
=C2=A0=C2=A0=C2=A0 (completion-all-completions "" oba= rray nil 0))); (6.105048999999999 15 3.9362529999999936)

(benchmark-= run-compiled 5
=C2=A0 (let ((completion-styles '(basic)))
=C2=A0= =C2=A0=C2=A0 (completion-all-completions "" obarray nil 0))); (3.= 322738 10 2.0635609999999787)

So it doesn't se= em like an impossible task to make it as fast as "basic"
is now, especially for these cases of short input strings. For examp= le, since

(equal (let ((completion-styles '(fl= ex)))
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 (completion-all-c= ompletions "" obarray nil 0))
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0 (let ((completion-styles '(basic)))
=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0 (completion-all-completions "" obarray n= il 0)))

is t, the null-string case, which is proba= bly trivial to optimize ;-), would
bring a noticeable improv= ement to icomplete's UI, and probably
company's.
=

Of course for pathological (but reasonable) input= , it will often
be much much slower, because by nature flex = matches much
more candidates and manages around much more data.

(benchmark-run-compiled 5
= =C2=A0 (let ((completion-styles '(flex)))
=C2=A0=C2=A0=C2=A0 (comple= tion-all-completions "eeee" obarray nil 0))); (2.068143 5 1.15167= 9999999999)

(benchmark-run-compiled 5
=C2=A0 (let ((completion-st= yles '(basic)))
=C2=A0=C2=A0=C2=A0 (completion-all-completions "= ;eeee" obarray nil 0))); (0.333021 0 0.0)

(benchmark-run-compiled 5
=C2= =A0 (let ((completion-styles '(flex)))
=C2=A0=C2=A0=C2=A0 (completio= n-all-completions "kill" obarray nil 0))); (0.7081639999999999 1 = 0.26370900000000574)

(benchmark-run-compiled 5
=C2=A0 (let ((comp= letion-styles '(basic)))
=C2=A0=C2=A0=C2=A0 (completion-all-completi= ons "kill" obarray nil 0))); (0.444207 0 0.0)

So while the slowdown due= to a larger amount of candidates is something
we probably won't get around easily, a significant part of the= slowdown
seems to be the matching log= ic, and that can probably be optimized,
with nice user-visible consequences.
Jo=C3=A3o
--0000000000006ecb5b05848eefe0--