Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #107419 > unrolled thread

Appropriate optimization

Back to article view | Back to comp.lang.c

Contents

  Appropriate optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-29 13:44 -0700
    Re: Appropriate optimization Ian Collins <ian-news@hotmail.com> - 2017-03-30 10:41 +1300
      Re: Appropriate optimization supercat@casperkitty.com - 2017-03-29 15:22 -0700
    Re: Appropriate optimization supercat@casperkitty.com - 2017-03-29 15:10 -0700
      Re: Appropriate optimization Robert Wessel <robertwessel2@yahoo.com> - 2017-03-30 00:47 -0500
      Re: Appropriate optimization David Brown <david.brown@hesbynett.no> - 2017-03-30 10:15 +0200
      Re: Appropriate optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-30 10:11 -0700
        Re: Appropriate optimization David Brown <david.brown@hesbynett.no> - 2017-03-30 19:55 +0200
        Re: Appropriate optimization supercat@casperkitty.com - 2017-03-30 11:47 -0700
          Re: Appropriate optimization Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-30 12:03 -0700
            Re: Appropriate optimization Keith Thompson <kst-u@mib.org> - 2017-03-30 12:24 -0700
            Re: Appropriate optimization supercat@casperkitty.com - 2017-03-30 13:21 -0700
              Re: Appropriate optimization Ike Naar <ike@iceland.freeshell.org> - 2017-03-30 20:39 +0000
                Re: Appropriate optimization supercat@casperkitty.com - 2017-03-30 13:58 -0700
    Re: Appropriate optimization David Brown <david.brown@hesbynett.no> - 2017-03-30 10:20 +0200

#107419 — Appropriate optimization

This question is for anyone, but I'm specifically curious what Supercat
thinks...

Would it be an appropriate optimization to move the code on lines 101:
and 102: to somewhere in the middle of the if..expression on line 104:

          // Note:  This code is in the middle of a local function
    101:      int count = sizeof(thing) / my_sizing_determination(thing);
    102:      int size  = count * MY_COUNT_REQUIREMENT;
    103:
    104:      if (!p && (p = allocate_something(count, size)))
    105:      {
                  ... only the code in this block uses count and size
    Nnn:      }

The values not used before that point in the function, and they're
not used outside of the loop, and they're not flagged as volatile.
It would delay or prevent the call to my_sizing_determination(),
and is that a constraint?

What if it was merely this:

    101:      int count = sizeof(thing) / global_var_of_some_kind;

??  Would it be possible then since it's not really referencing
anything other than a global variable?

I'm wondering if it's possible to rearrange code to such an extent
that things which exist ahead of use like that could be moved to the
point of use, consuming processing time in the middle of an otherwise
syntactically correct if-expression, thereby not requiring the call
be made at all, or the values be computed at all, until the point of
their actual use, which leaves them uninitialized in the ABI in
certain cases.

I have never considered this type of optimizing before, but it came
up today and I was curious what other people think.

Thank you,
Rick C. Hodgin

[toc] | [next] | [standalone]

#107422

On 03/30/17 09:44 AM, Rick C. Hodgin wrote:
> This question is for anyone, but I'm specifically curious what Supercat
> thinks...
>
> Would it be an appropriate optimization to move the code on lines 101:
> and 102: to somewhere in the middle of the if..expression on line 104:
>
>            // Note:  This code is in the middle of a local function
>      101:      int count = sizeof(thing) / my_sizing_determination(thing);
>      102:      int size  = count * MY_COUNT_REQUIREMENT;
>      103:
>      104:      if (!p && (p = allocate_something(count, size)))
>      105:      {
>                    ... only the code in this block uses count and size
>      Nnn:      }
>
> The values not used before that point in the function, and they're
> not used outside of the loop, and they're not flagged as volatile.
> It would delay or prevent the call to my_sizing_determination(),
> and is that a constraint?

Why don't you just put them in the block where they belong?

-- 
Ian

[toc] | [prev] | [next] | [standalone]

#107431

On Wednesday, March 29, 2017 at 4:41:36 PM UTC-5, Ian Collins wrote:
> On 03/30/17 09:44 AM, Rick C. Hodgin wrote:
> > The values not used before that point in the function, and they're
> > not used outside of the loop, and they're not flagged as volatile.
> > It would delay or prevent the call to my_sizing_determination(),
> > and is that a constraint?
> 
> Why don't you just put them in the block where they belong?

If the result of a computation will be used in two or more conditionally
executed blocks, it may sometimes be cleaner to compute it unconditionally
in case anything needs it, have it get generated the first time it's
needed and arrange for its value to be reused, or have it get generated
each time it's used.  Since the relative performance of such things could be
affected by issues like pipeline scheduling the compiler may know more about
than the programmer, it can be useful for compilers to move things around to
take advantage of such knowledge.

[toc] | [prev] | [next] | [standalone]

#107426

On Wednesday, March 29, 2017 at 3:45:10 PM UTC-5, Rick C. Hodgin wrote:
> This question is for anyone, but I'm specifically curious what Supercat
> thinks...
> 
> Would it be an appropriate optimization to move the code on lines 101:
> and 102: to somewhere in the middle of the if..expression on line 104:
> 
>           // Note:  This code is in the middle of a local function
>     101:      int count = sizeof(thing) / my_sizing_determination(thing);
>     102:      int size  = count * MY_COUNT_REQUIREMENT;
>     103:
>     104:      if (!p && (p = allocate_something(count, size)))
>     105:      {
>                   ... only the code in this block uses count and size
>     Nnn:      }
> 
> The values not used before that point in the function, and they're
> not used outside of the loop, and they're not flagged as volatile.
> It would delay or prevent the call to my_sizing_determination(),
> and is that a constraint?

Any observable side effects from my_sizing_determination must occur at
the proper point in execution sequence.  The division operation, and any
aspects of my_sizing_determination which a compiler can be certain not
to have observable side effects, may be done at the compiler's leisure.
C++ has qualifiers which would specify that a call to a function will
not directly or indirectly cause any side-effects that would need to be
preserved, but C presently has no equivalent.

> What if it was merely this:
> 
>     101:      int count = sizeof(thing) / global_var_of_some_kind;
>
> ??  Would it be possible then since it's not really referencing
> anything other than a global variable?

That could be deferred if nothing could affect global_var_of_some_kind, but
a compiler should have options to prevent the deferral of such reads since
it could undermine safety checks.

> I'm wondering if it's possible to rearrange code to such an extent
> that things which exist ahead of use like that could be moved to the
> point of use, consuming processing time in the middle of an otherwise
> syntactically correct if-expression, thereby not requiring the call
> be made at all, or the values be computed at all, until the point of
> their actual use, which leaves them uninitialized in the ABI in
> certain cases.
>
> I have never considered this type of optimizing before, but it came
> up today and I was curious what other people think.

The Standard allows many such optimizations; they would be appropriate for
some kinds of implementations but not others.

[toc] | [prev] | [next] | [standalone]

#107454

On Wed, 29 Mar 2017 15:10:05 -0700 (PDT), supercat@casperkitty.com
wrote:

>On Wednesday, March 29, 2017 at 3:45:10 PM UTC-5, Rick C. Hodgin wrote:
>> This question is for anyone, but I'm specifically curious what Supercat
>> thinks...
>> 
>> Would it be an appropriate optimization to move the code on lines 101:
>> and 102: to somewhere in the middle of the if..expression on line 104:
>> 
>>           // Note:  This code is in the middle of a local function
>>     101:      int count = sizeof(thing) / my_sizing_determination(thing);
>>     102:      int size  = count * MY_COUNT_REQUIREMENT;
>>     103:
>>     104:      if (!p && (p = allocate_something(count, size)))
>>     105:      {
>>                   ... only the code in this block uses count and size
>>     Nnn:      }
>> 
>> The values not used before that point in the function, and they're
>> not used outside of the loop, and they're not flagged as volatile.
>> It would delay or prevent the call to my_sizing_determination(),
>> and is that a constraint?
>
>Any observable side effects from my_sizing_determination must occur at
>the proper point in execution sequence.  The division operation, and any
>aspects of my_sizing_determination which a compiler can be certain not
>to have observable side effects, may be done at the compiler's leisure.
>C++ has qualifiers which would specify that a call to a function will
>not directly or indirectly cause any side-effects that would need to be
>preserved, but C presently has no equivalent.


While that's true, if the compiler decides to inline the function, it
can often make that determination itself.  One of the big advantages
of inlining.

[toc] | [prev] | [next] | [standalone]

#107460

On 30/03/17 00:10, supercat@casperkitty.com wrote:

> C++ has qualifiers which would specify that a call to a function will
> not directly or indirectly cause any side-effects that would need to be
> preserved, but C presently has no equivalent.
> 

What qualifiers are these?

Some compilers have extensions to allow you to give this information,
such as gcc's __attribute__((pure)) and __attribute__((const)).  But
those are compiler extensions, and apply equally to C and C++.

C++ allows methods to be marked as "const", but that does not mean that
the function will not cause side-effects.

[toc] | [prev] | [next] | [standalone]

#107500

On Wednesday, March 29, 2017 at 6:10:23 PM UTC-4, supe...@casperkitty.com wrote:
> On Wednesday, March 29, 2017 at 3:45:10 PM UTC-5, Rick C. Hodgin wrote:
> > This question is for anyone, but I'm specifically curious what Supercat
> > thinks...
> > 
> > Would it be an appropriate optimization to move the code on lines 101:
> > and 102: to somewhere in the middle of the if..expression on line 104:
> > 
> >           // Note:  This code is in the middle of a local function
> >     101:      int count = sizeof(thing) / my_sizing_determination(thing);
> >     102:      int size  = count * MY_COUNT_REQUIREMENT;
> >     103:
> >     104:      if (!p && (p = allocate_something(count, size)))
> >     105:      {
> >                   ... only the code in this block uses count and size
> >     Nnn:      }
> > 
> > The values not used before that point in the function, and they're
> > not used outside of the loop, and they're not flagged as volatile.
> > It would delay or prevent the call to my_sizing_determination(),
> > and is that a constraint?
> 
> Any observable side effects from my_sizing_determination must occur at
> the proper point in execution sequence.  The division operation, and any
> aspects of my_sizing_determination which a compiler can be certain not
> to have observable side effects, may be done at the compiler's leisure.
> C++ has qualifiers which would specify that a call to a function will
> not directly or indirectly cause any side-effects that would need to be
> preserved, but C presently has no equivalent.
> 
> > What if it was merely this:
> > 
> >     101:      int count = sizeof(thing) / global_var_of_some_kind;
> >
> > ??  Would it be possible then since it's not really referencing
> > anything other than a global variable?
> 
> That could be deferred if nothing could affect global_var_of_some_kind, but
> a compiler should have options to prevent the deferral of such reads since
> it could undermine safety checks.
>
> > I'm wondering if it's possible to rearrange code to such an extent
> > that things which exist ahead of use like that could be moved to the
> > point of use, consuming processing time in the middle of an otherwise
> > syntactically correct if-expression, thereby not requiring the call
> > be made at all, or the values be computed at all, until the point of
> > their actual use, which leaves them uninitialized in the ABI in
> > certain cases.
> >
> > I have never considered this type of optimizing before, but it came
> > up today and I was curious what other people think.
> 
> The Standard allows many such optimizations; they would be appropriate for
> some kinds of implementations but not others.

I appreciate your response, Supercat.

I have several similar considerations I'm giving toward optimizations.
I never used to be on board with the idea of optimizations that cause
a deliberate re-ordering of things, but as my compiler design matures,
and I consider many things technically, I can see the advantage in
certain cases.

Thank you,
Rick C. Hodgin

[toc] | [prev] | [next] | [standalone]

#107505

On 30/03/17 19:11, Rick C. Hodgin wrote:
>
> I have several similar considerations I'm giving toward optimizations.
> I never used to be on board with the idea of optimizations that cause
> a deliberate re-ordering of things, but as my compiler design matures,
> and I consider many things technically, I can see the advantage in
> certain cases.
>

There can be many advantages in re-ordering for optimisation - if you 
want to get high efficiency code, there is no choice.  But there is no 
doubt that it can make it harder to follow the logic of the generated 
assembly code, and harder to use step-by-step debugging.  So there is a 
trade-off here.

[toc] | [prev] | [next] | [standalone]

#107510

On Thursday, March 30, 2017 at 12:11:18 PM UTC-5, Rick C. Hodgin wrote:
> I have several similar considerations I'm giving toward optimizations.
> I never used to be on board with the idea of optimizations that cause
> a deliberate re-ordering of things, but as my compiler design matures,
> and I consider many things technically, I can see the advantage in
> certain cases.

If it would seldom cost anything for a compiler to guarantee that a certain
action would at worst choose in unspecified fashion from a set of possible
behaviors, and such a guarantee would sometimes allow a programmer to write
much cleaner or more efficient code than would otherwise be possible, then
compilers should make such a guarantee available.  If a compiler could
sometimes benefit from being able to do something else, there should be a
means by which programmers can waive the guarantee when they don't need it.

Some people dislike the idea of cluttering up a language with "waiver"
directives, but if such directives are designed well they will actually
allow a language to be *simpler* than it otherwise would be.  Many rules
are complicated by a perceived need to balance semantic flexibility with
optimizations opportunities.  Adding directives could eliminate the need
for such balancing, at least when processing code which makes use of them.

Rather than argue about cases where programmers can't use aliasing, or
where compilers can't make aliasing assumptions, have the language provide
directives programmers can use when aliasing is needed but the Standard
would not otherwise require that compilers recognize it, as well as some
which would invite compilers to assume aliasing won't occur even if the
Standard would otherwise require that they allow for the possibility.  A
directive forcing a compiler to recognize aliasing in certain cases may
mean that it can't generate code which is as "fast" as the *non-working*
code it could generate without such directives, but it could still generate
code which was as good or better than it could generate if a programmer had
to work around the lack of such a directive.

[toc] | [prev] | [next] | [standalone]

#107512

On Thursday, March 30, 2017 at 7:47:07 PM UTC+1, supe...@casperkitty.com wrote:
> On Thursday, March 30, 2017 at 12:11:18 PM UTC-5, Rick C. Hodgin wrote:
> > I have several similar considerations I'm giving toward optimizations.
> > I never used to be on board with the idea of optimizations that cause
> > a deliberate re-ordering of things, but as my compiler design matures,
> > and I consider many things technically, I can see the advantage in
> > certain cases.
> 
> Some people dislike the idea of cluttering up a language with "waiver"
> directives, but if such directives are designed well they will actually
> allow a language to be *simpler* than it otherwise would be.  Many rules
> are complicated by a perceived need to balance semantic flexibility with
> optimizations opportunities.  Adding directives could eliminate the need
> for such balancing, at least when processing code which makes use of them.
> 
Since C historically has allowed aliasing, "noalias" rather than "alias"
has been added to the language.

But a common pattern is

void foo(type *result, const type *a, const type *b);

It's not a problem if a and b alias each other. However you often want the
equivalent of "+=", which means passing a as the result. Since aliasing
is allowed, the function writer normally writes to a temporary then 
flushes out at the last moment (I also usually permit null and check
for it). But the burden is placed on the programmer, whilst really
the compiler should be enforcing or at least warning is writes to "result"
are interleaved with reads from  "a" or "b".

[toc] | [prev] | [next] | [standalone]

#107514

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
[...]
> Since C historically has allowed aliasing, "noalias" rather than "alias"
> has been added to the language.

"noalias" was proposed, but was never added to the language.  Are you
thinking of "restrict"?

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#107517

On Thursday, March 30, 2017 at 2:04:11 PM UTC-5, Malcolm McLean wrote:
> On Thursday, March 30, 2017 at 7:47:07 PM UTC+1, supe...@casperkitty.com wrote:
> > Some people dislike the idea of cluttering up a language with "waiver"
> > directives, but if such directives are designed well they will actually
> > allow a language to be *simpler* than it otherwise would be.  Many rules
> > are complicated by a perceived need to balance semantic flexibility with
> > optimizations opportunities.  Adding directives could eliminate the need
> > for such balancing, at least when processing code which makes use of them.
> > 
> Since C historically has allowed aliasing, "noalias" rather than "alias"
> has been added to the language.

C implementations that were designed to be suitable for systems programming
have allowed aliasing, though some (especially on unusual hardware) may have
imposed special requirements.  "Modern" compilers, however, can't even
recognize aliasing in cases like:

    struct s1 {int x;};
    struct s2 {int x;};
    union u { struct s1 s1; struct s2 s2;};

    int read_s1_x(struct s1 *p) { return p->x; }
    int read_s2_x(struct s2 *p) { return p->x; }
    int write_s1_x(struct s1 *p, int value) { p->x = value; }
    int write_s2_x(struct s2 *p, int value) { p->x = value; }

    int test(union u *u1, union u *u2)
    {
      write_s2_x(&u2->s2, 0);
      if (!read_s1_x(&u1->s1))
        write_s2_x(&u2->s2, 1);
      return read_s1_x(&u1->s1);
    }

I'm not sure what the authors of gcc think the "address-of" operator is
supposed to yield when applied to a union member, if taking the address
of a member doesn't "activate" it sufficiently to allow reading a member
of a Common Initial Sequence.

[toc] | [prev] | [next] | [standalone]

#107519

On 2017-03-30, supercat@casperkitty.com <supercat@casperkitty.com> wrote:
>     int write_s1_x(struct s1 *p, int value) { p->x = value; }

Did you mean

    void write_s1_x(struct s1 *p, int value) { p->x = value; }

?

[toc] | [prev] | [next] | [standalone]

#107520

On Thursday, March 30, 2017 at 3:42:11 PM UTC-5, Ike Naar wrote:
> On 2017-03-30, supercat wrote:
> >     int write_s1_x(struct s1 *p, int value) { p->x = value; }
> 
> Did you mean
> 
>     void write_s1_x(struct s1 *p, int value) { p->x = value; }
> 
> ?

I did, though I believe the behavior of the former would be defined in cases
where the caller ignores the return value (as is the case here).

[toc] | [prev] | [next] | [standalone]

#107461

On 29/03/17 22:44, Rick C. Hodgin wrote:
> This question is for anyone, but I'm specifically curious what Supercat
> thinks...
> 
> Would it be an appropriate optimization to move the code on lines 101:
> and 102: to somewhere in the middle of the if..expression on line 104:
> 
>           // Note:  This code is in the middle of a local function
>     101:      int count = sizeof(thing) / my_sizing_determination(thing);
>     102:      int size  = count * MY_COUNT_REQUIREMENT;
>     103:
>     104:      if (!p && (p = allocate_something(count, size)))
>     105:      {
>                   ... only the code in this block uses count and size
>     Nnn:      }
> 
> The values not used before that point in the function, and they're
> not used outside of the loop, and they're not flagged as volatile.
> It would delay or prevent the call to my_sizing_determination(),
> and is that a constraint?
> 

In this particular case, line 104 uses both "count" and "size", so they
need to be evaluated before that.

But in general, all the compiler has to preserve is the ordering of
"observable behaviour" - file I/O, program start/stop, and volatile
accesses.  Everything else can be moved around, repeated, eliminated,
split up, combined, and otherwise massaged as long as all the observable
behaviour is as it should be.  Function calls can also be moved around
if the compiler knows about the observable behaviour in the call - but
if it does not know the definition of the function, then it must assume
the worst.

So a call to an external function "foo" is assumed to access volatiles
and any globally visible data.  But if "foo" is defined in the same
translation unit, or the compiler has other information about it from
somewhere (for example, the compiler knows how the standard library
functions work), then it might know that it is safe to move it around.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web