Re: [PATCH 04/16] Add embedded list interface (header only)

On Friday, June 22, 2012 04:41:20 PM Tom Lane wrote:
> Andres Freund <andres(at)2ndquadrant(dot)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