Does D have "structural sharing" of immutable collections?

[bearophile]

Andrei Alexandrescu:

> Yah, FP doesn't like arrays and immutable containers 
> essentially eschew arrays altogether.

In the Chapel/X10 worlds I have read about various strategies to 
use mutable arrays too in parallel/concurrent situations. 
Probably some of those ideas will be quite useful in D too.


> (The most surprising thing to me is that the FP community
> generally fails to acknowledge that as a problem.)

Again and again I have seen how modern CPUs like linear scans on 
(small) arrays of values. Sometimes the performance is 
surprising, and beats almost everything else, including binary 
searches on the same small array.

This sometimes means that using a single core on such mutable 
arrays from C/C++/D leads to faster code (and far less 
electricity consumed) than using 4-8 cores on less optimal data 
structures (like structures with many pointers).

This is also why your idea of "small string optimization" was 
probably leading to significantly higher performance, and why I 
think the built-in D AAs will need a "small associative array" 
optimization (that even Python dicts have, for a number of items 
less than 9), BigInts will need a small value (no heap) 
optimization, and so on for other Phobos data structures 
(including lists!). Often such optimizations means just storing 
the few values in a small array instead of a fancier data 
structure (like a list), so adding such optimizations is usually 
not hard.

Bye,
bearophile