Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Daniel Colascione]

On 10/9/13 10:52 AM, Paul Eggert wrote:
> ------------------------------------------------------------
> revno: 114593
> revision-id: eggert@cs.ucla.edu-20131009175238-dkbu5sk6zbqznw80
> parent: rgm@gnu.org-20131009171720-4kzu0813fkap59g3
> committer: Paul Eggert <eggert@cs.ucla.edu>
> branch nick: trunk
> timestamp: Wed 2013-10-09 10:52:38 -0700
> message:
>    * lisp.h (eassert): Don't use 'assume'.
>    
>    Sometimes 'assume' wins in performance, and sometimes it loses,
>    so it shouldn't be used all the time.  Perhaps we need two
>    flavors of 'eassert', one for where 'assume' is far more likely
>    to help or to hurt; but that can be done later.
>    Problem reported by Dmitry Andipov in
>    <http://lists.gnu.org/archive/html/emacs-devel/2013-10/msg00276.html>.
>    Also, don't include <verify.h>; no longer needed.

Can you please either 1) restore eassert_and_assume and its callers or 
20 restore the assume calls in alloc.c and data.c? By merging 
eassert_and_assume with eassert, then removing the assume from eassert, 
you've essentially removed calls to assume and pessimized the code.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Paul Eggert]

Daniel Colascione wrote:
> By merging eassert_and_assume with eassert, then removing the assume from eassert, you've essentially removed calls to assume and pessimized the code.

OK, in trunk bzr 114622 I restored eassert_and_assume
(under the shorter name 'eassume'), but can you measure
how much performance you're gaining with this change?
The eassume macro is tricky to use (as it sometimes makes
performance worse) so I'd rather omit it if any
performance gains are insignificant.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Eli Zaretskii]

> Date: Thu, 10 Oct 2013 23:36:24 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> 
> Daniel Colascione wrote:
> > By merging eassert_and_assume with eassert, then removing the assume from eassert, you've essentially removed calls to assume and pessimized the code.
> 
> OK, in trunk bzr 114622 I restored eassert_and_assume
> (under the shorter name 'eassume'), but can you measure
> how much performance you're gaining with this change?
> The eassume macro is tricky to use (as it sometimes makes
> performance worse) so I'd rather omit it if any
> performance gains are insignificant.

I'm also curious as to why this is needed.  Again, 'assume' is an
optimization device, and 'eassert' is not normally compiled in
optimized builds.  What are the use cases for this?

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Daniel Colascione]

On 10/11/13 12:00 AM, Eli Zaretskii wrote:
>> Date: Thu, 10 Oct 2013 23:36:24 -0700
>> From: Paul Eggert <eggert@cs.ucla.edu>
>>
>> Daniel Colascione wrote:
>>> By merging eassert_and_assume with eassert, then removing the assume from eassert, you've essentially removed calls to assume and pessimized the code.
>>
>> OK, in trunk bzr 114622 I restored eassert_and_assume
>> (under the shorter name 'eassume'), but can you measure
>> how much performance you're gaining with this change?

I don't expect major gains yet, since I haven't fully fleshed out my 
actual use of the feature. That said, I don't like the code generation 
that happens without the assume: the compiler has to generate code as if 
we could be working with negative numbers, but that never happens in 
reality.

>> The eassume macro is tricky to use (as it sometimes makes
>> performance worse) so I'd rather omit it if any
>> performance gains are insignificant.

I'd rather keep it in so it gains more use, especially if we insist on 
using signed arithmetic everywhere.  It doesn't "make performance worse" 
per se: what it does is evaluate side effects in its argument, and 
sometimes those side effects are expensive. If used with an argument 
that's cheap to evaluate --- say, eassume (x < y) --- it should only 
help performance.

> I'm also curious as to why this is needed.  Again, 'assume' is an
> optimization device, and 'eassert' is not normally compiled in
> optimized builds.  What are the use cases for this?

True, assertions and assume declarations are different, but they're 
similar in that they both communicate information about constraints.  A 
macro like eassume is useful because, with one line of code, it informs 
the optimizer about a possible optimization _and_ checks (when checking 
is on) that what we told the optimizer isn't full of lies. The last bit 
is important because the consequence of an incorrect assume declaration 
is incorrect code generation.

The side effect problem Dmitry found is the reason I didn't just fold 
assume into eassert myself. Having a single macro available that assumes 
and asserts can be useful to avoid duplication when touching new code 
that wants both kinds of semantics. IIRC from the other thread, Emacs is 
smaller when we merge the two constructs, so it looks like there are 
real gains to be had.

I think the bulk of assertions can be converted: while it's easy to 
imagine IT_STRING_CHARPOS turning into a call to some expensive 
function, it's harder to imagine something like EQ gaining new side effects.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Eli Zaretskii]

> Date: Fri, 11 Oct 2013 00:41:00 -0700
> From: Daniel Colascione <dancol@dancol.org>
> CC: emacs-devel@gnu.org
> 
> > I'm also curious as to why this is needed.  Again, 'assume' is an
> > optimization device, and 'eassert' is not normally compiled in
> > optimized builds.  What are the use cases for this?
> 
> True, assertions and assume declarations are different, but they're 
> similar in that they both communicate information about constraints.  A 
> macro like eassume is useful because, with one line of code, it informs 
> the optimizer about a possible optimization _and_ checks (when checking 
> is on) that what we told the optimizer isn't full of lies. The last bit 
> is important because the consequence of an incorrect assume declaration 
> is incorrect code generation.
> 
> The side effect problem Dmitry found is the reason I didn't just fold 
> assume into eassert myself. Having a single macro available that assumes 
> and asserts can be useful to avoid duplication when touching new code 
> that wants both kinds of semantics. IIRC from the other thread, Emacs is 
> smaller when we merge the two constructs, so it looks like there are 
> real gains to be had.
> 
> I think the bulk of assertions can be converted: while it's easy to 
> imagine IT_STRING_CHARPOS turning into a call to some expensive 
> function, it's harder to imagine something like EQ gaining new side effects.

Maybe I'm missing something, but I don't think this answers my
question.

Let me rephrase: assertions are used in unoptimized code, and compile
to nothing in optimized code.  'assume' is not needed in unoptimized
code, since that code is grossly inefficient anyway.  Thus, it sounds
like the two are almost perfectly orthogonal, and lumping them
together into a single construct is likely to continue bumping upon
problems that stem from basic incompatibility between the use cases,
which target two different non-overlapping build types.

IOW, you should almost _never_ need to use 'assume' where you use
'eassert', and vice versa.  So why do we need a single macro that does
both?

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Daniel Colascione]

On 10/11/13 1:08 AM, Eli Zaretskii wrote:
> Let me rephrase: assertions are used in unoptimized code, and compile
> to nothing in optimized code.  'assume' is not needed in unoptimized
> code, since that code is grossly inefficient anyway.  Thus, it sounds
> like the two are almost perfectly orthogonal

Say we have this function:

void foo (int *a, int *b) { *a = *a / *b; }

Suppose it's part of foo's contract that it never be called with *b == 
0.  In checked builds, we add an assertion to catch callers that violate 
the contract:

void foo (int *a, int *b) { eassert (*b != 0); *a = *a / *b; }

Now suppose we also want the optimizer to take advantage of the fact 
that *b != 0.  Because we have the assertion, we're confident that 
callers never actually pass a *b equal to 0.

void foo (int *a, int *b)
{ eassert (*b != 0); assume (*b != 0); *a = *a / *b; }

Now we've said *b != 0 twice. That's silly. We should just combine the 
eassert and assume into a single construct:

void foo (int *a, int *b) { eassume (*b != 0); *a = *a / *b; }

The connection between assume and assert is that both of them accept an 
expression that we expect to always evaluate to true.  It's only what 
the program does with that information that differs: in the assert case, 
we check that the constraint is met. In the assume case, we optimize 
assuming the constraint has been met. The condition itself is almost 
always the same.

> , and lumping them
> together into a single construct is likely to continue bumping upon
> problems that stem from basic incompatibility between the use cases,
> which target two different non-overlapping build types.

Only when we have side effects.  Looking through the code just now, I 
only saw a few assertions that weren't obviously free of side effects.

> IOW, you should almost _never_ need to use 'assume' where you use
> 'eassert', and vice versa.  So why do we need a single macro that does
> both?

I'd actually argue that you should almost always combine assert and 
assume. You've gone through the trouble of spelling out constraints on 
program execution: why not let the optimizer take advantage of that 
information?

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Stephen J. Turnbull]

Daniel Colascione writes:

 > I'd actually argue that you should almost always combine assert and 
 > assume. You've gone through the trouble of spelling out constraints on 
 > program execution: why not let the optimizer take advantage of that 
 > information?

I'd say +1 except that apparently optimizers are sufficiently stupid
as to compile worse code when assume is present (at least that's what
Paul seemed to claim).

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Eli Zaretskii]

> Date: Fri, 11 Oct 2013 01:19:21 -0700
> From: Daniel Colascione <dancol@dancol.org>
> CC: eggert@cs.ucla.edu, emacs-devel@gnu.org
> 
> On 10/11/13 1:08 AM, Eli Zaretskii wrote:
> > Let me rephrase: assertions are used in unoptimized code, and compile
> > to nothing in optimized code.  'assume' is not needed in unoptimized
> > code, since that code is grossly inefficient anyway.  Thus, it sounds
> > like the two are almost perfectly orthogonal
> 
> Say we have this function:
> 
> void foo (int *a, int *b) { *a = *a / *b; }
> 
> Suppose it's part of foo's contract that it never be called with *b == 
> 0.  In checked builds, we add an assertion to catch callers that violate 
> the contract:
> 
> void foo (int *a, int *b) { eassert (*b != 0); *a = *a / *b; }
> 
> Now suppose we also want the optimizer to take advantage of the fact 
> that *b != 0.

That is a hypothetical situation.  In Emacs, the code is already
written on the assumption that *b != 0, so it is already "optimized"
for that.  In most cases, you won't see any code that can be optimized
out using this assumption, as the programmer already did that --
that's why she added the assertion in the first place.

IOW, assertions in Emacs code are in places where the programmer
_thinks_ something must be true, and writes code based on that
assumption, but she isn't really 100% sure that something to be true.
So the assertion is left behind to catch the cases which the
programmer missed because of her misconceptions.

You are obviously thinking about a different reason of using
assertions: to assert certain invariants in the code and enforce
contracts of certain APIs.  But that is almost never the case in
Emacs, because (gasp!) almost every Emacs API has no well-defined
contract at all!

> > , and lumping them
> > together into a single construct is likely to continue bumping upon
> > problems that stem from basic incompatibility between the use cases,
> > which target two different non-overlapping build types.
> 
> Only when we have side effects.

For now, yes.  I'm afraid that's just the tip of the iceberg, though.

> Looking through the code just now, I only saw a few assertions that
> weren't obviously free of side effects.

The problem is to make sure an assertion obviously _is_ free of side
effects.  With Emacs's massive use of macros, which call other macros,
which call other macros, which... -- that is extremely hard.  And why
should a programmer who just wants to assert something go to such
great lengths?  That is just a maintenance burden for which I find no
good justification.

> > IOW, you should almost _never_ need to use 'assume' where you use
> > 'eassert', and vice versa.  So why do we need a single macro that does
> > both?
> 
> I'd actually argue that you should almost always combine assert and 
> assume.

Not in Emacs, IMO.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Daniel Colascione]

On 10/11/13 1:59 AM, Stephen J. Turnbull wrote:
> apparently optimizers are sufficiently stupid
> as to compile worse code when assume is present (at least that's what
> Paul seemed to claim).

I don't think that's actually the case. We implement assume using GCC's 
__builtin_unreachable: if (!(assumed_condition)) { 
__builtin_unreachable(); }.  If assumed_condition has side effects, then 
normal C language semantics requires that the compiler emit code to 
implement these side effects. The code required to do so might make the 
surrounding code "worse" than it would be otherwise, but the problem is 
with the side effects, not the optimizer hint per se. I haven't seen any 
instance of assume itself reducing the quality of produced code.

We don't have this problem with plain assertions, since in non-checked 
builds, we emit 0&&(assertion) so that the compiler need not ever 
actually evaluate assertion. (Also, it's for this reason that MSVC's 
__assume construct is cleaner than __builtin_unreachable.)

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Daniel Colascione]

On 10/11/13 2:06 AM, Eli Zaretskii wrote:
>> Date: Fri, 11 Oct 2013 01:19:21 -0700
>> From: Daniel Colascione <dancol@dancol.org>
>> CC: eggert@cs.ucla.edu, emacs-devel@gnu.org
>>
>> On 10/11/13 1:08 AM, Eli Zaretskii wrote:
>>> Let me rephrase: assertions are used in unoptimized code, and compile
>>> to nothing in optimized code.  'assume' is not needed in unoptimized
>>> code, since that code is grossly inefficient anyway.  Thus, it sounds
>>> like the two are almost perfectly orthogonal
>>
>> Say we have this function:
>>
>> void foo (int *a, int *b) { *a = *a / *b; }
>>
>> Suppose it's part of foo's contract that it never be called with *b ==
>> 0.  In checked builds, we add an assertion to catch callers that violate
>> the contract:
>>
>> void foo (int *a, int *b) { eassert (*b != 0); *a = *a / *b; }
>>
>> Now suppose we also want the optimizer to take advantage of the fact
>> that *b != 0.
>
> That is a hypothetical situation.  In Emacs, the code is already
> written on the assumption that *b != 0, so it is already "optimized"
> for that.

While the programmer may have written her C code under the assumption 
that an asserted condition holds, the compiler can't know that the 
asserted condition holds when generating its machine code. The point of 
the assume mechanism is to provide this information to the compiler.

> In most cases, you won't see any code that can be optimized
> out using this assumption, as the programmer already did that --
> that's why she added the assertion in the first place.

At the C level, not the code generation level.

> IOW, assertions in Emacs code are in places where the programmer
> _thinks_ something must be true, and writes code based on that
> assumption, but she isn't really 100% sure that something to be true.
> So the assertion is left behind to catch the cases which the
> programmer missed because of her misconceptions.
>
> You are obviously thinking about a different reason of using
> assertions: to assert certain invariants in the code and enforce
> contracts of certain APIs.  But that is almost never the case in
> Emacs, because (gasp!) almost every Emacs API has no well-defined
> contract at all!

Aren't these two cases actually the same? An API contract violation is 
just a special case of "not 100% sure that something [is] true", where 
"that something" is a function being called correctly. We add assertions 
to check that a program maintains certain invariants. We should take 
maximum advantage of the reasoning we've already done.

>>> , and lumping them
>>> together into a single construct is likely to continue bumping upon
>>> problems that stem from basic incompatibility between the use cases,
>>> which target two different non-overlapping build types.
>>
>> Only when we have side effects.
>
> For now, yes.  I'm afraid that's just the tip of the iceberg, though.

What other problems can you imagine?

>> Looking through the code just now, I only saw a few assertions that
>> weren't obviously free of side effects.
>
> The problem is to make sure an assertion obviously _is_ free of side
> effects.  With Emacs's massive use of macros, which call other macros,
> which call other macros, which... -- that is extremely hard.  And why
> should a programmer who just wants to assert something go to such
> great lengths?  That is just a maintenance burden for which I find no
> good justification.

What great lengths? Most common macros --- things like EQ --- are 
clearly free of side effects. The more exotic assertions probably aren't 
worth assuming anyway.

If GCC had some builtin that allowed us to determine whether an 
expression was free of side effects, we could use that to make the 
decision automatically at compile time. Until we get such a facility, 
though, providing some kind of eassert_and_assume macro helps people 
make the best of simple assertions while avoiding the side effect 
problem for more complicated ones.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Eli Zaretskii]

> Date: Fri, 11 Oct 2013 02:18:51 -0700
> From: Daniel Colascione <dancol@dancol.org>
> CC: eggert@cs.ucla.edu, emacs-devel@gnu.org
> 
> > That is a hypothetical situation.  In Emacs, the code is already
> > written on the assumption that *b != 0, so it is already "optimized"
> > for that.
> 
> While the programmer may have written her C code under the assumption 
> that an asserted condition holds, the compiler can't know that the 
> asserted condition holds when generating its machine code. The point of 
> the assume mechanism is to provide this information to the compiler.

The compiler will be unable to take advantage of that information,
because there's no source code to apply that information to.

> > In most cases, you won't see any code that can be optimized
> > out using this assumption, as the programmer already did that --
> > that's why she added the assertion in the first place.
> 
> At the C level, not the code generation level.

Code is generated from the C code, not out of thin air.

> > You are obviously thinking about a different reason of using
> > assertions: to assert certain invariants in the code and enforce
> > contracts of certain APIs.  But that is almost never the case in
> > Emacs, because (gasp!) almost every Emacs API has no well-defined
> > contract at all!
> 
> Aren't these two cases actually the same?

No, they are not.  E.g., if the programmer's assumption was wrong, and
there are in fact valid use cases where her assertion doesn't hold,
then in production code (where the assertions are defined away) your
'assume' will degrade the code quality for legitimate use cases.

> >>> , and lumping them
> >>> together into a single construct is likely to continue bumping upon
> >>> problems that stem from basic incompatibility between the use cases,
> >>> which target two different non-overlapping build types.
> >>
> >> Only when we have side effects.
> >
> > For now, yes.  I'm afraid that's just the tip of the iceberg, though.
> 
> What other problems can you imagine?

How should I know?  Does anyone know under which conditions, exactly,
a badly engineered bridge will collapse?

> > The problem is to make sure an assertion obviously _is_ free of side
> > effects.  With Emacs's massive use of macros, which call other macros,
> > which call other macros, which... -- that is extremely hard.  And why
> > should a programmer who just wants to assert something go to such
> > great lengths?  That is just a maintenance burden for which I find no
> > good justification.
> 
> What great lengths? Most common macros --- things like EQ --- are 
> clearly free of side effects.

There are a lot of macros much more complex than EQ.

> The more exotic assertions probably aren't worth assuming anyway.

Not sure I understand what you are saying here.

> If GCC had some builtin that allowed us to determine whether an 
> expression was free of side effects, we could use that to make the 
> decision automatically at compile time. Until we get such a facility, 
> though, providing some kind of eassert_and_assume macro helps people 
> make the best of simple assertions while avoiding the side effect 
> problem for more complicated ones.

I think you are wrong, but I guess I'm unable to convince you.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Daniel Colascione]

On 10/11/13 2:36 AM, Eli Zaretskii wrote:
>> Date: Fri, 11 Oct 2013 02:18:51 -0700
>> From: Daniel Colascione <dancol@dancol.org>
>> CC: eggert@cs.ucla.edu, emacs-devel@gnu.org
>>
>>> That is a hypothetical situation.  In Emacs, the code is already
>>> written on the assumption that *b != 0, so it is already "optimized"
>>> for that.
>>
>> While the programmer may have written her C code under the assumption
>> that an asserted condition holds, the compiler can't know that the
>> asserted condition holds when generating its machine code. The point of
>> the assume mechanism is to provide this information to the compiler.
>
> The compiler will be unable to take advantage of that information,
> because there's no source code to apply that information to.

I don't understand this argument. In my example, the assume would inform 
the compiler that it didn't have to emit code to handle division in the 
case that *b is zero. Similar principles apply to assertions about 
numeric ranges, pointer non-NULL-ness, etc. The C99 restrict keyword is 
similar, in a sense.

>>> In most cases, you won't see any code that can be optimized
>>> out using this assumption, as the programmer already did that --
>>> that's why she added the assertion in the first place.
>>
>> At the C level, not the code generation level.
>
> Code is generated from the C code, not out of thin air.

And we're talking about giving the compiler more information about the C 
code.

>>> You are obviously thinking about a different reason of using
>>> assertions: to assert certain invariants in the code and enforce
>>> contracts of certain APIs.  But that is almost never the case in
>>> Emacs, because (gasp!) almost every Emacs API has no well-defined
>>> contract at all!
>>
>> Aren't these two cases actually the same?
>
> No, they are not.  E.g., if the programmer's assumption was wrong, and
> there are in fact valid use cases where her assertion doesn't hold,
> then in production code (where the assertions are defined away) your
> 'assume' will degrade the code quality for legitimate use cases.

Any assertion that might not actually hold is a bug. That a progammer 
might, after an assertion, insert code to act sanely in the case that an 
assertion does not hold is irrelevant: it's reacting to an error, not 
dealing with a situation that ought to occur in practice. If the 
programmer really expects an assertion not to hold, he can use a variant 
that doesn't assume the condition holds. But these cases should be rare.

>>>>> , and lumping them
>>>>> together into a single construct is likely to continue bumping upon
>>>>> problems that stem from basic incompatibility between the use cases,
>>>>> which target two different non-overlapping build types.
>>>>
>>>> Only when we have side effects.
>>>
>>> For now, yes.  I'm afraid that's just the tip of the iceberg, though.
>>
>> What other problems can you imagine?
>
> How should I know?  Does anyone know under which conditions, exactly,
> a badly engineered bridge will collapse?

So this point boils down to "I have a bad feeling about this"?

>>> The problem is to make sure an assertion obviously _is_ free of side
>>> effects.  With Emacs's massive use of macros, which call other macros,
>>> which call other macros, which... -- that is extremely hard.  And why
>>> should a programmer who just wants to assert something go to such
>>> great lengths?  That is just a maintenance burden for which I find no
>>> good justification.
>>
>> What great lengths? Most common macros --- things like EQ --- are
>> clearly free of side effects.
>
> There are a lot of macros much more complex than EQ.

So don't use the assume-and-assert macros for questionable cases.

>> The more exotic assertions probably aren't worth assuming anyway.
>
> Not sure I understand what you are saying here.

I'm speculating that the optimization value to be gained from assuming 
very complex conditions is smaller than the value gained for assuming 
relatively simple conditions.

>> If GCC had some builtin that allowed us to determine whether an
>> expression was free of side effects, we could use that to make the
>> decision automatically at compile time. Until we get such a facility,
>> though, providing some kind of eassert_and_assume macro helps people
>> make the best of simple assertions while avoiding the side effect
>> problem for more complicated ones.
>
> I think you are wrong, but I guess I'm unable to convince you.

AFAICT, your opposition here boils down to the idea that there's some 
fundamental difference between, on one hand, statements we make about 
program behavior when we're debugging, and on the other hand, statements 
we make about program behavior when we're optimizing. Except for some 
cases involving deficiencies in the language-level mechanisms with which 
we make these statements, I don't see why we should regard these 
statements as different at all. To the exent these deficiencies force us 
to care about the difference --- the side effect issue --- we can get 
around the problem by using one macro to express "assert and assume" and 
to express "just assert", since it's always safe to assert a statement 
we're assuming to be true, but not necessarily the other way around.

You could argue that having two macros instead of one imposes a 
maintenance burden and that there isn't a payoff sufficient to justify 
this burden, but I don't think the maintenance cost of having another 
macro is very large, especially if we leave existing assertions as they 
are and use the assume-and-assert macro only for cases that are clearly 
free of side effects.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Stephen J. Turnbull]

Daniel Colascione writes:
 > On 10/11/13 1:59 AM, Stephen J. Turnbull wrote:

 > > apparently optimizers are sufficiently stupid as to compile worse
 > > code when assume is present (at least that's what Paul seemed to
 > > claim).
 > 
 > I don't think that's actually the case. We implement assume using GCC's 
 > __builtin_unreachable:
 >     if (!(assumed_condition)) {  __builtin_unreachable(); }.
 > If assumed_condition has side effects, then normal semantics
 > requires that the compiler emit code to implement [them].

Ah, OK, it's not the optimizer that's stupid, it's just GCC.  What
else is new, eh?[1]

However, I have to agree with Eli.[2]  One writes "assert(width>0)" when
one is about to write "aspect_ratio = height/width", and doesn't want
to write

    if (width > 0)
        aspect_ratio = height/width;
    else
        beep_loudly_to_annoy_user();  /* or other error recovery */

One would hope that a optimizing compiler given

    assume(width > 0);                /* Look Ma, all plusses! */
    if (width > 0)
        aspect_ratio = height/width;
    else
        beep_loudly_to_annoy_user();  /* or other error recovery */

would produce the same machine code as just

    aspect_ratio = height/width;

but look! we've already done that optimization.  It just comes
naturally.

I've seen a lot of handwaving, but if there's a case where assume
helps the compiler produce better code in Emacs, I've yet to see it
presented.


Footnotes: 
[1]  I'm sure they have their reasons.  Whatever they are, they sure
weren't invented by Emacs hackers.

[2]  Note that it's not necessarily a question of valid use cases that
the programmer didn't imagine.  There may be a bug elsewhere in the
program that manifests here, or even in the compiler.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Dmitry Antipov]

On 10/11/2013 01:55 PM, Daniel Colascione wrote:

> You could argue that having two macros instead of one imposes a maintenance burden
> and that there isn't a payoff sufficient to justify this burden, but I don't think
> the maintenance cost of having another macro is very large, especially if we leave
> existing assertions as they are and use the assume-and-assert macro only for cases
> that are clearly free of side effects.

May be I missed something, but could you please provide an example where
assume (...) really yields in better code?  As for the signed vs. (more
efficient) unsigned arithmetic, you can't turn:

int f (int x, int y, int z)
{
   return x / y + y / z + z / x;
}

into:

unsigned f (unsigned x, unsigned y, unsigned z)
{
   return x / y + y / z + z / x;
}

using assume(...), e.g.

int f (int x, int y, int z)
{
   assume (x >= 0);
   assume (y >= 0);
   assume (z >= 0);
   return x / y + y / z + z / x;
}

is just the same as in the first case.

Dmitry

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Eli Zaretskii]

> Date: Fri, 11 Oct 2013 02:55:44 -0700
> From: Daniel Colascione <dancol@dancol.org>
> CC: eggert@cs.ucla.edu, emacs-devel@gnu.org
> 
> >> While the programmer may have written her C code under the assumption
> >> that an asserted condition holds, the compiler can't know that the
> >> asserted condition holds when generating its machine code. The point of
> >> the assume mechanism is to provide this information to the compiler.
> >
> > The compiler will be unable to take advantage of that information,
> > because there's no source code to apply that information to.
> 
> I don't understand this argument. In my example, the assume would inform 
> the compiler that it didn't have to emit code to handle division in the 
> case that *b is zero.

I think Stephen explained this already.

> >>> In most cases, you won't see any code that can be optimized
> >>> out using this assumption, as the programmer already did that --
> >>> that's why she added the assertion in the first place.
> >>
> >> At the C level, not the code generation level.
> >
> > Code is generated from the C code, not out of thin air.
> 
> And we're talking about giving the compiler more information about the C 
> code.

Information about C code that just isn't there will not help the
compiler.

> If the programmer really expects an assertion not to hold, he can
> use a variant that doesn't assume the condition holds. But these
> cases should be rare.

You are wrong: in Emacs, these cases are the vast majority.  Just take
a look at the code which uses assertions.

> >>> For now, yes.  I'm afraid that's just the tip of the iceberg, though.
> >>
> >> What other problems can you imagine?
> >
> > How should I know?  Does anyone know under which conditions, exactly,
> > a badly engineered bridge will collapse?
> 
> So this point boils down to "I have a bad feeling about this"?

No, it boils down to "this is bad engineering".

> >>> The problem is to make sure an assertion obviously _is_ free of side
> >>> effects.  With Emacs's massive use of macros, which call other macros,
> >>> which call other macros, which... -- that is extremely hard.  And why
> >>> should a programmer who just wants to assert something go to such
> >>> great lengths?  That is just a maintenance burden for which I find no
> >>> good justification.
> >>
> >> What great lengths? Most common macros --- things like EQ --- are
> >> clearly free of side effects.
> >
> > There are a lot of macros much more complex than EQ.
> 
> So don't use the assume-and-assert macros for questionable cases.

People tend to forget subtle and obscure factoids.  The risk of any
one of us to forget and just treat this macro as a function call is
real.  See bug #15565 as a clear example.

> >> The more exotic assertions probably aren't worth assuming anyway.
> >
> > Not sure I understand what you are saying here.
> 
> I'm speculating that the optimization value to be gained from assuming 
> very complex conditions is smaller than the value gained for assuming 
> relatively simple conditions.

But if assume-and-assert macro exists, this abuse is exactly what is
going to happen.

> AFAICT, your opposition here boils down to the idea that there's some 
> fundamental difference between, on one hand, statements we make about 
> program behavior when we're debugging, and on the other hand, statements 
> we make about program behavior when we're optimizing.

Yes.

> Except for some cases involving deficiencies in the language-level
> mechanisms with which we make these statements, I don't see why we
> should regard these statements as different at all.

Again, explained by Stephen.  You will find in Emacs sources gobs of
examples of what Stephen shows.

> You could argue that having two macros instead of one imposes a 
> maintenance burden and that there isn't a payoff sufficient to justify 
> this burden, but I don't think the maintenance cost of having another 
> macro is very large, especially if we leave existing assertions as they 
> are and use the assume-and-assert macro only for cases that are clearly 
> free of side effects.

I submit that in most cases determining whether an expression is free
of side effects is prohibitively time consuming.  As result, people
will simply not do that analysis, and we will have more bugs like
15565.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Stefan Monnier]

> I've seen a lot of handwaving, but if there's a case where assume
> helps the compiler produce better code in Emacs, I've yet to see it
> presented.

Indeed, the cases where the compiler can optimize the code based on the
assume statement are fairly rare, because in most cases the programmer
has already done most of this work by hand.

I tend to agree with Daniel that `assert' should pretty much always be
"assert + assume", in theory.  In practice the fact that "assume" may
occasionally have a cost, and the fact that it rarely offers further
optimization opportunities, makes it less attractive than it appears
at first.

At the same time, this is all a tempest in a teapot: the difference
is minuscule either way.


        Stefan


PS: Cases where assert+assume could make a difference is if we only had
(say) the CAR macro but not the XCAR macro, in which case an
"assert+assume (CONSP (x))" could be used to tell the compiler that the
type test embedded in CAR can be skipped.
But of course, we don't trust the compiler to do this optimization for
us, so instead we created the XCAR macro, at which point the
"assert+assume (CONSP (x))" is no better than just "assert (CONSP (x))".

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Paul Eggert]

Dmitry Antipov wrote:

> May be I missed something, but could you please provide an example where
> assume (...) really yields in better code?

I observed minor performance improvements, though it wasn't
clear to me that they would result in significant
user-visible performance wins.  Here's a toy example:

	#include <verify.h>
	#define BITS_PER_WORD 16
	int arem (int x) { return x % BITS_PER_WORD; }
	int brem (int x) { assume (x >= 0); return x % BITS_PER_WORD; }

On Fedora 19 x86-64 with gcc -O2, this generates:

	arem:
		movl	%edi, %edx
		sarl	$31, %edx
		shrl	$28, %edx
		leal	(%rdi,%rdx), %eax
		andl	$15, %eax
		subl	%edx, %eax
		ret

	brem:
		movl	%edi, %eax
		andl	$15, %eax
		ret

brem is simpler and faster because the compiler knows that
the dividend is nonnegative.

This is a simple case.  In other, more complicated cases, it
wasn't clear to me that the code with 'assume (COND)' was
faster -- it could be slower, as far as I could see, even
when COND was obviously side-effect free.  I worry that at
least some of these cases reflect optimization glitches in
GCC, but perhaps in the long run these glitches will get
fixed.

My main worry about 'eassume' vs 'eassert' is the maintenance
hassle.  Obviously one shouldn't use 'eassume' on expressions
with side effects, but that's not always obvious.  For example:

  eassert (input_blocked_p ());

Is it OK to replace this with eassume?  At first it seems
so, as input_blocked_p is an inline function that only reads
a variable.  But that'd be incorrect, as the variable is
volatile, and accessing a volatile variable counts as a side
effect, and GCC cannot optimize it away.  This is fairly
tricky stuff, alas; is it worth worrying about this sort
of thing?

This is why I asked Daniel for a performance assessment of
how well 'assume' really helped Emacs.  For example, currently
Emacs does this in alloc.c:

  eassume (exact_payload_bytes <= total_payload_bytes);

Does this result in significant performance improvements?
If not, it's probably not worth the maintenance hassle to
distinguish 'eassume' from 'eassert', and we should simply
replace this 'eassume' calls with 'eassert'.  But if if
there's an important performance win sometimes with
'eassume', then it is probably worth the maintenance hassle,
at least for the cases where there is such a win.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Stephen J. Turnbull]

Stefan Monnier writes:

 > At the same time, this is all a tempest in a teapot: the difference
 > is minuscule either way.

Not if people start sprinkling assume() all over the place.  It
becomes one more thing to check, and because implementations differ,
you'll have to check your particular compiler's implementation and
whether it changes behavior when it encounters that particular
assume()ption.

I really can't think of a more mischievous coding practice.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Daniel Colascione]

On 10/11/13 8:22 AM, Paul Eggert wrote:
> This is a simple case.  In other, more complicated cases, it
> wasn't clear to me that the code with 'assume (COND)' was
> faster -- it could be slower, as far as I could see, even
> when COND was obviously side-effect free.  I worry that at
> least some of these cases reflect optimization glitches in
> GCC, but perhaps in the long run these glitches will get
> fixed.

Do you have a particular case that concerns you, or an example of one of 
these optimizer glitches? I haven't seen a single instance of a correct, 
side-effect-free assume resulting in incorrect code generation.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Daniel Colascione]

On 10/11/13 4:19 AM, Eli Zaretskii wrote:
>> Date: Fri, 11 Oct 2013 02:55:44 -0700
>> From: Daniel Colascione <dancol@dancol.org>
>> CC: eggert@cs.ucla.edu, emacs-devel@gnu.org
>>
>>>> While the programmer may have written her C code under the assumption
>>>> that an asserted condition holds, the compiler can't know that the
>>>> asserted condition holds when generating its machine code. The point of
>>>> the assume mechanism is to provide this information to the compiler.
>>>
>>> The compiler will be unable to take advantage of that information,
>>> because there's no source code to apply that information to.
>>
>> I don't understand this argument. In my example, the assume would inform
>> the compiler that it didn't have to emit code to handle division in the
>> case that *b is zero.
>
> I think Stephen explained this already.

No, he didn't, and neither did you.

>>>>> In most cases, you won't see any code that can be optimized
>>>>> out using this assumption, as the programmer already did that --
>>>>> that's why she added the assertion in the first place.
>>>>
>>>> At the C level, not the code generation level.
>>>
>>> Code is generated from the C code, not out of thin air.
>>
>> And we're talking about giving the compiler more information about the C
>> code.
>
> Information about C code that just isn't there will not help the
> compiler.

We're asserting things about symbols that appear textually in nearby 
code. That's the information we're providing. Claiming that we're not 
providing information about real code is nonsense. You can't manually 
perform all the transformations the compiler itself might. You can 
perform some, but not all, optimization manually.

>> If the programmer really expects an assertion not to hold, he can
>> use a variant that doesn't assume the condition holds. But these
>> cases should be rare.
>
> You are wrong: in Emacs, these cases are the vast majority.  Just take
> a look at the code which uses assertions.

No, I don't think those cases are the majority. I can compile Emacs 
--enable-checking, then run it without seeing it insantly crash and 
burn. That I can do so means these assertions are asserting things that 
are actually true. The idea that we're putting into assert conditions 
that might not be true is very strange. If a condition really might not 
be true, the right thing is to signal an error or abort Emacs, not write 
eassert.

>>>>> The problem is to make sure an assertion obviously _is_ free of side
>>>>> effects.  With Emacs's massive use of macros, which call other macros,
>>>>> which call other macros, which... -- that is extremely hard.  And why
>>>>> should a programmer who just wants to assert something go to such
>>>>> great lengths?  That is just a maintenance burden for which I find no
>>>>> good justification.
>>>>
>>>> What great lengths? Most common macros --- things like EQ --- are
>>>> clearly free of side effects.
>>>
>>> There are a lot of macros much more complex than EQ.
>>
>> So don't use the assume-and-assert macros for questionable cases.
>
> People tend to forget subtle and obscure factoids.  The risk of any
> one of us to forget and just treat this macro as a function call is
> real.  See bug #15565 as a clear example.

Bug 15565 was caused by changing the semantics of existing calls to 
eassert. This bug forms a poor argument against having a different macro 
that asserts and assumes.

>>>> The more exotic assertions probably aren't worth assuming anyway.
>>>
>>> Not sure I understand what you are saying here.
>>
>> I'm speculating that the optimization value to be gained from assuming
>> very complex conditions is smaller than the value gained for assuming
>> relatively simple conditions.
>
> But if assume-and-assert macro exists, this abuse is exactly what is
> going to happen.

I can see changing eassert to eassume being problematic. I don't buy at 
all the idea that somehow _having_ an assert-and-assume macro is 
dangerous, especially if you document that this macro might evaluate its 
argument even in assertion-disabled builds. It has a different name and 
acts differently. That's what names are for, to distinguish behaviors.

But I'm clearly not winning this one. I think that 1) having a different 
macro with different semantics is actually perfectly safe and 
maintainable, and that 2) measurable (if minor) improvements in code 
generation warrant changing some assertions to use this different macro 
instead of eassert. But if others disagree this strongly, let's take out 
the feature until we can show a specific case where it makes a bigger 
difference.

Re: [Emacs-diffs] trunk r114593: * lisp.h (eassert): Don't use 'assume'.

[Paul Eggert]

Daniel Colascione wrote:
> I haven't seen a single instance of a correct, side-effect-free assume resulting in incorrect code generation.

As far as I could tell, the generated code wasn't incorrect,
it was merely slower.  I didn't measure the performance, but
the generated code did look worse (I could have been mistaken
of course).

Have you measured the user-visible performance of Emacs when
it internally uses eassume rather than eassert?  Is there
a significant performance improvement?  If not, perhaps we
should omit eassume, as not being worth the trouble.