| From: | "Bossart, Nathan" <bossartn(at)amazon(dot)com> |
|---|---|
| To: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Andres Freund <andres(at)anarazel(dot)de> |
| Cc: | Kyotaro Horiguchi <horikyota(dot)ntt(at)gmail(dot)com>, "sulamul(at)gmail(dot)com" <sulamul(at)gmail(dot)com>, "pgsql-hackers(at)postgresql(dot)org" <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: inefficient loop in StandbyReleaseLockList() |
| Date: | 2021-10-28 22:40:12 |
| Message-ID: | 366F868D-ECEA-4EDA-A03F-8D5795DB0849@amazon.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On 10/28/21, 3:15 PM, "Andres Freund" <andres(at)anarazel(dot)de> wrote:
> Which leads to to wonder whether the better fix would be to switch to deleting
> the last element, but still use the while (!empty) style. That should convert
> the O(n^2) due to 1cff1b9 back to O(n). It might or might not be faster/slower
> than using foreach(), but it should be within the same ballpark.
Yeah, deleting from the end of the list yields a similar improvement.
foreach() appears to be slightly faster, but the difference is
basically negligible. For a list of a million integers, foreach()
consistently takes ~12ms, deleting from the end of the list takes
~15ms, and deleting from the beginning of the list takes ~4 minutes.
Nathan
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Justin Pryzby | 2021-10-28 22:59:22 | add more support for PG_DIAG_COLUMN_NAME |
| Previous Message | Tom Lane | 2021-10-28 22:24:51 | Re: inefficient loop in StandbyReleaseLockList() |