From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.bugs Subject: bug#62352: Very slow scroll-down-line with a lot of text properties Date: Sun, 26 Mar 2023 07:55:08 +0300 Message-ID: <834jq8az83.fsf@gnu.org> References: <51545b85-029c-a6ff-f733-e486f261f6c0@gmail.com> <83355x7sx2.fsf@gnu.org> <08b5f766dd5d453016a7@heytings.org> <83sfdtcab8.fsf@gnu.org> <83h6u9c89f.fsf@gnu.org> <834jq9c4kb.fsf@gnu.org> <83pm8wby5e.fsf@gnu.org> <38eca973-0d1b-cd3b-1602-00d22c8c1afe@gmail.com> <83ileobu0t.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="13851"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 62352@debbugs.gnu.org, gregory@heytings.org To: geza.herman@gmail.com Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Mar 26 06:56:19 2023 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 1pgIQV-0003Lz-3f for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 26 Mar 2023 06:56:19 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pgIQH-0001F3-IG; Sun, 26 Mar 2023 00:56:05 -0400 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 1pgIQF-0001Ec-95 for bug-gnu-emacs@gnu.org; Sun, 26 Mar 2023 00:56:03 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pgIQE-0000r1-P9 for bug-gnu-emacs@gnu.org; Sun, 26 Mar 2023 00:56:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1pgIQE-0000Nf-C9 for bug-gnu-emacs@gnu.org; Sun, 26 Mar 2023 00:56:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 26 Mar 2023 04:56:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 62352 X-GNU-PR-Package: emacs Original-Received: via spool by 62352-submit@debbugs.gnu.org id=B62352.16798065221414 (code B ref 62352); Sun, 26 Mar 2023 04:56:02 +0000 Original-Received: (at 62352) by debbugs.gnu.org; 26 Mar 2023 04:55:22 +0000 Original-Received: from localhost ([127.0.0.1]:43820 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pgIPZ-0000Mj-Sn for submit@debbugs.gnu.org; Sun, 26 Mar 2023 00:55:22 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:46712) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pgIPY-0000MU-Fy for 62352@debbugs.gnu.org; Sun, 26 Mar 2023 00:55:21 -0400 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pgIPR-0000PA-1X; Sun, 26 Mar 2023 00:55:14 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=5v0/T+sadwrZ/6EuKni/CAbRYX95adNrPywJvhWi4I0=; b=REK7o+Fif3YrOq09DABl vo8agC9F5Ly+Sd4avfmaEGe1t+JhLsnr5Mbl/FUs7TOYOPNG6Q+UyvXmxrm9nS2s/AnP2QMCP7pNm 28oUHCkzKD7Rxh6gx0JYGFsgxbnXdlZgNpAdnrB0gU3OofY8J2HkpnGj76H4fS5sEh1XqsQNRwbWb cbvKr14B7wMrHTzQ3Rst6aHNgccwXj3BNfNCSJ71ELatiGiBseme9KwBhIGo5g3ZFTUdTuXhmwQbu S2ZP6I1rhsSLuAv8Ybp+GrkoAwFuIhgDriMmDVKOGL1mRX3ZzEBKMl5t335NeR0MeC0uAWkDNpCNU NW4j6qxjGpQlyQ==; Original-Received: from [87.69.77.57] (helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pgIPN-0001Eu-IB; Sun, 26 Mar 2023 00:55:10 -0400 In-Reply-To: (message from Herman, =?UTF-8?Q?G=C3=A9za?= on Sat, 25 Mar 2023 22:39:34 +0100) 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-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.bugs:258651 Archived-At: > Date: Sat, 25 Mar 2023 22:39:34 +0100 > Cc: gregory@heytings.org, 62352@debbugs.gnu.org > From: Herman, Géza > > >> I'm not necessarily suggesting a cache. Maybe it's better to actually > >> always manage additional data structures. So, if a text property is > >> added, it's not just set for the specific character area, but it will > >> also modify search structures right away. So additional data structures > >> were always in sync. Sure, it has some overhead. But if emacs does a lot > >> of linear searches (and having a look at these functions, I see a lot of > >> linear searches), this overhead will be quickly mitigated by the much > >> faster searches. For example, if emacs had a list which only contained > >> text segments with the composition property, the current 500-char area > >> search will be much faster. > > Emacs already handles text properties using an efficient data > > structure, see intervals.c. Feel free to suggest improvements to the > > algorithms we use there. > The problem is not there. The problem is that find_composition is only > interested in the composition property, yet it scans all the properties > linearly. It doesn't scan linearly. It calls next-single-property-change, which traverses the interval tree we use for storing text properties. Please take a look at the implementation of next-single-property-change in textprop.c. > And it scans it for 500 characters. This file has a lot of > properties, this means a lot of unnecessary and duplicated work (because > it does this for each character displayed, or something like this). If > the composition property had its own list, then this problem wouldn't exist. If the composition property had its own data structure, Emacs would need to search them both when it looks for a change in _any_ property (something that happens quite a lot in other places), and handle various combinations of hits in both data structures. That'd be a significant complication for a small gain.