From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp2 ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id FYZgGWuglGDDUAAAgWs5BA (envelope-from ) for ; Fri, 07 May 2021 04:05:31 +0200 Received: from aspmx1.migadu.com ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp2 with LMTPS id KE17FGuglGAqSwAAB5/wlQ (envelope-from ) for ; Fri, 07 May 2021 02:05:31 +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 751431280D for ; Fri, 7 May 2021 04:05:30 +0200 (CEST) Received: from localhost ([::1]:53802 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1leprs-0004Wi-NC for larch@yhetil.org; Thu, 06 May 2021 22:05:28 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:37188) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lepr5-0004WX-5u for emacs-orgmode@gnu.org; Thu, 06 May 2021 22:04:40 -0400 Received: from mail-lj1-x230.google.com ([2a00:1450:4864:20::230]:33609) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lepr0-0001SM-88 for emacs-orgmode@gnu.org; Thu, 06 May 2021 22:04:38 -0400 Received: by mail-lj1-x230.google.com with SMTP id s25so9619286lji.0 for ; Thu, 06 May 2021 19:04:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:subject:in-reply-to:references:cc:date:message-id :mime-version; bh=QFHlPCHSMEw1Ad/BsH7/Ftg4LydJMtxSFksJt00MZ3I=; b=BENQL7dUlwRCVEdkb8ALt8DVd4L9F9uegODP/DGO6Fd4h3sheq1wEihKjL+SWoIQXL nFroO4RKGVrNDM6hpypr6iMtg3E5YEkMQ3ZC3Y/Hlt37axt65XMXN+7dxMk22CiZrEm8 IPSrLnoJK/T0t1P2eAfCYEGUf10RqEkp5n4iy3elHMU3oHAsCMCBP+pL2WBwYEWDbJRH fnIuC793Baq0AxcDAqNu0pHqZPuJ/LTUBjC4EIBLEM2+4B84fuKq7xTVlt+UjRnZGjwk anRYkgLz23Ct/bhpHdud1RA8HPqtduZRxQtTHkExFr3uJaUUlcSBWjLMRTk46Vv1vZ6i z3Lw== 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:in-reply-to:references:cc:date :message-id:mime-version; bh=QFHlPCHSMEw1Ad/BsH7/Ftg4LydJMtxSFksJt00MZ3I=; b=USiuUIgR5Njl4dFALT7+HXLzx7qFDh2/tzqBOmpVWApdfFkHV9OQx5p+yGu4Vd8q1e 1t+Ba+RPyBrUYmYv0De+5lCEIWp6tna0BLSbE+Q56QrwRZKhA95cewfrgrh2yV7XeD+x 9ebZTtF3CiqLfs8NpziYoAOO6awsKSylN7xEBGbHM9ZWajw0UD2MF9Fxe5Lmm+7gP7S1 eY805cc+IjqmeCmS+p/HrbObcXKKj4kL+Gda2BsvjhNC2SArPxelFyAgcNWsTHx31lmx oZVe8v27ZPIpcQpPbABkfy7x6uMs84WofAUERsDhoUCBCJmKAGEJF2KxgQibO9iNS/JL PeaQ== X-Gm-Message-State: AOAM5304Pf2J2UKZWUuQGwBJBgBy58Exk+igP4Hu/rR1Wpp5zMgLUu+Z 9zPAfOfzm/NW8To/NN2TP2w= X-Google-Smtp-Source: ABdhPJzmTyKtkpma5aK9iRXnzg+QNs3+6HbL7psWyKtF3WRNIIupwwQL2Q3DohhCnBjv2Zs8POFbTQ== X-Received: by 2002:a2e:a71e:: with SMTP id s30mr5587246lje.137.1620353071452; Thu, 06 May 2021 19:04:31 -0700 (PDT) Received: from localhost ([141.105.67.194]) by smtp.gmail.com with ESMTPSA id g22sm534035lfb.205.2021.05.06.19.04.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 May 2021 19:04:30 -0700 (PDT) From: Ihor Radchenko To: Maxim Nikulin Subject: Re: [PATCH] Use cache in org-up-heading-safe In-Reply-To: References: <874kfieduh.fsf@localhost> <87tung2aoq.fsf@localhost> Date: Fri, 07 May 2021 10:08:57 +0800 Message-ID: <87o8dn2t3a.fsf@localhost> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Received-SPF: pass client-ip=2a00:1450:4864:20::230; envelope-from=yantar92@gmail.com; helo=mail-lj1-x230.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: , Cc: emacs-orgmode@gnu.org 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=1620353131; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:in-reply-to:in-reply-to: references:references:list-id:list-help:list-unsubscribe: list-subscribe:list-post:dkim-signature; bh=QFHlPCHSMEw1Ad/BsH7/Ftg4LydJMtxSFksJt00MZ3I=; b=aQ6gE2JXWrrEH+FgRvQJY3+VhKXbTB8leHCFAvB5YsUMAfbdH/izHDZbS8LuAMMUNDZqbT AQFrNTOqKtViV8e1gkuwTLLRSXn7KnU/u0x4/rkwzo1int4MZBvs9SlwpUv2YtoWxLCQIi KYLkKACM2/eFz9LfZ6Td0UHUUoVutwoyVB4IsrfY73f61c9530DgHjuKAswRMsYS3kUsNU aC7wJ3iUGcfbraZLV2VMY74hbCN5q8ZUgSF0hodjafhVn4Olce7qz6M6XQHAAycQskJR8D 8GX/5VVSJnqb7K0vd2u5o/8AId+jRq06eXv2fj6zKpzxgxfvn/t3Sq67rn4bIQ== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1620353131; a=rsa-sha256; cv=none; b=kvHqsy6wbgLWjN0jPNrwclZtoFJRYw+k5/hpqpCnOV7aXb63kgC/1IqXGll/eP1pGCjUzv f3vjg1s9qdxzFUEDZI5ByY86rg+/jceanbEI8MEmrMvRcz42dW8MELouTA1i87ADh7PMkd ct6L98Nre+Yov7rZvTOV1WAYvud6ZtzXggtwFlxbEscQxopbuBjxw1CALgKSxU66FHebDa eF86RFQVA6P903ED0PhXYKCpMz13jvCviRlJ/jqrYAvvbKx1QkNx5KL5caEsxEkIoJsFaB WzhSCcl4l0OjT2inkhXGLzrDt2W99oB7yjKMO8IB3ANdWc2uaWQ2KcF+vhK88A== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=pass header.d=gmail.com header.s=20161025 header.b=BENQL7dU; 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: -1.16 Authentication-Results: aspmx1.migadu.com; dkim=pass header.d=gmail.com header.s=20161025 header.b=BENQL7dU; 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: 751431280D X-Spam-Score: -1.16 X-Migadu-Scanner: scn0.migadu.com X-TUID: 89T6PVq+7UwR --=-=-= Content-Type: text/plain Maxim Nikulin writes: > Though I still have not tested the patch, I think, it is an improvement > and it is helpful in its current form. I am unable to tell if it follows > code style. FYI, this patch may also slightly improve the performance of org-get-outline-path. > My bad, you mentioned tags earlier, but I grepped org-agenda.el only. > My new idea is that org-get-tags may have its own cache as well. Unsure > if it should be tried. I am trying it now ;) No benchmarks yet, but it also provides a subjective improvement. However, I am trying to reuse org-element-cache for tags. org-element-cache is smart enough to update itself partially on buffer changes. However, there are (known) bugs in org-element-cache. I managed to track down some, but still need to test thoughtfully before submitting upstream. > Did you just replace gethash by avl-tree? Yes > Likely my idea is based on a > wrong assumption. I hoped that having positions of headers it is > possible to avoid jumps (goto-char ...) preceded or followed by regexp > matching almost completely. Previous header for arbitrary initial > position can be found using binary search through structure obtained > during scan. Sorry, I cannot follow what you mean. The call to goto-char in org-up-heading-safe is required by function docstring - we need to move point to the parent heading. >> + (re-search-backward >> + (format "^\\*\\{1,%d\\} " level-up) nil t) >> + (funcall outline-level)))) > > Unsure concerning the following optimization from the point of > readability and reliability in respect to future modifications. Outline > level can be derived from the length of matched string without the > funcall requiring extra regexp. I am not sure here. outline-level also consults outline-heading-alist, though I found no references to that variable in Org mode code. Otherwise, outline-level already reuses match-data. There is no regexp matching there. P.S. I just found that hash-tables are created by reference, so we need to call make-hash-table separately in each buffer with cache. Updated patch attached. --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0001-Use-cache-in-org-up-heading-safe.patch >From 08a175752b14f84767a71665773aa64807606af4 Mon Sep 17 00:00:00 2001 Message-Id: <08a175752b14f84767a71665773aa64807606af4.1620316036.git.yantar92@gmail.com> From: Ihor Radchenko Date: Thu, 6 May 2021 14:13:20 +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 | 30 ++++++++++++++++++++++++++---- 1 file changed, 26 insertions(+), 4 deletions(-) diff --git a/lisp/org.el b/lisp/org.el index 0ff13c79c..7c58f0e2e 100644 --- a/lisp/org.el +++ b/lisp/org.el @@ -20440,6 +20440,10 @@ (defun org-up-heading-all (arg) With argument, move up ARG levels." (outline-up-heading arg t)) +(defvar-local org--up-heading-cache nil + "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 @@ -20449,10 +20453,28 @@ (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) + (unless org--up-heading-cache + (setq org--up-heading-cache (make-hash-table))) + (if (and (eq (buffer-chars-modified-tick) org--up-heading-cache-tick) + (setq level-cache (gethash (point) org--up-heading-cache))) + (when (<= (point-min) (car level-cache) (point-max)) + ;; Parent is inside accessible part of the buffer. + (progn (goto-char (car level-cache)) + (cdr level-cache))) + ;; Buffer modified. Invalidate cache. + (unless (eq (buffer-chars-modified-tick) org--up-heading-cache-tick) + (setq-local org--up-heading-cache-tick + (buffer-chars-modified-tick)) + (clrhash org--up-heading-cache)) + (let* ((level-up (1- (funcall outline-level))) + (pos (point)) + (result (and (> level-up 0) + (re-search-backward + (format "^\\*\\{1,%d\\} " level-up) nil t) + (funcall outline-level)))) + (when result (puthash pos (cons (point) result) org--up-heading-cache)) + result))))) (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 --=-=-=--