On Friday, June 22, 2012 04:41:20 PM Tom Lane wrote:
> Andres Freund <andres@2ndquadrant.com> writes:
> > Oh, I and Peter weren't talking about the pg_list.h stuff, it was about
> > my 'embedded list' implementation which started this subthread. The
> > pg_list.h/list.c stuff isn't problematic as far as I have seen in
> > profiles; its checks are pretty simple so I do not find that surprising.
> > We might want to disable it by default anyway.
> >
> > In my code the list checking stuff iterates over the complete list after
> > modifications and checks that all prev/next pointers are correct so its
> > linear in itself...
>
> Well, so does list.c, so I'd expect the performance risks to be similar.
> Possibly you're testing on longer lists than are typical in the backend.
I don't think list.c does so:
static void
check_list_invariants(const List *list)
{if (list == NIL) return;
Assert(list->length > 0);Assert(list->head != NULL);Assert(list->tail != NULL);
Assert(list->type == T_List || list->type == T_IntList || list->type == T_OidList);
if (list->length == 1) Assert(list->head == list->tail);if (list->length == 2) Assert(list->head->next ==
list->tail);Assert(list->tail->next== NULL);
}
But yes, the lists I deal with are significantly longer, so replacing O(n) by
O(n^2) is rather painful there...
Andres
-- Andres Freund http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services