Re: POC: converting Lists into arrays

Andres Freund <andres(at)anarazel(dot)de> writes:
> On 2019-03-02 18:11:43 -0500, Tom Lane wrote:
>> I wonder what test cases Andres has been looking at that convince
>> him that we need a reimplementation of Lists.

> My main observation was from when the expression evaluation was using
> lists all over. List iteration overhead was very substantial there. But
> that's not a problem anymore, because all of those are gone now due to
> the expression rewrite. I personally wasn't actually advocating for a
> new list implementation, I was/am advocating that we should move some
> tasks over to a more optimized representation.

I doubt that you'll get far with that; if this experiment is anything
to go by, it's going to be really hard to make the case that twiddling
the representation of widely-known data structures is worth the work
and bug hazards.

> I still regularly see list overhead matter in production workloads. A
> lot of it being memory allocator overhead, which is why I'm concerned
> with a rewrite that doesn't reduce the number of memory allocations.

Well, I did that in the v3 patch, and it still hasn't moved the needle
noticeably in any test case I've tried. At this point I'm really
struggling to see a reason why we shouldn't just mark this patch rejected
and move on. If you have test cases that suggest differently, please
show them don't just handwave.

The cases I've been looking at suggest to me that we'd make far
more progress on the excessive-palloc'ing front if we could redesign
things to reduce unnecessary copying of parsetrees. Right now the
planner does an awful lot of copying because of fear of unwanted
modifications of multiply-linked subtrees. I suspect that we could
reduce that overhead with some consistently enforced rules about
not scribbling on input data structures; but it'd take a lot of work
to get there, and I'm afraid it'd be easily broken :-(

regards, tom lane