From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier 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 21:14:39 -0400 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: text/plain Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="154637"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) Cc: emacs-devel , Dmitry Gutov To: =?windows-1252?B?Sm/jbyBU4XZvcmE=?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Mar 21 02:14:57 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 1h6mIH-000e1R-LX for ged-emacs-devel@m.gmane.org; Thu, 21 Mar 2019 02:14:53 +0100 Original-Received: from localhost ([127.0.0.1]:57706 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h6mIG-0001Mf-JD for ged-emacs-devel@m.gmane.org; Wed, 20 Mar 2019 21:14:52 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:60425) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1h6mI7-0001LX-24 for emacs-devel@gnu.org; Wed, 20 Mar 2019 21:14:44 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1h6mI6-00070I-8N for emacs-devel@gnu.org; Wed, 20 Mar 2019 21:14:43 -0400 Original-Received: from mail01.iro.umontreal.ca ([132.204.25.201]:56680) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1h6mI5-0006zA-Ra for emacs-devel@gnu.org; Wed, 20 Mar 2019 21:14:42 -0400 Original-Received: from mail01.iro.umontreal.ca (mail01.iro.umontreal.ca [127.0.0.1]) by mail01.iro.umontreal.ca (Postfix) with ESMTP id 36DF880FE45A for ; Wed, 20 Mar 2019 21:14:41 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; h=content-type:content-type:mime-version:user-agent:in-reply-to :date:date:references:message-id:subject:subject:to:from:from; s=dkim; t=1553130880; x=1553994881; bh=b7DbLS81rU3Ye4CfSZaF3jF5 Sgn02dpnZ/Qp30BeiEs=; b=jLdFsi+PJpHdA8neghXmoxIbhjSeMToBUCrKjhk/ uowFS33cPMw7H2PWXhvCrdrES1f6XRmSc8ShrhBMJgwtxck4139VXsLHdUGgUGh9 g7DN8BS8ib/xdzP6hhhHP4AJh7/5cfO/FbvHUB6/GeWLPmTMzayMFm732j5H6Q5t /0GNNpHBiTDDuWWjrRotpXqLS/VFo6KIeUphAEgUOwRQbBIx2pMYu8a4VBAVSIwF /EiiDMUF0tUW2bWaWm+d2yPeAQLXVw/hhOlPco+ptQ1fjP6DgzQA+B2MV8B4AMhz We1LQmlZgrVTQaAeRcPC6dxTsGZVkHJolblhxEfIrEBUJA== X-Virus-Scanned: amavisd-new at iro.umontreal.ca Original-Received: from mail01.iro.umontreal.ca ([127.0.0.1]) by mail01.iro.umontreal.ca (mail01.iro.umontreal.ca [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vOz-y-ptPcvy for ; Wed, 20 Mar 2019 21:14:40 -0400 (EDT) Original-Received: from pastel (75-119-242-252.dsl.teksavvy.com [75.119.242.252]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 1841180FE43D; Wed, 20 Mar 2019 21:14:40 -0400 (EDT) In-Reply-To: (=?windows-1252?Q?=22Jo=E3o_T=E1vora=22's?= message of "Wed, 20 Mar 2019 23:25:08 +0000") X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 132.204.25.201 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:234440 Archived-At: > 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) Completing the empty string is the worst case for the "highlight" part, but not for the actual filtering. For the filtering, you may like to try completing a string like "eeeeel": `basic` will very quickly return the empty set, whereas flex may take a lot longer, especially if your completion table contains some long strings with lots and lots of `e`s in it but no `l` (that should be enough to trigger the exponential behavior of the backtracking regexp matcher) Stefan