D library projects

[Steven Schveighoffer]

On Sat, 14 Nov 2009 22:08:23 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> dsimcha wrote:
>> Tango has a bunch of
>> collections.
>
> Are those following Java's collection design?

The original collections in Tango were ported from Doug Lea's original  
code, not the Java design (which was also based on Doug Lea's design).   
The newer ones are rewritten from scratch, but in the same feel.

dcollections have some Java feel in that they are classes and interfaces,  
but also add C++ style iterators (cursors).

>> I think what we really need is to define what paradigm we're using for
>> collections.  Here are some questions that really need to be answered  
>> before we
>> can start implementing a std.collections:
>>  1.  How do we prioritize the following when tradeoffs have to be made:
>>      a.  Safety
>>     b.  Flexibility
>>     c.  Performance
>>     d.  Simplicity/Ease of use
>>  STL, for example, primarily focuses on performance and flexibility at  
>> the expense
>> of simplicity and safety.  We might not want that tradeoff.
>
> I think policies should decide here. Let the user make the choice and  
> offer a good set of defaults.

I agree -- it should be possible with the metaprogramming power of D to  
allow for the user to choose his weapon -- power and speed vs. safe.  I  
think simplicity is a given.

For example, it could be a version statement that decides whether ranges  
of a container do runtime checks for safety.

>> 2.  Should we use an OO flavor w/ classes and explicit Interface  
>> interfaces or a
>> more template-y flavor with structs and compile-time interfaces?
>
> I'd be leaning more towards classes, but I'm still waiting for a killer  
> argument one way or another.

I think shoehorning containers that are graph based into value types might  
be a little strenuous.  All the builtin D container types are essentially  
reference types (arrays are not exactly reference types but behave mostly  
like reference types), I don't see why we should change that.

Making them classes allows for interfaces which helps allow runtime  
decisions for things like copying data between containers that are of  
different types.  See dcollections and how easy it is to copy data from  
one type to another.

> 6.  Should we allow custom allocators?  I would actually say no,
>> because based on
>> my experience with my TempAlloc collections, if you're using a custom  
>> allocator,
>> you probably want to design the implementation with the details of that  
>> allocator
>> in mind.  Furthermore, it may be hard to make things safe without  
>> knowing
>> something about how the memory allocator works.
>
> Good question. Would love to, but I don't know how to design a good  
> solution.

In dcollections, the custom allocator is a template argument for the  
collection class.

Using a custom allocator has brought tremendous speedups, because you go  
through fewer collection cycles, and waste much less space.

I think it's possible to design a custom allocator framework that is  
hidden completely from the API.  dcollections has 2 different allocators  
-- the default is a custom allocator I wrote to cut down on the GC  
collection cycles (which I also contributed to Tango and is now their  
default allocator), and the alternative is an allocator which simply uses  
the GC to allocate all nodes with 'new'.  The code to use such containers  
does not change if you change the allocator.

Tango does have an allocator that ONLY works for pure value types (types  
that have no pointers in them), and it is even faster than my custom  
allocator, but it requires you "know what you are doing."  I think with  
the power of D2 we should be able to come up with some template magic that  
disallows such an allocator from being used with the wrong types.

-Steve