dcollections 1.0 and 2.0a beta released

Steven Schveighoffer schveiguy at yahoo.com
Mon May 24 11:49:33 PDT 2010


On Mon, 24 May 2010 12:27:10 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 05/24/2010 11:14 AM, Steven Schveighoffer wrote:
>> On Mon, 24 May 2010 11:45:44 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>> On 05/24/2010 10:23 AM, Steven Schveighoffer wrote:
>>>> On Mon, 24 May 2010 10:10:51 -0400, Andrei Alexandrescu
>>>> <SeeWebsiteForEmail at erdani.org> wrote:
>>>>
>>>>> On 05/24/2010 06:54 AM, Steven Schveighoffer wrote:
>>>>>> length is allowed to return NO_LENGTH_SUPPORT if O(1) length isn't
>>>>>> possible,
>>>>>
>>>>> Do you agree that's an awkwardness?
>>>>
>>>> Yes, at that point it's an optimization. The only place where I assume
>>>> length could be invalid is when working with the Iterator!V type,  
>>>> which
>>>> might not be a dcollections object.
>>>
>>> That doesn't matter. Since you define NO_LENGTH_SUPPORT and you have
>>> interfaces, the door is ajar forever. Client code can't write this:
>>>
>>> auto total = cont1.length + cont2.length;
>>>
>>> because that is incorrect code (that compiles, runs, and produces some
>>> odd result).
>>>
>>> So don't take it lightly. NO_LENGTH_SUPPORT means no length support.
>>> Then pretending it's supported will only harm everyone.
>>
>> I get what you are saying. What I meant was it's moot if you are not
>> using interfaces. If you don't know what the underlying type is, then
>> you have to do a runtime check.
>>
>> I agree it's awkward, and I could have not included length as a member
>> of Iterator, in which case it would be on all the container types and
>> NO_LENGTH_SUPPORT would not exist. All containers are meant to have a
>> valid length, it is only with non-container Iterators that length can be
>> NO_LENGTH_SUPPORT.
>>
>>>> However, supporting non-length containers via
>>>> generic programming vs. interfaces would be much smoother.
>>>>
>>>>>> In that case, you can do
>>>>>> coll.begin.empty to determine if the collection has any elements.
>>>>>
>>>>> Then why not make length optional and define empty? From the above it
>>>>> looks like an obviously better design.
>>>>>
>>>>>> But all dcollections are bi-directional anyways, there is no singly
>>>>>> linked list. That was a decision I made early on, because it allows
>>>>>> more
>>>>>> assumptions about dcollections' containers. I think length-less  
>>>>>> singly
>>>>>> linked lists would be a good addition to phobos that are not part
>>>>>> of the
>>>>>> collection hierarchy, they are almost on par with builtin arrays as
>>>>>> being so simple.
>>>>>
>>>>> Do you see dcollections' inability to express slists as a problem?
>>>>
>>>> I don't see them as unable to express slists. They would break the
>>>> design guidelines that I set for collections being iterable in both
>>>> directions, but an slist fits fine within the List interface.
>>>
>>> What's the required complexity of concat?
>>
>> O(n) with n being the number of elements added
>>
>>> Is add expected to put things in a specific place? How does slist
>>> implement back()?
>>>
>>> slist does not fit the List interface.
>>
>> 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 :)  The overhead of storage is minimal compared  
to the elements of the list, which do not contain said overhead.

> 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.  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.

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.

-Steve


More information about the Digitalmars-d-announce mailing list