From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp10.migadu.com ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id yHwVMvMy8GG0XAAAgWs5BA (envelope-from ) for ; Tue, 25 Jan 2022 18:27:15 +0100 Received: from aspmx1.migadu.com ([2001:41d0:2:4a6f::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp10.migadu.com with LMTPS id UKmvKfMy8GEYwgAAG6o9tA (envelope-from ) for ; Tue, 25 Jan 2022 18:27:15 +0100 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 3FAF09298 for ; Tue, 25 Jan 2022 18:27:15 +0100 (CET) Received: from localhost ([::1]:42146 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nCPb8-0005vX-AE for larch@yhetil.org; Tue, 25 Jan 2022 12:27:14 -0500 Received: from eggs.gnu.org ([209.51.188.92]:42820) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nCPaY-0005vO-7q for emacs-orgmode@gnu.org; Tue, 25 Jan 2022 12:26:38 -0500 Received: from [2607:f8b0:4864:20::102a] (port=53090 helo=mail-pj1-x102a.google.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nCPaW-0007ZW-33 for emacs-orgmode@gnu.org; Tue, 25 Jan 2022 12:26:37 -0500 Received: by mail-pj1-x102a.google.com with SMTP id o64so20630967pjo.2 for ; Tue, 25 Jan 2022 09:26:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=references:user-agent:from:to:subject:date:in-reply-to:message-id :mime-version:content-transfer-encoding; bh=OfFhKbBuCM0YEUzVt9qAWLCUNGBDotw4HrUabQfXmeA=; b=Bh22QZpgLmkz2hq8kTKr1oIL7oHzM9uk+UtprzJpeJADIZDR/txuUuW/e9mz32FYca f4FX+EpXuCUQRXvb0KVXGNokAexafscxN5nQDto6SD8+BZ7LOneyxz545Fj0y3BBOw7X ZArHtLJvxyZNDvtnkXULLByWT6kE/Xu9nsku788qhcFBTG2NOFBs1ibLvLco+wd9uei/ 5EeV1G7FNV2DhMpybCvrCmD4ftO/6sxOseDHqgo35cYYZZImE5iWzDbL3mksuEJsovCq /csblozvTZ1T7GeQBxC5DQtF/1KdmbgDN2iSM9RLFyA0MDkGQPbskhxxprJuqAB2b4b0 3h7g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:references:user-agent:from:to:subject:date :in-reply-to:message-id:mime-version:content-transfer-encoding; bh=OfFhKbBuCM0YEUzVt9qAWLCUNGBDotw4HrUabQfXmeA=; b=klRGrHaG/KWCp9r7CnhjqZWh66NEhYNE8UariYugVAS+g38gLxSy1vzGu2vlVfldSz l1Tw9HnJRbqAD43kbUoLEXiD4cI67xTZRTOTlSbz/Pvmc9JvMe3D8ZKaPyR+Urh3kVmK ZjAIw7Z4r4jXgtYQU512IIhKMXi/Tb/DQRPrgOtZuTGMGrQmEN/CuHl0Alvwt2m+Dm1m 1LwSiw/n198zvrk4V8VBNUQG7ZpRMeZiaZ35lte06XQdNOI470/TFKy7flvByW2s4MRC HXafm5UNS9aki4wvNhqkyYBUeimQX73Vlc9f5mNts3h06N1BOVuedbtzHOipM1GYVJ4/ K6hQ== X-Gm-Message-State: AOAM533GaB7/TwiIzVeb2iUrsx/n5u/ld23EhCJB+1bvpsnHnTbUoy5+ xIy7p/6JPpcnJTyNnJy3CmIABd3JNA0= X-Google-Smtp-Source: ABdhPJxoV3Qh06+rHlBjUppuPdMtPNrr+GKIwkkY1z3e3rlByLAYDxtd/rklu1GPPwgHPYhxIJzsbw== X-Received: by 2002:a17:90b:4f49:: with SMTP id pj9mr4508083pjb.211.1643131593623; Tue, 25 Jan 2022 09:26:33 -0800 (PST) Received: from dingbat (2001-44b8-31f2-bb00-ccfd-eb43-81e6-ad1a.static.ipv6.internode.on.net. [2001:44b8:31f2:bb00:ccfd:eb43:81e6:ad1a]) by smtp.gmail.com with ESMTPSA id k12sm21757465pfc.107.2022.01.25.09.26.32 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 25 Jan 2022 09:26:33 -0800 (PST) References: <147178804.982080.1643087944384@ichabod.co-bxl> <87k0enx5v6.fsf@localhost> User-agent: mu4e 1.7.6; emacs 28.0.91 From: Tim Cross To: emacs-orgmode@gnu.org Subject: Re: Poor org-babel-tangle-file performance with more than 100 trivial noweb-references Date: Wed, 26 Jan 2022 03:25:46 +1100 In-reply-to: <87k0enx5v6.fsf@localhost> Message-ID: <87a6fjenga.fsf@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Host-Lookup-Failed: Reverse DNS lookup failed for 2607:f8b0:4864:20::102a (failed) Received-SPF: pass client-ip=2607:f8b0:4864:20::102a; envelope-from=theophilusx@gmail.com; helo=mail-pj1-x102a.google.com X-Spam_score_int: -12 X-Spam_score: -1.3 X-Spam_bar: - X-Spam_report: (-1.3 / 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_FROM=0.001, PDS_HP_HELO_NORDNS=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RDNS_NONE=0.793, 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.29 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 X-Migadu-Country: US ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1643131635; 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:dkim-signature; bh=OfFhKbBuCM0YEUzVt9qAWLCUNGBDotw4HrUabQfXmeA=; b=WIBRnlfNL+UwuQ/bT3GRuo21g837WJ9MULuwBntNP4iCjb4qUQ+5uqdD098abkT0hjHNa9 JPrTq7yRo+qV3aJWyWqxl2BnYegBcNHdEYAUF4GQ3Izp2wWGoC68yVWZxKQLc2dHSD0Iav 2f6XiIY2Vs7LIAjFhpLx33uzaFsAbtsh4CjmrUeHoE4/UVQGSfg467sj5E0ZWi6qtkbncu ntJZJdzQR7admOwrRJ/J1NHjk29mV7joJjhWTstimCa5Wksr56zNSANouezbOojAXxOXW0 gGqFDeriH92CCORotuC+NGiaL+1rRLaBTgdUv1ww04YlN5FDEwcsMj4e4k02MQ== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1643131635; a=rsa-sha256; cv=none; b=QHny3hu0eD331TaZp438nVXf7d6yWDvn+J7ME1ViXvojTAN7TlS3RDDAYfNvjE04Ukoqlf XuxGGoZ4FAUgTH9UEqnuUYTYeAlmAHMAFcSrSlnlQ/JJWixN6RCkIcHKtKfWApkBVWo9M2 0zMJ0mPXN0gZinkYAzNG5ZGbPaNTybMRMHSD+NcZnqAL1h2shPRr0Grc41OSNUUSXFiGiD zCDTlqhyS9c+ro2ZLT9OH/uZP/9q9JGLIxRU4NSgG2g9k60H9eHoX0olx9x2jP4vkl4RU+ xub1b6jFRkNYhXMSS/+xVp4WJDeKtiPhUMEwIdrfoBUQYIzhJWlXbtS5260EZg== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=Bh22QZpg; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (aspmx1.migadu.com: domain of "emacs-orgmode-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="emacs-orgmode-bounces+larch=yhetil.org@gnu.org" X-Migadu-Spam-Score: -4.33 Authentication-Results: aspmx1.migadu.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=Bh22QZpg; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (aspmx1.migadu.com: domain of "emacs-orgmode-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="emacs-orgmode-bounces+larch=yhetil.org@gnu.org" X-Migadu-Queue-Id: 3FAF09298 X-Spam-Score: -4.33 X-Migadu-Scanner: scn1.migadu.com X-TUID: u/HtFqAmVVgG Ihor Radchenko writes: > pareto optimal writes: > >> Using =3Demacs -Q=3D to tangle org files with more than over 100 noweb-r= efs gets slow fast. >> >> Given this org code for N=3D2: >> Using Gcc Emacs 28.0.91 (which I typicall use) I get these results: >> >> | N blocks | runtime | # of GCs | >> |----------+---------+----------| >> |=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 10 |=C2=A0=C2=A0 0.027 |=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 0 | >> |=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 20 |=C2=A0=C2=A0 0.049 |=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 0 | >> |=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 40 |=C2=A0=C2=A0 0.121 |=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 0 | >> |=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 80 |=C2=A0=C2=A0 0.391 |=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 0 | >> |=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 160 |=C2=A0=C2=A0 1.426 |=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0 0 | >> |=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 320 |=C2=A0=C2=A0 6.765 |=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0 0 | >> |=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 640 |=C2=A0 23.972 |=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0 0 | >> >> so roughly it scales like: >> >> #+begin_example >> 0.8x (10-20) >> 2.5x=C2=A0 (20-40) >> 3x=C2=A0 (40-80) >> 3.5x=C2=A0 (160-320) >> 4x=C2=A0 (320-640) >> #+end_example >> >> Though I'm not sure how much that can tell us... my guess is noweb-ref's= don't use a dictionary with =3DO(1)=3D lookups? > > Thanks for the nice benchmark and for providing a test case! > > You are using stable version of Org. We did some important performance > improvements on main. The same benchmark using latest main (26decec): > > | N blocks | runtime | # of GCs | > |----------+---------+----------| > | 10 | 0.030 | 0 | > | 20 | 0.067 | 0 | > | 40 | 0.065 | 0 | > | 80 | 0.081 | 0 | > | 160 | 0.214 | 0 | > | 320 | 0.597 | 0 | > | 640 | 2.225 | 0 | > | 1280 | 9.221 | 0 | > | 2560 | 36.966 | 0 | > > And with disabled self-verification code: > (setq org-element--cache-self-verify nil) > | N blocks | runtime | # of GCs | > |----------+---------+----------| > | 10 | 0.078 | 0 | > | 20 | 0.075 | 0 | > | 40 | 0.063 | 0 | > | 80 | 0.085 | 0 | > | 160 | 0.095 | 0 | > | 320 | 0.178 | 0 | > | 640 | 0.311 | 0 | > | 1280 | 0.819 | 0 | > | 2560 | 2.302 | 0 | > | 5120 | 8.878 | 0 | > | 10240 | 32.706 | 0 | > > Graphical comparison: > > > > > There is ~80x improvement. > > However, the scaling is still not quite linear: > > > > > So, there is still some power-law nonlinearity in the tangle code. > > Benchmarking revealed the following: > 8259 95% - org-babel-tangle-file > 8259 95% - org-babel-tangle > 8170 94% - org-babel-tangle-collect-blocks > 3620 41% - org-in-archived-heading-p > 3600 41% org-before-first-heading-p > > Showing that nonlinear scaling comes from regexp search. > > Caching org-before-first-heading-p improves the performance further (see > Org 9.6-dev no self-verify + patch curves): > > | N blocks | runtime | # of GCs | > |----------+---------+----------| > | 10 | 0.118 | 0 | > | 20 | 0.106 | 0 | > | 40 | 0.136 | 0 | > | 80 | 0.157 | 0 | > | 160 | 0.139 | 0 | > | 320 | 0.212 | 0 | > | 640 | 0.542 | 0 | > | 1280 | 0.797 | 0 | > | 2560 | 1.533 | 0 | > | 5120 | 4.651 | 0 | > | 10240 | 16.745 | 0 | > > The profiling gives: > > 16817 63% - org-babel-tangle-file > 16280 61% - org-babel-tangle > 16200 61% - org-babel-tangle-collect-blocks > 1360 5% + org-babel-tangle-single-block > 1210 4% + org-babel-get-src-block-info > > Most of the CPU time is spent in org-babel-tangle-collect-blocks, which > is basically another regexp search for all the source blocks in buffer. > The scaling is still slightly non-linear - maybe your source block > regexp is too complex: > > (defvar org-babel-src-block-regexp > (concat > ;; (1) indentation (2) lang > "^\\([ \t]*\\)#\\+begin_src[ \t]+\\([^ \f\t\n\r\v]+\\)[ \t]*" > ;; (3) switches > "\\([^\":\n]*\"[^\"\n*]*\"[^\":\n]*\\|[^\":\n]*\\)" > ;; (4) header arguments > "\\([^\n]*\\)\n" > ;; (5) body > "\\([^\000]*?\n\\)??[ \t]*#\\+end_src") > "Regexp used to identify code blocks.") > > On the other hand, the test data is already within quite non-realistic > over 5000 number of blocks. Probably, further performance improvement is > not very useful (we already have some overheads at smaller N). > > Best, > Ihor > > ----- > The Org file used to generate plots: > > #+name: nocache > | N blocks | runtime | # of GCs | > > |----------+---------+----------| > | 10 | 0.027 | 0 | > | 20 | 0.049 | 0 | > | 40 | 0.121 | 0 | > | 80 | 0.391 | 0 | > | 160 | 1.426 | 0 | > | 320 | 6.765 | 0 | > | 640 | 23.972 | 0 | > > #+name: cache > | N blocks | runtime | # of GCs | > > |----------+---------+----------| > | 10 | 0.030 | 0 | > | 20 | 0.067 | 0 | > | 40 | 0.065 | 0 | > | 80 | 0.081 | 0 | > | 160 | 0.214 | 0 | > | 320 | 0.597 | 0 | > | 640 | 2.225 | 0 | > | 1280 | 9.221 | 0 | > | 2560 | 36.966 | 0 | > > #+name: cache-no-self > | N blocks | runtime | # of GCs | > > |----------+---------+----------| > | 10 | 0.078 | 0 | > | 20 | 0.075 | 0 | > | 40 | 0.063 | 0 | > | 80 | 0.085 | 0 | > | 160 | 0.095 | 0 | > | 320 | 0.178 | 0 | > | 640 | 0.311 | 0 | > | 1280 | 0.819 | 0 | > | 2560 | 2.302 | 0 | > | 5120 | 8.878 | 0 | > | 10240 | 32.706 | 0 | > > #+name: cache-no-self+fix > | N blocks | runtime | # of GCs | > > |----------+---------+----------| > | 10 | 0.118 | 0 | > | 20 | 0.106 | 0 | > | 40 | 0.136 | 0 | > | 80 | 0.157 | 0 | > | 160 | 0.139 | 0 | > | 320 | 0.212 | 0 | > | 640 | 0.542 | 0 | > | 1280 | 0.797 | 0 | > | 2560 | 1.533 | 0 | > | 5120 | 4.651 | 0 | > | 10240 | 16.745 | 0 | > > #+begin_src gnuplot :var d1=3Dnocache :var d2=3Dcache :var d3=3Dcache-no-= self :var d4=3Dcache-no-self+fix :file benchmark1.png > set title 'Tangle code performance timing' > US=3D'u 1:2 w lp ps 2' > set xlabel "N blocks" > set ylabel "Time, sec" > set key top right > plot d1 @US t'Org 9.5.2 stable', d2 @US t'Org 9.6-dev', d3 @US t'Org 9.6-= dev no self-verify', d4 @US t'Org 9.6-dev no self-verify + patch' > #+end_src > > > #+RESULTS[edd2a2d5d80b31876917faee349ed71ba0fe239a]: > [[file:/home/yantar92/.data/52/0930af-75ae-4d88-ae6a-d8dde39ecc72/benchma= rk1.png]] > > #+begin_src gnuplot :var d1=3Dnocache :var d2=3Dcache :var d3=3Dcache-no-= self :var d4=3Dcache-no-self+fix :file benchmark2.png > set title 'Tangle code performance scaling (normalized)' > US=3D'w lp ps 2' > set xlabel "N blocks" > set ylabel "Time, normalized by time at N=3D640" > set key top left > set xrange [0:6000] > plot d2 u 1:($2/2.225) @US t'Org 9.6-dev', d3 u 1:($2/0.311) @US t'Org 9.= 6-dev no self-verify', d1 u 1:($2/23.972) @US t'Org 9.5.2 stable', d4 u 1:(= $2/0.542) @US t'Org 9.6-dev no self-verify + patch', x*x/870000 t'x^2',=20 > #+end_src > > #+RESULTS[b170ef78ac377f6d2ad1c2eabb20cd62dc0ea33f]: > [[file:/home/yantar92/.data/52/0930af-75ae-4d88-ae6a-d8dde39ecc72/benchma= rk2.png]] This is nice work. Well done on all you and others have been doing along th= ese lines to improve performance.=20