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 1mimzj-0003Ox-UL for pgsql-hackers@arkaria.postgresql.org; Fri, 05 Nov 2021 00:22:11 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1mimzi-0005hL-4O for pgsql-hackers@arkaria.postgresql.org; Fri, 05 Nov 2021 00:22:10 +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 1mimzh-0005hC-S6 for pgsql-hackers@lists.postgresql.org; Fri, 05 Nov 2021 00:22:09 +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 1mimzb-0000ui-KY for pgsql-hackers@postgresql.org; Fri, 05 Nov 2021 00:22:08 +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 1A50Lu8N364795; Thu, 4 Nov 2021 20:21:57 -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: <20211104221248.pgo4h6wvnjl6uvkb@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> Comments: In-reply-to Andres Freund message dated "Thu, 04 Nov 2021 15:12:48 -0700" MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-ID: <364793.1636071716.1@sss.pgh.pa.us> Content-Transfer-Encoding: quoted-printable Date: Thu, 04 Nov 2021 20:21:56 -0400 Message-ID: <364794.1636071716@sss.pgh.pa.us> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk Andres Freund writes: > I wonder if it's worth adding a note to list_delete_first() mentioning i= ts > O(N) behaviour. It's not immediately visible from the code, and from the= list > name one could very well be excused to not be worried about O(N) costs. Hm. I think it's not the only list function with O(N) behavior; in fact there used to be more such functions than there are now. But I could get behind a patch that annotates all of them. regards, tom lane