[m-dev.] a conditional field update operator

[Zoltan Somogyi]

On Thu, 9 Mar 2017 10:55:32 +1100, Paul Bone <paul at bone.id.au> wrote:
> > For those, I am pretty sure it is a bad idea. Suppose you have a 1% chance
> > of accidentally using deep equality instead of pointer equality. Then it may be
> > that 0.5% of the time you compare two 100-byte structures for equality
> > instead of two pointers, and 0.5% of the time you compare two 10 megabyte
> > structures for equality instead of two pointers. The cost of that second 0.5%
> > will be *way* more than what can be possibly justified by the amount of allocation
> > being saved.
> 
> Perhaps I'm wrong but I had assumed that a normal equality test (such as
> unification) will first compare pointers, and then do the deep tests only if
> the pointers are unequal, and short ciruit as soon as two fields are
> unequal.  And that it will do this transitively.

That is correct.

>  So that the actual /
> amortized cost is low or trivial.

Unfortunately, that does not follow. The bitwise equality tests on pointers
may reduce the cost of the equality test from traversing 10 Mb to traversing
(say) 10 Kb, but that cost is still *much* bigger than benefit you are trying to gain,
which is comparable to the cost of traversing a few tens of bytes. And
in the absence of a conditional update operator, those pointer equality tests
will tend to be less effective, because programmers will be more likely to write
traversals that don't preserve bitwise equality when the "updated" version
of a sub data structure is semantically equal to its old version.

> Either way, I don't think this should be the normal comparison used by a :?=
> operator.  But it might make sense that this is available to developers who
> want it.  Of course they could write it manually, I don't think it would be
> used very often relative to the your proposal with pointer equality.

In the absence of a convincing use case, I won't implement it.
 
> > I intended my original mail specifically to ask you guys to think about
> > *potential future* uses of conditional update, not just actual, current uses.
> > I see I should have made that more explicit.
> 
> I also thought that part of the intent is to ask what uses may occur in
> closed code bases such as Prince.

I was giving you an opportunity to put your two cents in, yes.

> The other developers will know more than
> me about this, but AIUI there's less need for this in Prince than the
> Mercury compiler.  Also sometimes when we manipulate tree-like structures
> (the DOM) we do so using mutvars, because the structures have cycles that
> are easier to manipulate with mutvars.

I see. This proposal will do nothing to help code using mutvars, but you know that.
 
> Each additional branch also affects the predictability of other branches, it
> may cause them to be evicted from the cache.

Yes. That is one reason why predicting the performance of any piece of code
from first principles (i.e. without measurement) has gone from perfectly possible
if quite tedious in the 1960s, to effectively impossible in the last two or three decades.
 
> From what I actually know about Boehm GC checking the free lists should be a
> few (dependent) memory reads and a well-predicted branch on the fast path.
> It's important that they are dependent reads (it does pointer following) so
> it may create stalls. Each time a free list is populated it is done so by
> lazy scanning of a memory block.

That is sequential access. Modern CPUs have circuits to detect sequential access
patterns, even when the programs is following several independent sequential
access patterns at once (e.g. when reading from two vectors to add them),
and they try to prefetch the contents of the next several addresses in each stream
so that it is in the cache (preferably L1) by the time the program asks for it.

In this case, for each of the most popular allocation sizes, such prefetches will likely
pull into the cache the next several words after the current allocation point
in the page at the head of the freelist. So while these reads may be dependent,
they are not that likely to be slow.

> That's been my understanding for a while.  But I wasn't aware of Nick's
> paper, is this the one? http://dotat.at/tmp/msp02.pdf

The paper I remember was similar but different. I don't know if that means
I was thinking of a different paper, or remembered this one incorrectly.
Or it may have been a post on his blog; he has some good ones.

Zoltan.