Re: POC: converting Lists into arrays

Hi,

On 2019-02-23 21:24:40 -0500, Tom Lane wrote:
> For quite some years now there's been dissatisfaction with our List
> data structure implementation.  Because it separately palloc's each
> list cell, it chews up lots of memory, and it's none too cache-friendly
> because the cells aren't necessarily adjacent.

Indeed. Might be worthwhile to note that linked list, even if stored in
adjacent memory, are *still* not very friendly for out-of-order CPUs, as
they introduce a dependency between fetching the pointer to the next
element, and processing the next element. Whereas for arrays etc CPUs
start executing instructions for the next element, before finishing the
last one.


> Every time this has come up, I've opined that the right fix is to jack
> up the List API and drive a new implementation underneath, as we did
> once before (cf commit d0b4399d81).

Btw, should we remove the ENABLE_LIST_COMPAT stuff independent of this
discussion? Seems like we could even just do that for 12.


> The big-picture performance change is that this makes list_nth()
> a cheap O(1) operation, while lappend() is still pretty cheap;
> on the downside, lcons() becomes O(N), as does insertion or deletion
> in the middle of a list.  But we don't use lcons() very much
> (and maybe a lot of the existing usages aren't really necessary?),
> while insertion/deletion in long lists is a vanishingly infrequent
> operation.  Meanwhile, making list_nth() cheap is a *huge* win.

Right.


> The most critical thing that we lose by doing this is that when a
> List is modified, all of its cells may need to move, which breaks
> a lot of code that assumes it can insert or delete a cell while
> hanging onto a pointer to a nearby cell.

We could probably "fix" both this, and the cost of making such
modifications, by having more of an list-of-arrays style
representation. When adding/removing middle-of-the-"list" elements, we
could chop that array into two (by modifying metadata, not freeing), and
shove the new data into a new array inbetween.  But I don't think that'd
overall be a win, even if it'd get us out of the silent API breakage
business.


> Another annoying consequence of lnext() needing a List pointer is that
> the List arguments of foreach() and related macros are now evaluated
> each time through the loop.  I could only find half a dozen places
> where that was actually unsafe (all fixed in the draft patch), but
> it's still bothersome.  I experimented with ways to avoid that, but
> the only way I could get it to work was to define foreach like this:

Yea, that problem is why the ilist stuff has the iterator
datastructure. That was before we allowed variable defs in for
though...


> #define foreach(cell, l)        for (const List *cell##__foreach = foreach_setup(l, &cell);          cell != NULL;
cell= lnext(cell##__foreach, cell))
 
> 
> static inline const List *
> foreach_setup(const List *l, ListCell **cell)
> {
>     *cell = list_head(l);
>     return l;
> }
> 
> That works, but there are two problems.  The lesser one is that a
> not-very-bright compiler might think that the "cell" variable has to
> be forced into memory, because its address is taken.

I don't think that's a huge problem. I don't think there are any
platforms we really care about with such compilers? And I can't imagine
that being the only performance problem on such a platform.


> The bigger one is
> that this coding forces the "cell" variable to be exactly "ListCell *";
> you can't add const or volatile qualifiers to it without getting
> compiler warnings.  There are actually more places that'd be affected
> by that than by the need to avoid multiple evaluations.  I don't think
> the const markings would be a big deal to lose, and the two places in
> do_autovacuum that need "volatile" (because of a nearby PG_TRY) could
> be rewritten to not use foreach.  So I'm tempted to do that, but it's
> not very pretty.

Hm, that's a bit ugly, indeed.


> Maybe somebody can think of a better solution?

We could cast away const & volatile on most compilers, and do better on
gcc & clang, I guess. We could use typeof() and similar games to add the
relevant qualifiers. Or alternatively, also optionally of course, use
C11 _Generic trickery for defining the type.  But that seems
unsatisfying (but safe, I think).



> There's a lot of potential follow-on work that I've not touched yet:
> 
> 1. This still involves at least two palloc's for every nonempty List,
> because I kept the header and the data array separate.  Perhaps it's
> worth allocating those in one palloc.  However, right now there's an
> assumption that the header of a nonempty List doesn't move when you
> change its contents; that's embedded in the API of the lappend_cell
> functions, and more than likely there's code that depends on that
> silently because it doesn't bother to store the results of other
> List functions back into the appropriate pointer.  So if we do that
> at all I think it'd be better tackled in a separate patch; and I'm
> not really convinced it's worth the trouble and extra risk of bugs.

Hm, I think if we force external code to audit their code, we better
also do this. This is a significant number of allocations, and I don't
think it'd be good to spread this out over two releases.



Greetings,

Andres Freund