Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mjUFk-0001aQ-Oa for pgsql-hackers@arkaria.postgresql.org; Sat, 06 Nov 2021 22:33:36 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1mjUFD-0002Oz-0D for pgsql-hackers@arkaria.postgresql.org; Sat, 06 Nov 2021 22:33:03 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mjUFC-0002Oq-JR for pgsql-hackers@lists.postgresql.org; Sat, 06 Nov 2021 22:33:02 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mjUFA-0006fV-Nb for pgsql-hackers@postgresql.org; Sat, 06 Nov 2021 22:33:01 +0000 Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1]) by sss.pgh.pa.us (8.15.2/8.15.2) with ESMTP id 1A6MWs4Y613308; Sat, 6 Nov 2021 18:32:54 -0400 From: Tom Lane To: Andres Freund cc: bossartn@amazon.com, Kyotaro Horiguchi , michael@paquier.xyz, sulamul@gmail.com, pgsql-hackers@postgresql.org Subject: Re: inefficient loop in StandbyReleaseLockList() In-reply-to: <20211106222251.msmjshfhvcvy3lpd@alap3.anarazel.de> References: <1138901.1635782315@sss.pgh.pa.us> <1311319.1635804078@sss.pgh.pa.us> <20211102.114313.713245704579079227.horikyota.ntt@gmail.com> <1376384.1635862908@sss.pgh.pa.us> <1512317.1635867355@sss.pgh.pa.us> <20211104221248.pgo4h6wvnjl6uvkb@alap3.anarazel.de> <364794.1636071716@sss.pgh.pa.us> <588672.1636221972@sss.pgh.pa.us> <20211106222251.msmjshfhvcvy3lpd@alap3.anarazel.de> Comments: In-reply-to Andres Freund message dated "Sat, 06 Nov 2021 15:22:51 -0700" MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-ID: <613306.1636237974.1@sss.pgh.pa.us> Content-Transfer-Encoding: quoted-printable Date: Sat, 06 Nov 2021 18:32:54 -0400 Message-ID: <613307.1636237974@sss.pgh.pa.us> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk Andres Freund writes: > On 2021-11-06 14:06:12 -0400, Tom Lane wrote: >> + * Note that this takes time proportional to the length of the list, >> + * since the remaining entries must be moved. >> */ >> List * >> list_delete_first(List *list) > Perhaps we could point to list_delete_last()? But it's an improvement wi= thout > that too. Good point. The note at list_delete_last that it's O(1) isn't really on point --- instead, the text for list_delete_first should be like + * Note that this takes time proportional to the length of the list, + * since the remaining entries must be moved. Consider reversing the + * list order so that you can use list_delete_last() instead. However, + * if that causes you to replace lappend() with lcons(), you haven't + * improved matters. regards, tom lane