From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 ) for ; 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 ) for ; 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 ; 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 ) 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 ) 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 ) 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 ; 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 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 May 2021 08:03:56 -0700 (PDT) From: Ihor Radchenko 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." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-orgmode-bounces+larch=yhetil.org@gnu.org Sender: "Emacs-orgmode" 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: From: Ihor Radchenko 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 --=-=-=--