Re: ArrayLists instead of List (for some things)

On 3 November 2017 at 12:41, David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> wrote:
> On 3 November 2017 at 03:26, Craig Ringer <craig(at)2ndquadrant(dot)com> wrote:
>> On 2 November 2017 at 22:22, David Rowley <david(dot)rowley(at)2ndquadrant(dot)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