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.
Regards, Jan
--
Jan Wieck
Senior Software Engineer
http://slony.info
diff --git a/src/backend/utils/mmgr/mcxt.c b/src/backend/utils/mmgr/mcxt.c
index 705f3ef..d1a2e02 100644
--- a/src/backend/utils/mmgr/mcxt.c
+++ b/src/backend/utils/mmgr/mcxt.c
@@ -331,21 +331,13 @@ MemoryContextSetParent(MemoryContext context, MemoryContext new_parent)
{
MemoryContext parent = context->parent;
- if (context == parent->firstchild)
- parent->firstchild = context->nextchild;
+ if (context->prevchild != NULL)
+ context->prevchild->nextchild = context->nextchild;
else
- {
- MemoryContext child;
-
- for (child = parent->firstchild; child; child = child->nextchild)
- {
- if (context == child->nextchild)
- {
- child->nextchild = context->nextchild;
- break;
- }
- }
- }
+ parent->firstchild = context->nextchild;
+
+ if (context->nextchild != NULL)
+ context->nextchild->prevchild = context->prevchild;
}
/* And relink */
@@ -353,12 +345,16 @@ MemoryContextSetParent(MemoryContext context, MemoryContext new_parent)
{
AssertArg(MemoryContextIsValid(new_parent));
context->parent = new_parent;
+ context->prevchild = NULL;
context->nextchild = new_parent->firstchild;
+ if (new_parent->firstchild != NULL)
+ new_parent->firstchild->prevchild = context;
new_parent->firstchild = context;
}
else
{
context->parent = NULL;
+ context->prevchild = NULL;
context->nextchild = NULL;
}
}
@@ -714,6 +710,7 @@ MemoryContextCreate(NodeTag tag, Size size,
node->methods = methods;
node->parent = NULL; /* for the moment */
node->firstchild = NULL;
+ node->prevchild = NULL;
node->nextchild = NULL;
node->isReset = true;
node->name = ((char *) node) + size;
@@ -728,6 +725,8 @@ MemoryContextCreate(NodeTag tag, Size size,
{
node->parent = parent;
node->nextchild = parent->firstchild;
+ if (parent->firstchild != NULL)
+ parent->firstchild->prevchild = node;
parent->firstchild = node;
/* inherit allowInCritSection flag from parent */
node->allowInCritSection = parent->allowInCritSection;
diff --git a/src/include/nodes/memnodes.h b/src/include/nodes/memnodes.h
index 577ab9c..bbb58bd 100644
--- a/src/include/nodes/memnodes.h
+++ b/src/include/nodes/memnodes.h
@@ -79,6 +79,7 @@ typedef struct MemoryContextData
MemoryContextMethods *methods; /* virtual function table */
MemoryContext parent; /* NULL if no parent (toplevel context) */
MemoryContext firstchild; /* head of linked list of children */
+ MemoryContext prevchild; /* previous child of same parent */
MemoryContext nextchild; /* next child of same parent */
char *name; /* context name (just for debugging) */
MemoryContextCallback *reset_cbs; /* list of reset/delete callbacks */
#!/usr/bin/env python
import sys
def main(argv):
if len(argv) == 0:
num_stmts = 20000
else:
num_stmts = int(argv[0])
print "\\timing"
print "DO $$"
print "DECLARE"
print " ts1 timestamp;"
print " ts2 timestamp;"
print " dummy integer;"
print "BEGIN"
print " SELECT timeofday() INTO ts1;"
print " RAISE NOTICE 'start: %', ts1;"
for i in range(0, num_stmts):
print " SELECT %d INTO dummy;"%i
print " SELECT timeofday() INTO ts2;"
print " RAISE NOTICE 'end: %', ts2;"
print " RAISE NOTICE 'duration: %', (ts2 - ts1);"
print "END;"
print "$$;"
if __name__ == '__main__':
sys.exit(main(sys.argv[1:]))
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
