digitalmars.D - Making RCSlice and DIP74 work with const and immutable
- Andrei Alexandrescu (20/20) Feb 28 2015 Tracing garbage collection can afford the luxury of e.g. mutating data
- Manu via Digitalmars-d (12/31) Feb 28 2015 Perhaps an operator that may be implemented to return a mutable
- Andrei Alexandrescu (4/14) Feb 28 2015 That's already abuse. No.
- Manu via Digitalmars-d (11/25) Feb 28 2015 However the user likes? It would just be a mutable pointer. For RC, it
- Andrei Alexandrescu (2/4) Feb 28 2015 That didn't get talked about in I don't remember. -- Andrei
- Manu via Digitalmars-d (6/11) Feb 28 2015 So, what's the solution?
- Atila Neves (9/23) Mar 01 2015 I've lost count now of how many times I've had to downgrade to
- Jakob Ovrum (7/16) Mar 01 2015 `match.captures` is a range; it's only natural for a range to
- Atila Neves (18/39) Mar 03 2015 I know why it doesn't work. I know the reasons that go into the
- H. S. Teoh via Digitalmars-d (34/48) Feb 28 2015 I ran into the same problem, and as a result I hardly ever make use of
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (2/60) Mar 01 2015 You still cannot access it through a const reference, though.
- H. S. Teoh via Digitalmars-d (6/20) Mar 01 2015 The whole point is to use Const!T instead of const(T).
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (3/28) Mar 01 2015 But that's intrusive! You can only apply it code you control, or
- H. S. Teoh via Digitalmars-d (9/31) Mar 01 2015 I don't see any other way of supporting logical const without violating
- ted (7/14) Feb 28 2015 It seems to me that (in the particular case of _this_ RC metadata - not
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (15/15) Mar 01 2015 The RC wrapper allocates _mutable_ memory for the reference count
- Jakob Ovrum (23/28) Mar 01 2015 I don't think const or immutable intrusive-reference-counted
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (6/29) Mar 01 2015 Argh! I didn't think about this. Any chance we can deprecate this
- ketmar (5/15) Mar 01 2015 but deprecating this is... illogical at best. immutable objects are=20
- "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> (8/33) Mar 01 2015 Don't know. It was more of a question than a recommendation. It
- Paolo Invernizzi (4/15) Mar 02 2015 No way! Neither for joke, please!
- Atila Neves (30/53) Mar 01 2015 I haven't put much thought into this, but here's an idea:
- Zach the Mystic (5/27) Mar 01 2015 I need to get educated on this issue. First suggestion: Just
- Zach the Mystic (3/15) Mar 01 2015 Well I guess it's about optimizing code. So the question is what
- Michel Fortin (11/34) Mar 01 2015 Store the metadata in a global hash table.
- "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= (5/11) Mar 02 2015 But there is no difference between having metadata as part of the
- Steven Schveighoffer (43/62) Mar 02 2015 So, the largest problem (already pointed out by many here), is that
- Steven Schveighoffer (4/11) Mar 02 2015 All this, except I meant the array runtime treats both const *and*
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
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)? AndreiPerhaps 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
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
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:However the user likes? It would just be a mutable pointer. For RC, it may just be an int*.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?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.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.
Feb 28 2015
On 2/28/15 6:33 PM, Manu via Digitalmars-d wrote:one of the biggest recurring complaints relating to the D type systemThat didn't get talked about in I don't remember. -- Andrei
Feb 28 2015
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: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'.one of the biggest recurring complaints relating to the D type systemThat didn't get talked about in I don't remember. -- Andrei
Feb 28 2015
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: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/ AtilaOn 2/28/15 6:33 PM, Manu via Digitalmars-d wrote: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'.one of the biggest recurring complaints relating to the D type systemThat didn't get talked about in I don't remember. -- Andrei
Mar 01 2015
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
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 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. AtilaI'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 03 2015
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: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.On 2/28/15 6:33 PM, Manu via Digitalmars-d wrote: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'.one of the biggest recurring complaints relating to the D type systemThat didn't get talked about in I don't remember. -- Andrei
Feb 28 2015
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:You still cannot access it through a const reference, though.On 1 March 2015 at 12:48, Andrei Alexandrescu via Digitalmars-d <digitalmars-d puremagic.com> wrote: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.On 2/28/15 6:33 PM, Manu via Digitalmars-d wrote: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'.one of the biggest recurring complaints relating to the D type systemThat didn't get talked about in I don't remember. -- Andrei
Mar 01 2015
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:[...]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.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
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:But that's intrusive! You can only apply it code you control, or at least you have to convince everyone to use it.On Sunday, 1 March 2015 at 06:42:02 UTC, H. S. Teoh wrote:[...]The whole point is to use Const!T instead of const(T).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
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: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' PerryOn Sun, Mar 01, 2015 at 01:43:44PM +0000, via Digitalmars-d wrote:But that's intrusive! You can only apply it code you control, or at least you have to convince everyone to use it.On Sunday, 1 March 2015 at 06:42:02 UTC, H. S. Teoh wrote:[...]The whole point is to use Const!T instead of const(T).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,You still cannot access it through a const reference, though.and to address some obvious roadblocks, like how to make MyClassimplicitly 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.
Mar 01 2015
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)? AndreiIt 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
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
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)? AndreiI 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
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: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.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)? AndreiI 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.Not if the RC wrapper allocated the memory in the first place. It knows that it can't be in ROM.
Mar 01 2015
On Sun, 01 Mar 2015 15:53:06 +0000, Marc Sch=C3=BCtz wrote: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?=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.
Mar 01 2015
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: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.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?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.
Mar 01 2015
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:No way! Neither for joke, please! --- /PHowever, 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.
Mar 02 2015
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
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
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:Well I guess it's about optimizing code. So the question is what the optimizer needs to know, and why.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.
Mar 01 2015
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
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
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
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