From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp2 ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id SNmOHQEmlGCk3QAAgWs5BA (envelope-from ) for ; Thu, 06 May 2021 19:23:13 +0200 Received: from aspmx1.migadu.com ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp2 with LMTPS id OH4IGQEmlGALZQAAB5/wlQ (envelope-from ) for ; Thu, 06 May 2021 17:23:13 +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 EFEE324763 for ; Thu, 6 May 2021 19:23:12 +0200 (CEST) Received: from localhost ([::1]:46116 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lehiR-00047T-20 for larch@yhetil.org; Thu, 06 May 2021 13:23:11 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:53702) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lehOd-0003xd-Pu for emacs-orgmode@gnu.org; Thu, 06 May 2021 13:02:47 -0400 Received: from ciao.gmane.io ([116.202.254.214]:38648) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lehOP-0003vL-BA for emacs-orgmode@gnu.org; Thu, 06 May 2021 13:02:35 -0400 Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1lehOL-0007dm-PO for emacs-orgmode@gnu.org; Thu, 06 May 2021 19:02:25 +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: Fri, 7 May 2021 00:02:19 +0700 Message-ID: References: <874kfieduh.fsf@localhost> <87tung2aoq.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: <87tung2aoq.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.248, 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=1620321793; 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=SirgehcldYbWOwNZ8nquP32UH2CeN2eiacXEB77OGok=; b=t50Egr1coM2c+lMvjGNGoCIeKWFfjtBVQdEiKTHlQKm15kXT1gYVe6J1DCcXkC6vxkJaYT k8LB9uTrKJNgU8B0JZJayMDPL54A6Y6dpMsQqpN2nB1iq4gRZrlbX7FMuH+ZKsQIdnLf4e 6YMzK5TGajbk9rZMFsDbAzLCgM3f6DcLBhxAWB3pgc78DhbflS6HWw6Ud5CrFNsxYoHsTu R0UWPvxXjX1C0R7Lt5EmQYh+/I/UO0Vq5IZERMmJnuI5sEVDwAsB9BFyuAj4UCa/mm2hQC NhGOSj3Hh/4lkhMx6v1c66BCNek4kUVRc3BV1W/WKLZgNs8h/mvIwguH7/TEXw== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1620321793; a=rsa-sha256; cv=none; b=DWfrkC9VddyHsjGihzFIOoAFYTh32bumuyUXCKX6QsMNorHkcW1iFw+JIsjDHScuQSDOD9 Pyxw8p2/0YiEqHKC8kkrG68R9fa5Ewg8FliMcw+GS8aiczVd8j9ghD13gcbP57FUCcDVlZ W0gIc5fnHGimyrb6Itoy54cJHS0LY8GyBFHout4Kiz2MgFvDD+ol+yMupwk1dRS9eQ6Aek IraTaarwlVRSwye4L2Q9+D4bdofMh87YlZOmQxhyFz1muGeOz3IYTsMwbWryorp/eo4kGZ yy+qRJl8isrqIJ7KkV9e5JsQ8Ge6aYuYZDqg39gSmC0VkeV+x0Qrv8rEyikHkA== 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: -0.36 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: EFEE324763 X-Spam-Score: -0.36 X-Migadu-Scanner: scn0.migadu.com X-TUID: Mv43QmRYeI8W 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. Despite continuing discussion, I am unsure if it could be significantly better. On 06/05/2021 21:34, Ihor Radchenko wrote: > Maxim Nikulin writes: >> In org-agenda.el org-up-heading-safe function is called only from >> org-find-top-headline. > > That's probably not the slowest part. org-agenda also calls > org-up-heading-safe indirectly. In particular, org-get-tags is calling > org-up-heading-safe to get inherited tags. It is org-get-tags that is > taking >50% time of agenda generation in my agendas. And > org-up-heading-safe was the largest contributor to that >50% time. 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. > Scan through the whole buffer could be faster, but it is not always > desired. Most of Org code only need information for current headline. > Re-scanning the whole buffer would be costly. > > Also, I tried to compare avl-tree with hash table. However, avl-tree > does not give much benefit for my test case of an agenda with ~12000 > todo items. Since avl-tree requires much more custom code, hash table > should be better. Did you just replace gethash by avl-tree? 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. > + (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. If originally this code path had 50% contribution and performance already becomes several times better, further optimization of this part does not matter.