Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-03 Thread Craig Ringer
On 3 November 2017 at 12:41, David Rowley wrote: > On 3 November 2017 at 03:26, Craig Ringer wrote: >> On 2 November 2017 at 22:22, David Rowley >> wrote: >>> Maybe, but the new implementation is not going to do

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread David Rowley
On 3 November 2017 at 03:26, Craig Ringer wrote: > On 2 November 2017 at 22:22, David Rowley > wrote: >> Maybe, but the new implementation is not going to do well with places >> where we perform lcons(). Probably many of those places could be

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread Andres Freund
On 2017-11-02 10:38:34 -0400, Tom Lane wrote: > David Rowley writes: > > On 3 November 2017 at 03:17, Tom Lane wrote: > >> We've jacked up the List API and driven a new implementation underneath > >> once before. Maybe it's time to do that

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread David Rowley
On 3 November 2017 at 03:27, Stephen Frost wrote: > * David Rowley (david.row...@2ndquadrant.com) wrote: >> We could get around a few of these problems if Lists were implemented >> internally as arrays, however, arrays are pretty bad if we want to >> delete an item out the

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread Tom Lane
David Rowley writes: >> It seems to me that a whole lot of the complaints about this could be >> resolved simply by improving the List infrastructure to allocate ListCells >> in batches. That would address the question of "too much palloc traffic" >> and greatly

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread David Rowley
On 3 November 2017 at 03:38, Tom Lane wrote: > David Rowley writes: >> On 3 November 2017 at 03:17, Tom Lane wrote: >>> We've jacked up the List API and driven a new implementation underneath >>> once before. Maybe it's time

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread Tom Lane
David Rowley writes: > On 3 November 2017 at 03:17, Tom Lane wrote: >> We've jacked up the List API and driven a new implementation underneath >> once before. Maybe it's time to do that again. > Maybe, but the new implementation is not going to

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread Stephen Frost
David, * David Rowley (david.row...@2ndquadrant.com) wrote: > Our List implementation internally uses linked lists which are > certainly good for some things, but pretty bad at other things. Linked > lists are pretty bad when you want to fetch the Nth element, as it > means looping ever each

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread Craig Ringer
On 2 November 2017 at 22:22, David Rowley wrote: > On 3 November 2017 at 03:17, Tom Lane wrote: >> We've jacked up the List API and driven a new implementation underneath >> once before. Maybe it's time to do that again. > > Maybe, but the new

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread Craig Ringer
On 2 November 2017 at 22:17, Tom Lane wrote: > David Rowley writes: >> Comments on the design are welcome, but I was too late to the >> commitfest, so there are other priorities. However, if you have a >> strong opinion, feel free to voice it. >

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread David Rowley
On 3 November 2017 at 03:17, Tom Lane wrote: > We've jacked up the List API and driven a new implementation underneath > once before. Maybe it's time to do that again. Maybe, but the new implementation is not going to do well with places where we perform lcons(). Probably

Re: [HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread Tom Lane
David Rowley writes: > Comments on the design are welcome, but I was too late to the > commitfest, so there are other priorities. However, if you have a > strong opinion, feel free to voice it. I do not like replacing Lists piecemeal; that's a recipe for ongoing API

[HACKERS] ArrayLists instead of List (for some things)

2017-11-02 Thread David Rowley
Hackers, Our List implementation internally uses linked lists which are certainly good for some things, but pretty bad at other things. Linked lists are pretty bad when you want to fetch the Nth element, as it means looping ever each previous element until you get to the Nth. They're also pretty