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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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