Thread: [HACKERS] ArrayLists instead of List (for some things)
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 bad for a modern CPU due to their memory access pattern. 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 middle as we'd have to shuffle everything over one spot. Linked lists are much better here... at least they are when you already have the cell you want to remove... so we can't expect that we can just rewrite List to use arrays instead. I've attached a first cut implementation of "AList". I was originally going to call it "ArrayList", but my fingers were getting tired, so I change it. This first cut version replaces nothing in the code base to use ALists. This email (and due to the timing of it) is more of a marker that this is being worked on. I know in particular that Andres has complained at least once about List usages in the executor, which I agree is not great. Looking at the usage of list_nth() is quite scary! My plans for this include: * Make targetlists from createplan onwards use ALists. Every time I look at build_path_tlist() I gawk at the number of palloc calls that are going on inside those lappend() calls. We already know how many items will be in the list, so with AList we could just alist_premake(list_length(path->pathtarget->exprs)) and we'd never have to palloc() another element for that list again. We do the same again in various mutator functions in setrefs.c too! * list_nth usage in adjust_appendrel_attrs_mutator() to speed up translation between parent and child Vars * And also, umm, <mumble> simple_rte_array and simple_rel_array</mumble>. Well, we'd still need somewhere to store all the RelOptInfos, but the idea is that it would be rather nice if we could not expand the entire inheritance hierarchy of a relation, and it would be rather nice if we could just add the partitions that we need, rather than add them all and setting dummy paths for the ones we're not interested in. Anyway, please don't debate the usages of the new type here. As for all the above plans, I admit to not having a full handle on them yet. I wrote the Array List implementation so I could get a better idea on how possible each of those would be, so, for now, to prevent any duplicate work, here it is... (Including in Andres because I know he's mentioned his dislike for List in the executor) 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. -- David Rowley http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
David Rowley <david.rowley@2ndquadrant.com> 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 breakage and back-patching pain. Plus we'll then have *four*
different linked-list implementations in the backend, which sure
seems like too many.
We've jacked up the List API and driven a new implementation underneath
once before. Maybe it's time to do that again.
regards, tom lane
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On 3 November 2017 at 03:17, Tom Lane <tgl@sss.pgh.pa.us> 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 many of those places could be changed to lappend(), but I bet there's plenty that need prepend. -- David Rowley http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
On 2 November 2017 at 22:17, Tom Lane <tgl@sss.pgh.pa.us> wrote: > David Rowley <david.rowley@2ndquadrant.com> 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 breakage and back-patching pain. Plus we'll then have *four* > different linked-list implementations in the backend, which sure > seems like too many. > > We've jacked up the List API and driven a new implementation underneath > once before. Maybe it's time to do that again. I know some systems use hybrid linked array-lists, where linked list cells are multi-element. https://en.wikipedia.org/wiki/Unrolled_linked_list I don't have much experience with them myself. -- Craig Ringer http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
On 2 November 2017 at 22:22, David Rowley <david.rowley@2ndquadrant.com> wrote: > On 3 November 2017 at 03:17, Tom Lane <tgl@sss.pgh.pa.us> 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 many of those places could be > changed to lappend(), but I bet there's plenty that need prepend. Yeah, and it's IMO significant that pretty much every nontrivial system with ADTs offers multiple implementations of list data structures, often wrapped with a common API. Java's Collections, the STL, you name it. -- Craig Ringer http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
David, * David Rowley (david.rowley@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 previous element until you get to the Nth. > They're also pretty bad for a modern CPU due to their memory access > pattern. I can certainly understand this complaint. > 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 middle as we'd have to shuffle everything over > one spot. Linked lists are much better here... at least they are when > you already have the cell you want to remove... so we can't expect > that we can just rewrite List to use arrays instead. This actually depends on just how you delete the item out of the array, though there's a trade-off there. If you "delete" the item by marking it as "dead" then you don't need to re-shuffle everything, but, of course, then you have to make sure to 'skip' over those by running down the array for each list_nth() call- but here's the thing, with a small list that's all in a tighly packed array, that might not be too bad. Certainly far better than having to grab random memory on each step and I'm guessing you'd only actually store the "data" item for a given list member in the array if it's a integer/oid/etc list, not when it's actually a pointer being stored in the list, so you're always going to be working with pretty tightly packed arrays where scanning the list on the list_nth call really might be darn close to as fast as using an offset to the actual entry in the array, unless it's a pretty big list, but I don't think we've actually got lots of multi-hundred-deep lists. Of course, you'd have to watch out for cases where there's a lot of deletes happening, since that would effectively make this list longer. Anyway, just something to consider. Having to actually store the "delete" flag would have some cost to it also, unless you happen to already be storing something per entry and have an extra bit to spare. Others who are more versed in CPU magics than I am are certainly welcome to comment on if they think this makes sense to consider, I'm no CPU architecture guru. > Anyway, please don't debate the usages of the new type here. As for > all the above plans, I admit to not having a full handle on them yet. +1. Thanks! Stephen
David Rowley <david.rowley@2ndquadrant.com> writes:
> On 3 November 2017 at 03:17, Tom Lane <tgl@sss.pgh.pa.us> 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 many of those places could be
> changed to lappend(), but I bet there's plenty that need prepend.
[ shrug... ] To me, that means this implementation isn't necessarily
the right solution.
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 improve the it-accesses-all-over-memory situation too.
Possibly there are more aggressive changes that could be implemented
without breaking too many places, but I think it would be useful to
start there and see what it buys us.
regards, tom lane
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On 3 November 2017 at 03:38, Tom Lane <tgl@sss.pgh.pa.us> wrote: > David Rowley <david.rowley@2ndquadrant.com> writes: >> On 3 November 2017 at 03:17, Tom Lane <tgl@sss.pgh.pa.us> 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 many of those places could be >> changed to lappend(), but I bet there's plenty that need prepend. > > [ shrug... ] To me, that means this implementation isn't necessarily > the right solution. True, of course, could be worked around probably with some bit flags to record if lcons was called, and then consume the elements in reverse. We might have to shuffle things along a bit for Lists that get lcons and lappend calls. The API break that I can't see a way around is: /* does the list have 0 elements? */ if (list == NIL) ... That would need to be rewritten as: if (list_length(list) == 0) ... > 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 improve the it-accesses-all-over-memory situation too. > > Possibly there are more aggressive changes that could be implemented > without breaking too many places, but I think it would be useful to > start there and see what it buys us. Yeah, certainly would be a good way of determining the worth of changing. -- David Rowley http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
David Rowley <david.rowley@2ndquadrant.com> 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 improve the it-accesses-all-over-memory situation too.
>>
>> Possibly there are more aggressive changes that could be implemented
>> without breaking too many places, but I think it would be useful to
>> start there and see what it buys us.
> Yeah, certainly would be a good way of determining the worth of changing.
BTW, with just a little more work that could be made to address the
list-nth-is-expensive problem too. I'm imagining a call that preallocates
an empty list with room for N ListCells (or perhaps, if we need to
preserve compatibility with NIL == NULL, creates a single-element list
with room for N-1 more cells), plus some tracking in list.c of whether
the list cells have been consumed in order. Given the typical use-case of
building lists strictly with lappend, list_nth() could index directly into
the ListCell slab as long as it saw the List header's "is_linear" flag was
true.
regards, tom lane
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On 3 November 2017 at 03:27, Stephen Frost <sfrost@snowman.net> wrote: > * David Rowley (david.rowley@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 middle as we'd have to shuffle everything over >> one spot. Linked lists are much better here... at least they are when >> you already have the cell you want to remove... so we can't expect >> that we can just rewrite List to use arrays instead. > > This actually depends on just how you delete the item out of the array, > though there's a trade-off there. If you "delete" the item by marking > it as "dead" then you don't need to re-shuffle everything, but, of > course, then you have to make sure to 'skip' over those by running down > the array for each list_nth() call- but here's the thing, with a small > list that's all in a tighly packed array, that might not be too bad. > Certainly far better than having to grab random memory on each step and > I'm guessing you'd only actually store the "data" item for a given list > member in the array if it's a integer/oid/etc list, not when it's > actually a pointer being stored in the list, so you're always going to > be working with pretty tightly packed arrays where scanning the list on > the list_nth call really might be darn close to as fast as using an > offset to the actual entry in the array, unless it's a pretty big list, > but I don't think we've actually got lots of multi-hundred-deep lists. I was hoping to have list_nth as always O(1) so that we'd never be tempted again to use arrays directly like we are not for things like simle_rel_array[]. Probably it could be made to work quickly in most cases by tracking if there are any deleted items and just do the direct array lookups if nothing is deleted, and if something is deleted then visit index n minus bms_num_members() of some deleted bitmapset for the bits earlier than the Nth element. bms_num_members() could be made faster with 64bit bitmap words and __builtin_popcountl() falling back on the number_of_ones[] array when not available. Would also require a bms_num_members_before() function. In the implementation that I attached, I showed an example of how to delete items out an array list, which I think is quite a bit cleaner than how we generally do it today with List. (e.g in reconsider_outer_join_clauses()) However, it'll still perform badly when just a single known item is being removed. -- David Rowley http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
On 2017-11-02 10:38:34 -0400, Tom Lane wrote: > David Rowley <david.rowley@2ndquadrant.com> writes: > > On 3 November 2017 at 03:17, Tom Lane <tgl@sss.pgh.pa.us> 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 many of those places could be > > changed to lappend(), but I bet there's plenty that need prepend. > > [ shrug... ] To me, that means this implementation isn't necessarily > the right solution. > > 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 improve the it-accesses-all-over-memory situation too. It'll however not solve the problem that pointer chained datastructures have very poor access patterns. > Possibly there are more aggressive changes that could be implemented > without breaking too many places, but I think it would be useful to > start there and see what it buys us. I'm suspicious that that will result in causing pain twice, once doing the compromise thing, and once doing it right. FWIW, I'd started pursuing converting a lot of executor uses of lists with arrays. But everywhere I did, particularly the uses inside the expression machinery, I noticed that larger changes where needed. For the expression stuff we needed a much larger architectural change (hence the stuff in 10 I did with Tom's help). The other big user of lists at the execution phase are targetlists - I think there the architectural change is also bigger: Rebuilding/analyzing all the targetlists, tupledescs etc at execution time is the architectural problem, not the use of lists itself (although that's also bad). The amount of cycles spent in ExecTypeFromTL() etc and friends is partially caused by the use of lists, but the real problem is that we're doing all that work in the first place. So I personally think most uses of lists at execution time are archetecturally wrong, therefore optimizing their implementation is just a bandaid. Where I think the arguments for a more optimized implementation are better is the parser, where we really don't ahead of time know the size of the data we're dealing with. Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
On 3 November 2017 at 03:26, Craig Ringer <craig@2ndquadrant.com> wrote: > On 2 November 2017 at 22:22, David Rowley <david.rowley@2ndquadrant.com> 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 >> changed to lappend(), but I bet there's plenty that need prepend. > > Yeah, and it's IMO significant that pretty much every nontrivial > system with ADTs offers multiple implementations of list data > structures, often wrapped with a common API. > > Java's Collections, the STL, you name it. I've never really looked at much Java, but I've done quite a bit of dotnet stuff in my time and they have a common interface ICollection and various data structures that implement that interface. Which is implemented by a bunch of classes, something like: ConcurrentDictionary (hash table) Dictionary (hash table) HashSet (hash table) LinkedList (some kinda linked list) List (Arrays, probably) SortedDictionary (bst, I think) SortedList (no idea, perhaps a btree) SortedSet Bag (no idea, but does not care about any order) Probably there are more, but the point is that they obviously don't believe there's a one-size-fits-all type. I don't think we should do that either. However, I've proved nothing on the performance front yet, so that should probably be my next step. -- David Rowley http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
On 3 November 2017 at 12:41, David Rowley <david.rowley@2ndquadrant.com> wrote: > On 3 November 2017 at 03:26, Craig Ringer <craig@2ndquadrant.com> wrote: >> On 2 November 2017 at 22:22, David Rowley <david.rowley@2ndquadrant.com> 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 >>> changed to lappend(), but I bet there's plenty that need prepend. >> >> Yeah, and it's IMO significant that pretty much every nontrivial >> system with ADTs offers multiple implementations of list data >> structures, often wrapped with a common API. >> >> Java's Collections, the STL, you name it. > > I've never really looked at much Java, but I've done quite a bit of > dotnet stuff in my time and they have a common interface ICollection > and various data structures that implement that interface. Which is > implemented by a bunch of classes, something like > > ConcurrentDictionary (hash table) > Dictionary (hash table) > HashSet (hash table) > LinkedList (some kinda linked list) > List (Arrays, probably) > SortedDictionary (bst, I think) > SortedList (no idea, perhaps a btree) > SortedSet > Bag (no idea, but does not care about any order) > > Probably there are more, but the point is that they obviously don't > believe there's a one-size-fits-all type. I don't think we should do > that either. However, I've proved nothing on the performance front > yet, so that should probably be my next step. Right. If you've done C# you've done cleaned-up, modernized Java. C# and Java both have an advantage we don't, namely JIT compilation, so they can afford to do more with common interfaces then do runtime specialization. As a pure C project we don't really have that option, so it's unlikely to be efficient for us to have a fully common interface and dynamic dispatch. Even C++ only gets away with its common interfaces in the STL because it does compile-time specialization via templates, non-virtual methods, etc. There's only so much you can perpetrate with macros and rely on the compiler to clean up before it just gets awful. So I imagine if we do land up with a couple of collections we'd probably have an AList, alcons, alappend, etc. Bit of a pain, but hardly the end of the world. -- Craig Ringer http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
On Fri, 3 Nov 2017 at 03:17, Tom Lane <tgl@sss.pgh.pa.us> wrote: > > David Rowley <david.rowley@2ndquadrant.com> 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 breakage and back-patching pain. Plus we'll then have *four* > different linked-list implementations in the backend, which sure > seems like too many. > > We've jacked up the List API and driven a new implementation underneath > once before. Maybe it's time to do that again. (reviving this old thread as it's still on my list of things to work on) How would you feel if I submitted a patch that changed all locations where we test for an empty list with: if (list) or if (list == NIL) to a more standard form of if (list_is_empty(list)) ? The idea here is that I'd like a way to preallocate memory for a list to a given size before we start populating it, and that flies in the face of how we currently test for list emptiness. Such a macro could be backpatched to assist extensions. -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services