www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - optimized immutable containers

reply "finalpatch" <fengli gmail.com> writes:
Is anyone aware of the new immutable containers in .Net framework?
http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx.

While we can attach the immutable qualifier to any D containers, 
they will not perform nearly as well because they are essentially 
mutable structures. Making them immutable doesn't change the way 
they work, it merely forbids us to call the modifying methods. 
Every time we need to modify them we have to copy the entire 
thing which is not very efficient.

The .Net immutable containers are specially optimized so that 
they share the underlying data as much as possible. Creating a 
modified copy is cheap, usually O(1) or O(logN).

I think having something similar in D would make immutables much 
more attractive.
Jul 02 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
finalpatch:


 I think having something similar in D would make immutables 
 much more attractive.


I think that eventually we'll have some good immutable data 
structure in Phobos (based on finger trees, etc). But first 
probably there's a need for some mutable ones :-)

Bye,
bearophile
Jul 02 2013
prev sibling parent reply "w0rp" <devw0rp gmail.com> writes:
I suppose you could implement an efficiently copied immutable 
singly linked list like this very easily. I think that's a basic 
functional programming idea, new list with head + list. Making 
the nodes garbage collected would save on memory usage.
Jul 03 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 3 July 2013 at 07:22:00 UTC, w0rp wrote:

 I suppose you could implement an efficiently copied immutable 
 singly linked list like this very easily. I think that's a 
 basic functional programming idea, new list with head + list. 
 Making the nodes garbage collected would save on memory usage.


The irony here (as stated by Bearophile) is that this is 
currently how our SList and DList are actually implemented: Not 
value nor ref semantics: Just shared owner ship of nodes...

EG:
--------
import std.stdio, std.container;

void main()
{
     alias SLI = SList!int;
     auto a = SLI(1);
     auto b = a;
     auto c = a;
     b.insertFront(0);
     c.insertFront(2);

     writeln("a[]: ", a[]);
     writeln("b[]: ", b[]);
     writeln("c[]: ", c[]);
}
--------
a[]: [1]
b[]: [0, 1]
c[]: [2, 1]
--------

-_-
Jul 03 2013
parent reply "w0rp" <devw0rp gmail.com> writes:
On Wednesday, 3 July 2013 at 08:04:50 UTC, monarch_dodra wrote:

 The irony here (as stated by Bearophile) is that this is 
 currently how our SList and DList are actually implemented: Not 
 value nor ref semantics: Just shared owner ship of nodes...


Well, that was easy! I did not know that this is exactly how 
SList and DList are implemented, as I haven't had to use them 
yet, but that will come in handy eventualy. The operations on the 
types could use more qualifiers, though. Using them in pure 
functions would make it possible to implicitly convert them to 
immutable, which is a powerful thing indeed.
Jul 03 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 3 July 2013 at 22:03:14 UTC, w0rp wrote:

 On Wednesday, 3 July 2013 at 08:04:50 UTC, monarch_dodra wrote:

 The irony here (as stated by Bearophile) is that this is 
 currently how our SList and DList are actually implemented: 
 Not value nor ref semantics: Just shared owner ship of nodes...


 Well, that was easy! I did not know that this is exactly how 
 SList and DList are implemented, as I haven't had to use them 
 yet, but that will come in handy eventualy.


Just to be clear, I didn't say it before: That behavior is a bug, 
and is currently undergoing correction. Please don't relly on it.


 The operations on the types could use more qualifiers, though. 
 Using them in pure functions would make it possible to 
 implicitly convert them to immutable, which is a powerful thing 
 indeed.


Keep in mind that in D, const is "turtles all the way down", so 
it is no possible to have an "immutable container of mutable 
items". Once you give something the "const" handle, it is very 
hard to strip it.
Jul 03 2013
parent reply "w0rp" <devw0rp gmail.com> writes:
On Thursday, 4 July 2013 at 05:45:41 UTC, monarch_dodra wrote:

 Just to be clear, I didn't say it before: That behavior is a 
 bug, and is currently undergoing correction. Please don't relly 
 on it.


I see. Well, a garbage collected linked list is very easy to 
implement, so I suppose it's easy for you to get these semantics 
if you want them.


 The operations on the types could use more qualifiers, though. 
 Using them in pure functions would make it possible to 
 implicitly convert them to immutable, which is a powerful 
 thing indeed.


 Keep in mind that in D, const is "turtles all the way down", so 
 it is not possible to have an "immutable container of mutable 
 items". Once you give something the "const" handle, it is very 
 hard to strip it.


I am aware of how const and immutable work, and that's what I 
want. It's just nice that with a pure qualifier, you can 
sometimes build immutable data from functions returning mutable 
data without creating any copies.
Jul 03 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 4 July 2013 at 06:36:52 UTC, w0rp wrote:

 On Thursday, 4 July 2013 at 05:45:41 UTC, monarch_dodra wrote:

 Just to be clear, I didn't say it before: That behavior is a 
 bug, and is currently undergoing correction. Please don't 
 relly on it.


 I see. Well, a garbage collected linked list is very easy to 
 implement, so I suppose it's easy for you to get these 
 semantics if you want them.


For a Doubly linked list, the semantics and implementation are 
actually kind of hard to get right. What you basically have is a 
"chain" of nodes, and each list simply references a part of that 
chain. It is not, however, possible to "fork" that chain.

For Singly Linked list, the semantics and implementation are 
actually easier: The data structure is more like a "mountain 
river", where every chain is a creek that converges to the same 
river.


 The operations on the types could use more qualifiers, 
 though. Using them in pure functions would make it possible 
 to implicitly convert them to immutable, which is a powerful 
 thing indeed.


 Keep in mind that in D, const is "turtles all the way down", 
 so it is not possible to have an "immutable container of 
 mutable items". Once you give something the "const" handle, it 
 is very hard to strip it.


 I am aware of how const and immutable work, and that's what I 
 want. It's just nice that with a pure qualifier, you can 
 sometimes build immutable data from functions returning mutable 
 data without creating any copies.


Well, I was thinking maybe something maybe even better? An 
immutable shared container that contains shared mutable objects 
would be more helpful. Implemented as a *shared* class with no 
functions that pdrovide actual mutation. The container itself 
would provide lock-free access to all its elements, and then each 
element would individually manage concurrency.

Such a container could also provide shallow copy (eg: elements 
are not copied). The interface would need more work, but I think 
this is an example of what D could provide that is better than 
what other languages ca do.
Jul 04 2013