std.container.RedBlackTree versus C++ std::set

[Jonathan M Davis]

On Friday, February 15, 2013 19:14:21 Dan wrote:
> When you say things like "Andrei was considering phasing out
> postblits..." I get nervous. Can we please have some comments
> from Andrei/Walter about what the plans are? I'm not asking for
> the ultimate solution - just to know the general direction and
> where this issue stands at present. Is there anything any of us
> can do to help move this forward?

Yeah, they're unlikely to say much until something has actually been decided. 
Frequently, if you try and pin them down on stuff like that, you won't get an 
answer, especially if you ask out of the blue. But regardless, I wouldn't 
expect postblits to be gotten rid of (because that would break code). Rather, 
they would be discouraged, and newer code would be written to use copy 
constructors instead. But nothing has been decided for certain AFAIK.

> Regarding replacing expensive postblits with copy constructors -
> how does that help? The expense will remain the same - if you
> need a transitive copy, you need a transitive copy.

The problem has nothing to do with const. The problem const and immutable. 
It's impossible to write a const or immutable postblit constructor, because 
postblit operates by doing the copy and then allowing you to change it, 
whereas const and immutable cannot be changed. You need to construct the copy 
as const or immutable, which means you need to make the changes when you make 
the copy, which basically means that you need a copy constructor.

Efficiency comes in when arguing whether a postblit or copy constructor is 
appropriate in the first place or whether they can be implemented efficiently. 
Walter seems to be of the opinion that they should only be used in cases where 
they're actually efficient (i.e. you never use them for deep copying, only for 
handling stuff like ref-counting). He's much more in favor of COW. But much as 
he thinks that way, I don't think that there's any real risk of that being 
codified in the language at this point. Not only would it be very difficult to 
restrict postblit like that (if not impossible), but it would break tons of 
code (which Walter is very much against), and most everyone would scream (and 
several already did when he brought it up).

Andrei likes the idea of basically requiring that ranges have O(1) 
postblits/copy constructors so that algorithms can assume that copying is 
cheap, but he's never decided that we're going that way for certain, and even 
if we did, it would just mean that we wouldn't write code which cared about 
the expense of copying ranges, and anyone who wrote ranges that were expensive 
to copy would take a performance hit. Honestly, I suspect that that's mostly 
where we are already. And given how ranges work, an expensive postblit doesn't 
really make sense anyway.

No, I think that the only real concern here is if/when we'll get copy 
constructors so that we can copy const or immutable structs that require 
postblits or copy constructors. Walter and Andrei are very concerned about 
achieving and maintaining stability of the language and library, so any major 
breaking changes (especially to the language) would need to have very good 
reasons and would likely be discussed in detail in the newsgroup first. So, 
while I think that some of what they've said would be of some concern if D 
were still being designed (as opposed to being stabilized), given where we 
are, it's unlikely to be a concern.

- Jonathan M Davis