From mboxrd@z Thu Jan  1 00:00:00 1970
Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail
From: Stefan Monnier <monnier@iro.umontreal.ca>
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: <jwv4l7xm3uc.fsf-monnier+emacs@gnu.org>
References: <20190213212413.868.40960@vcs0.savannah.gnu.org>
	<20190213212415.148B9209D7@vcs0.savannah.gnu.org>
	<0ba3ca47-c7d6-a608-536e-94784ba3384b@yandex.ru>
	<CALDnm53-7bkf0+c_pf1JNzkiRpfyuowONXXChTEfuzW_Ln7aXA@mail.gmail.com>
	<jwvva0j6jsb.fsf-monnier+emacs@gnu.org>
	<aeafbcc5-0466-af36-e646-22aa0ef1544c@yandex.ru>
	<CALDnm52k-NMs8jfUHj2UoT=AFj3byQZZ8HU-axOqz0n0bRf1Gw@mail.gmail.com>
	<4f4e9ccd-b152-2b37-cad2-6c96b0a64d84@yandex.ru>
	<CALDnm53WS=T4A1x-sMAwiEf3xYwza1v79YQ=nvp17o9c=VvpAw@mail.gmail.com>
	<646c8d35-89a7-b12f-8a78-b05e6d8f781c@yandex.ru>
	<CALDnm53_N8_A0Fz7Ck4AjTZQmYxAaLRtuec8+DhweYR5DNmx5g@mail.gmail.com>
	<ba298a2e-3ced-8cf8-8552-1a0ddbee4885@yandex.ru>
	<m1lg1950k1.fsf@gmail.com> <jwv8sx9rbuv.fsf-monnier+emacs@gnu.org>
	<m1sgvh2rcq.fsf@gmail.com>
	<e877f54a-c55f-074e-672c-fef1d0c890e8@yandex.ru>
	<CALDnm51Sf9r6B=Bcby-4QD8VsTFvbmMbySrxy7DE66qfWAJrHw@mail.gmail.com>
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 <emacs-devel@gnu.org>, Dmitry Gutov <dgutov@yandex.ru>
To: =?windows-1252?B?Sm/jbyBU4XZvcmE=?= <joaotavora@gmail.com>
Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Mar 21 02:14:57 2019
Return-path: <emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org>
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 <emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org>)
	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 <emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org>)
	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 <monnier@iro.umontreal.ca>) 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 <monnier@iro.umontreal.ca>) 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 <monnier@iro.umontreal.ca>)
	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 <emacs-devel@gnu.org>; 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 <emacs-devel@gnu.org>;
	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: <CALDnm51Sf9r6B=Bcby-4QD8VsTFvbmMbySrxy7DE66qfWAJrHw@mail.gmail.com>
	(=?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." <emacs-devel.gnu.org>
List-Unsubscribe: <https://lists.gnu.org/mailman/options/emacs-devel>,
	<mailto:emacs-devel-request@gnu.org?subject=unsubscribe>
List-Archive: <http://lists.gnu.org/archive/html/emacs-devel/>
List-Post: <mailto:emacs-devel@gnu.org>
List-Help: <mailto:emacs-devel-request@gnu.org?subject=help>
List-Subscribe: <https://lists.gnu.org/mailman/listinfo/emacs-devel>,
	<mailto:emacs-devel-request@gnu.org?subject=subscribe>
Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org
Original-Sender: "Emacs-devel" <emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org>
Xref: news.gmane.org gmane.emacs.devel:234440
Archived-At: <http://permalink.gmane.org/gmane.emacs.devel/234440>

> 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