www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Making RCSlice and DIP74 work with const and immutable

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Tracing garbage collection can afford the luxury of e.g. mutating data 
that was immutable during its lifetime.

Reference counting needs to make minute mutations to data while 
references to that data are created. In fact, it's not mutation of the 
"useful" data, the payload of a data structure; it's mutation of 
metadata, additional information about the data (i.e. a reference count 
integral).

The RCOs described in DIP74 and also RCSlice discussed in this forum 
need to work properly with const and immutable. Therefore, they need a 
way to reliably define and access metadata for a data structure.

One possible solution is to add a " mutable" or " metadata" attribute 
similar to C++'s keyword "mutable". Walter and I both dislike that 
solution because it's hamfisted and leaves too much opportunity for 
abuse - people can essentially create unbounded amounts of mutable 
payload for an object claimed to be immutable. That makes it impossible 
(or unsafe) to optimize code based on algebraic assumptions.

We have a few candidates for solutions, but wanted to open with a good 
discussion first. So, how do you envision a way to define and access 
mutable metadata for objects (including immutable ones)?


Andrei
Feb 28 2015
next sibling parent reply Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 1 March 2015 at 11:40, Andrei Alexandrescu via Digitalmars-d
<digitalmars-d puremagic.com> wrote:

 Tracing garbage collection can afford the luxury of e.g. mutating data that
 was immutable during its lifetime.

 Reference counting needs to make minute mutations to data while references
 to that data are created. In fact, it's not mutation of the "useful" data,
 the payload of a data structure; it's mutation of metadata, additional
 information about the data (i.e. a reference count integral).

 The RCOs described in DIP74 and also RCSlice discussed in this forum need to
 work properly with const and immutable. Therefore, they need a way to
 reliably define and access metadata for a data structure.

 One possible solution is to add a " mutable" or " metadata" attribute
 similar to C++'s keyword "mutable". Walter and I both dislike that solution
 because it's hamfisted and leaves too much opportunity for abuse - people
 can essentially create unbounded amounts of mutable payload for an object
 claimed to be immutable. That makes it impossible (or unsafe) to optimize
 code based on algebraic assumptions.

 We have a few candidates for solutions, but wanted to open with a good
 discussion first. So, how do you envision a way to define and access mutable
 metadata for objects (including immutable ones)?


 Andrei


Perhaps an operator that may be implemented to return a mutable
metadata pointer for objects? From an algebraic point of view, it
should be defined that mutating metadata will have no effect on the
actual object.

Interestingly, I wonder if such an approach may also be used to
satisfy a common problem that people have with const objects, where
it's not possible to implement caching systems for repeated work
optimisation?
The result cache is another thing that may be stored in the object's
metadata...?
Feb 28 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/15 5:57 PM, Manu via Digitalmars-d wrote:

 Perhaps an operator that may be implemented to return a mutable
 metadata pointer for objects? From an algebraic point of view, it
 should be defined that mutating metadata will have no effect on the
 actual object.


But how would custom data be defined?


 Interestingly, I wonder if such an approach may also be used to
 satisfy a common problem that people have with const objects, where
 it's not possible to implement caching systems for repeated work
 optimisation?
 The result cache is another thing that may be stored in the object's
 metadata...?


That's already abuse. No.


Andrei
Feb 28 2015
parent reply Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 1 March 2015 at 12:22, Andrei Alexandrescu via Digitalmars-d
<digitalmars-d puremagic.com> wrote:

 On 2/28/15 5:57 PM, Manu via Digitalmars-d wrote:

 Perhaps an operator that may be implemented to return a mutable
 metadata pointer for objects? From an algebraic point of view, it
 should be defined that mutating metadata will have no effect on the
 actual object.



 But how would custom data be defined?


However the user likes? It would just be a mutable pointer. For RC, it
may just be an int*.



 Interestingly, I wonder if such an approach may also be used to
 satisfy a common problem that people have with const objects, where
 it's not possible to implement caching systems for repeated work
 optimisation?
 The result cache is another thing that may be stored in the object's
 metadata...?



 That's already abuse. No.


It's a very long-standing problem, one of the biggest recurring
complaints relating to the D type system, and the problem is of a very
similar nature; can't write to object because it's not mutable - but
we need this for RC, however may also be fine in caching cases because
cached results do not change the logical state of the object.
I see the same problem in both cases, and a good solution could
conceivably solve both problems.
Feb 28 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/15 6:33 PM, Manu via Digitalmars-d wrote:

 one of the biggest recurring
 complaints relating to the D type system


That didn't get talked about in I don't remember. -- Andrei
Feb 28 2015
next sibling parent reply Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 1 March 2015 at 12:48, Andrei Alexandrescu via Digitalmars-d
<digitalmars-d puremagic.com> wrote:

 On 2/28/15 6:33 PM, Manu via Digitalmars-d wrote:

 one of the biggest recurring
 complaints relating to the D type system



 That didn't get talked about in I don't remember. -- Andrei


So, what's the solution?
I've never complained about it, but I still have this problem
regularly. The solution in my experience is; 'everything is always
mutable'.
Feb 28 2015
parent reply "Atila Neves" <atila.neves gmail.com> writes:
On Sunday, 1 March 2015 at 02:53:34 UTC, Manu wrote:

 On 1 March 2015 at 12:48, Andrei Alexandrescu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 2/28/15 6:33 PM, Manu via Digitalmars-d wrote:

 one of the biggest recurring
 complaints relating to the D type system



 That didn't get talked about in I don't remember. -- Andrei


 So, what's the solution?
 I've never complained about it, but I still have this problem
 regularly. The solution in my experience is; 'everything is 
 always
 mutable'.


I've lost count now of how many times I've had to downgrade to 
auto despite always wanting immutable or const. This doesn't work:

  auto reg = regex(`(foo)`);
  const match = "foo".matchAll(reg);
  writeln(match.captures); //oops, captures isn't const

It should, but it doesn't. Maxime talked about it here as well:

http://pointersgonewild.com/2014/07/11/the-constness-problem/

Atila
Mar 01 2015
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Sunday, 1 March 2015 at 15:40:06 UTC, Atila Neves wrote:

 I've lost count now of how many times I've had to downgrade to 
 auto despite always wanting immutable or const. This doesn't 
 work:

  auto reg = regex(`(foo)`);
  const match = "foo".matchAll(reg);
  writeln(match.captures); //oops, captures isn't const

 It should, but it doesn't. Maxime talked about it here as well:

 http://pointersgonewild.com/2014/07/11/the-constness-problem/

 Atila


`match.captures` is a range; it's only natural for a range to 
have mutable state to be iterable.

D's const is a bridge between immutable and mutable. const has to 
be transitive because immutable is transitive. Don't use it as if 
it was C++ const: there's no logical const in D, and if there 
ever will be, it can't use the same `const` type qualifier.
Mar 01 2015
parent "Atila Neves" <atila.neves gmail.com> writes:
On Sunday, 1 March 2015 at 15:49:12 UTC, Jakob Ovrum wrote:

 On Sunday, 1 March 2015 at 15:40:06 UTC, Atila Neves wrote:

 I've lost count now of how many times I've had to downgrade to 
 auto despite always wanting immutable or const. This doesn't 
 work:

 auto reg = regex(`(foo)`);
 const match = "foo".matchAll(reg);
 writeln(match.captures); //oops, captures isn't const

 It should, but it doesn't. Maxime talked about it here as well:

 http://pointersgonewild.com/2014/07/11/the-constness-problem/

 Atila


 `match.captures` is a range; it's only natural for a range to 
 have mutable state to be iterable.

 D's const is a bridge between immutable and mutable. const has 
 to be transitive because immutable is transitive. Don't use it 
 as if it was C++ const: there's no logical const in D, and if 
 there ever will be, it can't use the same `const` type 
 qualifier.


I know why it doesn't work. I know the reasons that go into the 
design decision. const has to be the way it is or else 
thread-safety goes out of the window. I'm not talking about 
logical const; I'm talking about making as many things const and 
immutable as I can to reduce the number of things I have to keep 
in my mind at any given time.

const foo = getFoo(); //no need to reason about foo anymore, it 
won't change
auto bar = getBar(); //oh-oh, now the next 50 lines can do 
whatever they want with this

I shouldn't have to make captures const if all I want to do is 
inspect the 3rd value. And yet I do. That was just one example, 
like I said I've lost count of how many times I've changed const 
to auto in my code because it wouldn't compile otherwise. I don't 
go as far as Manu as use mutable everywhere, just where I have 
to. And I'm always annoyed when it's the case.

Atila
Mar 03 2015
prev sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sun, Mar 01, 2015 at 12:53:24PM +1000, Manu via Digitalmars-d wrote:

 On 1 March 2015 at 12:48, Andrei Alexandrescu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 2/28/15 6:33 PM, Manu via Digitalmars-d wrote:

 one of the biggest recurring
 complaints relating to the D type system



 That didn't get talked about in I don't remember. -- Andrei


 
 So, what's the solution?
 I've never complained about it, but I still have this problem
 regularly. The solution in my experience is; 'everything is always
 mutable'.


I ran into the same problem, and as a result I hardly ever make use of
D's const system.

One possible solution that occurred to me, though, is to introduce a
kind of "logical const" template that constructs a partially-const type,
with the "logical data" parts const/immutable/etc., but the "metadata"
parts mutable. User-defined attributes could be used for this purpose:

	struct Metadata {}

	class MyClass {
		int field; // regular data field
		 Metadata int fieldCache; // metadata
		...
	}

	template Const(T) {
		class Const {
			const {
				// insert stuff not marked with
				//  Metadata here
			}
			// insert stuff marked with  Metadata here
		}
	}

So then Const!MyClass is a modified version of MyClass where the data
fields are const (similarly, we can define Immutable for the analogous
purpose) but the fields marked as metadata will remain mutable.

Of course, this is just a crude first stab at the problem; I'm sure
there's plenty of room for refinement to make it more usable, and to
address some obvious roadblocks, like how to make MyClass implicitly
convertible to Const!MyClass, etc.. But it seems likely that D's
template machinery can actually express this in a way that does not
violate the guarantee of physical const.


T

-- 
Doubt is a self-fulfilling prophecy.
Feb 28 2015
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 1 March 2015 at 06:42:02 UTC, H. S. Teoh wrote:

 On Sun, Mar 01, 2015 at 12:53:24PM +1000, Manu via 
 Digitalmars-d wrote:

 On 1 March 2015 at 12:48, Andrei Alexandrescu via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 2/28/15 6:33 PM, Manu via Digitalmars-d wrote:

 one of the biggest recurring
 complaints relating to the D type system



 That didn't get talked about in I don't remember. -- Andrei


 
 So, what's the solution?
 I've never complained about it, but I still have this problem
 regularly. The solution in my experience is; 'everything is 
 always
 mutable'.


 I ran into the same problem, and as a result I hardly ever make 
 use of
 D's const system.

 One possible solution that occurred to me, though, is to 
 introduce a
 kind of "logical const" template that constructs a 
 partially-const type,
 with the "logical data" parts const/immutable/etc., but the 
 "metadata"
 parts mutable. User-defined attributes could be used for this 
 purpose:

 	struct Metadata {}

 	class MyClass {
 		int field; // regular data field
 		 Metadata int fieldCache; // metadata
 		...
 	}

 	template Const(T) {
 		class Const {
 			const {
 				// insert stuff not marked with
 				//  Metadata here
 			}
 			// insert stuff marked with  Metadata here
 		}
 	}

 So then Const!MyClass is a modified version of MyClass where 
 the data
 fields are const (similarly, we can define Immutable for the 
 analogous
 purpose) but the fields marked as metadata will remain mutable.

 Of course, this is just a crude first stab at the problem; I'm 
 sure
 there's plenty of room for refinement to make it more usable, 
 and to
 address some obvious roadblocks, like how to make MyClass 
 implicitly
 convertible to Const!MyClass, etc.. But it seems likely that D's
 template machinery can actually express this in a way that does 
 not
 violate the guarantee of physical const.


You still cannot access it through a const reference, though.
Mar 01 2015
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sun, Mar 01, 2015 at 01:43:44PM +0000, via Digitalmars-d wrote:

 On Sunday, 1 March 2015 at 06:42:02 UTC, H. S. Teoh wrote:


[...]

So then Const!MyClass is a modified version of MyClass where the data
fields are const (similarly, we can define Immutable for the
analogous purpose) but the fields marked as metadata will remain
mutable.

Of course, this is just a crude first stab at the problem; I'm sure
there's plenty of room for refinement to make it more usable, and to
address some obvious roadblocks, like how to make MyClass implicitly
convertible to Const!MyClass, etc.. But it seems likely that D's
template machinery can actually express this in a way that does not
violate the guarantee of physical const.


 
 You still cannot access it through a const reference, though.


The whole point is to use Const!T instead of const(T).


T

-- 
Be in denial for long enough, and one day you'll deny yourself of things you
wish you hadn't.
Mar 01 2015
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 1 March 2015 at 15:08:47 UTC, H. S. Teoh wrote:

 On Sun, Mar 01, 2015 at 01:43:44PM +0000, via Digitalmars-d 
 wrote:

 On Sunday, 1 March 2015 at 06:42:02 UTC, H. S. Teoh wrote:


 [...]

So then Const!MyClass is a modified version of MyClass where 
the data
fields are const (similarly, we can define Immutable for the
analogous purpose) but the fields marked as metadata will 
remain
mutable.

Of course, this is just a crude first stab at the problem; 
I'm sure
there's plenty of room for refinement to make it more usable, 
and to
address some obvious roadblocks, like how to make MyClass 
implicitly
convertible to Const!MyClass, etc.. But it seems likely that 
D's
template machinery can actually express this in a way that 
does not
violate the guarantee of physical const.


 
 You still cannot access it through a const reference, though.


 The whole point is to use Const!T instead of const(T).


But that's intrusive! You can only apply it code you control, or 
at least you have to convince everyone to use it.
Mar 01 2015
parent "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sun, Mar 01, 2015 at 03:47:36PM +0000, via Digitalmars-d wrote:

 On Sunday, 1 March 2015 at 15:08:47 UTC, H. S. Teoh wrote:

On Sun, Mar 01, 2015 at 01:43:44PM +0000, via Digitalmars-d wrote:

On Sunday, 1 March 2015 at 06:42:02 UTC, H. S. Teoh wrote:


[...]

So then Const!MyClass is a modified version of MyClass where >the
data fields are const (similarly, we can define Immutable for the
analogous purpose) but the fields marked as metadata will >remain
mutable.

Of course, this is just a crude first stab at the problem; >I'm
sure there's plenty of room for refinement to make it more usable,

and to address some obvious roadblocks, like how to make MyClass

implicitly convertible to Const!MyClass, etc.. But it seems
likely that >D's template machinery can actually express this in
a way that >does not violate the guarantee of physical const.






You still cannot access it through a const reference, though.


The whole point is to use Const!T instead of const(T).


 
 But that's intrusive! You can only apply it code you control, or at
 least you have to convince everyone to use it.


I don't see any other way of supporting logical const without violating
physical const in some way. As soon as const(T) means anything other
than const(T), you open up a hole in the type system and the const
guarantee becomes no longer a guarantee, but a mere advisory like C++
const.


T

-- 
Let's not fight disease by killing the patient. -- Sean 'Shaleh' Perry
Mar 01 2015
prev sibling next sibling parent ted <foo bar.com> writes:
Andrei Alexandrescu wrote:


 
 We have a few candidates for solutions, but wanted to open with a good
 discussion first. So, how do you envision a way to define and access
 mutable metadata for objects (including immutable ones)?
 
 
 Andrei


It seems to me that (in the particular case of _this_ RC metadata - not 
attempting to cover any more general case (beyond my ken)), the compiler 
could internally mark class members that are modified inside the 
opAddRef/opRelease methods as mutable. This would not require any special 
source code markups.
--ted
Feb 28 2015
prev sibling next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
The RC wrapper allocates _mutable_ memory for the reference count 
on the heap (it has to do that anyway, because it needs to be 
shared by all instances). As far as I understand, mutating a 
mutable variable is safe if all users of that variable are aware 
that it's mutable, _even if it's only reachable through a const 
pointer_.

This condition is easy to enforce in an RC wrapper, it just has 
to keep the pointer to the refcount private. To make it easier to 
prove safety, the pointer needs to be declared as const; all 
refcount manipulation needs to happen through two small 
(inlinable) helper methods that do the appropriate cast() magic. 
The refcount can also be stored next to the payload (better for 
cache locality anyway), in which case we don't even need to store 
a const pointer at all, which also means that nobody can 
accidentally access it in the wrong way.
Mar 01 2015
prev sibling next sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Sunday, 1 March 2015 at 01:40:40 UTC, Andrei Alexandrescu 
wrote:

 We have a few candidates for solutions, but wanted to open with 
 a good discussion first. So, how do you envision a way to 
 define and access mutable metadata for objects (including 
 immutable ones)?


 Andrei


I don't think const or immutable intrusive-reference-counted 
classes is a feasible idea.

I understand the motivation: we want to dynamically allocate a 
class instance, initialize it and never mutate it again, and pass 
it around freely; *without* using tracing GC. Having it typed as 
immutable helps code readability and whatnot.

However, AFAICS, it comes with a serious problem. Immutable 
objects are freely passable between threads, so surely an 
immutable RC object would need atomic counting just like a shared 
RC object, but unlike shared, immutable does not necessarily 
express the intent of sharing between threads; the immutable RC 
object could easily be counting atomically for nothing.

There might be other problems, such as problems regarding ROM.

This is not a problem with reference-counting as a whole but with 
intrusive reference-counting. With RefCounted, 
immutable(RefCounted!T) makes no sense, but RefCounted!(immutable 
T) does. It's also neatly composable; 
shared(RefCounted!(immutable T)) makes sense too.

I wish we had external, composable reference-counting for class 
instances. I know why that's problematic, so sorry for posting 
without any suggestion on how to proceed...
Mar 01 2015
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 1 March 2015 at 15:28:56 UTC, Jakob Ovrum wrote:

 On Sunday, 1 March 2015 at 01:40:40 UTC, Andrei Alexandrescu 
 wrote:

 We have a few candidates for solutions, but wanted to open 
 with a good discussion first. So, how do you envision a way to 
 define and access mutable metadata for objects (including 
 immutable ones)?


 Andrei


 I don't think const or immutable intrusive-reference-counted 
 classes is a feasible idea.

 I understand the motivation: we want to dynamically allocate a 
 class instance, initialize it and never mutate it again, and 
 pass it around freely; *without* using tracing GC. Having it 
 typed as immutable helps code readability and whatnot.

 However, AFAICS, it comes with a serious problem. Immutable 
 objects are freely passable between threads, so surely an 
 immutable RC object would need atomic counting just like a 
 shared RC object, but unlike shared, immutable does not 
 necessarily express the intent of sharing between threads; the 
 immutable RC object could easily be counting atomically for 
 nothing.


Argh! I didn't think about this. Any chance we can deprecate this 
behaviour? It's also an obstacle for the implementation of 
thread-local heaps.


 There might be other problems, such as problems regarding ROM.


Not if the RC wrapper allocated the memory in the first place. It 
knows that it can't be in ROM.
Mar 01 2015
next sibling parent reply ketmar <ketmar ketmar.no-ip.org> writes:
On Sun, 01 Mar 2015 15:53:06 +0000, Marc Sch=C3=BCtz wrote:


 However, AFAICS, it comes with a serious problem. Immutable objects are
 freely passable between threads, so surely an immutable RC object would
 need atomic counting just like a shared RC object, but unlike shared,
 immutable does not necessarily express the intent of sharing between
 threads; the immutable RC object could easily be counting atomically
 for nothing.


=20
 Argh! I didn't think about this. Any chance we can deprecate this
 behaviour? It's also an obstacle for the implementation of thread-local
 heaps.


but deprecating this is... illogical at best. immutable objects are=20
immutable, so why can't i pass 'em to any thread? do you mean that i=20
can't use `immutable string =3D "mystr";` in different threads without=20
copying anymore?=
Mar 01 2015
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 1 March 2015 at 17:03:46 UTC, ketmar wrote:

 On Sun, 01 Mar 2015 15:53:06 +0000, Marc Schütz wrote:


 However, AFAICS, it comes with a serious problem. Immutable 
 objects are
 freely passable between threads, so surely an immutable RC 
 object would
 need atomic counting just like a shared RC object, but unlike 
 shared,
 immutable does not necessarily express the intent of sharing 
 between
 threads; the immutable RC object could easily be counting 
 atomically
 for nothing.


 
 Argh! I didn't think about this. Any chance we can deprecate 
 this
 behaviour? It's also an obstacle for the implementation of 
 thread-local
 heaps.


 but deprecating this is... illogical at best. immutable objects 
 are
 immutable, so why can't i pass 'em to any thread? do you mean 
 that i
 can't use `immutable string = "mystr";` in different threads 
 without
 copying anymore?


Don't know. It was more of a question than a recommendation. It 
might be impractical.

OTOH, I don't think it's illogical, because thread-locality and 
immutability are independent concepts. There can be shared 
mutable data (`shared`)  as well as thread-local immutable data. 
Hmm... that would be equivalent to `const`, no? But that's 
getting off-topic.
Mar 01 2015
prev sibling parent "Paolo Invernizzi" <paolo.invernizzi no.address> writes:
On Sunday, 1 March 2015 at 15:53:07 UTC, Marc Schütz wrote:

 On Sunday, 1 March 2015 at 15:28:56 UTC, Jakob Ovrum wrote:

 However, AFAICS, it comes with a serious problem. Immutable 
 objects are freely passable between threads, so surely an 
 immutable RC object would need atomic counting just like a 
 shared RC object, but unlike shared, immutable does not 
 necessarily express the intent of sharing between threads; the 
 immutable RC object could easily be counting atomically for 
 nothing.


 Argh! I didn't think about this. Any chance we can deprecate 
 this behaviour? It's also an obstacle for the implementation of 
 thread-local heaps.


No way! Neither for joke, please!

---
/P
Mar 02 2015
prev sibling next sibling parent "Atila Neves" <atila.neves gmail.com> writes:
I haven't put much thought into this, but here's an idea:

struct MetadataWrapper(T, M) {
     immutable T payload; //or const via static if?
     M _metadata;
     alias payload this;
     ref M metadata() { return _metadata;}
}

auto withMetadata(T, Ts...)(Ts args) {
     return MetadataWrapper!(T, int)(cast(immutable)(new T(args)), 
0);
}

It's short and stupid but works:

void main() {
     import std.stdio;

     static class MyClass {
         this(string s) {
             this.s = s;
         }
         string s;
         string stuff() const pure nothrow  safe { return s ~ " 
and stuff";}
     }

     auto foo = withMetadata!MyClass("a string");
     writeln("calling stuff on foo: ", foo.stuff());
     writeln("foo's metadata is ", foo.metadata);
     foo.metadata++;
     writeln("foo's metadata is ", foo.metadata);
}



On Sunday, 1 March 2015 at 01:40:40 UTC, Andrei Alexandrescu 
wrote:

 Tracing garbage collection can afford the luxury of e.g. 
 mutating data that was immutable during its lifetime.

 Reference counting needs to make minute mutations to data while 
 references to that data are created. In fact, it's not mutation 
 of the "useful" data, the payload of a data structure; it's 
 mutation of metadata, additional information about the data 
 (i.e. a reference count integral).

 The RCOs described in DIP74 and also RCSlice discussed in this 
 forum need to work properly with const and immutable. 
 Therefore, they need a way to reliably define and access 
 metadata for a data structure.

 One possible solution is to add a " mutable" or " metadata" 
 attribute similar to C++'s keyword "mutable". Walter and I both 
 dislike that solution because it's hamfisted and leaves too 
 much opportunity for abuse - people can essentially create 
 unbounded amounts of mutable payload for an object claimed to 
 be immutable. That makes it impossible (or unsafe) to optimize 
 code based on algebraic assumptions.

 We have a few candidates for solutions, but wanted to open with 
 a good discussion first. So, how do you envision a way to 
 define and access mutable metadata for objects (including 
 immutable ones)?


 Andrei
Mar 01 2015
prev sibling next sibling parent reply "Zach the Mystic" <reachzach gggmail.com> writes:
On Sunday, 1 March 2015 at 01:40:40 UTC, Andrei Alexandrescu 
wrote:

 Tracing garbage collection can afford the luxury of e.g. 
 mutating data that was immutable during its lifetime.

 Reference counting needs to make minute mutations to data while 
 references to that data are created. In fact, it's not mutation 
 of the "useful" data, the payload of a data structure; it's 
 mutation of metadata, additional information about the data 
 (i.e. a reference count integral).

 The RCOs described in DIP74 and also RCSlice discussed in this 
 forum need to work properly with const and immutable. 
 Therefore, they need a way to reliably define and access 
 metadata for a data structure.

 One possible solution is to add a " mutable" or " metadata" 
 attribute similar to C++'s keyword "mutable". Walter and I both 
 dislike that solution because it's hamfisted and leaves too 
 much opportunity for abuse - people can essentially create 
 unbounded amounts of mutable payload for an object claimed to 
 be immutable. That makes it impossible (or unsafe) to optimize 
 code based on algebraic assumptions.

 We have a few candidates for solutions, but wanted to open with 
 a good discussion first. So, how do you envision a way to 
 define and access mutable metadata for objects (including 
 immutable ones)?


I need to get educated on this issue. First suggestion: Just 
break the type system by encouraging the idiom of using casts in 
opAddRef and opRelease. It's too easy, but I don't know why.
Mar 01 2015
parent "Zach the Mystic" <reachzach gggmail.com> writes:
On Sunday, 1 March 2015 at 16:45:04 UTC, Zach the Mystic wrote:

 On Sunday, 1 March 2015 at 01:40:40 UTC, Andrei Alexandrescu 
 wrote:

 One possible solution is to add a " mutable" or " metadata" 
 attribute similar to C++'s keyword "mutable". Walter and I 
 both dislike that solution because it's hamfisted and leaves 
 too much opportunity for abuse - people can essentially create 
 unbounded amounts of mutable payload for an object claimed to 
 be immutable. That makes it impossible (or unsafe) to optimize 
 code based on algebraic assumptions.


 I need to get educated on this issue. First suggestion: Just 
 break the type system by encouraging the idiom of using casts 
 in opAddRef and opRelease. It's too easy, but I don't know why.


Well I guess it's about optimizing code. So the question is what 
the optimizer needs to know, and why.
Mar 01 2015
prev sibling next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2015-03-01 01:40:42 +0000, Andrei Alexandrescu said:


 Tracing garbage collection can afford the luxury of e.g. mutating data 
 that was immutable during its lifetime.
 
 Reference counting needs to make minute mutations to data while 
 references to that data are created. In fact, it's not mutation of the 
 "useful" data, the payload of a data structure; it's mutation of 
 metadata, additional information about the data (i.e. a reference count 
 integral).
 
 The RCOs described in DIP74 and also RCSlice discussed in this forum 
 need to work properly with const and immutable. Therefore, they need a 
 way to reliably define and access metadata for a data structure.
 
 One possible solution is to add a " mutable" or " metadata" attribute 
 similar to C++'s keyword "mutable". Walter and I both dislike that 
 solution because it's hamfisted and leaves too much opportunity for 
 abuse - people can essentially create unbounded amounts of mutable 
 payload for an object claimed to be immutable. That makes it impossible 
 (or unsafe) to optimize code based on algebraic assumptions.
 
 We have a few candidates for solutions, but wanted to open with a good 
 discussion first. So, how do you envision a way to define and access 
 mutable metadata for objects (including immutable ones)?


Store the metadata in a global hash table.

There's a problem with reference counting immutable objects: they are 
implicitly shared. Any metadata attached to them thus needs to be 
shared. Accessing the metadata through a global shared hash table isn't 
going to be that much of a performance hit compared to whatever 
mechanism is used to synchronize access to that data.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Mar 01 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Sunday, 1 March 2015 at 20:39:54 UTC, Michel Fortin wrote:

 There's a problem with reference counting immutable objects: 
 they are implicitly shared. Any metadata attached to them thus 
 needs to be shared. Accessing the metadata through a global 
 shared hash table isn't going to be that much of a performance 
 hit compared to whatever mechanism is used to synchronize 
 access to that data.


But there is no difference between having metadata as part of the 
object and using a hash table as long as the mutable and 
immutable data sits on separate cache lines. (The object address 
is basically a hash key, and memory is a big table).
Mar 02 2015
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 2/28/15 8:40 PM, Andrei Alexandrescu wrote:

 Tracing garbage collection can afford the luxury of e.g. mutating data
 that was immutable during its lifetime.

 Reference counting needs to make minute mutations to data while
 references to that data are created. In fact, it's not mutation of the
 "useful" data, the payload of a data structure; it's mutation of
 metadata, additional information about the data (i.e. a reference count
 integral).

 The RCOs described in DIP74 and also RCSlice discussed in this forum
 need to work properly with const and immutable. Therefore, they need a
 way to reliably define and access metadata for a data structure.

 One possible solution is to add a " mutable" or " metadata" attribute
 similar to C++'s keyword "mutable". Walter and I both dislike that
 solution because it's hamfisted and leaves too much opportunity for
 abuse - people can essentially create unbounded amounts of mutable
 payload for an object claimed to be immutable. That makes it impossible
 (or unsafe) to optimize code based on algebraic assumptions.

 We have a few candidates for solutions, but wanted to open with a good
 discussion first. So, how do you envision a way to define and access
 mutable metadata for objects (including immutable ones)?


So, the largest problem (already pointed out by many here), is that 
immutable is implicitly shared.

This means const must be treated as implicitly shared.

But I have an idea, not sure if it's viable or not, to try and mitigate 
this. What if, at the point of passing in a mutable or immutable item to 
a const function, opAddRef is called. Then when the function call 
returns, opRelease is called. Then during the function, you never have 
to worry about const ref counting, and you never have to worry about 
trying to atomically ref count mutable items.

This means opAddRef() const and opRelease() const would be illegal.

Of course, for shared and immutable items, you will need to deal with an 
atomic/shared count. I haven't figured out that problem yet, but I think 
Michel Fortin has some good ideas.

This leaves the only issue of creating "const" RC objects. We can just 
ban that (no sense in doing that, just create an immutable version). 
const then effectively becomes a borrowing type constructor.

Just as an aside, I know that immutable is implicitly shared because it 
does not need to be synchronized with a mutex. This makes it ideal for 
sharing. But the reality is, there are other reasons to make something 
immutable. And it poisons const in this way. Note that the array runtime 
still treats const items as thread local, not shared. This could 
potentially cause problems if you shared a tail-immutable array, and 
tried appending.

I would love to see immutable be by default thread local, and need to 
cast into shared(immutable) to be shareable. shared(immutable) is still 
pretty easy to use, since it would require no synchronization (except in 
these exceptional ways we are talking about).

One very important thing to consider here, is the optimization of pure 
functions. An immutable pointer passed into a pure function means the 
compiler can elide identical calls. This means opAddRef() immutable 
CANNOT be pure, or at least it cannot be strong pure. This really hints 
towards some sort of global hash.

But there may be a better way: What if the compiler marked a region of 
the data inside the object as "meta", and then when you called 
opAddRef() immutable, it's really calling opAddRef(Meta m) immutable. 
The way this works is:

1. The meta data is NOT EXTRACTABLE from the object any other way.
2. The meta data is ALWAYS mutable and (effectively) shared.

Essentially, this is how synchronized works too. And you can logically 
place the metadata somewhere outside the object if that makes more sense.

Just thinking out loud here...

-Steve
Mar 02 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 3/2/15 4:10 PM, Steven Schveighoffer wrote:


 Just as an aside, I know that immutable is implicitly shared because it
 does not need to be synchronized with a mutex. This makes it ideal for
 sharing. But the reality is, there are other reasons to make something
 immutable. And it poisons const in this way. Note that the array runtime
 still treats const items as thread local, not shared. This could
 potentially cause problems if you shared a tail-immutable array, and
 tried appending.


All this, except I meant the array runtime treats both const *and* 
immutable items as thread-local.

-Steve
Mar 02 2015