Re: equal() perf tweak

Neil Conway <neilc(at)samurai(dot)com> writes:
> On Mon, 2003-11-03 at 18:19, Tom Lane wrote:
>> I have already done something much like this in a few hotspots using the
>> FastList structure. But notationally, it's a pain in the neck compared
>> to the existing List code. If you can think of a way to implement this
>> without adding a lot of notational cruft, I'd sure be for it.

> Which specific notational capabilities did you have in mind? i.e. is it
> just something like 'foreach' loop syntax sugar, or something else in
> particular?

Well, if you look at the FastList mods I made, such as this one:
http://developer.postgresql.org/cvsweb.cgi/pgsql-server/src/backend/optimizer/plan/createplan.c.diff?r1=1.143&r2=1.144
they are just plain messy. Part of this comes from the fact that I
didn't want to engage in a wholesale rewrite, and so the code had to
interoperate with List-based stuff instead of replacing it.

I had an idea this morning about a way to reduce the notational changes
needed. Suppose we redefine typedef List as the list header structure,
so that references to Lists are still of type "List *":

typedef struct List
{
NodeTag type; // T_List, T_IntList, or T_OidList
struct ListCell *lhead;
struct ListCell *ltail;
int llength;
} List;

typedef struct ListCell
{
union
{
void *ptr_value;
int int_value;
Oid oid_value;
} elem;
struct ListCell *next;
} ListCell;

(This is the same as what you suggested except that I put a NodeTag
back into List; we really can't do without that.)

The idea that makes this work is to stipulate that "(List *) NULL"
is still a valid representation of an empty list. Then it still works
to initialize a List* variable with

List *mylist = NIL;

which immediately gets rid of half of the notational problem with
FastList (messy initialization). The first lcons() or lappend()
operation would have to palloc the List header as well as the first
ListCell, but that's no problem.

I think actually you'd want to specify that "(List *) NULL" is the
*only* valid representation of an empty list, because otherwise you
have to insert some exceedingly ugly special-case code in equal() to
get it to treat a NULL pointer as equal to a pointer to a List header
that has zero llength. But this is not so bad, because it means that the
special-case code for "(List *) NULL" replaces the special cases that
would otherwise deal with lhead or ltail being NULL, instead of being an
additional special case.

Hmm ... taking that one step further, you could probably avoid the need
for two palloc's in the first lcons/lappend if the List header were
combined with the first ListCell. This would make for some grottiness
in ldelete when removing the first list entry, but that's probably
a good tradeoff.

The above has a number of notational advantages over what we have now
--- for example, we can eliminate the separate routines for equali()
and equalo(), because the list header's NodeTag will tell which kind of
elements the list holds, and so the general equal() routine can be made
to handle all cases correctly. Also, the contents of ListCell are
reduced from 3 words to 2 (we don't bother storing a NodeTag in each
individual cell) which makes for a nice space savings on big lists.
(I think to exploit this, aset.c would have to be tweaked to make the
minimum allocation chunk 8 bytes rather than 16, but that's easy.)

Most of this change could be hidden within the List-related code. The
only serious objection I see is that the iterator variable needed for
traversing a List now needs to be of type ListCell* rather than List*.
That would require touching a lot of places, though it's a fairly simple
change. All the other List operations could keep their existing API.

I'm starting to like this ... I'd love to revert those FastList changes.

regards, tom lane