On 09/11/2015 09:38 AM, Tom Lane wrote:
> Jan Wieck <jan@wi3ck.info> writes:
>> The attached script demonstrates an O(N^2) problem we recently became
>> aware of. The script simply executes a large anonymous code block that
>> doesn't do anything useful. Usage is
>
>> ./t1.py [NUM_STMTS] | psql [DBNAME]
>
>> NUM_STMTS defaults to 20,000. The code block executes rather fast, but
>> the entire script runs for over a minute (at 20,000 statements) on a
>> 2.66 GHz Xeon.
>
>> The time is spent when all the prepared SPI statements are freed at the
>> end of execution. All prepared SPI statements are children of the Cache
>> context. MemoryContext children are a single linked list where new
>> members are inserted at the head. This works best when children are
>> created and destroyed in a last-in-first-out pattern. SPI however
>> destroys the SPI statements in the order they were created, forcing
>> MemoryContextSetParent() to traverse the entire linked list for each child.
>
>> The attached patch makes MemoryContext children a double linked list
>> that no longer needs any list traversal no find the position of the
>> child within the list.
>
> Seems less invasive to fix SPI to delete in the opposite order?
That would assume that there are no other code paths that destroy memory
contexts out of LIFO order.
Regards, Jan
--
Jan Wieck
Senior Software Engineer
http://slony.info