From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <emacs-orgmode-bounces+larch=yhetil.org@gnu.org>
Received: from mp1 ([2001:41d0:2:4a6f::])
	(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits))
	by ms0.migadu.com with LMTPS
	id 6PX6HJxikWBCLwEAgWs5BA
	(envelope-from <emacs-orgmode-bounces+larch=yhetil.org@gnu.org>)
	for <larch@yhetil.org>; Tue, 04 May 2021 17:05:00 +0200
Received: from aspmx1.migadu.com ([2001:41d0:2:4a6f::])
	(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits))
	by mp1 with LMTPS
	id GHeUGJxikWBfSwAAbx9fmQ
	(envelope-from <emacs-orgmode-bounces+larch=yhetil.org@gnu.org>)
	for <larch@yhetil.org>; Tue, 04 May 2021 15:05:00 +0000
Received: from lists.gnu.org (lists.gnu.org [209.51.188.17])
	(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
	(No client certificate requested)
	by aspmx1.migadu.com (Postfix) with ESMTPS id BB66314E87
	for <larch@yhetil.org>; Tue,  4 May 2021 17:04:59 +0200 (CEST)
Received: from localhost ([::1]:49936 helo=lists1p.gnu.org)
	by lists.gnu.org with esmtp (Exim 4.90_1)
	(envelope-from <emacs-orgmode-bounces+larch=yhetil.org@gnu.org>)
	id 1ldwbZ-00049M-Sb
	for larch@yhetil.org; Tue, 04 May 2021 11:04:57 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:38058)
 by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <yantar92@gmail.com>)
 id 1ldwal-00048P-AU
 for emacs-orgmode@gnu.org; Tue, 04 May 2021 11:04:07 -0400
Received: from mail-pf1-x432.google.com ([2607:f8b0:4864:20::432]:42919)
 by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128)
 (Exim 4.90_1) (envelope-from <yantar92@gmail.com>)
 id 1ldwad-0005lX-Cs
 for emacs-orgmode@gnu.org; Tue, 04 May 2021 11:04:07 -0400
Received: by mail-pf1-x432.google.com with SMTP id h127so2979387pfe.9
 for <emacs-orgmode@gnu.org>; Tue, 04 May 2021 08:03:58 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=from:to:subject:date:message-id:mime-version;
 bh=DFqcSYJ9RpwJm0VyoH8adAHLCHFkz74HWk3J+6inhTQ=;
 b=I2ssKbWJdmz6qOUqpnIbyFepW+JM9zeeRE/VlxSx72x4qgoNCZ5YdG/2f1xouOIA9J
 LvfA6uUhkLcjB0D/cpxXhc+F82Lhuwwsl1ZpAj84woyRusNJA5dXqYqXWout4212EQVs
 zd6tR2szlZPxlrknOz+DGkwfp8UZrRSgslMaV3hamed+DAWQbkc92u7rvsMFFNqKJr9m
 IIlN9dfmbsDCf5/+sgcqf/JLqeQPlH0W2dalVRgthKbyUkDh5FS+sBoDlerYpYE9H8Pr
 84P4o1BqjAKnuFrFx35VMFZNASt4LlMH7Eyh2gXrKS22VpxHRRWR8foPGIxOnpGWIPyQ
 toUg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:from:to:subject:date:message-id:mime-version;
 bh=DFqcSYJ9RpwJm0VyoH8adAHLCHFkz74HWk3J+6inhTQ=;
 b=AnM2Ai+1KvDNAkSGKNk2udx3/4Wcz49JgpQUYhD2U9KAwJQgQoTfCW2MicRo37o+Gt
 h4GtECRY7ZObY01TYhIqgvvxybD7B3NbFMPBk7gqhNKvjG7cK5ewNvCpFSU4Cmk8UOm+
 XTKDqjU0JcDStoi5ZgzQgoGczYnQlvQIzekA2SapyrrA2BN+vxmPruFRY+WWlTfVWb+K
 sPrPgDqHz/aB+ed6NYwqf2++w3ajttwIkVTJVuL/e6A3rkq1Cssp4qPIu1uU0l8Pg03H
 psG/dulmxF7CXwISphYHakyQSkYrYiXxTXWHMYZ2CQAU0syMB8PVM2Bx3GdF/k0YzaDA
 xHeQ==
X-Gm-Message-State: AOAM531p63+7sapeJuyAytlB4GDEDCmUUDd+Kg2ZjFzNrwLDzcF5mIiA
 as849u4LVOCaFX67CXlhM2j1k0SqFukc8w==
X-Google-Smtp-Source: ABdhPJz4E4BbZ5eH53B5skB9BEkhWhJvM4b6ggW8lOvSuJ7HLWNWvq4VfM+n6IIkyeE4bYbmKTzbIw==
X-Received: by 2002:a17:90a:1c02:: with SMTP id
 s2mr27588592pjs.17.1620140637272; 
 Tue, 04 May 2021 08:03:57 -0700 (PDT)
Received: from localhost ([158.255.2.9])
 by smtp.gmail.com with ESMTPSA id a1sm6858005pfi.22.2021.05.04.08.03.54
 for <emacs-orgmode@gnu.org>
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Tue, 04 May 2021 08:03:56 -0700 (PDT)
From: Ihor Radchenko <yantar92@gmail.com>
To: emacs-orgmode@gnu.org
Subject: [PATCH] Use cache in org-up-heading-safe
Date: Tue, 04 May 2021 23:08:22 +0800
Message-ID: <874kfieduh.fsf@localhost>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
Received-SPF: pass client-ip=2607:f8b0:4864:20::432;
 envelope-from=yantar92@gmail.com; helo=mail-pf1-x432.google.com
X-Spam_score_int: -17
X-Spam_score: -1.8
X-Spam_bar: -
X-Spam_report: (-1.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
 DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1,
 FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-BeenThere: emacs-orgmode@gnu.org
X-Mailman-Version: 2.1.23
Precedence: list
List-Id: "General discussions about Org-mode." <emacs-orgmode.gnu.org>
List-Unsubscribe: <https://lists.gnu.org/mailman/options/emacs-orgmode>,
 <mailto:emacs-orgmode-request@gnu.org?subject=unsubscribe>
List-Archive: <https://lists.gnu.org/archive/html/emacs-orgmode>
List-Post: <mailto:emacs-orgmode@gnu.org>
List-Help: <mailto:emacs-orgmode-request@gnu.org?subject=help>
List-Subscribe: <https://lists.gnu.org/mailman/listinfo/emacs-orgmode>,
 <mailto:emacs-orgmode-request@gnu.org?subject=subscribe>
Errors-To: emacs-orgmode-bounces+larch=yhetil.org@gnu.org
Sender: "Emacs-orgmode" <emacs-orgmode-bounces+larch=yhetil.org@gnu.org>
X-Migadu-Flow: FLOW_IN
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org;
	s=key1; t=1620140700;
	h=from:from:sender:sender:reply-to:subject:subject:date:date:
	 message-id:message-id:to:to:cc:mime-version:mime-version:
	 content-type:content-type:list-id:list-help:list-unsubscribe:
	 list-subscribe:list-post:dkim-signature;
	bh=DFqcSYJ9RpwJm0VyoH8adAHLCHFkz74HWk3J+6inhTQ=;
	b=sq9nrAzrZBjhWl1MHLK8V/BL3RgIIHBDEewO9sE7z1reGyhbDOA4lsu1yaGNWWc36uiuT/
	ou+zkxQzAb2sXxTZxizMO6tRr+GIH+3Og+xsRu8lwraNozTz5kuKugZDbp6oiMioJaTm8/
	3wxViaQu2ynG7NldePdIEeyxkFocpZA3XNXeZRDcZ55MpEiHr9bry7QiOD9thd4u0hQX9v
	zd07HwJn3V/VIQWDd54Z9bS34ul3xOtaVHmwirWScyupvBpNEijF7nZrtDWVGYNRuvcw7F
	ccB1A7HN3dvUf0eMCtslDNOUCjoA6ITVFNHUYUfhHbBSsriVsCI+LChKovokXg==
ARC-Seal: i=1; s=key1; d=yhetil.org; t=1620140700; a=rsa-sha256; cv=none;
	b=FqHeBWY2tJYjLWzJrminUk+KWScTZ3seuD47XTzPGLZi4Vw23GpOwiQukquoaglLSl5ZuZ
	my99q4or5iZQUFtUWjRu0/HD+MT4xqHDy7HnXygF8e7nzSffyrXv8ZPKPggOz3k7V3Zj0N
	uFeK2kkQYruBa6cVCGwf6QgYJABYfzml5MS0ou/CwQEzw7Nq94SY5WInLjDAzgnLUEPgtJ
	8fmnNMlrwCa3YzYMQ4BBrEiZDZq2DKuJqd8GE5esEP1AOEuB+LwO6wz5BNXPI0oqjDn+qI
	nWELhc4f3Noxe8wy2SUfxX+bQbrR6IXWrCLec0zDyoGtGS8z0SEGaaHxtJek4w==
ARC-Authentication-Results: i=1;
	aspmx1.migadu.com;
	dkim=pass header.d=gmail.com header.s=20161025 header.b=I2ssKbWJ;
	dmarc=pass (policy=none) header.from=gmail.com;
	spf=pass (aspmx1.migadu.com: domain of emacs-orgmode-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=emacs-orgmode-bounces@gnu.org
X-Migadu-Spam-Score: -2.66
Authentication-Results: aspmx1.migadu.com;
	dkim=pass header.d=gmail.com header.s=20161025 header.b=I2ssKbWJ;
	dmarc=pass (policy=none) header.from=gmail.com;
	spf=pass (aspmx1.migadu.com: domain of emacs-orgmode-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=emacs-orgmode-bounces@gnu.org
X-Migadu-Queue-Id: BB66314E87
X-Spam-Score: -2.66
X-Migadu-Scanner: scn0.migadu.com
X-TUID: yFAboYsh2Z/Q

--=-=-=
Content-Type: text/plain

Hello,

While testing another patch for agenda fontification, I noticed that
agenda can spend up to half!! time doing org-up-heading-safe. Mostly
inside queries for inherited tags and properties.

I managed to make org-up-heading-safe up to 50x faster using position
cache.

If this patch also works for others, org-agenda-use-tag-inheritance
might become much less of an issue.

Benchmark:

1. (elp-instrument-function #'org-up-heading-safe)
2. Run agenda
3. (elp-results) ;; function, # calls, total time, avg time

Without cache:
org-up-heading-safe  27555       8.4234025759  0.0003056941

With cache, first run:
org-up-heading-safe  23227       0.5300747539  2.282...e-05

With cache, second run on unchanged buffer:
org-up-heading-safe  23227       0.1447754880  6.233...e-06

Best,
Ihor


--=-=-=
Content-Type: text/x-diff
Content-Disposition: inline;
 filename=0001-Use-cache-in-org-up-heading-safe.patch

>From fe1e7094a7b76ba6bf282c5c4409a32b36827d56 Mon Sep 17 00:00:00 2001
Message-Id: <fe1e7094a7b76ba6bf282c5c4409a32b36827d56.1620140628.git.yantar92@gmail.com>
From: Ihor Radchenko <yantar92@gmail.com>
Date: Tue, 4 May 2021 22:55:14 +0800
Subject: [PATCH] Use cache in org-up-heading-safe

* lisp/org.el (org-up-heading-safe): Use buffer-local cache to store
positions of parent headings.  The cache is invalidated when buffer
text is changed, according to `buffer-chars-modified-tick'.
(org--up-heading-cache):  Buffer-local hash-table storing the cache.
(org--up-heading-cache-tick):  The buffer modification state for
currently active `org--up-heading-cache'.

The optimisation is critical when running agenda or org-entry-get
queries using property/tag inheritance.  In such scenarios
`org-up-heading-safe' can be called thousands of times.  For example,
building todo agenda on large number of headings lead to the following
benchmark results:

Benchmark:

1. (elp-instrument-function #'org-up-heading-safe)
2. Run agenda
3. (elp-results) ;; function, # calls, total time, avg time

Without cache:
org-up-heading-safe  27555       8.4234025759  0.0003056941

With cache, first run:
org-up-heading-safe  23227       0.5300747539  2.282...e-05

With cache, second run on unchanged buffer:
org-up-heading-safe  23227       0.1447754880  6.233...e-06

The final speedup is 1-2 orders of magnitude (~15-56 times).
---
 lisp/org.el | 43 +++++++++++++++++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 4 deletions(-)

diff --git a/lisp/org.el b/lisp/org.el
index b8678359f..4385903ee 100644
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -19434,6 +19434,10 @@ (defun org-up-heading-all (arg)
 With argument, move up ARG levels."
   (outline-up-heading arg t))
 
+(defvar-local org--up-heading-cache (make-hash-table)
+  "Buffer-local `org-up-heading-safe' cache.")
+(defvar-local org--up-heading-cache-tick nil
+  "Buffer `buffer-chars-modified-tick' in `org--up-heading-cache'.")
 (defun org-up-heading-safe ()
   "Move to the heading line of which the present line is a subheading.
 This version will not throw an error.  It will return the level of the
@@ -19443,10 +19447,41 @@ (defun org-up-heading-safe ()
 because it relies on stars being the outline starters.  This can really
 make a significant difference in outlines with very many siblings."
   (when (ignore-errors (org-back-to-heading t))
-    (let ((level-up (1- (funcall outline-level))))
-      (and (> level-up 0)
-	   (re-search-backward (format "^\\*\\{1,%d\\} " level-up) nil t)
-	   (funcall outline-level)))))
+    (let ((level-cache (gethash (point) org--up-heading-cache)))
+      (if (and level-cache
+               (eq (buffer-chars-modified-tick) org--up-heading-cache-tick))
+          (when (<= (point-min) level-cache (point-max))
+            ;; Parent is inside accessible part of the buffer.
+            (progn (goto-char level-cache)
+                   (funcall outline-level)))
+        ;; Buffer modified.  Invalidate cache.
+        (when level-cache
+          (clrhash org--up-heading-cache)
+          (setq-local org--up-heading-cache-tick
+                      (buffer-chars-modified-tick)))
+        (let ((level-up (1- (funcall outline-level)))
+              (pos (point)))
+          (let (result)
+            (setq result
+                  (and (> level-up 0)
+	               (re-search-backward
+                        (format "^\\*\\{1,%d\\} " level-up) nil t)
+	               (funcall outline-level)))
+            (when result
+              (puthash pos (point) org--up-heading-cache))))))))
+;; (defun org-up-heading-safe ()
+;;   "Move to the heading line of which the present line is a subheading.
+;; This version will not throw an error.  It will return the level of the
+;; headline found, or nil if no higher level is found.
+
+;; Also, this function will be a lot faster than `outline-up-heading',
+;; because it relies on stars being the outline starters.  This can really
+;; make a significant difference in outlines with very many siblings."
+;;   (when (ignore-errors (org-back-to-heading t))
+;;     (let ((level-up (1- (funcall outline-level))))
+;;       (and (> level-up 0)
+;; 	   (re-search-backward (format "^\\*\\{1,%d\\} " level-up) nil t)
+;; 	   (funcall outline-level)))))
 
 (defun org-up-heading-or-point-min ()
   "Move to the heading line of which the present is a subheading, or point-min.
-- 
2.26.3


--=-=-=--