Re: Double linking MemoryContext children

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?
        regards, tom lane