From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp1 ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id 8AkMDg52lmA6gwAAgWs5BA (envelope-from ) for ; Sat, 08 May 2021 13:29:18 +0200 Received: from aspmx1.migadu.com ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp1 with LMTPS id aKmeCQ52lmCBbgAAbx9fmQ (envelope-from ) for ; Sat, 08 May 2021 11:29:18 +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 A7D5912C87 for ; Sat, 8 May 2021 13:29:17 +0200 (CEST) Received: from localhost ([::1]:50464 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lfL91-0007TG-My for larch@yhetil.org; Sat, 08 May 2021 07:29:15 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:38516) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lfL8f-0007Su-2e for emacs-orgmode@gnu.org; Sat, 08 May 2021 07:28:53 -0400 Received: from ciao.gmane.io ([116.202.254.214]:48158) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lfL8d-00043l-3y for emacs-orgmode@gnu.org; Sat, 08 May 2021 07:28:52 -0400 Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1lfL8Z-0000YQ-Sm for emacs-orgmode@gnu.org; Sat, 08 May 2021 13:28:47 +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: Sat, 8 May 2021 18:28:41 +0700 Message-ID: References: <874kfieduh.fsf@localhost> <87tung2aoq.fsf@localhost> <87o8dn2t3a.fsf@localhost> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------D119D634B519242AC5849CA3" User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 In-Reply-To: <87o8dn2t3a.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=1620473357; 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:in-reply-to:in-reply-to: references:references:list-id:list-help:list-unsubscribe: list-subscribe:list-post; bh=M83Te7LDU4loWVpNgsuAdeYx5Ch6ghRndJNi8X2Qi+U=; b=eFGhpu161PGe7MrzIzSvnQCEqvMyOC9yH58NXNKPqJ//RpJyQ0u1e7RlXoZohQU5FYOqSf bOWcIgzNdi4nfAiGSd34oMNDcdTswZD4nW2iQKNxAxL2XoXufQ+SXpKyEgHkjMzNMCIM37 Yqb14pxAS2svJL/4M9HWMlqGpka0RD/ZVNwK4CwUQ39Tz05llDT4fE5GjNE0q07Kt1/QCv QgZDALj844+xG2cUcTj/S+l53QM8qHUiEp4eenOcFnBpBJxx1eP94Y73/S9kcB/u54Asz3 5/7JiOdfCBqPMJxcUuBzPUpy82yoM9NMAntx0j3HNLgkbC9vq4HAhAb2RHIVwA== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1620473357; a=rsa-sha256; cv=none; b=Dy6LhY+T+kboxpEF6qn7foYiUPBC6tE8CsMP2xuOvK1H2dhMZ3TRtwc8M+ZVOisywZKo/E rmibK9Hj/E7c9rb16ux2A1BkiggbzUTCtOB8I34JaW7ZV781wLkqvMH31MkQSlTpzaymk5 P9oKNkPVSQnW3pqBZewcw4uJJuALY2429CgDfdAVCcdZ/cNa47I+vSLiPt6uPJJxgtDV6o cUXgZOCT41BMpfHlPKCHjCxTU8k7pFVWo0dBDlBYwVqdvduotj2X83cypYt7DYFk26JZfS YZQrj+iEmZ4hi6gw3qpuzMSB0CR3hg9wGWkQqXj6qtRACx0gEPAnbr7DWpZotw== ARC-Authentication-Results: i=1; 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-Spam-Score: 0.25 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: A7D5912C87 X-Spam-Score: 0.25 X-Migadu-Scanner: scn0.migadu.com X-TUID: RakuMD7oGktZ This is a multi-part message in MIME format. --------------D119D634B519242AC5849CA3 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit On 07/05/2021 09:08, Ihor Radchenko wrote: > Maxim Nikulin writes: >> 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. I am trying to minimize number of regexp searches. Mostly it is applied when information concerning multiple headings is required (agenda, refile targets). It unlikely will get some benefits during interactive calls related to single heading. For a file having 3000 headings, scanning though it takes ~0.1sec to get the following properties: position, level, list of parents (with same properties). Note that no expensive operations are performed like cleaning up of heading title. Having list of headings (and its length), it is possible to build a tree for binary search in linear time. It takes ~0.01sec. Having the tree, it is possible to instantly find heading for *arbitrary* position in the buffer. Likely the next operation is goto to the heading or to it parent and parsing the line for more detailed properties. The latter is cacheable, structure for heading properties can be expanded. Hash works only for fixed set of positions, to use hash it is necessary to find position of the heading at first. On the other hand, to take advantage of binary tree, more substantial modification of code is required. Since there is no operations as insertion or deletion of nodes from tree, no complex code is required to implement balancing rotations. That is why I think that avl-tree is an overkill. See the attachment for experimental (thus almost untested) code. Likely you will find code style quite ugly. I am not happy with 0.1 sec for a moderately large file. It is close to the limit for comfortable interactive operations. >>> + (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. Sorry. You are right. The function does what I proposed to write explicitly. For some reason I believed that outline-level calls something like looking-at. Maybe I checked it earlier and completely forgot. --------------D119D634B519242AC5849CA3 Content-Type: text/plain; charset=UTF-8; name="nm-btree.org" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="nm-btree.org" CiMrYmVnaW5fc3JjIGVsaXNwIDpyZXN1bHRzIG5vbmUKCiAgOzsgSGVhZGluZyBwcm9wZXJ0 aWVzCiAgKGRlZnVuIG5tLWhlYWRpbmctcHJvcGVydGllcy1uZXcgKHBvc2l0aW9uIGxldmVs IHBhcmVudHMpCiAgICAiSGVhZGluZyBwcm9wZXJ0aWVzOiAocG9zaXRpb24gLiAobGV2ZWwg LiBwYXJlbnQpKSIKICAgIChjb25zIHBvc2l0aW9uIChjb25zIGxldmVsIHBhcmVudHMpKSkK CiAgKGRlZnVuIG5tLWhlYWRpbmctcHJvcGVydGllcy1sZXZlbCAocHJvcHMpCiAgICAoY2Fk ciBwcm9wcykpCgogIChkZWZ1biBubS1oZWFkaW5nLXByb3BlcnRpZXMtcG9zIChwcm9wcykK ICAgIChjYXIgcHJvcHMpKQoKICAoZGVmdW4gbm0taGVhZGluZy1wcm9wZXJ0aWVzLXBhcmVu dHMgKHByb3BzKQogICAgKGNkZHIgcHJvcHMpKQoKICAoZGVmdW4gbm0taGVhZGluZy1wb3Mt bGVzc3AgKHZhbHVlIHByb3BzKQogICAgKDwgdmFsdWUgKG5tLWhlYWRpbmctcHJvcGVydGll cy1wb3MgcHJvcHMpKSkKCiAgKGRlZnVuIG5tLWJ1ZmZlci1oZWFkaW5ncy1yZXZlcnNlZCAo YnVmZmVyKQogICAgKHdpdGgtY3VycmVudC1idWZmZXIgYnVmZmVyCiAgICAgIChzYXZlLXJl c3RyaWN0aW9uCgkoc2F2ZS1leGN1cnNpb24KCSAgKHdpZGVuKQoJICAoZ290by1jaGFyIChw b2ludC1taW4pKQoJICAobGV0ICgoY291bnQgMCkKCQkoaGVhZGluZ3MgKCkpCgkJKHBhcmVu dHMgKCkpKQoJICAgICh3aGlsZSAocmUtc2VhcmNoLWZvcndhcmQgb3JnLW91dGxpbmUtcmVn ZXhwLWJvbCBuaWwgdCkKCSAgICAgIChsZXQqICgocG9zIChtYXRjaC1iZWdpbm5pbmcgMCkp CgkJICAgICAobGV2ZWwgKC0gKG1hdGNoLWVuZCAwKSBwb3MgMSkpKQoJCSh3aGlsZSAoYW5k IHBhcmVudHMgKD49IChubS1oZWFkaW5nLXByb3BlcnRpZXMtbGV2ZWwgKGNhciBwYXJlbnRz KSkgbGV2ZWwpKQoJCSAgKHBvcCBwYXJlbnRzKSkKCQkoc2V0cSBjb3VudCAoMSsgY291bnQp KQoJCShsZXQgKChwcm9wcyAobm0taGVhZGluZy1wcm9wZXJ0aWVzLW5ldyBwb3MgbGV2ZWwg cGFyZW50cykpKQoJCSAgKHB1c2ggcHJvcHMgaGVhZGluZ3MpCgkJICAocHVzaCBwcm9wcyBw YXJlbnRzKSkpKQoJICAgIChhbmQgaGVhZGluZ3MgKGNvbnMgaGVhZGluZ3MgY291bnQpKSkp KSkpCgoKICA7OyBiaW5hcnkgc2VhcmNoIHRyZWUKICAoZGVmdW4gbm0tYnRyZWUtbmV3LW5v ZGUgKCkKICAgICIoKGxlZnQgcmlnaHQpIC4gcHJvcGVydGllcyIKICAgIChjb25zIChjb25z IG5pbCBuaWwpIG5pbCkpCgogIChkZWZ1biBubS1idHJlZS1ub2RlLWxlZnQgKG5vZGUpCiAg ICAoY2FhciBub2RlKSkKCiAgKGRlZnVuIG5tLWJ0cmVlLW5vZGUtc2V0LWxlZnQgKG5vZGUg Y2hpbGQpCiAgICAoc2V0Y2FyIChjYXIgbm9kZSkgY2hpbGQpKQoKICAoZGVmdW4gbm0tYnRy ZWUtbm9kZS1zZXQtcmlnaHQgKG5vZGUgY2hpbGQpCiAgICAoc2V0Y2RyIChjYXIgbm9kZSkg Y2hpbGQpKQoKICAoZGVmdW4gbm0tYnRyZWUtbm9kZS1yaWdodCAobm9kZSkKICAgIChjZGFy IG5vZGUpKQoKICAoZGVmdW4gbm0tYnRyZWUtbm9kZS1wcm9wZXJ0aWVzIChub2RlKQogICAg KGNkciBub2RlKSkKCiAgKGRlZnVuIG5tLWJ0cmVlLW5vZGUtc2V0LXByb3BlcnRpZXMgKG5v ZGUgcHJvcGVydGllcykKICAgIChzZXRjZHIgbm9kZSBwcm9wZXJ0aWVzKSkKCiAgKGRlZnVu IG5tLWJ0cmVlLWZyb20tcmV2ZXJzZWQgKHNjYW4tcmVzdWx0KQogICAgKGFuZAogICAgIHNj YW4tcmVzdWx0CiAgICAgKGxldCogKChrZXktcHJvcGVydGllcy1saXN0IChjYXIgc2Nhbi1y ZXN1bHQpKQoJICAgIChsZW5ndGggKGNkciBzY2FuLXJlc3VsdCkpCgkgICAgKGhlYWQgKG5t LWJ0cmVlLW5ldy1ub2RlKSkKCSAgICAocXVldWUgKGxpc3QgKGNvbnMgbGVuZ3RoIGhlYWQp KSkpIDsgbGlzdCBvZiAoY291bnQgLiBub2RlKQogICAgICAgKHdoaWxlIHF1ZXVlCgkgKGxl dCogKChpdGVtIChwb3AgcXVldWUpKQoJCShjb3VudCAoY2FyIGl0ZW0pKQoJCShub2RlIChj ZHIgaXRlbSkpKQoJICAgKGNvbmQKCSAgICAoKGVxIGNvdW50IDEpIDsgbGVhZiBvciBvbmx5 IHNpbmdsZSBjaGlsZAoJICAgICAobm0tYnRyZWUtbm9kZS1zZXQtcHJvcGVydGllcyBub2Rl IChwb3Aga2V5LXByb3BlcnRpZXMtbGlzdCkpKQoJICAgICgobm0tYnRyZWUtbm9kZS1yaWdo dCBub2RlKSA7IHJpZ2h0IGNoaWxkcmVuIGNvbXBsZXRlZAoJICAgICAobm0tYnRyZWUtbm9k ZS1zZXQtcHJvcGVydGllcyBub2RlIChwb3Aga2V5LXByb3BlcnRpZXMtbGlzdCkpCgkgICAg IChsZXQgKChsZWZ0LW5vZGUgKG5tLWJ0cmVlLW5ldy1ub2RlKSkpCgkgICAgICAgKG5tLWJ0 cmVlLW5vZGUtc2V0LWxlZnQgbm9kZSBsZWZ0LW5vZGUpCgkgICAgICAgKHB1c2ggKGNvbnMg KDEtIGNvdW50KSBsZWZ0LW5vZGUpIHF1ZXVlKSkpCgkgICAgKHQgKGxldCogKChyaWdodC1j b3VudCAoLyAoY2FyIGl0ZW0pIDIpKQoJCSAgICAgIChyaWdodC1ub2RlIChubS1idHJlZS1u ZXctbm9kZSkpKQoJCSAobm0tYnRyZWUtbm9kZS1zZXQtcmlnaHQgbm9kZSByaWdodC1ub2Rl KQoJCSAoc2V0Y2FyIGl0ZW0gKC0gY291bnQgcmlnaHQtY291bnQpKQoJCSAocHVzaCBpdGVt IHF1ZXVlKQoJCSAocHVzaCAoY29ucyByaWdodC1jb3VudCByaWdodC1ub2RlKSBxdWV1ZSkp KSkpKQogICAgICAgaGVhZCkpKQoKICAoZGVmdW4gbm0tYnRyZWUtZmluZC1sZWZ0ICh0cmVl IHZhbHVlICZvcHRpb25hbCBjbXApCiAgICAiRmluZCBsYXN0IGVsZW1lbnQgbm90IGxlc3Mg dGhhbiB2YWx1ZSIKICAgIChsZXQgKChjbXAgKG9yIGNtcCAjJ25tLWhlYWRpbmctcG9zLWxl c3NwKSkKCSAgKHJlc3VsdCBuaWwpKQogICAgICAod2hpbGUgdHJlZQoJKHNldHEgdHJlZSAo aWYgKGZ1bmNhbGwgY21wIHZhbHVlIChubS1idHJlZS1ub2RlLXByb3BlcnRpZXMgdHJlZSkp CgkJICAgICAgIChubS1idHJlZS1ub2RlLWxlZnQgdHJlZSkKCQkgICAgIChzZXRxIHJlc3Vs dCB0cmVlKQoJCSAgICAgKG5tLWJ0cmVlLW5vZGUtcmlnaHQgdHJlZSkpKSkKICAgICAgKG5t LWJ0cmVlLW5vZGUtcHJvcGVydGllcyByZXN1bHQpKSkKIytlbmRfc3JjCgojK2JlZ2luX3Ny YyBlbGlzcAogIChieXRlLWNvbXBpbGUgIydubS1idWZmZXItaGVhZGluZ3MtcmV2ZXJzZWQp CiAgKGJ5dGUtY29tcGlsZSAjJ25tLWJ0cmVlLWZyb20tcmV2ZXJzZWQpCiAgKGJ5dGUtY29t cGlsZSAjJ25tLWJ0cmVlLWZpbmQtbGVmdCkKCiAgKGxldCogKChidWZmZXIgIm5vdGVzLm9y ZyIpCgkgKHNjYW4tcmVzdWx0IChubS1idWZmZXItaGVhZGluZ3MtcmV2ZXJzZWQgYnVmZmVy KSkKCSAodHJlZSAobm0tYnRyZWUtZnJvbS1yZXZlcnNlZCBzY2FuLXJlc3VsdCkpCgkgKGxp bSAod2l0aC1jdXJyZW50LWJ1ZmZlciBidWZmZXIKCQkoc2F2ZS1yZXN0cmljdGlvbgoJCSAg KHdpZGVuKQoJCSAgKHBvaW50LW1heCkpKSkpCiAgICAobGlzdAogICAgIChhcHBlbmQgJygi c2NhbiB4MTAiKQoJICAgICAoYmVuY2htYXJrLXJ1biAxMAoJICAgICAgIChubS1idWZmZXIt aGVhZGluZ3MtcmV2ZXJzZWQgYnVmZmVyKSkpCiAgICAgKGFwcGVuZCAnKCJidHJlZSB4MTAi KQoJICAgICAoYmVuY2htYXJrLXJ1biAxMAoJICAgICAgIChubS1idHJlZS1mcm9tLXJldmVy c2VkIHNjYW4tcmVzdWx0KSkpCiAgICAgKGFwcGVuZCAnKCJzY2FuK2J0cmVlIHgxMCIpCgkg ICAgIChiZW5jaG1hcmstcnVuIDEwCgkgICAgICAgKGxldCogKChzY2FuLXJlc3VsdDEgKG5t LWJ1ZmZlci1oZWFkaW5ncy1yZXZlcnNlZCBidWZmZXIpKQoJCSAgICAgICh0cmVlMSAobm0t YnRyZWUtZnJvbS1yZXZlcnNlZCBzY2FuLXJlc3VsdDEpKSkKCQkgdHJlZTEpKSkKICAgICAo YXBwZW5kICcoImZpbmQgcmFuZG9tIHgxMCAwMDAiKQoJICAgICAoYmVuY2htYXJrLXJ1biAx MDAwMAoJICAgICAgIChubS1idHJlZS1maW5kLWxlZnQgdHJlZSAocmFuZG9tIGxpbSkpKSkK ICAgICAobGlzdCAibm9kZXMiIChjZHIgc2Nhbi1yZXN1bHQpICIiICIiKSkpCiMrZW5kX3Ny YwoKIytSRVNVTFRTOgp8IHNjYW4geDEwICAgICAgICAgICAgfCAgIDAuODYxMTM4MjY4OTk5 OTk5OSB8IDAgfCAgICAgICAgICAgICAgICAgMC4wIHwKfCBidHJlZSB4MTAgICAgICAgICAg IHwgIDAuMDc3MDU5NjI0MDAwMDAwMDEgfCAxIHwgMC4wNTY0ODMyMjE5OTk5OTk3OCB8Cnwg c2NhbitidHJlZSB4MTAgICAgICB8ICAgICAgICAgIDAuOTQwNDY3MjM4IHwgMSB8IDAuMDU2 ODUzNzM2OTk5OTk5OTYgfAp8IGZpbmQgcmFuZG9tIHgxMCAwMDAgfCAwLjA0NzcxMjA5Njk5 OTk5OTk5NSB8IDAgfCAgICAgICAgICAgICAgICAgMC4wIHwKfCBub2RlcyAgICAgICAgICAg ICAgIHwgICAgICAgICAgICAgICAgIDM0MTMgfCAgIHwgICAgICAgICAgICAgICAgICAgICB8 CgpXaXRob3V0IH5ieXRlLWNvbXBpbGV+Cnwgc2NhbiB4MTAgICAgICAgICAgICB8ICAxLjIw MzE1MzU5OTk5OTk5OTggfCAgNCB8IDAuMjI4NDU5MDY3MDAwMDAwMTggfAp8IGJ0cmVlIHgx MCAgICAgICAgICAgfCAgICAgICAgIDAuNDk4MjE0MjQxIHwgIDYgfCAwLjM0MDY3NDY0Mjk5 OTk5ODk0IHwKfCBzY2FuK2J0cmVlIHgxMCAgICAgIHwgIDEuNzAyNjMwNDIzMDAwMDAwMiB8 IDEwIHwgIDAuNTY4NjkyNjE0OTk5OTk5OCB8CnwgZmluZCByYW5kb20geDEwIDAwMCB8IDAu MDg3ODk5MTI3MDAwMDAwMDEgfCAgMCB8ICAgICAgICAgICAgICAgICAwLjAgfAp8IG5vZGVz ICAgICAgICAgICAgICAgfCAgICAgICAgICAgICAgICAzNDEzIHwgICAgfCAgICAgICAgICAg ICAgICAgICAgIHwK --------------D119D634B519242AC5849CA3--