On Saturday, 17 December 2011 at 23:31:47 UTC, Andrei
Alexandrescu wrote:
On 12/13/11 9:08 PM, Jonathan M Davis wrote:
Is the plan for std.container still to have all of its
containers be final
classes (classes so that they're reference types and final so
that their
functions are inlinable)? Or has that changed? I believe that
Andrei said
something recently about discussing reference counting and
containers with
Walter.
The reason that I bring this up is that Array and SList are
still structs, and
the longer that they're structs, the more code that will break
when they get
changed to classes. Granted, some level of code breakage may
occur when we add
custom allocators to them, but since that would probably only
affect the
constructor (and preferably wouldn't affect anything if you
want to simply
create a container with the GC heap as you would now were
Array and SList
classes), the breakage for that should be minimal.
Is there any reason for me to not just go and make Array and
SList final
classes and create a pull request for it?
- Jonathan M Davis
Apologies for being slow on this. It may be a fateful time to
discuss that right now, after all the discussion of what's
appropriate for stdlib vs. application code etc.
As some of you know, Walter and I went back and forth several
times on this. First, there was the issue of making containers
value types vs. reference types. Making containers value types
would be in keep with the STL approach. However, Walter noted
that copying entire containers by default is most often NOT
desirable and there's significant care and adornments in C++
programs to make sure that that default behavior is avoided
(e.g. adding const& to function parameters).
So we decided to make containers reference types, and that
seemed to be a good choice.
The second decision is classes vs. structs. Walter correctly
pointed out that the obvious choice for defining a reference
type in D - whether the type is momonorphic or polymorphic - is
making it a class. If containers aren't classes, the reasoning
went, it means we took a wrong step somewhere; it might mean
our flagship abstraction for reference types is not suitable
for, well, defining a reference type.
Fast forward a couple of months, a few unslept nights, and a
bunch of newsgroup and IRC conversations. Several additional
pieces came together.
The most important thing I noticed is that people expect
standard containers to have sophisticated memory management.
Many ask not about containers as much as "containers with
custom allocators". Second, containers tend to be large memory
users by definition. Third, containers are self-contained (heh)
and relatively simple in terms of what they model, meaning that
they _never_ suffer from circular references, like general
entity types might.
All of these arguments very strongly suggest that many want
containers to be types with deterministic control over memory
and accept configurable allocation strategies (regions, heap,
malloc, custom). So that would mean containers should be
reference counted structs.
This cycle of thought has happened twice, and the evidence
coming the second time has been stronger. The first time around
I went about and started implementing std.container with
reference counting in mind. The code is not easy to write, and
is not to be recommended for most types, hence my thinking (at
the end of the first cycle) that we should switch to class
containers. One fear I have is that people would be curious,
look at the implementation of std.container, and be like "so am
I expected to do all this to define a robust type"? I start to
think that the right answer to that is to improve library
support for good reference counted types, and define reference
counted struct containers that are deterministic.
Safety is also an issue. I was hoping I'd provide safety as a
policy, e.g. one may choose for a given container whether they
want safe or not (and presumably fast). I think it's best to
postpone that policy and focus for now on defining safe
containers with safe ranges. This precludes e.g. using T[] as a
range for Array!T.
Please discuss.
Andrei
My thoughts are:
- value vs. reference: definitely reference hence classes
- reference type - BAD idea. it adds code bloat, code complexity
and hurts performance, not to mention it conflicts with
concurrency which is the way of the future. - allocators -
EXCELLENT idea. As discussed previously the design must not be
the c++ one. - In addition to the general purpose ref. containers
we should provide a few special value type containers such as
small arrays with primitive types, a FlagSet with 1 bit per flag,
etc.
- safety - definitely safe by default and this is wat we should
concentrate ATM. unsafe could be added later.
ref-counted seems redundant to me if we provide allocators. There
should be an RC_alloc for this.
