Re: [HACKERS] ilist.h is not useful as-is
Andres Freund 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ilist.h is not useful as-is
> Andres Freund 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ilist.h is not useful as-is
Andres Freund 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ilist.h is not useful as-is
Hi,
On 2013-07-24 11:49:20 -0400, Tom Lane wrote:
> Andres Freund 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
>From 0dfa542f457ebd71640830a993e3a428720b4179 Mon Sep 17 00:00:00 2001
From: Andres Freund
Date: Wed, 24 Jul 2013 19:34:10 +0200
Subject: [PATCH 1/2] Add slist_delete_current()
---
src/backend/lib/ilist.c | 2 +-
src/backend/postmaster/bgworker.c | 5 -
src/backend/postmaster/postmaster.c | 4 ++--
src/include/lib/ilist.h | 32 +
src/include/postmaster/bgworker_internals.h | 2 +-
5 files changed, 36 insertions(+), 9 deletions(-)
diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c
index 957a118..dddb6eb 100644
--- a/src/backend/lib/ilist.c
+++ b/src/backend/lib/ilist.c
@@ -28,7 +28,7 @@
*
* It is not allowed to delete a 'node' which is is not in the list 'head'
*
- * Caution: this is O(n)
+ * Caution: this is O(n), use slist_delete_current() while iterating.
*/
void
slist_delete(slist_head *head, slist_node *node)
diff --git a/src/backend/postmaster/bgworker.c b/src/backend/postmaster/bgworker.c
index ada24e9..9967b69 100644
--- a/src/backend/postmaster/bgworker.c
+++ b/src/backend/postmaster/bgworker.c
@@ -272,10 +272,13 @@ BackgroundWorkerStateChange(void)
* the postmaster.
*/
void
-ForgetBackgroundWorker(RegisteredBgWorker *rw)
+ForgetBackgroundWorker(slist_mutable_iter *cur)
{
+ RegisteredBgWorker *rw;
BackgroundWorkerSlot *slot;
+ rw = slist_container(RegisteredBgWorker, rw_lnode, cur->cur);
+
Assert(rw->rw_shmem_slot < max_worker_processes);
slot = &BackgroundWorkerData->slot[rw->rw_shmem_slot];
slot->in_use = false;
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index b6b8111..0342be7 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -1452,7 +1452,7 @@ DetermineSleepTime(struct timeval * timeout)
if (rw->rw_worker.bgw_restart_time == BGW_NEVER_RESTART)
{
-ForgetBackgroundWorker(rw);
+ForgetBackgroundWorker(&siter);
continue;
}
@@ -5643,7 +5643,7 @@ StartOneBackgroundWorker(void)
{
if (rw->rw_worker.bgw_restart_time == BGW_NEVER_RESTART)
{
-ForgetBackgroundWorker(rw);
+ForgetBackgroundWorker(&iter);
continue;
}
diff --git a/src/include/lib/ilist.h b/src/include/lib/ilist.h
index 73f4115..f8f0458 100644
--- a/src/include/lib/ilist.h
+++ b/src/include/lib/ilist.h
@@ -211,7 +211,9 @@ typedef struct slist_head
* Used as state in slist_foreach
Re: [HACKERS] ilist.h is not useful as-is
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 Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ilist.h is not useful as-is
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ilist.h is not useful as-is
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 Herrerahttp://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ilist.h is not useful as-is
Andres Freund 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ilist.h is not useful as-is
On 2013-07-24 11:26:00 -0400, Tom Lane wrote: > So I went off to implement the SPITupleTable tracking discussed in > <6553.1374424...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] ilist.h is not useful as-is
So I went off to implement the SPITupleTable tracking discussed in <6553.1374424...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
