Re: [HACKERS] ArrayLists instead of List (for some things)
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 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
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 >> 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
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 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
On 3 November 2017 at 03:27, Stephen Frost wrote: > * David Rowley ([email protected]) 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
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 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
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 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
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 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
David, * David Rowley ([email protected]) 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 signature.asc Description: Digital signature
Re: [HACKERS] ArrayLists instead of List (for some things)
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 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
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. > > 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
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 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] ArrayLists instead of List (for some things)
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 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 ([email protected]) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
