std.container and classes

foobar foo at bar.com
Tue Dec 20 15:26:03 PST 2011


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.



More information about the Digitalmars-d mailing list