Обсуждение: ilist.h is not useful as-is

So I went off to implement the SPITupleTable tracking discussed in
<6553.1374424838@sss.pgh.pa.us>, and thought it would be cool to
use the slist infrastructure defined in lib/ilist.h rather than
creating a separate List node for each SPITupleTable struct.
However, I soon ran into a problem: there's no real support for
"remove the current element of an slist while we're scanning it",
which is really the only list manipulation I need.  The only way
to remove an element is slist_delete(), which will iterate over
the list *again* and thus create an O(N^2) penalty.  Or I could
use a dlist, but two pointers per struct seem pretty silly.

So I'm going to end up hand-implementing the same kind of manipulation
we frequently use with traditional Lists, namely keep a second variable
that's the preceding list element (not the next one) so I can unlink and
delete the target element when I find it.  ilist.h is not offering me
any useful support at all for this scenario.  Seems like we're missing
a bet here.
        regards, tom lane

On 2013-07-24 11:26:00 -0400, Tom Lane wrote:
> So I went off to implement the SPITupleTable tracking discussed in
> <6553.1374424838@sss.pgh.pa.us>, and thought it would be cool to
> use the slist infrastructure defined in lib/ilist.h rather than
> creating a separate List node for each SPITupleTable struct.
> However, I soon ran into a problem: there's no real support for
> "remove the current element of an slist while we're scanning it",
> which is really the only list manipulation I need.  The only way
> to remove an element is slist_delete(), which will iterate over
> the list *again* and thus create an O(N^2) penalty.  Or I could
> use a dlist, but two pointers per struct seem pretty silly.

> So I'm going to end up hand-implementing the same kind of manipulation
> we frequently use with traditional Lists, namely keep a second variable
> that's the preceding list element (not the next one) so I can unlink and
> delete the target element when I find it.  ilist.h is not offering me
> any useful support at all for this scenario.  Seems like we're missing
> a bet here.

Hm. Yes. This should be added. I didn't need it so far, but I definitely
can see usecases.

slist_delete_current(slist_mutable_iter *)?

I am willing to cough up a patch if you want.

This will require another member variable in slist_mutable_iter which
obviously will need to be maintained, but that seems fine to me since it
will reduce the cost of actually deleting noticeably.

Greetings,

Andres Freund

-- Andres Freund                       http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services

Andres Freund <andres@2ndquadrant.com> writes:
> On 2013-07-24 11:26:00 -0400, Tom Lane wrote:
>> So I'm going to end up hand-implementing the same kind of manipulation
>> we frequently use with traditional Lists, namely keep a second variable
>> that's the preceding list element (not the next one) so I can unlink and
>> delete the target element when I find it.  ilist.h is not offering me
>> any useful support at all for this scenario.  Seems like we're missing
>> a bet here.

> Hm. Yes. This should be added. I didn't need it so far, but I definitely
> can see usecases.
> slist_delete_current(slist_mutable_iter *)?
> I am willing to cough up a patch if you want.

Please.

> This will require another member variable in slist_mutable_iter which
> obviously will need to be maintained, but that seems fine to me since it
> will reduce the cost of actually deleting noticeably.

I think that's all right.  Conceivably we could introduce two forms of
iterator depending on whether you want to delete or not, but that seems
like overkill to me.

In fact, now that I think about it, the distinction between slist_iter
and slist_mutable_iter is really misstated in the comments, isn't it?
The *only* action on the list that's unsafe with an active slist_iter
is to delete the current element (and then continue iterating).
If the value of slist_mutable_iter is to support deletion of the current
element, then it seems obvious that it should support doing so
efficiently, ie it should carry both prev and next.  Also, if it's
carrying both of those, then use of slist_mutable_iter really doesn't
allow any action other than deleting the current element --- adding
new nodes "ahead" of the current element isn't safe.
        regards, tom lane

Andres Freund wrote:
> On 2013-07-24 11:26:00 -0400, Tom Lane wrote:

> > So I'm going to end up hand-implementing the same kind of manipulation
> > we frequently use with traditional Lists, namely keep a second variable
> > that's the preceding list element (not the next one) so I can unlink and
> > delete the target element when I find it.  ilist.h is not offering me
> > any useful support at all for this scenario.  Seems like we're missing
> > a bet here.
> 
> Hm. Yes. This should be added. I didn't need it so far, but I definitely
> can see usecases.
> 
> slist_delete_current(slist_mutable_iter *)?
> 
> I am willing to cough up a patch if you want.
> 
> This will require another member variable in slist_mutable_iter which
> obviously will need to be maintained, but that seems fine to me since it
> will reduce the cost of actually deleting noticeably.

Amusingly, this will mean ForgetBackgroundWorker() will need to have a
slist_mutable_iter * argument if it wants to use the new function ...

-- 
Álvaro Herrera                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 2013-07-24 11:53:39 -0400, Alvaro Herrera wrote:
> Andres Freund wrote:
> > On 2013-07-24 11:26:00 -0400, Tom Lane wrote:
> 
> > > So I'm going to end up hand-implementing the same kind of manipulation
> > > we frequently use with traditional Lists, namely keep a second variable
> > > that's the preceding list element (not the next one) so I can unlink and
> > > delete the target element when I find it.  ilist.h is not offering me
> > > any useful support at all for this scenario.  Seems like we're missing
> > > a bet here.
> > 
> > Hm. Yes. This should be added. I didn't need it so far, but I definitely
> > can see usecases.
> > 
> > slist_delete_current(slist_mutable_iter *)?
> > 
> > I am willing to cough up a patch if you want.
> > 
> > This will require another member variable in slist_mutable_iter which
> > obviously will need to be maintained, but that seems fine to me since it
> > will reduce the cost of actually deleting noticeably.
> 
> Amusingly, this will mean ForgetBackgroundWorker() will need to have a
> slist_mutable_iter * argument if it wants to use the new function ...

The only alternative I see would be to pass both the prev, and the cur
elements which seems to be less expressive from my POV.
I am open to other suggestions?

Greetings,

Andres Freund

-- Andres Freund                       http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services

Andres Freund wrote:
> On 2013-07-24 11:53:39 -0400, Alvaro Herrera wrote:
> > Andres Freund wrote:

> > Amusingly, this will mean ForgetBackgroundWorker() will need to have a
> > slist_mutable_iter * argument if it wants to use the new function ...
> 
> The only alternative I see would be to pass both the prev, and the cur
> elements which seems to be less expressive from my POV.
> I am open to other suggestions?

In the grand scheme of things, I think it's fine.

-- 
Álvaro Herrera                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Hi,

On 2013-07-24 11:49:20 -0400, Tom Lane wrote:
> Andres Freund <andres@2ndquadrant.com> writes:
> > This will require another member variable in slist_mutable_iter which
> > obviously will need to be maintained, but that seems fine to me since it
> > will reduce the cost of actually deleting noticeably.
>
> I think that's all right.  Conceivably we could introduce two forms of
> iterator depending on whether you want to delete or not, but that seems
> like overkill to me.

Agreed. Especially as you point out there's no real point to
mutable_iter as committed.

> In fact, now that I think about it, the distinction between slist_iter
> and slist_mutable_iter is really misstated in the comments, isn't it?
> The *only* action on the list that's unsafe with an active slist_iter
> is to delete the current element (and then continue iterating).
> If the value of slist_mutable_iter is to support deletion of the current
> element, then it seems obvious that it should support doing so
> efficiently, ie it should carry both prev and next.  Also, if it's
> carrying both of those, then use of slist_mutable_iter really doesn't
> allow any action other than deleting the current element --- adding
> new nodes "ahead" of the current element isn't safe.

True. I think I mentally copy&pasted to much logic from the doubly
linked list case.

The first attached patch adds slist_delete_current(), updates the
comments addressing your points and converts the bgworker code to pass
the iterator around (it's more efficient which might actually matter
with a few hundred bgworkers).
I found the added newlines in slist_foreach_modify useful, but maybe they
should be removed again.

I think this should be included in 9.3 once reviewed.

The second patch adds a regression test for background workers via
worker_spi which I used to test slist_delete_current() addition. It's not 100% as
it, but I thought it worthwile to post it anyway
a) only tests dynamically registered workers, it should start it's own
   regression test starting some bgworkers statically
b) disables installcheck harshly causing a warning from make:
/home/andres/src/postgresql/src/makefiles/pgxs.mk:297: warning: ignoring old commands for target `installcheck'
Manually defining a pg_regress in 'check:' should fix it probably
because that part of pgxs.mk is dependant on REGRESS = being set.
c) it only tests BGW_NEVER_RESTART

Greetings,

Andres Freund

--
 Andres Freund                       http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

Andres Freund <andres@2ndquadrant.com> writes:
> The first attached patch adds slist_delete_current(), updates the
> comments addressing your points and converts the bgworker code to pass
> the iterator around (it's more efficient which might actually matter
> with a few hundred bgworkers).
> I found the added newlines in slist_foreach_modify useful, but maybe they
> should be removed again.

> I think this should be included in 9.3 once reviewed.

Agreed; since we have not shipped ilist.h in a release yet, the benefits
of having it behave the same in all branches should outweigh any pain
from changing this post-beta.

> The second patch adds a regression test for background workers via
> worker_spi which I used to test slist_delete_current() addition. It's not 100% as
> it, but I thought it worthwile to post it anyway

Hm.  I'll review and commit the ilist changes, but Alvaro or somebody
should decide if such a test is sensible.  I'd be a bit worried about
it in a "make installcheck" context ...
        regards, tom lane

> Andres Freund <andres@2ndquadrant.com> writes:
> > The first attached patch adds slist_delete_current(), updates the
> > comments addressing your points and converts the bgworker code to pass
> > the iterator around (it's more efficient which might actually matter
> > with a few hundred bgworkers).
> > I found the added newlines in slist_foreach_modify useful, but maybe they
> > should be removed again.
> 
> > I think this should be included in 9.3 once reviewed.
> 
> Agreed; since we have not shipped ilist.h in a release yet, the benefits
> of having it behave the same in all branches should outweigh any pain
> from changing this post-beta.

Especially as it shouldn't break any existing working code since the old
API is still there. Obviously it breaks the ABI, but ...

On 2013-07-24 14:29:42 -0400, Tom Lane wrote:
> > The second patch adds a regression test for background workers via
> > worker_spi which I used to test slist_delete_current() addition. It's not 100% as
> > it, but I thought it worthwile to post it anyway
> 
> Hm.  I'll review and commit the ilist changes, but Alvaro or somebody
> should decide if such a test is sensible.  I'd be a bit worried about
> it in a "make installcheck" context ...

I've disabled installcheck for that reason. Is there any way to override
a makefile target in gnu make without a warning?

If we want coverage for statically registered workers - which seems like
a good idea, we need our own postgresql.conf stanza and thus a manual
pg_regress invocation anyway. Which should fix that error.

Greetings,

Andres Freund

-- Andres Freund                       http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services

Andres Freund <andres@2ndquadrant.com> writes:
> The first attached patch adds slist_delete_current(), updates the
> comments addressing your points and converts the bgworker code to pass
> the iterator around (it's more efficient which might actually matter
> with a few hundred bgworkers).

Applied with fixes.  The slist_delete_current() logic wouldn't actually
work for deleting multiple adjacent list elements, because the foreach
macro would advance prev to point at the just-deleted element.  Compare
the places where we use list_delete_cell() in a loop --- we're careful
to advance prev only when we *don't* delete the current element.
I dealt with that by making slist_delete_current() back up the
iterator's "cur" pointer to equal "prev", so that the loop macro's next
copying of "cur" to "prev" is a no-op.  This means callers can't rely on
"cur" anymore after the deletion, but in typical usage they'd have
computed a pointer to their struct already so this shouldn't be a
problem.  Another fine point is you can't use both slist_delete and
slist_delete_current within the same loop, since the former wouldn't
apply this correction.

Also, I fixed the slist_foreach_modify macro to not doubly evaluate
its lhead argument, since I think we agreed that was a bad idea,
and did some more work on the comments.
        regards, tom lane