Memory allocation purity

[Jonathan M Davis via Digitalmars-d]

On Sun, 18 May 2014 06:58:25 -0700
"H. S. Teoh via Digitalmars-d" <digitalmars-d at puremagic.com> wrote:

> On Sat, May 17, 2014 at 11:51:44AM -0700, Jonathan M Davis via
> Digitalmars-d wrote:
> > On Thu, 15 May 2014 08:43:11 -0700
> > Andrei Alexandrescu via Digitalmars-d <digitalmars-d at puremagic.com>
> > wrote:
> >
> > > On 5/15/14, 6:28 AM, Dicebot wrote:
> > > > This is not true. Because of such code you can't ever
> > > > automatically memoize strongly pure function results by
> > > > compiler. A very practical concern.
> > >
> > > I think code that doesn't return pointers should be memoizable.
> > > Playing tricks with pointer comparisons would be appropriately
> > > penalized. -- Andrei
> >
> > Agreed. The fact that a pure function can return newly allocated
> > memory pretty much kills the idea of being able to memoize pure
> > functions that return pointers or references, because the program's
> > behavior would change if it were to memoize the result and reuse it.
> > However, that should have no effect on pure functions that return
> > value types - even if the function took pointers or references as
> > arguments or allocated memory internally. They should but perfectly
> > memoizable.
> [...]
>
>   bool func(int x) /* pure? */ {
>       int[] a, b;
>       a = new int[x];
>       b = new int[x];
>       return (a.ptr < b.ptr);
>   }
>
> Where do you draw the line?

Hmmmm. I think that it was pointed out somewhere else in this thread that that
sort of comparison is already undefined in C (and thus probably D) - certainly
it's not something that's really valid to do normally. However, there are
other things that we currently do "normally" which have similar problems (e.g.
toHash on Object hashing the reference). Maybe if we could come up with a set
of operations which weren't valid in a pure function because they'd behave
differently depending on which memory block was given to new, then we could
make it work. But we may simply need to say that memoization of pure functions
just isn't going to work if we allow allocations to take place in pure
functions. That wouldn't be ideal, but I'm also not convinced that it matters
much.

It's already so rare that memoization of a function call can occur, that I'm
pretty much convinced that memoization is useless as an optimization - at
least as long as the compiler is doing it. After all, how often does a
function get called with same the arguments within a single function let alone
a single expression (and as I understand it, memoization only ever occurs at
this point within either a single expression or statement - I don't remember
which - but regardless, it's not even within a whole function)? And since
there's no way that the compiler is going to memoize alls to a function across
functions or even across calls to the same function which is calling the
function which is being memoized, unless it's very common to call a function
with the same result within a single function (and I really don't think that
it is), then memoization by the compiler is really of minimal benefit, much as
it would be nice to have it where we can.

Regardless, we should error on the side of not memoizing in order to avoid
undefined behavior due to memory allocations causing the pure function to act
slightly differently across function calls (even when it's given the same
arguments).

- Jonathan M Davis