Re: Double linking MemoryContext children

Jan Wieck <jan(at)wi3ck(dot)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?

regards, tom lane