Re: A few thoughts on std.allocator
On Sunday, 10 May 2015 at 09:50:00 UTC, Andrei Alexandrescu wrote: (file:///Users/aalexandre/code/d/dlang.org/web/phobos-prerelease/std_experimental_allocator_free_tree.html) bad link
Re: A few thoughts on std.allocator
On 2015-05-10 09:50:00 +, Andrei Alexandrescu said: 3. Thread-local vs. shared objects Currently in D it's legal to allocate memory in one thread and deallocate it in another. (One simple way to look at it is casting to shared.) This has a large performance cost that only benefits very few actual cases. It follows that we need to change the notion that you first allocate memory and then brand it as shared. The "will be shared" knowledge must be present during allocation, and use different methods of allocation for the two cases. Shared is implicit in the case of immutable. Think carefully: if you implement this and it has any efficiency benefit for non-shared allocations, const-allocated objects and arrays will become more performant than immutable-allocated ones. People will thus have an incentive to stay away from immutable. -- Michel Fortin michel.for...@michelf.ca http://michelf.ca
Re: A few thoughts on std.allocator
On Sunday, 10 May 2015 at 10:51:54 UTC, Michel Fortin wrote: On 2015-05-10 09:50:00 +, Andrei Alexandrescu said: 3. Thread-local vs. shared objects Currently in D it's legal to allocate memory in one thread and deallocate it in another. (One simple way to look at it is casting to shared.) This has a large performance cost that only benefits very few actual cases. It follows that we need to change the notion that you first allocate memory and then brand it as shared. The "will be shared" knowledge must be present during allocation, and use different methods of allocation for the two cases. Shared is implicit in the case of immutable. Think carefully: if you implement this and it has any efficiency benefit for non-shared allocations, const-allocated objects and arrays will become more performant than immutable-allocated ones. People will thus have an incentive to stay away from immutable. If immutable does not pull its weight in other ways, it's just not worth it.
Re: A few thoughts on std.allocator
On 05/10/2015 11:50 AM, Andrei Alexandrescu wrote: In C, C++, and D people have allocated memory for a long time in the following manner: ... Long story short, arrays should sit on a different heap than objects. ... Unless this has been fixed in the interim, I believe DMD lowers new S(args) to [S(args)].ptr for struct S. It should be ensured that the global allocator will not be misinformed about the kind of allocation that takes place, by removing this lowering. 3. Thread-local vs. shared objects Currently in D it's legal to allocate memory in one thread and deallocate it in another. (One simple way to look at it is casting to shared.) This has a large performance cost that only benefits very few actual cases. It follows that we need to change the notion that you first allocate memory and then brand it as shared. The "will be shared" knowledge must be present during allocation, and use different methods of allocation for the two cases. ... 6. Immutable vs. mutable I'm not sure how this can be practically exploited. There must be something in the notion that, save for a brief write period after allocation, the memory will stay unmodified. Still thinking. ... Keep in mind that currently, entire regions of memory can change from mutable to immutable implicitly when returned from pure functions. Furthermore, as Michel points out, the ways 'immutable' can be leveraged is constrained by the fact that it implies 'shared'.
Re: A few thoughts on std.allocator
On 5/10/15 3:15 AM, anonymous wrote: On Sunday, 10 May 2015 at 09:50:00 UTC, Andrei Alexandrescu wrote: (file:///Users/aalexandre/code/d/dlang.org/web/phobos-prerelease/std_experimental_allocator_free_tree.html) bad link Pardon: erdani.com/d/phobos-prerelease/std_experimental_allocator_free_tree.html -- Andrei
Re: A few thoughts on std.allocator
On 5/10/15 3:51 AM, Michel Fortin wrote: Shared is implicit in the case of immutable. Think carefully: if you implement this and it has any efficiency benefit for non-shared allocations, const-allocated objects and arrays will become more performant than immutable-allocated ones. People will thus have an incentive to stay away from immutable. Good point. Well I'd say if things turn out that way, we shouldn't pessimize one case just to keep it aligned with another. There might be optimization opportunities particular to immutable data. -- Andrei
Re: A few thoughts on std.allocator
On Sunday, 10 May 2015 at 09:50:00 UTC, Andrei Alexandrescu wrote: 3. Thread-local vs. shared objects Currently in D it's legal to allocate memory in one thread and deallocate it in another. (One simple way to look at it is casting to shared.) This has a large performance cost that only benefits very few actual cases. It follows that we need to change the notion that you first allocate memory and then brand it as shared. The "will be shared" knowledge must be present during allocation, and use different methods of allocation for the two cases. In addition to an immutable/shared heap, it may also be necessary to transfer data from one thread to another. The shared heap is for data with shared ownership, while other data with (unique) ownership can be sent to other threads.
Re: A few thoughts on std.allocator
On Monday, 11 May 2015 at 09:55:36 UTC, Marc Schütz wrote: In addition to an immutable/shared heap, it may also be necessary to transfer data from one thread to another. The shared heap is for data with shared ownership, while other data with (unique) ownership can be sent to other threads. This is starting to sound close to deadalnix proposal about different heaps for "cooked" and raw (unique) data.
Re: A few thoughts on std.allocator
On Sunday, 10 May 2015 at 09:50:00 UTC, Andrei Alexandrescu wrote: 3. Thread-local vs. shared objects Currently in D it's legal to allocate memory in one thread and deallocate it in another. (One simple way to look at it is casting to shared.) This has a large performance cost that only benefits very few actual cases. It follows that we need to change the notion that you first allocate memory and then brand it as shared. The "will be shared" knowledge must be present during allocation, and use different methods of allocation for the two cases. As long as casting to or from shared really doesn't do anything other than change how the type system treats that type, we can't really assume much of anything with regards to where shared _or_ thread-local variables came from. Maybe it's still of benefit for the allocator to know that it's going to be dealing with shared as opposed to thread-local variables when doing the allocation, but I don't see how we can get rid of the possibility of an object being allocated on one thread and deallocated on another without making major changes to shared - and std.concurrency isn't going to work very well if we can't cast to and from shared or immutable to pass objects across threads - not unless we add some way to indicate in the type system that a variable is being passed across threads. It may very well be that we _need_ to change how shared is treated by the language and runtime and how its plumbing works, but as it stands, I don't see how we could possibly assume that whether an object is created as shared or thread-local - or even what thread it's created on - has much of anything to do with how it's _actually_ going to be used. In _most_ cases, an object is going to be used on the same thread that it's created on, and if it were possible to create an object as shared directly (which it usually isn't), then in most cases an object that was created as thread-local would be destroyed on the thread that it's created on, and an object created as shared would be used as shared and destroy on who-knows-which thread, but because of both the possibility and need to cast to and from shared to do anything useful with shared as well as passing objects across threads, we simply cannot assume anything about how an object will be used based on whether it's constructed as shared or not or which thread it's constructed on. For any of that to change, shared needs to change. - Jonathan M Davis
Re: A few thoughts on std.allocator
On Monday, 11 May 2015 at 10:54:10 UTC, Jonathan M Davis wrote: doing the allocation, but I don't see how we can get rid of the possibility of an object being allocated on one thread and deallocated on another without making major changes to shared - and std.concurrency isn't going to work very well if we can't cast to and from shared or immutable to pass objects across threads - not unless we add some way to indicate in the type system that a variable is being passed across threads. Behavioural typing is an active research field so if you are to statically prove that a specific program configuration at runtime causes a type to be unshared/immutable you are outside the language design comfort zone. Which I am very much in favour of ;-). More on behavioural typing: http://forum.dlang.org/thread/ovoarcbexpvrrceys...@forum.dlang.org Of course, the sensible thing to do is to have "behavioural typing light". E.g. to allow passage through gateways (with rather limiting constraints which allows static verification).
Re: A few thoughts on std.allocator
On 5/10/15 5:58 AM, Timon Gehr wrote:
Keep in mind that currently, entire regions of memory can change from
mutable to immutable implicitly when returned from pure functions.
Furthermore, as Michel points out, the ways 'immutable' can be leveraged
is constrained by the fact that it implies 'shared'.
After sleeping on this for a bit, it seems to me pure function need to
identify their allocations in some way to the caller. The simplest way
is to have them conservatively use the most conservative heap. We get to
refine these later.
For now, here's a snapshot of flags that the allocation primitives
should know about:
enum AllocOptions
{
/// Allocate an array, not an individual object
array,
/// Allocate a string of characters
string,
/// Plan to let the GC take care of this object
noFree,
/// This object will be shared between threads
forSharing,
/// This object will be moved between threads
forThreadTransfer,
/// This object will be mutable after initialization
mutableTarget,
/// The caller is a pure function, so result may be immutable
fromPureFunction,
/// Object allocated has pointers
hasPointers,
/// Typical (default) options
typical = array | noFree | forSharing | mutableTarget | hasPointers
}
Anything to add to this?
Andrei
Re: A few thoughts on std.allocator
On Monday, 11 May 2015 at 15:45:38 UTC, Andrei Alexandrescu wrote: /// The caller is a pure function, so result may be immutable fromPureFunction, It should simply say that allocation pointer is unique, the fact that it comes from pure functions is not important on its own. It should be legal to allocate such chunks from other sources too.
Re: A few thoughts on std.allocator
On 5/11/15 9:14 AM, Dicebot wrote: On Monday, 11 May 2015 at 15:45:38 UTC, Andrei Alexandrescu wrote: /// The caller is a pure function, so result may be immutable fromPureFunction, It should simply say that allocation pointer is unique, the fact that it comes from pure functions is not important on its own. It should be legal to allocate such chunks from other sources too. Much clearer, thanks. -- Andrei
Re: A few thoughts on std.allocator
On 2015-05-11 17:45, Andrei Alexandrescu wrote:
For now, here's a snapshot of flags that the allocation primitives
should know about:
enum AllocOptions
{
/// Allocate an array, not an individual object
array,
/// Allocate a string of characters
string,
/// Plan to let the GC take care of this object
noFree,
I would recommend using a positive name, in this case, "garbageCollected".
/// This object will be shared between threads
forSharing,
/// This object will be moved between threads
forThreadTransfer,
/// This object will be mutable after initialization
mutableTarget,
/// The caller is a pure function, so result may be immutable
fromPureFunction,
/// Object allocated has pointers
hasPointers,
/// Typical (default) options
typical = array | noFree | forSharing | mutableTarget | hasPointers
Shouldn't this be the first enum member, then this will be the default
value.
}
--
/Jacob Carlborg
Re: A few thoughts on std.allocator
On Monday, 11 May 2015 at 15:45:38 UTC, Andrei Alexandrescu wrote:
On 5/10/15 5:58 AM, Timon Gehr wrote:
Keep in mind that currently, entire regions of memory can
change from
mutable to immutable implicitly when returned from pure
functions.
Furthermore, as Michel points out, the ways 'immutable' can be
leveraged
is constrained by the fact that it implies 'shared'.
After sleeping on this for a bit, it seems to me pure function
need to identify their allocations in some way to the caller.
The simplest way is to have them conservatively use the most
conservative heap. We get to refine these later.
For now, here's a snapshot of flags that the allocation
primitives should know about:
enum AllocOptions
{
/// Allocate an array, not an individual object
array,
/// Allocate a string of characters
string,
/// Plan to let the GC take care of this object
noFree,
/// This object will be shared between threads
forSharing,
/// This object will be moved between threads
forThreadTransfer,
/// This object will be mutable after initialization
mutableTarget,
/// The caller is a pure function, so result may be immutable
fromPureFunction,
/// Object allocated has pointers
hasPointers,
/// Typical (default) options
typical = array | noFree | forSharing | mutableTarget |
hasPointers
}
Anything to add to this?
fixed or pinned?
This will allocate the memory ala malloc and ignore it from hence
forward. Similar to noFree but more expansive.
It seems to me that you really need to break up the allocation
options into both allocation and deallocation along with the AUTO
option. The auto option allows the compiler to attempt to
determine the best option(scan for ptr's, etc). It would be the
default option.
Allocation options are basically simpler and could include
allocation specific things such as:
Fast, Fixed, GC, Manual, Stack, Heap, etc
The deallocation options would essentially be your options
above(since they really are talking about what to do when an
object is deallocated).
Similarly I believe the GC and other memory managers should be
parametrized with some protocol between different managers for
cross-management.
E.g., Multiple heaps for different object memory orientation. GC
uses one heap, ARC uses another. If an object cross the
boundary(ptr to an object in another heap) then the memory
manager trying to free the object has to inform the other memory
manager.
This partitioning of memory into more specialized zones will
provide more optimized options for the programmer. At some point
Re: A few thoughts on std.allocator
On Monday, 11 May 2015 at 15:45:38 UTC, Andrei Alexandrescu wrote:
On 5/10/15 5:58 AM, Timon Gehr wrote:
Keep in mind that currently, entire regions of memory can
change from
mutable to immutable implicitly when returned from pure
functions.
Furthermore, as Michel points out, the ways 'immutable' can be
leveraged
is constrained by the fact that it implies 'shared'.
After sleeping on this for a bit, it seems to me pure function
need to identify their allocations in some way to the caller.
The simplest way is to have them conservatively use the most
conservative heap. We get to refine these later.
For now, here's a snapshot of flags that the allocation
primitives should know about:
enum AllocOptions
{
/// Allocate an array, not an individual object
array,
/// Allocate a string of characters
string,
/// Plan to let the GC take care of this object
noFree,
/// This object will be shared between threads
forSharing,
/// This object will be moved between threads
forThreadTransfer,
/// This object will be mutable after initialization
mutableTarget,
/// The caller is a pure function, so result may be immutable
fromPureFunction,
/// Object allocated has pointers
hasPointers,
/// Typical (default) options
typical = array | noFree | forSharing | mutableTarget |
hasPointers
}
Anything to add to this?
Would it be better to name these after their interpretation,
rather than expected use cases? For example, the allocator
doesn't care if something is an array, it cares about resizing,
and large block allocations. Perhaps s/array/expectRealloc/ (as
an example). Similar for other ones.
The benefit here is that if, for example, I have some non-array
use case for frequently reallocing then I can express that
directly rather than having to pretend it's like an array.
Re: A few thoughts on std.allocator
On 5/12/15 6:12 AM, Peter Alexander wrote: Would it be better to name these after their interpretation, rather than expected use cases? For example, the allocator doesn't care if something is an array, it cares about resizing, and large block allocations. Perhaps s/array/expectRealloc/ (as an example). Similar for other ones. Yah, "resizable" is nice and self-explanatory. Thanks! -- Andrei
Re: A few thoughts on std.allocator
On 5/10/15 6:51 AM, Michel Fortin wrote: On 2015-05-10 09:50:00 +, Andrei Alexandrescu said: 3. Thread-local vs. shared objects Currently in D it's legal to allocate memory in one thread and deallocate it in another. (One simple way to look at it is casting to shared.) This has a large performance cost that only benefits very few actual cases. It follows that we need to change the notion that you first allocate memory and then brand it as shared. The "will be shared" knowledge must be present during allocation, and use different methods of allocation for the two cases. Shared is implicit in the case of immutable. Think carefully: if you implement this and it has any efficiency benefit for non-shared allocations, const-allocated objects and arrays will become more performant than immutable-allocated ones. People will thus have an incentive to stay away from immutable. The whole concept of immutable being implicitly shareable is kind of broken. There are many reasons to have immutable unshared data, and it poisons const to the point where you really should consider any const variable to be also shared. -Steve
Re: A few thoughts on std.allocator
On 5/10/15 8:58 AM, Timon Gehr wrote: On 05/10/2015 11:50 AM, Andrei Alexandrescu wrote: In C, C++, and D people have allocated memory for a long time in the following manner: ... Long story short, arrays should sit on a different heap than objects. ... Unless this has been fixed in the interim, I believe DMD lowers new S(args) to [S(args)].ptr for struct S. It should be ensured that the global allocator will not be misinformed about the kind of allocation that takes place, by removing this lowering. That has been fixed. The compiler now calls a different runtime hook. -Steve
Re: A few thoughts on std.allocator
On Tuesday, 12 May 2015 at 15:51:38 UTC, Steven Schveighoffer wrote: The whole concept of immutable being implicitly shareable is kind of broken. There are many reasons to have immutable unshared data, and it poisons const to the point where you really should consider any const variable to be also shared. -Steve What are the extra implications of having to think of all const variables as shared? I guess it would mean the currently unimplemented memory barriers should happen for const variables as well. That does seem like a problem.
Re: A few thoughts on std.allocator
On 5/12/15 12:53 PM, Brad Anderson wrote:
On Tuesday, 12 May 2015 at 15:51:38 UTC, Steven Schveighoffer wrote:
The whole concept of immutable being implicitly shareable is kind of
broken. There are many reasons to have immutable unshared data, and it
poisons const to the point where you really should consider any const
variable to be also shared.
What are the extra implications of having to think of all const
variables as shared? I guess it would mean the currently unimplemented
memory barriers should happen for const variables as well. That does
seem like a problem.
The one that always comes to my mind is array appending:
immutable int[] x = new int[5];
const int[] y = x;
x ~= 1; // should this lock;
y ~= 1; // should this lock?
y = new int[5];
y ~= 1; // should this too? If so, isn't it a waste of cycles?
Of course, array appending is an odd duck here, as generally you are not
generally able to add data to an immutable piece of data.
But there are other cases. Consider a struct like this:
struct S
{
int a;
immutable int b;
}
I can create an S on the heap (or whatever allocator), and s.b could be
shared, but s.a could not be. How does that treat the block the entire S
is allocated in?
As much as it sucks, I'd prefer to see immutable not be implicitly
shared, and require a cast. We could specialize the cast so it's not a
true "ignore all the rules" cast. Sharing data is too fraught with
danger. A concept of uniqueness would help here too.
I think shared is broken in general, the only thing that's great about
it is *not* shared, which is defined by the absence of shared :) That is
something that's easy to wrap your head around.
-Steve
Re: A few thoughts on std.allocator
On 05/12/2015 05:52 PM, Steven Schveighoffer wrote: On 5/10/15 8:58 AM, Timon Gehr wrote: On 05/10/2015 11:50 AM, Andrei Alexandrescu wrote: In C, C++, and D people have allocated memory for a long time in the following manner: ... Long story short, arrays should sit on a different heap than objects. ... Unless this has been fixed in the interim, I believe DMD lowers new S(args) to [S(args)].ptr for struct S. It should be ensured that the global allocator will not be misinformed about the kind of allocation that takes place, by removing this lowering. That has been fixed. The compiler now calls a different runtime hook. -Steve Great.
Re: A few thoughts on std.allocator
On Tuesday, 12 May 2015 at 17:21:04 UTC, Steven Schveighoffer wrote: The one that always comes to my mind is array appending: immutable int[] x = new int[5]; const int[] y = x; x ~= 1; // should this lock; y ~= 1; // should this lock? As per my udnerstanding `shared` should _never_ result in automatic locking or barriers or whatever. It is simply a tag qualfier, with no extra magical semantics.
Re: A few thoughts on std.allocator
On Wednesday, 13 May 2015 at 05:35:18 UTC, Dicebot wrote: On Tuesday, 12 May 2015 at 17:21:04 UTC, Steven Schveighoffer wrote: The one that always comes to my mind is array appending: immutable int[] x = new int[5]; const int[] y = x; x ~= 1; // should this lock; y ~= 1; // should this lock? As per my udnerstanding `shared` should _never_ result in automatic locking or barriers or whatever. It is simply a tag qualfier, with no extra magical semantics. http://dlang.org/faq.html#shared_memory_barriers Perhaps this is out of date though.
Re: A few thoughts on std.allocator
On Tuesday, 12 May 2015 at 17:21:04 UTC, Steven Schveighoffer wrote: I think shared is broken in general, the only thing that's great about it is *not* shared, which is defined by the absence of shared :) That is something that's easy to wrap your head around. Yes, «shared» is either broken or lacks definition. It should be deprecated in favour of «local». What the optimizer needs to know is: 1. Can the object be removed from the set of variables affected by a full memory barrier? 2. Is there no aliasing to the object outside of the context: E.g.: x++; y.f(); x--; Is it safe to optimize this to: y.f(); ?
Re: A few thoughts on std.allocator
On Tuesday, 12 May 2015 at 17:21:04 UTC, Steven Schveighoffer
wrote:
The one that always comes to my mind is array appending:
immutable int[] x = new int[5];
const int[] y = x;
Do you mean:
immutable(int)[] x = new int[5];
const(int)[] y = x;
?
Because you can't append to or reassign an immutable or const
slice.
x ~= 1; // should this lock;
y ~= 1; // should this lock?
Assuming x and y are head-mutable;
Locking is needed because even though the elements themselves do
not need locking for inspection[1], the metadata (capacity and
whatever else is in there) is always mutable. In other words,
immutable(T)[] is implicitly convertible to immutable(T[]) which
means it can be freely shared between threads, but when the slice
refers to a druntime dynamic array, it *does* actually have
mutable indirection. Blergh, yet another reason why conflating
slices with dynamic arrays in the type system was probably a bad
idea. Or rather, a good reason why T[new] was a good idea for D2.
Then again, the cost is only paid if the dynamic array features
are actually used :)
[1] Immutable guarantees that the elements cannot be mutated from
*any* thread, while const guarantees that the data is either
immutable or thread-local, unless combined with shared. Remember
that there is such a thing as shared(const(T)), but no such thing
as shared(immutable(T)).
y = new int[5];
y ~= 1; // should this too? If so, isn't it a waste of cycles?
Yeah, it needs to lock and it is a waste... it could avoid it
with some kind of virtual dispatch mechanism.
Of course, array appending is an odd duck here, as generally
you are not generally able to add data to an immutable piece of
data.
Well, when the case is immutable(T)[], it's really not an odd
case: in general you *can* grow a head-mutable container. In the
case of an in-place append the existing elements are not touched,
and in the case of reallocation the old elements are simply
moved, which doesn't violate immutability either.
The issue is the invisible, mutable metadata that is inherent in
D's arrays, not an issue for head-mutable containers of
immutable/const elements in general.
But there are other cases. Consider a struct like this:
struct S
{
int a;
immutable int b;
}
I can create an S on the heap (or whatever allocator), and s.b
could be shared, but s.a could not be. How does that treat the
block the entire S is allocated in?
As they are in the same structure, `a` and `b` will always have
the same sharedness. In the case of immutable(S), both `a` and
`b` are immutable and can be shared, while in the case of mutable
S they are both unshared. I don't see it as an issue as long as S
vs immutable(S) is provided at time of allocation.
Re: A few thoughts on std.allocator
On Wednesday, 13 May 2015 at 06:23:40 UTC, Brad Anderson wrote: On Wednesday, 13 May 2015 at 05:35:18 UTC, Dicebot wrote: On Tuesday, 12 May 2015 at 17:21:04 UTC, Steven Schveighoffer wrote: The one that always comes to my mind is array appending: immutable int[] x = new int[5]; const int[] y = x; x ~= 1; // should this lock; y ~= 1; // should this lock? As per my udnerstanding `shared` should _never_ result in automatic locking or barriers or whatever. It is simply a tag qualfier, with no extra magical semantics. http://dlang.org/faq.html#shared_memory_barriers Perhaps this is out of date though. I have a feeling that no one know what shared truly means anymore. I remember talking about it with Andrei during last DConf and his explanation was that it is all about creating user types that encapsulate concurrency internally (+ atomics). I may remember wrong of course but was no mention of compiler actually doing anything special for it.
Re: A few thoughts on std.allocator
On 2015-05-12 17:21:03 +, Steven Schveighoffer said: Of course, array appending is an odd duck here, as generally you are not generally able to add data to an immutable piece of data. A similar odd duck would be reference counting (again, mutable metadata attached to immutable data). -- Michel Fortin michel.for...@michelf.ca http://michelf.ca
Re: A few thoughts on std.allocator
On 5/13/15 1:35 AM, Dicebot wrote: On Tuesday, 12 May 2015 at 17:21:04 UTC, Steven Schveighoffer wrote: The one that always comes to my mind is array appending: immutable int[] x = new int[5]; const int[] y = x; x ~= 1; // should this lock; y ~= 1; // should this lock? As per my udnerstanding `shared` should _never_ result in automatic locking or barriers or whatever. It is simply a tag qualfier, with no extra magical semantics. It's not automatic, the runtime does it. It uses the type information to determine whether it needs to lock or not. It also avoids the thread-local Most Recently Used cache to look up block info, since that may not be accurate. Essentially, the *lack* of shared can be used to optimize in the runtime. Right now, it assumes that const does not mean shared, but that can cause issues if you had a shared immutable array that you were appending to via a const reference. The logic for not locking there is that the vast VAST majority of cases do not have this problem. -Steve
Re: A few thoughts on std.allocator
On 5/13/15 3:02 AM, Jakob Ovrum wrote:
On Tuesday, 12 May 2015 at 17:21:04 UTC, Steven Schveighoffer wrote:
The one that always comes to my mind is array appending:
immutable int[] x = new int[5];
const int[] y = x;
Do you mean:
immutable(int)[] x = new int[5];
const(int)[] y = x;
?
Because you can't append to or reassign an immutable or const slice.
Yes, that is what I meant. Sorry.
x ~= 1; // should this lock;
y ~= 1; // should this lock?
Assuming x and y are head-mutable;
Locking is needed because even though the elements themselves do not
need locking for inspection[1], the metadata (capacity and whatever else
is in there) is always mutable.
OK, then consider that this:
void main()
{
string x;
x ~= "hello";
x ~= " world";
}
would require locking. That's unacceptable. Nobody would append with
strings if this all required locking for no reason. The runtime
currently does NOT lock for this case, it considers immutable and const
to be thread-local.
In other words, immutable(T)[] is
implicitly convertible to immutable(T[]) which means it can be freely
shared between threads, but when the slice refers to a druntime dynamic
array, it *does* actually have mutable indirection.
Yeah, that's why this case is an odd duck. It's not generally allowed to
access mutable metadata via an immutable pointer.
Blergh, yet another
reason why conflating slices with dynamic arrays in the type system was
probably a bad idea. Or rather, a good reason why T[new] was a good idea
for D2. Then again, the cost is only paid if the dynamic array features
are actually used :)
You will never convince me of this :) T[new] was a terrible idea.
y = new int[5];
y ~= 1; // should this too? If so, isn't it a waste of cycles?
Yeah, it needs to lock and it is a waste... it could avoid it with some
kind of virtual dispatch mechanism.
No, I think the answer is simpler. Introduce shared(immutable), and then
we can distinguish between immutable data that is shared and data that
is not shared. It also makes implementing local heaps easier. Shared
really is orthogonal to mutability.
Well, when the case is immutable(T)[], it's really not an odd case: in
general you *can* grow a head-mutable container. In the case of an
in-place append the existing elements are not touched, and in the case
of reallocation the old elements are simply moved, which doesn't violate
immutability either.
Right, I'm not saying it's violating immutability -- the data AFTER the
array that's in the block is not referenced anywhere, so it's
technically unique.
Here's something even weirder: If you append to y (const(int)[]) as a
reference to x (immutable(int)[]), then part of the array is immutable
and shareable, and the part that was appended is const and not shareable.
But there are other cases. Consider a struct like this:
struct S
{
int a;
immutable int b;
}
I can create an S on the heap (or whatever allocator), and s.b could
be shared, but s.a could not be. How does that treat the block the
entire S is allocated in?
As they are in the same structure, `a` and `b` will always have the same
sharedness. In the case of immutable(S), both `a` and `b` are immutable
and can be shared, while in the case of mutable S they are both
unshared. I don't see it as an issue as long as S vs immutable(S) is
provided at time of allocation.
This should work:
void main()
{
auto s = new S;
passToOtherThread(&s.b);
}
Which makes s.a unshared, and s.b shared. But the memory block needs to
be shareable.
-Steve
Re: A few thoughts on std.allocator
On Wednesday, 13 May 2015 at 17:49:38 UTC, Steven Schveighoffer
wrote:
OK, then consider that this:
void main()
{
string x;
x ~= "hello";
x ~= " world";
}
would require locking. That's unacceptable. Nobody would append
with strings if this all required locking for no reason. The
runtime currently does NOT lock for this case, it considers
immutable and const to be thread-local.
Well, it's necessary because the design of druntime arrays is
incompatible with D2's type system. Without locking,
multi-threaded applications that use dynamic array operations
could easily contain some particularly hard to track concurrency
bugs.
Simply not doing the locking and hoping that everything is fine
doesn't sound like a good plan (which I think we agree on, since
shared(immutable(T)) would solve it).
No, I think the answer is simpler. Introduce shared(immutable),
and then we can distinguish between immutable data that is
shared and data that is not shared. It also makes implementing
local heaps easier. Shared really is orthogonal to mutability.
Basically, shared(immutable(T)) would only be useful to
allocators, including arrays because they may need to allocate
when growing. I don't think it would be useful beyond that; the
sharedness of immutable data is probably not interesting to any
other kind of code.
It would make immutable considerably harder to use than it is
today. shared(immutable(T)) would be implicitly convertible to
shared(const(T)), but not const(T), which precludes the vast
majority of mutation-agnostic D code out there today (I have
never seen shared(const(T)) used in the wild). We would no longer
be able to do even the simplest things, like passing a path
string to another thread and use std.file.read on it.
Here's something even weirder: If you append to y
(const(int)[]) as a reference to x (immutable(int)[]), then
part of the array is immutable and shareable, and the part that
was appended is const and not shareable.
This should be the case for user-defined containers as well as
long as the element type doesn't have mutable indirection.
Appending on slices seems to handle this correctly as well,
rejecting attempts to append a const(T)[] to an immutable(T)[]
when T has mutable indirection.
This should work:
void main()
{
auto s = new S;
passToOtherThread(&s.b);
}
Which makes s.a unshared, and s.b shared. But the memory block
needs to be shareable.
That is an interesting example. Plain shared has the same problem:
struct S {
int a;
shared int b;
}
void main() {
import std.concurrency;
auto tid = spawn(() {});
auto s = new S;
tid.send(&s.b);
}
Types that contain shared anywhere within the type would have to
be allocated from a global allocator, and with the current state
of immutable, the same would have to be done for types that
contain immutable anywhere within it. Note that it's only the
case for head-shared/head-immutable; types like immutable(T)[] or
shared(T)* don't count.
Re: A few thoughts on std.allocator
On 5/13/15 8:00 PM, Jakob Ovrum wrote:
On Wednesday, 13 May 2015 at 17:49:38 UTC, Steven Schveighoffer wrote:
OK, then consider that this:
void main()
{
string x;
x ~= "hello";
x ~= " world";
}
would require locking. That's unacceptable. Nobody would append with
strings if this all required locking for no reason. The runtime
currently does NOT lock for this case, it considers immutable and
const to be thread-local.
Well, it's necessary because the design of druntime arrays is
incompatible with D2's type system. Without locking, multi-threaded
applications that use dynamic array operations could easily contain some
particularly hard to track concurrency bugs.
I don't think we should go there. I would say it's very unlikely to have
this bug occur, but you are right it could occur. I just don't think
destroying append performance for all const and immutable array types is
worth it to fix the bug opportunity.
No, I think the answer is simpler. Introduce shared(immutable), and
then we can distinguish between immutable data that is shared and data
that is not shared. It also makes implementing local heaps easier.
Shared really is orthogonal to mutability.
Basically, shared(immutable(T)) would only be useful to allocators,
including arrays because they may need to allocate when growing. I don't
think it would be useful beyond that; the sharedness of immutable data
is probably not interesting to any other kind of code.
Yes, it really only matters for cases where the immutable pointer can be
used to obtain mutable data. But these are important cases.
The fact that most code doesn't share *at all*, makes it less of an
issue. Perhaps we need some way to indicate that when an array is
shared, it can no longer be appended in-place. It would be as simple as
flipping the APPENDABLE bit. The problem is, you're not always passing
the immutable array directly.
It would make immutable considerably harder to use than it is today.
shared(immutable(T)) would be implicitly convertible to
shared(const(T)), but not const(T), which precludes the vast majority of
mutation-agnostic D code out there today (I have never seen
shared(const(T)) used in the wild). We would no longer be able to do
even the simplest things, like passing a path string to another thread
and use std.file.read on it.
Yeah, there is no attribute that takes shared/unshared. I don't know a
good solution to that, and I understand that shared(immutable) screws up
most usages for immutable. It's not a good answer.
The problem is that when you share an immutable pointer, it changes the
rules for that pointer, but no type information has been altered. It's
impossible to track.
I think the idea of making immutable not shared by default is probably
not a good answer, but I don't know of a good one. I have a feeling
whatever answer we choose is going to be really painful :(
-Steve
