Thread: Add new for_each macros for iterating over a List that do not require ListCell pointer

Many usages of the foreach macro in the Postgres codebase only use the
ListCell variable to then get its value. This adds macros that
simplify iteration code for that very common use case. Instead of
passing a ListCell you can pass a variable of the type of its
contents. This IMHO improves readability of the code by reducing the
total amount of code while also essentially forcing the use of useful
variable names.

While this might seem like a small quality of life improvement, in
practice it turns out to be very nice to use. At Microsoft we have
been using macros very similar to these ones in the Citus codebase for
a long time now and we pretty much never use plain foreach anymore for
new code.

Finally, I guess there needs to be some bikeshedding on the naming. In
the Citus codebase we call them foreach_xyz instead of the
for_each_xyz naming pattern that is used in this patchset. I'm not
sure what the current stance is on if foreach should be written with
or without an underscore between for and each. Currently pg_list.h
uses both.

P.S. Similar macros for forboth/forthree are also possible, but
require an exponential macro count handle all different possibilities,
which might not be worth the effort since forboth/forthree are used
much less often than foreach. In Citus we do have 3 forboth macros
that don't require ListCell for the most common cases (foreach_ptr,
foreach_ptr_oid, foreach_int_oid). But I did not want to clutter this
patchset with that discussion.

On Tue, Oct 24, 2023 at 06:03:48PM +0200, Jelte Fennema wrote:
> Many usages of the foreach macro in the Postgres codebase only use the
> ListCell variable to then get its value. This adds macros that
> simplify iteration code for that very common use case. Instead of
> passing a ListCell you can pass a variable of the type of its
> contents. This IMHO improves readability of the code by reducing the
> total amount of code while also essentially forcing the use of useful
> variable names.
> 
> While this might seem like a small quality of life improvement, in
> practice it turns out to be very nice to use. At Microsoft we have
> been using macros very similar to these ones in the Citus codebase for
> a long time now and we pretty much never use plain foreach anymore for
> new code.

This seems reasonable to me.

> Finally, I guess there needs to be some bikeshedding on the naming. In
> the Citus codebase we call them foreach_xyz instead of the
> for_each_xyz naming pattern that is used in this patchset. I'm not
> sure what the current stance is on if foreach should be written with
> or without an underscore between for and each. Currently pg_list.h
> uses both.

I don't have a strong opinion on the matter, but if I had to choose, I
guess I'd pick foreach_*() because these macros are most closely related to
foreach().

BTW after applying your patches, initdb began failing with the following
for me:

    TRAP: failed Assert("n >= 0 && n < list->length"), File: "list.c", Line: 770, PID: 902807

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

On Tue, 24 Oct 2023 at 18:47, Nathan Bossart <nathandbossart@gmail.com> wrote:
> BTW after applying your patches, initdb began failing with the following
> for me:
>
>         TRAP: failed Assert("n >= 0 && n < list->length"), File: "list.c", Line: 770, PID: 902807

Oh oops... That was an off by one error in the modified
foreach_delete_current implementation.
Attached is a fixed version.

On Tue, Oct 24, 2023 at 06:58:04PM +0200, Jelte Fennema wrote:
> On Tue, 24 Oct 2023 at 18:47, Nathan Bossart <nathandbossart@gmail.com> wrote:
>> BTW after applying your patches, initdb began failing with the following
>> for me:
>>
>>         TRAP: failed Assert("n >= 0 && n < list->length"), File: "list.c", Line: 770, PID: 902807
> 
> Oh oops... That was an off by one error in the modified
> foreach_delete_current implementation.
> Attached is a fixed version.

Thanks, that fixed it for me, too.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

On Wed, 25 Oct 2023 at 06:00, Jelte Fennema <postgres@jeltef.nl> wrote:
> Attached is a fixed version.

With foreach(), we commonly do "if (lc == NULL)" at the end of loops
as a way of checking if we did "break" to terminate the loop early.
Doing the equivalent with the new macros won't be safe as the list
element's value we broke on may be set to NULL. I think it might be a
good idea to document the fact that this wouldn't be safe with the new
macros, or better yet, document the correct way to determine if we
broke out the loop early.  I imagine someone will want to do some
conversion work at some future date and it would be good if we could
avoid introducing bugs during that process.

I wonder if we should even bother setting the variable to NULL at the
end of the loop.  It feels like someone might just end up mistakenly
checking for NULLs even if we document that it's not safe.  If we left
the variable pointing to the last list element then the user of the
macro is more likely to notice their broken code. It'd also save a bit
of instruction space.

David

On 2023-Oct-24, Jelte Fennema wrote:

> Many usages of the foreach macro in the Postgres codebase only use the
> ListCell variable to then get its value. This adds macros that
> simplify iteration code for that very common use case. Instead of
> passing a ListCell you can pass a variable of the type of its
> contents. This IMHO improves readability of the code by reducing the
> total amount of code while also essentially forcing the use of useful
> variable names.

+1 for getting rid of useless "lc" variables.

Looking at for_each_ptr() I think it may be cleaner to follow
palloc_object()'s precedent and make it foreach_object() instead (I have
no love for the extra underscore, but I won't object to it either).  And
like foreach_node, have it receive a type name to add a cast to.

I'd imagine something like

  SubscriptionRelState *rstate;

  foreach_object(SubscriptionRelState *, rstate, table_states_not_ready)
  {

-- 
Álvaro Herrera               48°01'N 7°57'E  —  https://www.EnterpriseDB.com/

On Wed, 25 Oct 2023 at 04:55, David Rowley <dgrowleyml@gmail.com> wrote:
> With foreach(), we commonly do "if (lc == NULL)" at the end of loops
> as a way of checking if we did "break" to terminate the loop early.

Afaict it's done pretty infrequently. The following crude attempt at
an estimate estimates it's only done about ~1.5% of the time a foreach
is used:
$ rg 'lc == NULL' | wc -l
13
$ rg '\bforeach\(lc,' -S | wc -l
899

> Doing the equivalent with the new macros won't be safe as the list
> element's value we broke on may be set to NULL. I think it might be a
> good idea to document the fact that this wouldn't be safe with the new
> macros, or better yet, document the correct way to determine if we
> broke out the loop early.  I imagine someone will want to do some
> conversion work at some future date and it would be good if we could
> avoid introducing bugs during that process.
>
> I wonder if we should even bother setting the variable to NULL at the
> end of the loop.  It feels like someone might just end up mistakenly
> checking for NULLs even if we document that it's not safe.  If we left
> the variable pointing to the last list element then the user of the
> macro is more likely to notice their broken code. It'd also save a bit
> of instruction space.

Makes sense. Addressed this now by mentioning this limitation and
possible workarounds in the comments of the new macros and by not
setting the loop variable to NULL/0. I don't think there's an easy way
to add this feature to these new macros natively, it's a limitation of
not having a second variable. This seems fine to me, since these new
macros are meant as an addition to foreach() instead of a complete
replacement.

Attached is a slightly updated version, with a bit simpler
implementation of foreach_delete_current.
Instead of decrementing i and then adding 1 to it when indexing the
list, it now indexes the list using a postfix decrement.

On Wed, 25 Oct 2023 at 13:52, Alvaro Herrera <alvherre@alvh.no-ip.org> wrote:
> Looking at for_each_ptr() I think it may be cleaner to follow
> palloc_object()'s precedent and make it foreach_object() instead (I have
> no love for the extra underscore, but I won't object to it either).  And
> like foreach_node, have it receive a type name to add a cast to.
>
> I'd imagine something like
>
>   SubscriptionRelState *rstate;
>
>   foreach_object(SubscriptionRelState *, rstate, table_states_not_ready)
>   {

Could you clarify why you think it may be cleaner? I don't see much
benefit to passing the type in there if all we use it for is adding a
cast. It seems like extra things to type for little benefit.
palloc_object uses the passed in type to not only do the cast, but
also to determine the size of the the allocation.

If foreach_object would allow us to remove the declaration further up
in the function I do see a benefit though.

I attached a new patchset which includes a 3rd patch that does this
(the other patches are equivalent to v4). I quite like that it moves
the type declaration to the loop itself, limiting its scope. But I'm
not fully convinced it's worth the hackiness of introducing a second
for loop that does a single iteration, just to be able to declare a
variable of a different type though. But I don't know another way of
achieving this. If this hack/trick is deemed acceptable, we can do the
same for the other newly introduced macros. The type would not even
need to be specified for oid/xid/int because it's already known to be
Oid/TransactionId/int respectively.

On Wed, Oct 25, 2023 at 12:39:01PM +0200, Jelte Fennema wrote:
> Attached is a slightly updated version, with a bit simpler
> implementation of foreach_delete_current.
> Instead of decrementing i and then adding 1 to it when indexing the
> list, it now indexes the list using a postfix decrement.

Both the macros and the comments in 0001 seem quite repetitive to me.
Could we simplify it with something like the following?

    #define foreach_internal(var, lst, func) \
        for (ForEachState var##__state = {(lst), 0}; \
             (var##__state.l != NIL && \
              var##__state.i < var##__state.l->length && \
             (var = func(&var##__state.l->elements[var##__state.i]), true)); \
             var##__state.i++)

    #define foreach_ptr(var, lst)   foreach_internal(var, lst, lfirst)
    #define foreach_int(var, lst)   foreach_internal(var, lst, lfirst_int)
    #define foreach_oid(var, lst)   foreach_internal(var, lst, lfirst_oid)
    #define foreach_xid(var, lst)   foreach_internal(var, lst, lfirst_xid)

    #define foreach_node(type, var, lst) \
        for (ForEachState var##__state = {(lst), 0}; \
             (var##__state.l != NIL && \
              var##__state.i < var##__state.l->length && \
             (var = lfirst_node(type, &var##__state.l->elements[var##__state.i]), true));\
             var##__state.i++)

There might be a way to use foreach_internal for foreach_node, too, but
this is probably already too magical...

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

On Fri, 1 Dec 2023 at 05:20, Nathan Bossart <nathandbossart@gmail.com> wrote:
> Could we simplify it with something like the following?

Great suggestion! Updated the patchset accordingly.

This made it also easy to change the final patch to include the
automatic scoped declaration logic for all of the new macros. I quite
like how the calling code changes to not have to declare the variable.
But it's definitely a larger divergence from the status quo than
without patch 0003. So I'm not sure if it's desired.

Finally, I also renamed the functions to use foreach instead of
for_each, since based on this thread that seems to be the generally
preferred naming.

The more I think about it and look at the code, the more I like the
usage of the loop style proposed in the previous 0003 patch (which
automatically declares a loop variable for the scope of the loop using
a second for loop).

I did some testing on godbolt.org and both versions of the macros
result in the same assembly when compiling with -O2 (and even -O1)
when compiling with ancient versions of gcc (5.1) and clang (3.0):
https://godbolt.org/z/WqfTbhe4e

So attached is now an updated patchset that only includes these even
easier to use foreach macros. I also updated some of the comments and
moved modifying foreach_delete_current and foreach_current_index to
their own commit.

On Thu, 14 Dec 2023 at 16:54, Jelte Fennema-Nio <postgres@jeltef.nl> wrote:
>
> On Fri, 1 Dec 2023 at 05:20, Nathan Bossart <nathandbossart@gmail.com> wrote:
> > Could we simplify it with something like the following?
>
> Great suggestion! Updated the patchset accordingly.
>
> This made it also easy to change the final patch to include the
> automatic scoped declaration logic for all of the new macros. I quite
> like how the calling code changes to not have to declare the variable.
> But it's definitely a larger divergence from the status quo than
> without patch 0003. So I'm not sure if it's desired.
>
> Finally, I also renamed the functions to use foreach instead of
> for_each, since based on this thread that seems to be the generally
> preferred naming.

On Mon, 18 Dec 2023 at 19:00, Jelte Fennema-Nio <postgres@jeltef.nl> wrote:
>
> The more I think about it and look at the code, the more I like the
> usage of the loop style proposed in the previous 0003 patch (which
> automatically declares a loop variable for the scope of the loop using
> a second for loop).
>
> I did some testing on godbolt.org and both versions of the macros
> result in the same assembly when compiling with -O2 (and even -O1)
> when compiling with ancient versions of gcc (5.1) and clang (3.0):
> https://godbolt.org/z/WqfTbhe4e
>
> So attached is now an updated patchset that only includes these even
> easier to use foreach macros. I also updated some of the comments and
> moved modifying foreach_delete_current and foreach_current_index to
> their own commit.
>
> On Thu, 14 Dec 2023 at 16:54, Jelte Fennema-Nio <postgres@jeltef.nl> wrote:
> >
> > On Fri, 1 Dec 2023 at 05:20, Nathan Bossart <nathandbossart@gmail.com> wrote:
> > > Could we simplify it with something like the following?
> >
> > Great suggestion! Updated the patchset accordingly.
> >
> > This made it also easy to change the final patch to include the
> > automatic scoped declaration logic for all of the new macros. I quite
> > like how the calling code changes to not have to declare the variable.
> > But it's definitely a larger divergence from the status quo than
> > without patch 0003. So I'm not sure if it's desired.
> >
> > Finally, I also renamed the functions to use foreach instead of
> > for_each, since based on this thread that seems to be the generally
> > preferred naming.

Thanks for working on this, this simplifies foreach further.
I noticed that this change can be done in several other places too. I
had seen the following parts of code from logical replication files
can be changed:
1) The below in pa_detach_all_error_mq function can be changed to foreach_ptr
foreach(lc, ParallelApplyWorkerPool)
{
shm_mq_result res;
Size nbytes;
void    *data;
ParallelApplyWorkerInfo *winfo = (ParallelApplyWorkerInfo *) lfirst(lc);

2) The below in logicalrep_worker_detach function can be changed to foreach_ptr
foreach(lc, workers)
{
LogicalRepWorker *w = (LogicalRepWorker *) lfirst(lc);

if (isParallelApplyWorker(w))
logicalrep_worker_stop_internal(w, SIGTERM);
}

3) The below in  ApplyLauncherMain function can be changed to foreach_ptr
/* Start any missing workers for enabled subscriptions. */
sublist = get_subscription_list();
foreach(lc, sublist)
{
Subscription *sub = (Subscription *) lfirst(lc);
LogicalRepWorker *w;
TimestampTz last_start;
TimestampTz now;
long elapsed;

if (!sub->enabled)
continue;

4) The below in  pa_launch_parallel_worker function can be changed to
foreach_ptr
ListCell   *lc;

/* Try to get an available parallel apply worker from the worker pool. */
foreach(lc, ParallelApplyWorkerPool)
{
winfo = (ParallelApplyWorkerInfo *) lfirst(lc);

if (!winfo->in_use)
return winfo;
}

Should we start doing these changes too now?

Regards,
Vignesh

On Tue, 19 Dec 2023 at 11:59, vignesh C <vignesh21@gmail.com> wrote:
> I noticed that this change can be done in several other places too.

My guess would be that ~90% of all existing foreach loops in the
codebase can be easily rewritten (and simplified) using these new
macros. So converting all of those would likely be quite a bit of
work. In patch 0003 I only converted a few of them to get some
coverage of the new macros and show how much simpler the usage of them
is.

> Should we start doing these changes too now?

I think we should at least wait until this patchset is merged before
we start changing other places. If there's some feedback on the macros
and decide we change how they get called, then it would be a waste of
time to have to change all the call sites.

And even once these patches are merged to master, I think we should
only do any bulk changes if/when we backport these macros to all
supported PG versions. Backporting to PG12 is probably the hardest,
since List its internal layout got heavily changed in PG13. Probably
not too hard though, in Citus we've had similar macros work since
PG11. I'm also not sure what the policy is for backporting patches
that introduce new functions/macros in public headers.

We probably even want to consider some automatic rewriting script (for
the obvious cases) and/or timing the merge, to avoid having to do many
rebases of the patch.

On Tue, Dec 19, 2023 at 03:44:43PM +0100, Jelte Fennema-Nio wrote:
> On Tue, 19 Dec 2023 at 11:59, vignesh C <vignesh21@gmail.com> wrote:
>> I noticed that this change can be done in several other places too.
> 
> My guess would be that ~90% of all existing foreach loops in the
> codebase can be easily rewritten (and simplified) using these new
> macros. So converting all of those would likely be quite a bit of
> work. In patch 0003 I only converted a few of them to get some
> coverage of the new macros and show how much simpler the usage of them
> is.

I'm not sure we should proceed with rewriting most/all eligible foreach
loops.  I think it's fine to use the new macros in new code or to update
existing loops in passing when changing nearby code, but rewriting
everything likely just introduces back-patching pain in return for little
discernible gain.

> And even once these patches are merged to master, I think we should
> only do any bulk changes if/when we backport these macros to all
> supported PG versions. Backporting to PG12 is probably the hardest,
> since List its internal layout got heavily changed in PG13. Probably
> not too hard though, in Citus we've had similar macros work since
> PG11. I'm also not sure what the policy is for backporting patches
> that introduce new functions/macros in public headers.

Unless there's some way to argue this is a bug, security issue, or data
corruption problem [0], I seriously doubt we will back-patch this.

[0] https://www.postgresql.org/support/versioning/

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

On Tue, 19 Dec 2023 at 16:52, Nathan Bossart <nathandbossart@gmail.com> wrote:
> I'm not sure we should proceed with rewriting most/all eligible foreach
> loops.  I think it's fine to use the new macros in new code or to update
> existing loops in passing when changing nearby code, but rewriting
> everything likely just introduces back-patching pain in return for little
> discernible gain.

To clarify: I totally agree that if we're not backpatching this we
shouldn't do bulk changes on existing loops to avoid pain when
backpatching other patches.

> Unless there's some way to argue this is a bug, security issue, or data
> corruption problem [0], I seriously doubt we will back-patch this.

In the past some tooling changes have been backpatched, e.g.
isolationtester has received various updates over the years (I know
because this broke Citus its isolationtester tests a few times because
the output files changed slightly). In some sense this patch could be
considered tooling too. Again: not saying we should back-patch this,
but we could only realistically bulk update loops if we do.

On Tue, 19 Dec 2023 at 21:22, Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> On Tue, Dec 19, 2023 at 03:44:43PM +0100, Jelte Fennema-Nio wrote:
> > On Tue, 19 Dec 2023 at 11:59, vignesh C <vignesh21@gmail.com> wrote:
> >> I noticed that this change can be done in several other places too.
> >
> > My guess would be that ~90% of all existing foreach loops in the
> > codebase can be easily rewritten (and simplified) using these new
> > macros. So converting all of those would likely be quite a bit of
> > work. In patch 0003 I only converted a few of them to get some
> > coverage of the new macros and show how much simpler the usage of them
> > is.
>
> I'm not sure we should proceed with rewriting most/all eligible foreach
> loops.  I think it's fine to use the new macros in new code or to update
> existing loops in passing when changing nearby code, but rewriting
> everything likely just introduces back-patching pain in return for little
> discernible gain.

+1 for this. Let's just provide the for_each macros to be used for new code.
This means that the
0003-Use-new-foreach_xyz-macros-in-a-few-places.patch will not be
present in the final patch right?

Regards,
Vignesh

On Wed, Dec 20, 2023 at 12:21:05PM +0530, vignesh C wrote:
> On Tue, 19 Dec 2023 at 21:22, Nathan Bossart <nathandbossart@gmail.com> wrote:
>> I'm not sure we should proceed with rewriting most/all eligible foreach
>> loops.  I think it's fine to use the new macros in new code or to update
>> existing loops in passing when changing nearby code, but rewriting
>> everything likely just introduces back-patching pain in return for little
>> discernible gain.
> 
> +1 for this. Let's just provide the for_each macros to be used for new code.
> This means that the
> 0003-Use-new-foreach_xyz-macros-in-a-few-places.patch will not be
> present in the final patch right?

It might be worth changing at least one of each type to make sure the
macros compile, but yes, I don't think we need to proceed with any sort of
bulk changes of existing loops for now.

BTW I think v7-0001 and v7-0002 are in pretty good shape.  I'm going to
mark this as ready-for-committer and see if I can get those two committed
sooner than later.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

I spent some time preparing this for commit, which only amounted to some
light edits.  I am posting a new version of the patch in order to get one
more round of cfbot coverage and to make sure there is no remaining
feedback.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

On Wed, 3 Jan 2024 at 20:55, Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> I spent some time preparing this for commit, which only amounted to some
> light edits.  I am posting a new version of the patch in order to get one
> more round of cfbot coverage and to make sure there is no remaining
> feedback.

Overall your light edits look good to me. The commit message is very
descriptive and I like the shortening of the comments. The only thing
I feel is that I think lost some my original intent is this sentence:

+ * different types.  The outer loop only does a single iteration, so we expect
+ * optimizing compilers will unroll it, thereby optimizing it away.

The "we expect" reads to me as if we're not very sure that compilers
do this optimization. Even though we are quite sure. Maybe some small
changes like this to clarify that.

The outer loop only does a single iteration, so we expect that **any**
optimizing compilers will unroll it, thereby optimizing it away. **We
know for sure that gcc and clang do this optimization.**

On Wed, Jan 03, 2024 at 10:57:07PM +0100, Jelte Fennema-Nio wrote:
> Overall your light edits look good to me. The commit message is very
> descriptive and I like the shortening of the comments. The only thing
> I feel is that I think lost some my original intent is this sentence:
> 
> + * different types.  The outer loop only does a single iteration, so we expect
> + * optimizing compilers will unroll it, thereby optimizing it away.
> 
> The "we expect" reads to me as if we're not very sure that compilers
> do this optimization. Even though we are quite sure. Maybe some small
> changes like this to clarify that.
> 
> The outer loop only does a single iteration, so we expect that **any**
> optimizing compilers will unroll it, thereby optimizing it away. **We
> know for sure that gcc and clang do this optimization.**

WFM.  Thanks for reviewing the edits.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

Jelte Fennema-Nio <postgres@jeltef.nl> writes:
> The "we expect" reads to me as if we're not very sure that compilers
> do this optimization. Even though we are quite sure. Maybe some small
> changes like this to clarify that.

> The outer loop only does a single iteration, so we expect that **any**
> optimizing compilers will unroll it, thereby optimizing it away. **We
> know for sure that gcc and clang do this optimization.**

I like Nathan's wording.  Your assertion is contradicted by cases as
obvious as -O0, and I'm sure a lot of other holes could be poked in it
as well (e.g, just how far back might gcc choose to do that unrolling?
Does the size of the loop body matter?)

            regards, tom lane

On Wed, 3 Jan 2024 at 23:13, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I like Nathan's wording.

To be clear, I don't want to block this patch on the wording of that
single comment. So, if you feel Nathan's wording was better, I'm fine
with that too. But let me respond to your arguments anyway:

> Your assertion is contradicted by cases as
> obvious as -O0

My suggestion specifically mentions optimizing compilers, -O0 is by
definition not an optimizing compiler.

> just how far back might gcc choose to do that unrolling?

gcc 5.1 and clang 3.0 (possibly earlier, but this is the oldest I was
able to test the code with on godbolt). As seen upthread:

> I did some testing on godbolt.org and both versions of the macros
> result in the same assembly when compiling with -O2 (and even -O1)
> when compiling with ancient versions of gcc (5.1) and clang (3.0):
> https://godbolt.org/z/WqfTbhe4e

> Does the size of the loop body matter?)

I copy pasted a simple printf ~800 times and the answer seems to be
no, it doesn't matter: https://godbolt.org/z/EahYPa8KM

Committed after some additional light edits.  Thanks for the patch!

On Wed, Jan 03, 2024 at 11:36:36PM +0100, Jelte Fennema-Nio wrote:
> On Wed, 3 Jan 2024 at 23:13, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I like Nathan's wording.
> 
> To be clear, I don't want to block this patch on the wording of that
> single comment. So, if you feel Nathan's wording was better, I'm fine
> with that too. But let me respond to your arguments anyway:

I decided to keep the v8 wording, if for no other reason than I didn't see
the need for lots of detail about how it compiles.  IMHO even the vague
mention of loop unrolling is probably more than is really necessary.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com