On 10/28/21, 3:15 PM, "Andres Freund" <and...@anarazel.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