Re: POC: converting Lists into arrays

On Mon, Mar 4, 2019 at 01:11:35PM -0500, Tom Lane wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> > I think the reason why you're not seeing a performance benefit is
> > because the problem is not that lists are generically a more expensive
> > data structure than arrays, but that there are cases when they are
> > more expensive than arrays. If you only ever push/pop at the front,
> > of course a list is going to be better. If you often look up elements
> > by index, of course an array is going to be better. If you change
> > every case where the code currently uses a list to use something else
> > instead, then you're changing both the winning and losing cases.
>
> I don't think this argument is especially on-point, because what I'm
> actually seeing is just that there aren't any list operations that
> are expensive enough to make much of an overall difference in
> typical queries. To the extent that an array reimplementation
> reduces the palloc traffic, it'd take some load off that subsystem,
> but apparently you need not-typical queries to really notice.
> (And, if the real motivation is aggregate palloc savings, then yes you
> really do want to replace everything...)

Could it be that allocating List* structures near the structure it
points to is enough of a benefit in terms of cache hits that it is a
loss when moving to a List* array?

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ As you are, so once was I. As I am, so you will be. +
+ Ancient Roman grave inscription +