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 qG33FanSkmAq5AAAgWs5BA (envelope-from ) for ; Wed, 05 May 2021 19:15:21 +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 oAiqEanSkmBLIQAAbx9fmQ (envelope-from ) for ; Wed, 05 May 2021 17:15:21 +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 1D80CCE77 for ; Wed, 5 May 2021 19:14:57 +0200 (CEST) Received: from localhost ([::1]:39796 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1leL6u-0003Bg-8Z for larch@yhetil.org; Wed, 05 May 2021 13:14:56 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:40702) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1leKZY-00054j-Sd for emacs-orgmode@gnu.org; Wed, 05 May 2021 12:40:30 -0400 Received: from ciao.gmane.io ([116.202.254.214]:54566) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1leKZW-0001me-Mp for emacs-orgmode@gnu.org; Wed, 05 May 2021 12:40:27 -0400 Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1leKZT-0005bI-T9 for emacs-orgmode@gnu.org; Wed, 05 May 2021 18:40:23 +0200 X-Injected-Via-Gmane: http://gmane.org/ To: emacs-orgmode@gnu.org From: Maxim Nikulin Subject: Re: [PATCH] Use cache in org-up-heading-safe Date: Wed, 5 May 2021 23:40:16 +0700 Message-ID: References: <874kfieduh.fsf@localhost> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.7.1 In-Reply-To: <874kfieduh.fsf@localhost> Content-Language: en-US Received-SPF: pass client-ip=116.202.254.214; envelope-from=geo-emacs-orgmode@m.gmane-mx.org; helo=ciao.gmane.io X-Spam_score_int: 28 X-Spam_score: 2.8 X-Spam_bar: ++ X-Spam_report: (2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_ADSP_CUSTOM_MED=0.001, FORGED_GMAIL_RCVD=1, FORGED_MUA_MOZILLA=2.309, FREEMAIL_FORGED_FROMDOMAIN=0.248, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, NICE_REPLY_A=-0.001, NML_ADSP_CUSTOM_MED=0.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no 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=1620234897; 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: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:list-id:list-help: list-unsubscribe:list-subscribe:list-post; bh=I911iDcs7XGqvQcT/er4VII5Z7JamYggd6axNCuTmH4=; b=NJZpEHavwXHfqiky+kzAf5fmX/BA5qr1D4Zyv9PpFpu4RrrEFRYCGIrt396VnOFuCX7SLC 7+3zVofJ8C/Q9605Kut9UipnaVQV8w+89KauEqRgGXWCahePO7JvO1HlYXneNO4MJ3z1tz uBPeYQJzFq6UOR5WCwMT6u/hUUjQzfRMQFrbos1JNs1KJ+86J0raD1H1WPNhN5VPjmQDBE e5eNp44EziYfoLTXheEPF0+l3+ns56bpMbcbUbSkmAfvOGuK6J3xZvlI7oxl6R6YejmhTN htmDUWlXEN1A5e2oaAbzxDaIMusgyVyRW0XS6PVG5obttjGPNCkRcfk3qfzYig== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1620234897; a=rsa-sha256; cv=none; b=B7n6PuXxJUB+fhOFdcWtcOW5k2h/+mKMstbcZ0Xut99ZDRzwK8UkQb/pkMRn9guRvuLwgX g5WR7BDsbeEC0lBYwpDtrhARY0ryyrYN2fAEeftVreepMqCMMD4AfIAh81y3c7aui+Vb5D vhw69pJbmUVMmNPRgaKoDS/koSrtgxKdqtnk8KlWqQgUFRZdQY4F6soG2nr3+wiv4uteML LASKSnsN1sPkVArNpy1a68NgDoqR9NeEjuhOqKWPxq8V5I0G3G8d8DTYuApndrItn4hnHW cKr5kYtCFl3/fCz9fYiIEgHNprtnQHpZ35EhzfID2WIUYU69u7FbNIzZUnJuxg== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=none; 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.87 Authentication-Results: aspmx1.migadu.com; dkim=none; dmarc=fail reason="SPF not aligned (relaxed), No valid DKIM" header.from=gmail.com (policy=none); 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: 1D80CCE77 X-Spam-Score: -1.87 X-Migadu-Scanner: scn0.migadu.com X-TUID: x/v2kVWSil2l On 04/05/2021 22:08, Ihor Radchenko wrote: > > 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. I have not tested the patch due to I do not use agenda. My interest was stimulated solely by my attempts to make org-refile-get-targets faster. I consider it as an improvement. I have noticed the only thing that must be fixed: comments with old variant of the function. Reaction to my other comments is optional. In org-agenda.el org-up-heading-safe function is called only from org-find-top-headline. So the purpose of the dance with backward searches is to get top level headings. My expectation is that scan through the whole buffer and storing result in a structure that allows binary search of position (array, red-black tree, etc) may be even faster. Alternatively lazily obtained position of top heading could be stored in cache to reduce number of iterations on org-find-top-line. > + (let ((level-cache (gethash (point) org--up-heading-cache))) > + (if (and level-cache > + (eq (buffer-chars-modified-tick) org--up-heading-cache-tick)) If buffer-chars-modified-tick is faster than gethash then reordering might result in very slight improvement of performance. > + ;; Parent is inside accessible part of the buffer. > + (progn (goto-char level-cache) > + (funcall outline-level))) I do not see any reason why outline level can not be cached in pair with position. > + (let (result) > + (setq result I am not a lisp guru, so from my point of view this can be reduced to (let ((result ... > + (format "^\\*\\{1,%d\\} " level-up) nil t) \t as an alternative to " " is used in org-refile.el, e.g. "^\\*+[ \t]+". Unsure which variant is canonical one and I see that regexp is taken from original function, so no regression is expected. > +;; (defun org-up-heading-safe () > +;; "Move to the heading line of which the present line is a subheading. Clean-up here is required, other notes may be ignored.