I cc'ed the hackers list -- I hope you won't mind.
On Wednesday 17 March 2004 02:34 am, Neil Conway wrote:
> "Jonathan M. Gardner" <jgardner@jonathangardner.net> writes:
> > I formatted and added some documentation for List, FastList, and
> > Node. You can also browse to the list.c, pg_list.h, and nodes.h to
> > see some more of my documentation.
>
> Just a heads-up: list.c and pg_list.h will be reimplemented fairly
> soon in CVS HEAD (the code isn't committed yet, but there's a
> preliminary patch I can send you if you're interested). So if you're
> going to spend some time documenting stuff, choosing something else
> might be a good place to start (dynahash, maybe?).
>
Send the patch over. I'd love to see it. I'll add some Doxygen-friendly
documentation to it if you don't mind. Shouldn't this be in a branch? It
sounds like it's going to be a ton of work, as the interface may change.
I'm actually intensely interested in the Query struct right now as I need to
understand it to get Materialized Views working right. The List concept is
plain enough that I didn't waste much time documenting it -- mostly adding
an extra '*' here and there to tell Doxygen that it was documentation and
not just a comment.
> BTW, per your comment on Lisp-ness: actually, the lispy style of
> linked list implementation (cons cells) is the cause of some
> performance problems in the backend. It means that both length() and
> lappend() are O(n) operations; nconc() is also O(n), and equal() is a
> lot slower than it could be (once length() is O(1), we can
> immediately reject lists with different lengths as being
> non-equal). The linked list rewrite gets rid of FastList (which is
> just an ugly performance hack) and replaces the linked list
> implementation with a new design that does not use cons cells. We
> manage the linked list through a pointer to a separate "List" struct,
> rather than merely a pointer to the head node. We also store the
> length of the list in the struct. As a result, all the above
> operations are now constant time (well, except for equal(), but that
> is now significantly faster in the common case).
>
It looks like the only thing it won't do well is random accesses. That
hardly ever happens in PostgreSQL, though, right?
--
Jonathan Gardner
jgardner@jonathangardner.net