From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Newsgroups: gmane.emacs.bugs Subject: bug#48841: fido-mode is slower than ido-mode with similar settings Date: Mon, 7 Jun 2021 09:52:59 +0100 Message-ID: References: <87eedgy7pt.fsf@gmail.com> <1f659c88-4d9d-8fc9-733a-5e6068f9ed4a@yandex.ru> <87a6o3x5j7.fsf@gmail.com> <87y2bnv5xc.fsf@gmail.com> <35be6652-9c8d-ee21-e9eb-9598ad6777eb@yandex.ru> Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000094bd205c4292c46" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="37899"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Stefan Monnier , 48841@debbugs.gnu.org To: Dmitry Gutov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Mon Jun 07 10:54:33 2021 Return-path: Envelope-to: geb-bug-gnu-emacs@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 1lqB1j-0009fz-1W for geb-bug-gnu-emacs@m.gmane-mx.org; Mon, 07 Jun 2021 10:54:31 +0200 Original-Received: from localhost ([::1]:44612 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lqB1i-0002mU-3b for geb-bug-gnu-emacs@m.gmane-mx.org; Mon, 07 Jun 2021 04:54:30 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:54406) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lqB1H-0002mI-9K for bug-gnu-emacs@gnu.org; Mon, 07 Jun 2021 04:54:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:42881) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lqB1G-0006EV-Fr for bug-gnu-emacs@gnu.org; Mon, 07 Jun 2021 04:54:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1lqB1G-0002gA-EM for bug-gnu-emacs@gnu.org; Mon, 07 Jun 2021 04:54:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: =?UTF-8?Q?Jo=C3=A3o_?= =?UTF-8?Q?T=C3=A1vora?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 07 Jun 2021 08:54:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 48841 X-GNU-PR-Package: emacs Original-Received: via spool by 48841-submit@debbugs.gnu.org id=B48841.162305600410255 (code B ref 48841); Mon, 07 Jun 2021 08:54:02 +0000 Original-Received: (at 48841) by debbugs.gnu.org; 7 Jun 2021 08:53:24 +0000 Original-Received: from localhost ([127.0.0.1]:54427 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lqB0d-0002fK-Lp for submit@debbugs.gnu.org; Mon, 07 Jun 2021 04:53:23 -0400 Original-Received: from mail-pf1-f177.google.com ([209.85.210.177]:41769) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1lqB0b-0002f3-0i for 48841@debbugs.gnu.org; Mon, 07 Jun 2021 04:53:22 -0400 Original-Received: by mail-pf1-f177.google.com with SMTP id x73so12576976pfc.8 for <48841@debbugs.gnu.org>; Mon, 07 Jun 2021 01:53:20 -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=aM3peZxgz3qG7mfQMQnJl8cjmMJ9dxCDWM2MeMZFHAg=; b=j7Ur1G2B/HTudQdYEvzgBqDlqiUy/xTZDBsuNbNzgLTALKQlYA8TgdALNC2D+CV2u2 sBp6CPARKJLoomQMaXC3io9MJ2tjZx4l7jWb2NuREw5PNeFF4pSDMi5mBMQmjija4y4D QuH5pTtkUafPpbFU7fR1yJXiKG62p/FtPPM61arr5OOms+0ptd7cbeh1IBTD+jCHywx+ RXCTkUOqRgQg6M1lDvFlKvZ960jIr4se3V6N+RfQj8VBPa3u2pytrrJlSLY6AUILelFx vEA5bU2lMhLg2Flb+9FzciermEpvClpCpAKHjrmsVI96r+/oCx4LWMRrr1ystk/cVLhA 4jnw== 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=aM3peZxgz3qG7mfQMQnJl8cjmMJ9dxCDWM2MeMZFHAg=; b=jRsXrBRBhZkCRP/LbdnXNRxsFKB3xtuPZHlviS7cHbEllbE6Q7cO131PblHeFHLmu2 h0TO1TuaDXho1eNs0buXNlOLcC4VKnmdZaKnx2RcE/bPOrI5DwoPIjhkasr5ZfO0hp6s /fA9grfgKd3xTu52bhM6K7vSjo/YCbMzZQ8TfQ+4BBmj/F6kcma8OgjX08J0/xv/d798 3OC7H13DtxFXnQj0qN1odtcKH5Y3kowM2WH6R2bL5rumjc9IQWb41zAmYyGspmdCaTli HqkpN/6K9MHQCwqWYvu4IJsiwA28/x9i8qV55Ah4GweOMnHVQrHFlElGBR9tGDWUSSFT MZZQ== X-Gm-Message-State: AOAM531mCrZNm4yiZ7k/ej2RCJZoEbNqD7iqWlVy9XfDqiV7n+lo9AnA 0AKsa2dsovEr0xmVFJTD7/Pdbi9ev/tNEzV9IAc= X-Google-Smtp-Source: ABdhPJyGCFz5qsXjNnFAQnQoiim6k0rqfmqFIHlCbAQHUuYycHJXBYw7J23G9RD4wtEwUNQ07u2Qv3sqeJLrnzqV6Zk= X-Received: by 2002:a65:63d2:: with SMTP id n18mr16905363pgv.447.1623055995062; Mon, 07 Jun 2021 01:53:15 -0700 (PDT) In-Reply-To: X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:208177 Archived-At: --000000000000094bd205c4292c46 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Mon, Jun 7, 2021, 01:11 Dmitry Gutov wrote: > On 07.06.2021 02:49, Jo=C3=A3o T=C3=A1vora wrote: > > > Same result, indeed. We should note, though, that > > completion-pcm--hilit-commonality has some steps that were added > > together with the 'flex' style, for it to work. > > > > > > But nothing algorithmically aberrant, I think. > > Just some stuff adding work to GC, I think. > O(n) stuff being a property and a number on each string, small in comparison to the string. Maybe moving all of them to parameters and return values (making it a > static function and having the caller manage state) would help, I > haven't tried that exactly. > Normally, in those adventures you end up with the same allocations somewhere else, and uglier code. But you can try. > Might be noise, or you might be thrashing of CPU caches, who knows? If > > the string length is on the same cache line as the contents of the > > string you're reading, then evicting that to go read the value of a > > boxed integer somewhere radically different is slow. > > But the string value is boxed as well, right? The key is locality. If the string length and data happen to live nearby in memory (in the same box, so to speak), there's a decent chance that reading one brings the other into the cache, and you get a nice hit depending on your subsequent operation. Here I'm just speculating, as I said. In managed languages such as Lisps, it's somewhat unpredictable. It's also always hardware dependent. Though given C/C++, a known processor and the right application, this will make a world of a difference, and will yield truly "weird" results (which arent weird at all after you understand the logic). Like, for example a vector being much better at sorted insertion than a linked list. (!) Look it up. Bjarne Stroustrup has one of those talks. Jo=C3=A3o --000000000000094bd205c4292c46 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Mon, Jun 7, 2021, 01:11 Dmitry Gutov <dgutov@yandex.ru> wrote:
On 07.06.2021 02:49, Jo=C3=A3o T=C3=A1vora wrote:

>=C2=A0 =C2=A0 =C2=A0Same result, indeed. We should note, though, that >=C2=A0 =C2=A0 =C2=A0completion-pcm--hilit-commonality has some steps th= at were added
>=C2=A0 =C2=A0 =C2=A0together with the 'flex' style, for it to w= ork.
>
>
> But nothing algorithmically aberrant, I think.

Just some stuff adding work to GC, I think.

O(n) stuff being a property and = a number on each string, small in comparison to the string.

Maybe moving all of them to parameters and return values (making it a
static function and having the caller manage state) would help, I
haven't tried that exactly.

Normally, in those adventures you end up wit= h the same allocations somewhere else, and uglier code. But you can try.

> Might be noise, or you might be thrashing of CPU caches, who knows? If=
> the string length is on the same cache line as the contents of the > string you're reading, then evicting that to go read the value of = a
> boxed integer somewhere radically different is slow.

But the string value is boxed as well, right?=C2=A0

The key is locality. If the = string length and data happen to live nearby in memory (in the same box, so= to speak), there's a decent chance that reading one brings the other i= nto the cache, and you get a nice hit depending on your subsequent operatio= n.=C2=A0

Here I'm ju= st speculating, as I said. In managed languages such as Lisps, it's som= ewhat unpredictable. It's also always hardware dependent. Though given = C/C++, a known processor and the right application, this will make a world = of a difference, and will yield truly "weird" results (which aren= t weird at all after you understand the logic). Like, for example a vector = being much better at sorted insertion than a linked list. (!) Look it up. B= jarne Stroustrup has one of those talks.

<= div dir=3D"auto">Jo=C3=A3o

--000000000000094bd205c4292c46--