dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

On 05/24/2010 01:49 PM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 12:27:10 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>>> A pointer to the end element would be required for both appending and
>>> back().
>>
>> This further erodes my confidence. Size needs to be maintained _and_ a
>> pointer to the last element must be maintained. For many uses, all of
>> this stuff is unnecessary overhead.
>
> You make it sound like incrementing a counter and changing a pointer are
> incredibly slow operations :)

They are. Ask Walter for a good example.

> The overhead of storage is minimal
> compared to the elements of the list, which do not contain said overhead.

I'm talking containers of lists here.

>> I think we need to build the shared vision that in Phobos we're
>> competing against hand-written, highly-optimized code. This is the
>> fight STL took and largely won. We can't afford to lower our standards
>> for one tiny bit.
>>
>> I was once talking over a beer about the advantages of container
>> abstractions. Walter slapped my face by defining the fastest SLL in
>> the world on a napkin. It looked like this:
>>
>> struct List { int v; List * next; }
>>
>> He took so little time to define that, and the primitives he needed
>> were so simple and fast, that it was an absolute overkill to replace
>> that with a generic whiz-bang container. If I'd mentioned there'd be
>> any extra data involved, that would mean the end of negotiation. "Why
>> do you need that?" "For length()!" "But I don't need length()!" "Well
>> you have to." "That's Communism in design!"
>>
>> And I agree.
>
> But something like the above is prone to all sorts of nasty things, like
> inadvertent cycles in your list.

Yeah, and I'd have my list of arguments to add too.

> Which may be acceptable to you if you
> want the bleeding fastest speed available. There will always be tailored
> code crafted to be as fast as possible for some specific design and
> dcollections and your slist just won't fit the bill.

Except that the set is considerably smaller for a well-designed slist.

> And dcollections' link list node is exactly what you wrote there (with a
> prev pointer of course). The only difference is, I don't define an
> element is the same as a list. The whole list has it's own data,
> including a pointer to the first element in the list.
>
> Look at D's arrays. Is appending with D's arrays the fastest it possibly
> could be? Hell no, but it's good enough for most situations, and safe.

If I could make them faster without adversely affecting the performance 
of other operations, I would. There's considerable constraints at plain 
in the array design for historical and other reasons.


Andrei