Horton

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

Andres Freund <andres@2ndquadrant.com>

View thread
From: Andres Freund <andres@2ndquadrant.com>
To: pgsql-hackers@postgresql.org
Cc: Tom Lane <tgl@sss.pgh.pa.us>, Peter Geoghegan <peter@2ndquadrant.com>, Robert Haas <robertmhaas@gmail.com>
Date: 2012-06-22T14:48:23Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Don't waste the last segment of each 4GB logical log file.

  2. Stamp HEAD as 9.3devel.

  3. Wake WALSender to reduce data loss at failover for async commit.

  4. Make the visibility map crash-safe.

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