POC: converting Lists into arrays
For quite some years now there's been dissatisfaction with our List
data structure implementation. Because it separately palloc's each
list cell, it chews up lots of memory, and it's none too cache-friendly
because the cells aren't necessarily adjacent. Moreover, our typical
usage is to just build a list by repeated lappend's and never modify it,
so that the flexibility of having separately insertable/removable list
cells is usually wasted.
Every time this has come up, I've opined that the right fix is to jack
up the List API and drive a new implementation underneath, as we did
once before (cf commit d0b4399d81). I thought maybe it was about time
to provide some evidence for that position, so attached is a POC patch
that changes Lists into expansible arrays, while preserving most of
their existing API.
The big-picture performance change is that this makes list_nth()
a cheap O(1) operation, while lappend() is still pretty cheap;
on the downside, lcons() becomes O(N), as does insertion or deletion
in the middle of a list. But we don't use lcons() very much
(and maybe a lot of the existing usages aren't really necessary?),
while insertion/deletion in long lists is a vanishingly infrequent
operation. Meanwhile, making list_nth() cheap is a *huge* win.
The most critical thing that we lose by doing this is that when a
List is modified, all of its cells may need to move, which breaks
a lot of code that assumes it can insert or delete a cell while
hanging onto a pointer to a nearby cell. In almost every case,
this takes the form of doing list insertions or deletions inside
a foreach() loop, and the pointer that's invalidated is the loop's
current-cell pointer. Fortunately, with list_nth() now being so cheap,
we can replace these uses of foreach() with loops using an integer
index variable and fetching the next list element directly with
list_nth(). Most of these places were loops around list_delete_cell
calls, which I replaced with a new function list_delete_nth_cell
to go along with the emphasis on the integer index.
I don't claim to have found every case where that could happen,
although I added debug support in list.c to force list contents
to move on every list modification, and this patch does pass
check-world with that support turned on. I fear that some such
bugs remain, though.
There is one big way in which I failed to preserve the old API
syntactically: lnext() now requires a pointer to the List as
well as the current ListCell, so that it can figure out where
the end of the cell array is. That requires touching something
like 150 places that otherwise wouldn't have had to be touched,
which is annoying, even though most of those changes are trivial.
I thought about avoiding that by requiring Lists to keep a "sentinel"
value in the cell after the end of the active array, so that lnext()
could look for the sentinel to detect list end. However, that idea
doesn't really work, because if the list array has been moved, the
spot where the sentinel had been could have been reallocated and
filled with something else. So this'd offer no defense against the
possibility of a stale ListCell pointer, which is something that
we absolutely need defenses for. As the patch stands we can have
quite a strong defense, because we can check whether the presented
ListCell pointer actually points into the list's current data array.
Another annoying consequence of lnext() needing a List pointer is that
the List arguments of foreach() and related macros are now evaluated
each time through the loop. I could only find half a dozen places
where that was actually unsafe (all fixed in the draft patch), but
it's still bothersome. I experimented with ways to avoid that, but
the only way I could get it to work was to define foreach like this:
#define foreach(cell, l) for (const List *cell##__foreach = foreach_setup(l, &cell); cell != NULL; cell = lnext(cell##__foreach, cell))
static inline const List *
foreach_setup(const List *l, ListCell **cell)
{
*cell = list_head(l);
return l;
}
That works, but there are two problems. The lesser one is that a
not-very-bright compiler might think that the "cell" variable has to
be forced into memory, because its address is taken. The bigger one is
that this coding forces the "cell" variable to be exactly "ListCell *";
you can't add const or volatile qualifiers to it without getting
compiler warnings. There are actually more places that'd be affected
by that than by the need to avoid multiple evaluations. I don't think
the const markings would be a big deal to lose, and the two places in
do_autovacuum that need "volatile" (because of a nearby PG_TRY) could
be rewritten to not use foreach. So I'm tempted to do that, but it's
not very pretty. Maybe somebody can think of a better solution?
There's a lot of potential follow-on work that I've not touched yet:
1. This still involves at least two palloc's for every nonempty List,
because I kept the header and the data array separate. Perhaps it's
worth allocating those in one palloc. However, right now there's an
assumption that the header of a nonempty List doesn't move when you
change its contents; that's embedded in the API of the lappend_cell
functions, and more than likely there's code that depends on that
silently because it doesn't bother to store the results of other
List functions back into the appropriate pointer. So if we do that
at all I think it'd be better tackled in a separate patch; and I'm
not really convinced it's worth the trouble and extra risk of bugs.
2. list_qsort() is now absolutely stupidly defined. It should just
qsort the list's data array in-place. But that requires an API
break for the caller-supplied comparator, since there'd be one less
level of indirection. I think we should change this, but again it'd
be better done as an independent patch to make it more visible in the
git history.
3. There are a number of places where we've built flat arrays
paralleling Lists, such as the planner's simple_rte_array. That's
pointless now and could be undone, buying some code simplicity.
Various other micro-optimizations could doubtless be done too;
I've not looked hard.
I haven't attempted any performance measurements on this, but at
least in principle it should speed things up a bit, especially
for complex test cases involving longer Lists. I don't have any
very suitable test cases at hand, anyway.
I think this is too late for v12, both because of the size of the
patch and because of the likelihood that it introduces a few bugs.
I'd like to consider pushing it early in the v13 cycle, though.
regards, tom lane
Attachments:
Hello Tom,
For quite some years now there's been dissatisfaction with our List
data structure implementation. Because it separately palloc's each
list cell, it chews up lots of memory, and it's none too cache-friendly
because the cells aren't necessarily adjacent. Moreover, our typical
usage is to just build a list by repeated lappend's and never modify it,
so that the flexibility of having separately insertable/removable list
cells is usually wasted.Every time this has come up, I've opined that the right fix is to jack
up the List API and drive a new implementation underneath, as we did
once before (cf commit d0b4399d81). I thought maybe it was about time
to provide some evidence for that position, so attached is a POC patch
that changes Lists into expansible arrays, while preserving most of
their existing API.
My 0.02ￜ about this discussion (I assume that it is what you want): I had
the same issue in the past on a research project. I used a similar but
slightly different approach:
I did not touch the existing linked list implementation but provided
another data structure, which was a linked list of buckets (small arrays)
stack kept from the head, with buckets allocated on need but not freed
until the final deallocation. If pop was used extensively, a linked list
of freed bucket was kept, so that they could be reused. Some expensive
list-like functions were not provided, so the data structure could replace
lists in some but not all instances, which was fine. The dev had then to
choose which data structure was best for its use case, and critical
performance cases could be replaced.
Note that a "foreach", can be done reasonably cleanly with a
stack-allocated iterator & c99 struct initialization syntax, which is now
allowed in pg AFAICR, something like:
typedef struct { ... } stack_iterator;
#define foreach_stack(i, s) \
for (stack_iterator i = SITER_INIT(s); SITER_GO_ON(&i); SITER_NEXT(&i))
Used with a simple pattern:
foreach_stack(i, s)
{
item_type = GET_ITEM(i);
...
}
This approach is not as transparent as your approach, but changes are
somehow less extensive, and it provides choices instead of trying to do a
one solution must fit all use cases. Also, it allows to revisit the
pointer to reference choices on some functions with limited impact.
In particular the data structure is used for a "string buffer"
implementation (like the PQExpBuffer stuff).
--
Fabien.
On Sat, Feb 23, 2019 at 9:24 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Every time this has come up, I've opined that the right fix is to jack
up the List API and drive a new implementation underneath, as we did
once before (cf commit d0b4399d81). I thought maybe it was about time
to provide some evidence for that position, so attached is a POC patch
that changes Lists into expansible arrays, while preserving most of
their existing API.
I'm not really convinced that this is the way to go. The thing is,
any third-party code people have that uses a List may simply break.
If you kept the existing List and changed a bunch of existing code to
use a new Vector implementation, or Thomas's SimpleVector stuff, then
that wouldn't happen. The reason why people - or at least me - have
been reluctant to accept that you can just jack up the API and drive a
new implementation underneath is that the new implementation will
involve breaking guarantees on which existing code relies; indeed,
your email makes it pretty clear that this is the case. If you could
replace the existing implementation without breaking any code, that
would be a no-brainer but there's no real way to do that and get the
performance benefits you're seeking to obtain.
It is also perhaps worth mentioning that reimplementing a List as an
array means that it is... not a list. That is a pretty odd state of
affairs, and to me is another sign that we want to leave the existing
thing alone and convert some/most/all core code to use a new thing.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Robert Haas <robertmhaas@gmail.com> writes:
On Sat, Feb 23, 2019 at 9:24 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Every time this has come up, I've opined that the right fix is to jack
up the List API and drive a new implementation underneath, as we did
once before (cf commit d0b4399d81).
I'm not really convinced that this is the way to go. The thing is,
any third-party code people have that uses a List may simply break.
If you kept the existing List and changed a bunch of existing code to
use a new Vector implementation, or Thomas's SimpleVector stuff, then
that wouldn't happen.
I'm not following your point here. If we change key data structures
(i.e. parsetrees, plan trees, execution trees) to use some other list-ish
API, that *in itself* breaks everything that accesses those data
structures. The approach I propose here isn't zero-breakage, but it
requires far fewer places to be touched than a complete API replacement
would do.
Just as with the dlist/slist stuff, inventing a new list API might be
acceptable for all-new data structures that didn't exist before, but
it isn't going to really help for code and data structures that've been
around for decades.
If you could
replace the existing implementation without breaking any code, that
would be a no-brainer but there's no real way to do that and get the
performance benefits you're seeking to obtain.
Yup. So are you saying that we'll never redesign parsetrees again?
We break things regularly, as long as the cost/benefit justifies it.
It is also perhaps worth mentioning that reimplementing a List as an
array means that it is... not a list. That is a pretty odd state of
affairs, and to me is another sign that we want to leave the existing
thing alone and convert some/most/all core code to use a new thing.
I completely disagree. Your proposal is probably an order of magnitude
more painful than the approach I suggest here, while not really offering
any additional performance benefit (or if you think there would be some,
you haven't explained how). Strictly on cost/benefit grounds, it isn't
ever going to happen that way.
regards, tom lane
On Mon, Feb 25, 2019 at 1:17 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I'm not following your point here. If we change key data structures
(i.e. parsetrees, plan trees, execution trees) to use some other list-ish
API, that *in itself* breaks everything that accesses those data
structures. The approach I propose here isn't zero-breakage, but it
requires far fewer places to be touched than a complete API replacement
would do.
Sure, but if you have third-party code that touches those things,
it'll fail to compile. With your proposed approach, there seems to be
a risk that it will compile but not work.
Yup. So are you saying that we'll never redesign parsetrees again?
We break things regularly, as long as the cost/benefit justifies it.
I'm mostly objecting to the degree that the breakage is *silent*.
I completely disagree. Your proposal is probably an order of magnitude
more painful than the approach I suggest here, while not really offering
any additional performance benefit (or if you think there would be some,
you haven't explained how). Strictly on cost/benefit grounds, it isn't
ever going to happen that way.
Why would it be ten times more painful, exactly?
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Robert Haas <robertmhaas@gmail.com> writes:
On Mon, Feb 25, 2019 at 1:17 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I'm not following your point here. If we change key data structures
(i.e. parsetrees, plan trees, execution trees) to use some other list-ish
API, that *in itself* breaks everything that accesses those data
structures. The approach I propose here isn't zero-breakage, but it
requires far fewer places to be touched than a complete API replacement
would do.
Sure, but if you have third-party code that touches those things,
it'll fail to compile. With your proposed approach, there seems to be
a risk that it will compile but not work.
Failing to compile isn't really a benefit IMO. Now, if we could avoid
the *semantic* differences (like whether it's safe to hold onto a pointer
into a List while doing FOO on the list), then we'd have something.
The biggest problem with what I'm proposing is that it doesn't always
manage to do that --- but any other implementation is going to break
such assumptions too. I do not think that forcing cosmetic changes
on people is going to do much to help them revisit possibly-hidden
assumptions like those. What will help is to provide debugging aids to
flush out such assumptions, which I've endeavored to do in this patch.
And I would say that any competing proposal is going to be a failure
unless it provides at-least-as-effective support for flushing out bugs
in naive updates of existing List-using code.
I completely disagree. Your proposal is probably an order of magnitude
more painful than the approach I suggest here, while not really offering
any additional performance benefit (or if you think there would be some,
you haven't explained how). Strictly on cost/benefit grounds, it isn't
ever going to happen that way.
Why would it be ten times more painful, exactly?
Because it involves touching ten times more code (and that's a very
conservative estimate). Excluding changes in pg_list.h + list.c,
what I posted touches approximately 600 lines of code (520 insertions,
644 deletions to be exact). For comparison's sake, there are about
1800 uses of foreach in the tree, each of which would require at least
3 changes to replace (the foreach itself, the ListCell variable
declaration, and at least one lfirst() reference in the loop body).
So we've already blown past 5000 lines worth of changes if we want to
do it another way ... and that's just *one* component of the List API.
Nor is there any reason to think the changes would be any more mechanical
than what I had to do here. (No fair saying that I already found the
trouble spots, either. A different implementation would likely break
assumptions in different ways.)
If I said your proposal involved two orders of magnitude more work,
I might not be far off the mark.
regards, tom lane
On Mon, Feb 25, 2019 at 10:59 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Because it involves touching ten times more code (and that's a very
conservative estimate). Excluding changes in pg_list.h + list.c,
what I posted touches approximately 600 lines of code (520 insertions,
644 deletions to be exact). For comparison's sake, there are about
1800 uses of foreach in the tree, each of which would require at least
3 changes to replace (the foreach itself, the ListCell variable
declaration, and at least one lfirst() reference in the loop body).
If we knew that the list code was the bottleneck in a handful of
cases, then I'd come down on Robert's side here. It would then be
possible to update the relevant bottlenecked code in an isolated
fashion, while getting the lion's share of the benefit. However, I
don't think that that's actually possible. The costs of using Lists
everywhere are real and measurable, but it's also highly distributed.
At least, that's my recollection from previous discussion from several
years back. I remember talking about this with Andres in early 2016.
So we've already blown past 5000 lines worth of changes if we want to
do it another way ... and that's just *one* component of the List API.
If you want to stop third party code from compiling, you can find a
way to do that without really changing your approach. Nothing stops
you from changing some symbol names minimally, and then making
corresponding mechanical changes to all of the client code within the
tree. Third party code authors would then follow this example, with
the expectation that it's probably going to be a totally mechanical
process.
I'm not necessarily advocating that approach. I'm simply pointing out
that a compromise is quite possible.
Nor is there any reason to think the changes would be any more mechanical
than what I had to do here. (No fair saying that I already found the
trouble spots, either. A different implementation would likely break
assumptions in different ways.)
The idea of making a new vector/array implementation that is a more or
less drop in replacement for List seems okay to me. C++ has both a
std::list and a std::vector, and they support almost the same
interface. Obviously the situation is different here, since you're
retrofitting a new implementation with different performance
characteristics, rather than implementing both in a green field
situation. But it's not that different.
--
Peter Geoghegan
Hi,
On 2019-02-25 13:02:03 -0500, Robert Haas wrote:
On Sat, Feb 23, 2019 at 9:24 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Every time this has come up, I've opined that the right fix is to jack
up the List API and drive a new implementation underneath, as we did
once before (cf commit d0b4399d81). I thought maybe it was about time
to provide some evidence for that position, so attached is a POC patch
that changes Lists into expansible arrays, while preserving most of
their existing API.I'm not really convinced that this is the way to go. The thing is,
any third-party code people have that uses a List may simply break.
If you kept the existing List and changed a bunch of existing code to
use a new Vector implementation, or Thomas's SimpleVector stuff, then
that wouldn't happen. The reason why people - or at least me - have
been reluctant to accept that you can just jack up the API and drive a
new implementation underneath is that the new implementation will
involve breaking guarantees on which existing code relies; indeed,
your email makes it pretty clear that this is the case. If you could
replace the existing implementation without breaking any code, that
would be a no-brainer but there's no real way to do that and get the
performance benefits you're seeking to obtain.
Yea, it'd be more convincing. I'm not convinced it'd be a no-brainer
though. Unless you've been hacking PG for a fair bit, the pg_list.h APIs
are very hard to understand / remember. Given this change essentially
requires auditing all code that uses List, ISTM we'd be much better off
also changing the API at the same time. Yes that'll mean there'll be
vestigial uses nobody bothered to convert in extension etc, but that's
not that bad.
Greetings,
Andres Freund
Peter Geoghegan <pg@bowt.ie> writes:
If we knew that the list code was the bottleneck in a handful of
cases, then I'd come down on Robert's side here. It would then be
possible to update the relevant bottlenecked code in an isolated
fashion, while getting the lion's share of the benefit. However, I
don't think that that's actually possible. The costs of using Lists
everywhere are real and measurable, but it's also highly distributed.
At least, that's my recollection from previous discussion from several
years back. I remember talking about this with Andres in early 2016.
Yeah, that's exactly the point. If we could replace some small number
of places with a vector-ish data structure and get all/most of the win,
then that would be the way to go about it. But I'm pretty sure that
we aren't going to make much of an improvement without wholesale
changes. Nor is it really all that attractive to have some pieces of
the parse/plan/execution tree data structures using one kind of list
while other places use another. If we're to attack this at all,
I think we should go for a wholesale replacement.
Another way of looking at this is that if we expected that extensions
had a lot of private Lists, unrelated to these core data structures,
it might be worth preserving the List implementation so as not to cause
problems for such usage. But I doubt that that's the case; or that
any such private lists are more likely to be broken by these API changes
than the core usage is (600 changes in however many lines we've got is
not a lot); or that people would really want to deal with two independent
list implementations with different behaviors just to avoid revisiting
some portions of their code while they're being forced to revisit others
anyway.
If you want to stop third party code from compiling, you can find a
way to do that without really changing your approach. Nothing stops
you from changing some symbol names minimally, and then making
corresponding mechanical changes to all of the client code within the
tree. Third party code authors would then follow this example, with
the expectation that it's probably going to be a totally mechanical
process.
Yeah, if we expected that only mechanical changes would be needed, and
forcing certain syntax changes would be a good guide to what had to be
done, then this'd be a helpful way to proceed. The lnext changes in
my proposed patch do indeed work like that. But the part that's actually
hard is finding/fixing the places where you can't safely use lnext
anymore, and there's nothing very mechanical about that. (Unless you want
to just forbid lnext altogether, which maybe is a reasonable thing to
contemplate, but I judged it overkill.)
BTW, I neglected to respond to Robert's earlier point that
It is also perhaps worth mentioning that reimplementing a List as an
array means that it is... not a list. That is a pretty odd state of
affairs
I think the reason we have Lisp-style lists all over the place has little
to do with whether those are ideal data structures, and a lot to do with
the fact that chunks of Postgres were originally written in Lisp, and
in that language using lists for everything is just How It's Done.
I don't have any problem with regarding that nomenclature as being mostly
a legacy thing, which is how I documented it in the proposed revision
to pg_list.h's header comment.
regards, tom lane
Hi,
On 2019-02-25 13:59:36 -0500, Tom Lane wrote:
Robert Haas <robertmhaas@gmail.com> writes:
On Mon, Feb 25, 2019 at 1:17 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I'm not following your point here. If we change key data structures
(i.e. parsetrees, plan trees, execution trees) to use some other list-ish
API, that *in itself* breaks everything that accesses those data
structures. The approach I propose here isn't zero-breakage, but it
requires far fewer places to be touched than a complete API replacement
would do.Sure, but if you have third-party code that touches those things,
it'll fail to compile. With your proposed approach, there seems to be
a risk that it will compile but not work.Failing to compile isn't really a benefit IMO.
It's a huge benefit. It's a lot of effort to look through all source
code for potential breakages. Especially if all list usages, rather than
some planner detail that comparatively few extensions touch, needs to be
audited.
I completely disagree. Your proposal is probably an order of magnitude
more painful than the approach I suggest here, while not really offering
any additional performance benefit (or if you think there would be some,
you haven't explained how). Strictly on cost/benefit grounds, it isn't
ever going to happen that way.Why would it be ten times more painful, exactly?
Because it involves touching ten times more code (and that's a very
conservative estimate). Excluding changes in pg_list.h + list.c,
what I posted touches approximately 600 lines of code (520 insertions,
644 deletions to be exact). For comparison's sake, there are about
1800 uses of foreach in the tree, each of which would require at least
3 changes to replace (the foreach itself, the ListCell variable
declaration, and at least one lfirst() reference in the loop body).
So we've already blown past 5000 lines worth of changes if we want to
do it another way ... and that's just *one* component of the List API.
Nor is there any reason to think the changes would be any more mechanical
than what I had to do here. (No fair saying that I already found the
trouble spots, either. A different implementation would likely break
assumptions in different ways.)
FWIW, rewrites of this kind can be quite nicely automated using
coccinelle [1]http://coccinelle.lip6.fr/. One sometimes needs to do a bit of mop-up with variable
names, but otherwise it should be mostly complete.
Greetings,
Andres Freund
Andres Freund <andres@anarazel.de> writes:
Yea, it'd be more convincing. I'm not convinced it'd be a no-brainer
though. Unless you've been hacking PG for a fair bit, the pg_list.h APIs
are very hard to understand / remember. Given this change essentially
requires auditing all code that uses List, ISTM we'd be much better off
also changing the API at the same time. Yes that'll mean there'll be
vestigial uses nobody bothered to convert in extension etc, but that's
not that bad.
The pain factor for back-patching is alone a strong reason for not just
randomly replacing the List API with different spellings.
regards, tom lane
Andres Freund <andres@anarazel.de> writes:
FWIW, rewrites of this kind can be quite nicely automated using
coccinelle [1]. One sometimes needs to do a bit of mop-up with variable
names, but otherwise it should be mostly complete.
I'm getting slightly annoyed by arguments that reject a live, workable
patch in favor of pie-in-the-sky proposals. Both you and Robert seem
to be advocating solutions that don't exist and would take a very large
amount of work to create. If you think differently, let's see a patch.
regards, tom lane
Hi,
On 2019-02-25 11:59:06 -0800, Peter Geoghegan wrote:
On Mon, Feb 25, 2019 at 10:59 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Because it involves touching ten times more code (and that's a very
conservative estimate). Excluding changes in pg_list.h + list.c,
what I posted touches approximately 600 lines of code (520 insertions,
644 deletions to be exact). For comparison's sake, there are about
1800 uses of foreach in the tree, each of which would require at least
3 changes to replace (the foreach itself, the ListCell variable
declaration, and at least one lfirst() reference in the loop body).If we knew that the list code was the bottleneck in a handful of
cases, then I'd come down on Robert's side here. It would then be
possible to update the relevant bottlenecked code in an isolated
fashion, while getting the lion's share of the benefit. However, I
don't think that that's actually possible. The costs of using Lists
everywhere are real and measurable, but it's also highly distributed.
At least, that's my recollection from previous discussion from several
years back. I remember talking about this with Andres in early 2016.
It's distributed, but not *that* distributed. The largest source of
"cost" at execution time used to be all-over expression evaluation, but
that's gone now. That was a lot of places, but it's not outside of reach
of a targeted change. Now it's targetlist handling, which'd have to
change together with plan time, where it's a large issue.
So we've already blown past 5000 lines worth of changes if we want to
do it another way ... and that's just *one* component of the List API.If you want to stop third party code from compiling, you can find a
way to do that without really changing your approach. Nothing stops
you from changing some symbol names minimally, and then making
corresponding mechanical changes to all of the client code within the
tree. Third party code authors would then follow this example, with
the expectation that it's probably going to be a totally mechanical
process.I'm not necessarily advocating that approach. I'm simply pointing out
that a compromise is quite possible.
That breaks extension code using lists unnecessarily though. And given
that there's semantic change, I don't htink it's an entirely mechanical
process.
Greetings,
Andres Freund
Hi,
On 2019-02-25 16:03:43 -0500, Tom Lane wrote:
Andres Freund <andres@anarazel.de> writes:
FWIW, rewrites of this kind can be quite nicely automated using
coccinelle [1]. One sometimes needs to do a bit of mop-up with variable
names, but otherwise it should be mostly complete.I'm getting slightly annoyed by arguments that reject a live, workable
patch in favor of pie-in-the-sky proposals. Both you and Robert seem
to be advocating solutions that don't exist and would take a very large
amount of work to create. If you think differently, let's see a patch.
Uhm, we're talking about an invasive proposal from two weekend days
ago. It seems far from crazy to voice our concerns with the silent
breakage you propose. Nor, even if we were obligated to work on an
alternative approach, which we aren't, would it be realistic for us to
have written an alternative implementation within the last few hours,
while also working on our own priorities.
I'm actually quite interested in this topic, both in the sense that it's
great to see work, and in the sense that I'm willing to help with the
effort.
Greetings,
Andres Freund
On Mon, Feb 25, 2019 at 1:04 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I'm getting slightly annoyed by arguments that reject a live, workable
patch in favor of pie-in-the-sky proposals. Both you and Robert seem
to be advocating solutions that don't exist and would take a very large
amount of work to create. If you think differently, let's see a patch.
ISTM that we should separate the question of whether or not the List
API needs to continue to work without needing to change code in third
party extensions from the question of whether or not the List API
needs to be replaced whole cloth. These are not exactly independent
questions, but they don't necessarily need to be discussed all at
once.
Andres said that he doesn't like the pg_list.h API. It's not pretty,
but is it really that bad?
The List implementation claims to be generic, but it's not actually
that generic. It has to work as a Node. It's not quite fair to say
that it's confusing without acknowledging that pg_list.h is special to
query processing.
--
Peter Geoghegan
Hi,
On 2019-02-25 13:21:30 -0800, Peter Geoghegan wrote:
ISTM that we should separate the question of whether or not the List
API needs to continue to work without needing to change code in third
party extensions from the question of whether or not the List API
needs to be replaced whole cloth. These are not exactly independent
questions, but they don't necessarily need to be discussed all at
once.
I'm not convinced by that - if we are happy with the list API, not
duplicating code would be a stronger argument than if we actually are
unhappy. It makes no sense to go around and replace the same code twice
in a row if we also think other changes should be made (at the same
time, we obviously ought not to do too much at once, otherwise we'll
never get anywhere).
Andres said that he doesn't like the pg_list.h API. It's not pretty,
but is it really that bad?
Yes. The function names alone confound anybody new to postgres, we tend
to forget that after a few years. A lot of the function return types are
basically unpredictable without reading the code, the number of builtin
types is pretty restrictive, and there's no typesafety around the choice
of actually stored.
Greetings,
Andres Freund
On 2/25/19 10:03 PM, Andres Freund wrote:
Hi,
On 2019-02-25 11:59:06 -0800, Peter Geoghegan wrote:
On Mon, Feb 25, 2019 at 10:59 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Because it involves touching ten times more code (and that's a very
conservative estimate). Excluding changes in pg_list.h + list.c,
what I posted touches approximately 600 lines of code (520 insertions,
644 deletions to be exact). For comparison's sake, there are about
1800 uses of foreach in the tree, each of which would require at least
3 changes to replace (the foreach itself, the ListCell variable
declaration, and at least one lfirst() reference in the loop body).If we knew that the list code was the bottleneck in a handful of
cases, then I'd come down on Robert's side here. It would then be
possible to update the relevant bottlenecked code in an isolated
fashion, while getting the lion's share of the benefit. However, I
don't think that that's actually possible. The costs of using Lists
everywhere are real and measurable, but it's also highly distributed.
At least, that's my recollection from previous discussion from several
years back. I remember talking about this with Andres in early 2016.It's distributed, but not *that* distributed. The largest source of
"cost" at execution time used to be all-over expression evaluation, but
that's gone now. That was a lot of places, but it's not outside of reach
of a targeted change. Now it's targetlist handling, which'd have to
change together with plan time, where it's a large issue.
So let's say we want to measure the improvement this patch gives us.
What would be some reasonable (and corner) cases to benchmark? I do have
some ideas, but as you've been looking at this in the past, perhaps you
have something better.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
On Mon, Feb 25, 2019 at 1:31 PM Andres Freund <andres@anarazel.de> wrote:
Andres said that he doesn't like the pg_list.h API. It's not pretty,
but is it really that bad?Yes. The function names alone confound anybody new to postgres, we tend
to forget that after a few years. A lot of the function return types are
basically unpredictable without reading the code, the number of builtin
types is pretty restrictive, and there's no typesafety around the choice
of actually stored.
But a lot of those restrictions are a consequence of needing what
amount to support functions in places as distant from pg_list.h as
pg_stat_statements.c, or the parser, or outfuncs.c. I'm not saying
that we couldn't do better here, but the design is constrained by
this. If you add a support for a new datatype, where does that leave
stored rules? Seems ticklish to me, at the very least.
--
Peter Geoghegan
Hi,
On 2019-02-25 22:35:37 +0100, Tomas Vondra wrote:
So let's say we want to measure the improvement this patch gives us.
What would be some reasonable (and corner) cases to benchmark? I do have
some ideas, but as you've been looking at this in the past, perhaps you
have something better.
I think queries over tables with a fair number of columns very easily
stress test the list overhead around targetlists - I don't have a
profile lying around, but the overhead of targetlist processing
(ExecTypeFromTL etc) at execution time clearly shows up. Larger
individual expressions can easily show up via eval_const_expressions()
etc and ExecInitExpr(). Both probably can be separated into benchmarks
with prepared statements (ExecTypeFromTl() and ExecInitExpr() will show
up, but planner work obviously not), and non-prepared benchmarks will
stress the planner more. I suspect there's also a few planner benefits
with large numbers of paths, but I don't quite remember the profiles
well enough to construct a benchmark from memory.
Greetings,
Andres Freund
Hi,
On 2019-02-25 13:41:48 -0800, Peter Geoghegan wrote:
On Mon, Feb 25, 2019 at 1:31 PM Andres Freund <andres@anarazel.de> wrote:
Andres said that he doesn't like the pg_list.h API. It's not pretty,
but is it really that bad?Yes. The function names alone confound anybody new to postgres, we tend
to forget that after a few years. A lot of the function return types are
basically unpredictable without reading the code, the number of builtin
types is pretty restrictive, and there's no typesafety around the choice
of actually stored.But a lot of those restrictions are a consequence of needing what
amount to support functions in places as distant from pg_list.h as
pg_stat_statements.c, or the parser, or outfuncs.c.
Those could trivially support distinguisiong at least between lists
containing pointer, int, oid, or node. But even optionally doing more
than that would be fairly easy. It's not those modules don't currently
know the types of elements they're dealing with?
If you add a support for a new datatype, where does that leave
stored rules?
We don't maintain stored rules across major versions (they break due to
a lot of changes), so I don't quite understand that problem.
Greetings,
Andres Freund
