Denis Koroskin Wrote:

> Walter Bright Wrote:
> 
> > Denis Koroskin wrote:
> > > It is *non*-deterministic. The decision to reallocate depends (or will depend) on LRU and it may be cleared by another thread (e.g. another thread may reset it manually or via a GC cycle run).
> > 
> > The LRU is thread local.
> 
> It will then prevent a moving GC from being possible in D.
> 
> Otherwise, moving a block of data will invalidate LRU which will result in non-deterministic reallocation.

It won't work with the existing GC either.  If a page is completely emptied then it can be re-used for different sized allocations.  This is why the current cache is wiped during a collection.

Sean Kelly wrote:
> Denis Koroskin Wrote:
> 
>> Walter Bright Wrote:
>> 
>>> Denis Koroskin wrote:
>>>> It is *non*-deterministic. The decision to reallocate depends
>>>> (or will depend) on LRU and it may be cleared by another thread
>>>> (e.g. another thread may reset it manually or via a GC cycle
>>>> run).
>>> The LRU is thread local.
>> It will then prevent a moving GC from being possible in D.
>> 
>> Otherwise, moving a block of data will invalidate LRU which will
>> result in non-deterministic reallocation.
> 
> It won't work with the existing GC either.  If a page is completely
> emptied then it can be re-used for different sized allocations.  This
> is why the current cache is wiped during a collection.

In both cases, the LRU can be adjusted rather than wiped to account for it.

Walter Bright Wrote:

> BCS wrote:
> > would you agree that it is not something the programer can predict in advance?
> 
> He can, but it is not reasonable to expect him to. But it's still deterministic.

I've been following this discussion about determinism and I think it addresses the problem from the wrong point of view, that of a specific implementation.

My concern is the semantics of the language. As it is defined right now, a conforming implementation is free to use a quantum random number generator to decide whether to re-allocate or not. Is it likely? I don't think so; but the non-determinism is part of the semantics of D arrays.

On Tue, Nov 17, 2009 at 4:38 PM, Bartosz Milewski <bartosz-nospam@relisoft.com> wrote:
> Walter Bright Wrote:
>
>> BCS wrote:
>> > would you agree that it is not something the programer can predict in advance?
>>
>> He can, but it is not reasonable to expect him to. But it's still deterministic.
>
> I've been following this discussion about determinism and I think it addresses the problem from the wrong point of view, that of a specific implementation.
>
> My concern is the semantics of the language. As it is defined right now, a conforming implementation is free to use a quantum random number generator to decide whether to re-allocate or not. Is it likely? I don't think so; but the non-determinism is part of the semantics of D arrays.

Then why not just fix the spec to say the behavior has to be deterministic?

--bb

Bartosz Milewski wrote:
> Walter Bright Wrote:
> 
>> BCS wrote:
>>> would you agree that it is not something the programer can predict in advance?
>> He can, but it is not reasonable to expect him to. But it's still deterministic.
> 
> I've been following this discussion about determinism and I think it addresses the problem from the wrong point of view, that of a specific implementation. 
> 
> My concern is the semantics of the language. As it is defined right now, a conforming implementation is free to use a quantum random number generator to decide whether to re-allocate or not. Is it likely? I don't think so; but the non-determinism is part of the semantics of D arrays.

It would not be difficult to specify in the language definition (and TDPL) that behavior is deterministic for a given platform. I think this has some impact on the freedom of the memory allocator, but probably not major.

Andrei

Andrei Alexandrescu Wrote:

> My concern is the semantics of the language. As it is defined right now, a conforming implementation is free to use a quantum random number generator to decide whether to re-allocate or not. Is it likely? I don't think so; but the non-determinism is part of the semantics of D arrays.
> 
> It would not be difficult to specify in the language definition (and TDPL) that behavior is deterministic for a given platform. I think this has some impact on the freedom of the memory allocator, but probably not major.

Actually this wouldn't fix the problem. Although this would make the program deterministic, it would still exhibit chaotic behavior (and chaos is a pretty good simulator of non-determinism--see random number generators).

An input string that is one character longer than in the previous run in one part of the program could cause change in allocation in a completely different part of the program (arbitrary long distance coupling).

Theoretically, the heap is deterministic, but in practice no program should depend on all pointers having exactly the same values from run to run. For all intents and purposes the heap should be treated as non-deterministic. This is why no language bothers to impose determinism on the heap. Neither should D.

Bartosz Milewski wrote:
> Andrei Alexandrescu Wrote:
> 
>> My concern is the semantics of the language. As it is defined right
>> now, a conforming implementation is free to use a quantum random
>> number generator to decide whether to re-allocate or not. Is it
>> likely? I don't think so; but the non-determinism is part of the
>> semantics of D arrays.
>> 
>> It would not be difficult to specify in the language definition
>> (and TDPL) that behavior is deterministic for a given platform. I
>> think this has some impact on the freedom of the memory allocator,
>> but probably not major.
> 
> Actually this wouldn't fix the problem. Although this would make the
> program deterministic, it would still exhibit chaotic behavior (and
> chaos is a pretty good simulator of non-determinism--see random
> number generators).

I am glad you have also reached that conclusion.

> An input string that is one character longer than in the previous run
> in one part of the program could cause change in allocation in a
> completely different part of the program (arbitrary long distance
> coupling).

Then you must restart your argument which was centered around non-determinism. It starts like that: "I read Andrei's chapter on arrays and there's one thing that concerns me. When a slice is extended, the decision to re-allocate, and therefore to cut its connection to other slices, is non-deterministic."


Andrei

On 2009-11-22 19:58:37 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> It's very simple, really. Appending to an array never results in overwriting elements of an existing array. Appending may terminate a sharing relationship. This is simple, easy to understand, and requires no understanding of the optimization paraphernalia, which I hope to be able to improve.

I think it's the "may terminate" part Bartosz (and some others) don't like, since it's hard to predict and may cause bugs that appear in an hard to understand pattern when misused.

I'm not exactly sure where to stand on this issue, but I might have a solution that looks like a compromise: use the MRU only for arrays of immutable elements, like strings. Since it's not possible to modify immutable data, it doesn't change the semantics if two slices are aliasing each other or not[^1]. Other arrays could get the more predictable behavior of always reallocating, but an optimizer could still avoid that when static analysis can prove that only one slice points to the data.

[^1]: It changes things somewhat if you take the address of elements and start comparing them, but I find it reasonable that taking address of things could reveal implementation details. It could change things if the element type has a postblit function, or a destructor, since you will avoid some copying, but I think that's fine.

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/