Re: POC: converting Lists into arrays

David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
> I went and had a few adventures with this patch to see if I could
> figure out why the small ~1% regression exists.

Thanks for poking around!

> ... I had
> suspected it was the lcons() calls being expensive because then need
> to push the elements up one place each time, not something that'll
> scale well with larger lists.

I just did some looking around at lcons() calls, and it's hard to identify
any that seem like they would be performance-critical. I did notice a
number of places that think that lcons'ing a item onto a list, and later
stripping it off with list_delete_first, is efficient. With the new
implementation it's far cheaper to lappend and then list_truncate instead,
at least if the list is long. If the list order matters then that's not
an option, but I found some places where it doesn't matter so we could get
an easy win. Still, it wasn't obvious that this would move the needle at
all.

> I then tried hacking at the foreach() macro after wondering if the
> lnext() call was somehow making things difficult for the compiler to
> predict what cell would come next.

Yeah, my gut feeling right now is that foreach() is producing crummy
code, though it's not obvious why it would need to. Maybe some
micro-optimization is called for. But I've not had time to pursue it.

> The only thing that I did to manage to speed the patch up was to ditch
> the additional NULL test in lnext(). I don't see why that's required
> since lnext(NULL) would have crashed with the old implementation.

Hmmm ...

> Perhaps if we're not going to see gains from the patch alone then
> we'll need to tag on some of the additional stuff that will take
> advantage of list_nth() being fast and test the performance of it all
> again.

Yeah, evaluating this patch in complete isolation is a bit unfair.
Still, it'd be nice to hold the line in advance of any follow-on
improvements.

regards, tom lane