Re: POC: converting Lists into arrays

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...)

> Yeah, changing things individually is more work, but that's how you
> get the wins without incurring the losses.

The concern I have is mostly about the use of lists as core infrastructure
in parsetree, plantree, etc data structures. I think any idea that we'd
replace those piecemeal is borderline insane: it's simply not worth it
from a notational and bug-risk standpoint to glue together some parts of
those structures differently from the way other parts are glued together.

regards, tom lane