On Sat, 14 Nov 2009 22:08:23 -0500, Andrei Alexandrescu
<[email protected]> 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
