Neil Conway <neilc@samurai.com> writes:
> (2) An additional word per List is hardly a prohibitive amount of
> overhead, as we don't create an obscene number of Lists (saving a
> word per ListCell would be a different matter).
Actually, it's free, considering that the alternatives are
int NodeTag;
foo *head;
foo *tail;
int length; -- or not.
On a 32-bit-pointer machine, you got your choice of 12 or 16 bytes ---
but palloc will round 12 to 16 anyway. On a 64-bit-pointer machine,
you got your choice of 20 or 24 bytes ... still no win, even if palloc
weren't going to round it to 32, because the MAXALIGN quantum is almost
certainly 8 on such a machine.
This does suggest that it might be worth making the struct layout be
int NodeTag;
int length;
foo *head;
foo *tail;
since this would avoid some padding overhead on a machine where pointers
are 8 bytes and need 8-byte alignment. It probably doesn't help given
the current implementation of palloc, but why throw away padding space?
> My intuition/judgement is that we call length() often enough in the
> backend that it is worth keeping track of the list length:
Its use in equal() and potential use for existing equali() and equalo()
calls seems like alone sufficient reason to do so. But it should be
relatively painless to prove this one way or the other by building the
code to keep track and then ripping out that code and putting back the
O(N) length() implementation. Benchmarking the two would settle the
matter, or at least give us real data to argue about...
regards, tom
