www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Memory allocation purity

reply "Brian Schott" <briancschott gmail.com> writes:
What is the plan for the "pure"-ity of memory management?

Right now the "new" operator is considered to be pure even though 
it is not, but related functinos like malloc, GC.addRange, 
GC.removeRange, and others are not.

This prevents large portions of std.allocator from being pure. 
This then prevents any containers library built on std.allocator 
from being pure, which does the same for any funcions and data 
structures written using those containers.

If malloc can never be considered pure, even when hidden behind 
an allocator, why can it be considered pure when hidden behind 
the GC?
May 14 2014
next sibling parent reply "w0rp" <devw0rp gmail.com> writes:
On Wednesday, 14 May 2014 at 22:42:47 UTC, Brian Schott wrote:

 What is the plan for the "pure"-ity of memory management?

 Right now the "new" operator is considered to be pure even 
 though it is not, but related functinos like malloc, 
 GC.addRange, GC.removeRange, and others are not.

 This prevents large portions of std.allocator from being pure. 
 This then prevents any containers library built on 
 std.allocator from being pure, which does the same for any 
 funcions and data structures written using those containers.

 If malloc can never be considered pure, even when hidden behind 
 an allocator, why can it be considered pure when hidden behind 
 the GC?


I think even C malloc should be considered pure. True, it affects 
global state by allocating memory, but it never changes existing 
values, it just allows for new values. free is pure because it 
isn't side-effecting, it deallocates what you give it. That's 
just my perspective on it though, others might have other views 
on it.
May 14 2014
parent reply "Idan Arye" <GenericNPC gmail.com> writes:
On Wednesday, 14 May 2014 at 22:50:10 UTC, w0rp wrote:

 I think even C malloc should be considered pure. True, it 
 affects global state by allocating memory, but it never changes 
 existing values, it just allows for new values. free is pure 
 because it isn't side-effecting, it deallocates what you give 
 it. That's just my perspective on it though, others might have 
 other views on it.


`free` is not pure, because if you have a reference to that 
memory that reference is no longer valid.
May 14 2014
next sibling parent "Meta" <jared771 gmail.com> writes:
On Thursday, 15 May 2014 at 01:33:36 UTC, Idan Arye wrote:

 On Wednesday, 14 May 2014 at 22:50:10 UTC, w0rp wrote:

 I think even C malloc should be considered pure. True, it 
 affects global state by allocating memory, but it never 
 changes existing values, it just allows for new values. free 
 is pure because it isn't side-effecting, it deallocates what 
 you give it. That's just my perspective on it though, others 
 might have other views on it.


 `free` is not pure, because if you have a reference to that 
 memory that reference is no longer valid.


It is weakly pure, i.e., it can only affect the world through the 
parameters given to it (and the state of the computer's memory... 
but we should ignore that).
May 14 2014
prev sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 01:33:34 +0000
Idan Arye via Digitalmars-d <digitalmars-d puremagic.com> wrote:


 On Wednesday, 14 May 2014 at 22:50:10 UTC, w0rp wrote:

 I think even C malloc should be considered pure. True, it
 affects global state by allocating memory, but it never changes
 existing values, it just allows for new values. free is pure
 because it isn't side-effecting, it deallocates what you give
 it. That's just my perspective on it though, others might have
 other views on it.


 `free` is not pure, because if you have a reference to that
 memory that reference is no longer valid.


But does that really matter from the perspective of pure? That's really more
of an  safety issue. There might be some way that that violates purtiy, but I
can't think of one at the moment.

free can't be strongly pure, because it's arguments couldn't be immutable (or
even const) without violating the type system, but I _think_ that it's fine
for free to be weakly pure. It's quite possible that I'm missing something
though.

- Jonathan M Davis
May 14 2014
prev sibling next sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wed, 14 May 2014 22:42:46 +0000
Brian Schott via Digitalmars-d <digitalmars-d puremagic.com> wrote:


 What is the plan for the "pure"-ity of memory management?

 Right now the "new" operator is considered to be pure even though
 it is not, but related functinos like malloc, GC.addRange,
 GC.removeRange, and others are not.

 This prevents large portions of std.allocator from being pure.
 This then prevents any containers library built on std.allocator
 from being pure, which does the same for any funcions and data
 structures written using those containers.

 If malloc can never be considered pure, even when hidden behind
 an allocator, why can it be considered pure when hidden behind
 the GC?


I think malloc should definitely be considered pure for the same reasons that
new is considered pure. I don't know about the other memory management
functions though. I'd really have to think through their side effects to have
an opinion on them. If we can make them pure though, that would certainly help
with ensuring that allocators can be pure.

- Jonathan M Davis
May 14 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2014 3:42 PM, Brian Schott wrote:

 If malloc can never be considered pure, even when hidden behind an allocator,


It cannot be pure as long as it can fail.


 why can it be considered pure when hidden behind the GC?


Because GC failures are not recoverable, so the pure allocation cannot fail.
May 14 2014
next sibling parent "Meta" <jared771 gmail.com> writes:
On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:

 On 5/14/2014 3:42 PM, Brian Schott wrote:

 If malloc can never be considered pure, even when hidden 
 behind an allocator,


 It cannot be pure as long as it can fail.


 why can it be considered pure when hidden behind the GC?


 Because GC failures are not recoverable, so the pure allocation 
 cannot fail.


Malloc is a tricky case. The results it returns are theoretically 
always unique, and it is referentially transparent if we pretend 
that we have infinite memory.
May 14 2014
prev sibling next sibling parent reply "Brian Schott" <briancschott gmail.com> writes:
On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:

 On 5/14/2014 3:42 PM, Brian Schott wrote:

 If malloc can never be considered pure, even when hidden 
 behind an allocator,


 It cannot be pure as long as it can fail.


 why can it be considered pure when hidden behind the GC?


 Because GC failures are not recoverable, so the pure allocation 
 cannot fail.


Can we say that Mallocator failures are not recoverable?
May 14 2014
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2014 5:44 PM, Brian Schott wrote:

 Can we say that Mallocator failures are not recoverable?


malloc itself does not have that property. But you could design a wrapper for
it 
that did.
May 14 2014
parent reply "Brian Schott" <briancschott gmail.com> writes:
On Thursday, 15 May 2014 at 00:48:52 UTC, Walter Bright wrote:

 On 5/14/2014 5:44 PM, Brian Schott wrote:

 Can we say that Mallocator failures are not recoverable?


 malloc itself does not have that property. But you could design 
 a wrapper for it that did.


I'm concerned specifically with this wrapper: 
https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L773

We need to make these functions pure if they are going to be 
usable.

Removing the stdlib import and adding

private extern (C)
{
     void* malloc(size_t) pure nothrow  trusted;
     void free(void*) pure nothrow  trusted;
     void* realloc(void*, size_t) pure nothrow  trusted;
}

as well as a throwing OutOfMemoryError if they fail should be 
sufficient, correct?
May 14 2014
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/14, 6:11 PM, Brian Schott wrote:

 On Thursday, 15 May 2014 at 00:48:52 UTC, Walter Bright wrote:

 On 5/14/2014 5:44 PM, Brian Schott wrote:

 Can we say that Mallocator failures are not recoverable?


 malloc itself does not have that property. But you could design a
 wrapper for it that did.


 I'm concerned specifically with this wrapper:
 https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L773

 We need to make these functions pure if they are going to be usable.

 Removing the stdlib import and adding

 private extern (C)
 {
      void* malloc(size_t) pure nothrow  trusted;
      void free(void*) pure nothrow  trusted;
      void* realloc(void*, size_t) pure nothrow  trusted;
 }

 as well as a throwing OutOfMemoryError if they fail should be
 sufficient, correct?


I think so. A more cautious solution would be to define PureMallocator 
in addition to Mallocator.

Andrei
May 14 2014
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 14 May 2014 21:11:30 -0400, Brian Schott <briancschott gmail.com>  
wrote:


 On Thursday, 15 May 2014 at 00:48:52 UTC, Walter Bright wrote:

 On 5/14/2014 5:44 PM, Brian Schott wrote:

 Can we say that Mallocator failures are not recoverable?


 malloc itself does not have that property. But you could design a  
 wrapper for it that did.


 I'm concerned specifically with this wrapper:  
 https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L773

 We need to make these functions pure if they are going to be usable.

 Removing the stdlib import and adding

 private extern (C)
 {
      void* malloc(size_t) pure nothrow  trusted;
      void free(void*) pure nothrow  trusted;
      void* realloc(void*, size_t) pure nothrow  trusted;
 }


Be careful. The above is all correct, but as has been discussed, the  
minute you start making returns immutable or parameters immutable, they  
become strong-pure, which has undesirable properties for allocators. If  
you wrap the above with calls to typed data, then strong-pure might be  
inferred.

The compiler can specially designate things like idup to make sure they  
always are considered weak-pure. But library code has to be more cautious.

-Steve
May 15 2014
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/14/14, 5:44 PM, Brian Schott wrote:

 On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:

 On 5/14/2014 3:42 PM, Brian Schott wrote:

 If malloc can never be considered pure, even when hidden behind an
 allocator,


 It cannot be pure as long as it can fail.


 why can it be considered pure when hidden behind the GC?


 Because GC failures are not recoverable, so the pure allocation cannot
 fail.


 Can we say that Mallocator failures are not recoverable?


FWIW std.allocator allows constructing a bunch of small-business 
allocators for which failure to allocate is entirely legit. The methods 
of such allocator may be weakly pure.

An allocator that ultimately falls back to GCAllocator and "never fails" 
should be pure - better yet, inferred as such.


Andrei
May 14 2014
prev sibling next sibling parent reply "Kapps" <opantm2+spam gmail.com> writes:
On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:

 Because GC failures are not recoverable, so the pure allocation 
 cannot fail.


Is this intentionally the case? I always thought you could handle 
it with onOutOfMemoryError if you knew that your program could 
handle running out of memory and free some memory (i.e., cached 
data) to recover. I've never actually had a use for it myself, so 
I'm just basing this off of newsgroup discussions I remember 
(possibly incorrectly) reading.
May 14 2014
parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thu, 15 May 2014 01:25:52 +0000
Kapps via Digitalmars-d <digitalmars-d puremagic.com> wrote:


 On Thursday, 15 May 2014 at 00:00:37 UTC, Walter Bright wrote:

 Because GC failures are not recoverable, so the pure allocation
 cannot fail.


 Is this intentionally the case? I always thought you could handle
 it with onOutOfMemoryError if you knew that your program could
 handle running out of memory and free some memory (i.e., cached
 data) to recover. I've never actually had a use for it myself, so
 I'm just basing this off of newsgroup discussions I remember
 (possibly incorrectly) reading.


It's intended that all Errors be considered unrecoverable. You can catch them
when necessary to try and do cleanup, but that's fairly risky, and you should
probably only do it when you're very sure of what's going on (which generally
means that the Error was thrown very close to where you're catching it).
There's no guarantee that automatic cleanup occurs when Errors are thrown
(unlike with Exceptions), so when an Error is thrown, the program tends to be
in a weird state on top of the weird state that caused the Error to be thrown
in the first place. In theory, you could catch an OutOfMemoryError very close
to where it was thrown and deal with it, but that's really not what was
intended.

- Jonathan M Davis
May 14 2014
prev sibling parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wed, 14 May 2014 17:00:39 -0700
Walter Bright via Digitalmars-d <digitalmars-d puremagic.com> wrote:


 On 5/14/2014 3:42 PM, Brian Schott wrote:

 If malloc can never be considered pure, even when hidden behind an
 allocator,


 It cannot be pure as long as it can fail.


 why can it be considered pure when hidden behind the GC?


 Because GC failures are not recoverable, so the pure allocation
 cannot fail.


Then we should create a wrapper for malloc which throws a MemoryError when
malloc fails. Then malloc failures would be the same as GC failures.

- Jonathan M Davis
May 14 2014
prev sibling next sibling parent reply "Meta" <jared771 gmail.com> writes:
On Wednesday, 14 May 2014 at 22:42:47 UTC, Brian Schott wrote:

 What is the plan for the "pure"-ity of memory management?

 Right now the "new" operator is considered to be pure even 
 though it is not, but related functinos like malloc, 
 GC.addRange, GC.removeRange, and others are not.

 This prevents large portions of std.allocator from being pure. 
 This then prevents any containers library built on 
 std.allocator from being pure, which does the same for any 
 funcions and data structures written using those containers.

 If malloc can never be considered pure, even when hidden behind 
 an allocator, why can it be considered pure when hidden behind 
 the GC?


Allocating memory through new and malloc should always be pure, I 
think, because failure either returns null in malloc's case, or 
throws an error in new's case. As for GC.addRange, 
GC.removeRange, etc... it's hard to say. These functions 
definitely alter the state of the GC, but it's all wrapped up in 
the GC's black box, guaranteed to never escape (I think? I don't 
know exactly how they're implemented). In the general case, as 
long as side-effects can be guaranteed to never affect anything 
outside of a function/class/struct, I think it can probably be 
pure (D's notion of purity, anyway).
May 14 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2014 5:03 PM, Meta wrote:

 Allocating memory through new and malloc should always be pure, I think,
because
 failure either returns null in malloc's case,


malloc cannot be pure if, with the same arguments, it returns null sometimes
and 
not other times.



 or throws an error in new's case.


A non-recoverable error.
   ^^^^^^^^^^^^^^^
May 14 2014
next sibling parent reply "Meta" <jared771 gmail.com> writes:
On Thursday, 15 May 2014 at 00:50:06 UTC, Walter Bright wrote:

 On 5/14/2014 5:03 PM, Meta wrote:

 Allocating memory through new and malloc should always be 
 pure, I think, because
 failure either returns null in malloc's case,


 malloc cannot be pure if, with the same arguments, it returns 
 null sometimes and not other times.



 or throws an error in new's case.


 A non-recoverable error.
   ^^^^^^^^^^^^^^^


If we pretend that there's infinite memory, then malloc will 
never return null.
May 14 2014
parent Walter Bright <newshound2 digitalmars.com> writes:
On 5/14/2014 5:56 PM, Meta wrote:

 On Thursday, 15 May 2014 at 00:50:06 UTC, Walter Bright wrote:

 On 5/14/2014 5:03 PM, Meta wrote:

 Allocating memory through new and malloc should always be pure, I think,
because
 failure either returns null in malloc's case,


 malloc cannot be pure if, with the same arguments, it returns null sometimes
 and not other times.



 or throws an error in new's case.


 A non-recoverable error.
   ^^^^^^^^^^^^^^^


 If we pretend that there's infinite memory, then malloc will never return null.


And what happens when malloc returns null?
May 14 2014
prev sibling next sibling parent reply Manu via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 15 May 2014 10:50, Walter Bright via Digitalmars-d
<digitalmars-d puremagic.com> wrote:

 On 5/14/2014 5:03 PM, Meta wrote:

 Allocating memory through new and malloc should always be pure, I think,
 because
 failure either returns null in malloc's case,



 malloc cannot be pure if, with the same arguments, it returns null sometimes
 and not other times.


Even if it doesn't fail, malloc called with identical arguments still
returns a different result every time.
You can't factor malloc outside a loop and cache the result because
it's being called repeatedly with the same argument like you're
supposed to be able to do with any other pure function.
You shouldn't be able to do that with gcalloc either... how can gcalloc be pure?
May 15 2014
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 15 May 2014 07:52:20 -0400, Manu via Digitalmars-d  
<digitalmars-d puremagic.com> wrote:


 On 15 May 2014 10:50, Walter Bright via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 5/14/2014 5:03 PM, Meta wrote:

 Allocating memory through new and malloc should always be pure, I  
 think,
 because
 failure either returns null in malloc's case,



 malloc cannot be pure if, with the same arguments, it returns null  
 sometimes
 and not other times.


 Even if it doesn't fail, malloc called with identical arguments still
 returns a different result every time.
 You can't factor malloc outside a loop and cache the result because
 it's being called repeatedly with the same argument like you're
 supposed to be able to do with any other pure function.
 You shouldn't be able to do that with gcalloc either... how can gcalloc  
 be pure?


That only applies to strong-pure functions. malloc would be weak-pure,  
since it returns a mutable pointer.

-Steve
May 15 2014