On 3 November 2017 at 03:26, Craig Ringer <cr...@2ndquadrant.com> wrote: > On 2 November 2017 at 22:22, David Rowley <david.row...@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
