pure functions

[junky_fellow]

I have read certain articles that encourage to use/write
pure functions (if possible) as they are better suited for
optimization.

I got one example that expalins how the code can be optimised.
For eg:

__pure int square(int x)
{
return x * x;
}

int f(int n)
{
return square(n) + square(n);
}

The function f() can be optimised to call pure function square() once.

Is there any other way pure functions help in optimization ?
Is the pure function itself produce much optimized code as compared
to non pure functions ?

 

[Keith Thompson]

I have read certain articles that encourage to use/write
pure functions (if possible) as they are better suited for
optimization.

I got one example that expalins how the code can be optimised.
For eg:

__pure int square(int x)
{
return x * x;
}

int f(int n)
{
return square(n) + square(n);
}

The function f() can be optimised to call pure function square() once.

Is there any other way pure functions help in optimization ?
Is the pure function itself produce much optimized code as compared
to non pure functions ?

You do know there's no "__pure" keyword in standard C (or any other
mechanism for specifying that a function is "pure"), don't you?

 

[Malcolm]

I have read certain articles that encourage to use/write
pure functions (if possible) as they are better suited for
optimization.

pure functions are a good idea, but efficiency considerations wouldn't be
high on my list of reasons why.

 

[pete]

pure functions are a good idea,
but efficiency considerations wouldn't be
high on my list of reasons why.

Pure functions aren't part of C.
This off topic thread has gone on way too long.

 

[S.Tobias]

I hear some people even say that efficiency considerations are
off-topic altogether in c.l.c. OTOH they are also one of the most
important factors for acceptance of new features into the C language.
I don't understand why many people here escape speed questions.
Is "ignore `restrict'" the only on-topic answer here?
I know that C does not make any specific guarantees in this area,
but some C constructs are designed to be better (or not worse)
than others. Wouldn't discussing opportunities for optimization
(or which constructs to avoid) be on-topic in c.l.c.?

Pure functions aren't part of C.

True, but such feature could one day become part of C (IMHO it is
a good candidate). I don't mean to change the subject of the group,
but couldn't preliminary discussions of new features in context of
present language rules start here, before they're brought to c.s.c
for a more serious treatment? After all, OP did not ask
about a specific implementation, but asked for possibilities
of optimization of pure functions in general (presumably within
the current C framework).

This off topic thread has gone on way too long.

Technically this is probably off-topic, true. But wouldn't
a discussion of the `restrict' keyword, as implemented on my
favourite free C compiler, be off-topic on 30 Nov 1999, and
on-topic the day after?

 

[CBFalconer]

.... snip ...

I hear some people even say that efficiency considerations are
off-topic altogether in c.l.c. OTOH they are also one of the most
important factors for acceptance of new features into the C language.
I don't understand why many people here escape speed questions.
Is "ignore `restrict'" the only on-topic answer here?
I know that C does not make any specific guarantees in this area,
but some C constructs are designed to be better (or not worse)
than others. Wouldn't discussing opportunities for optimization
(or which constructs to avoid) be on-topic in c.l.c.?

You have a point, especially when it comes to embedded or other
small systems. But by and large the compiler is usually better
able to optimize than you are, as long as the coding intent is
clear and accurate. 99.95% of the optimization questions just
shouldn't be asked at all. 50% of the remaining ones are answered
by moving a strlen call out of the loop, because you know the
returned value won't change and the compiler doesn't.

 

[Keith Thompson]

Pure functions aren't part of C.
This off topic thread has gone on way too long.

There's no feature in C that can be used to mark a function as "pure",
but it's certainly possible to write pure functions in C. If an
optimizing compiler can determine that a given function is "pure", it
can replace some calls with cached values, or eliminate calls whose
results aren't used, an optimization permitted by the "as-if" rule.

Discussion of pure functions within the context of standard C, and the
opportunities they can provide for potential optimizations, is
topical. Discussion of implementation-specific features to support
pure functions are off-topic (<OT>I'll take the liberty of mentioning
gcc's __attribute__ ((pure)), but I won't go into detail</OT>).
Advocacy of such features for future standards is probably more
topical in comp.std.c, but I see no real problem with bringing it up
here.

 

[Malcolm]

Discussion of pure functions within the context of standard C, and the
opportunities they can provide for potential optimizations, is
topical. Discussion of implementation-specific features to support
pure functions are off-topic (<OT>I'll take the liberty of mentioning
gcc's __attribute__ ((pure)), but I won't go into detail</OT>).
Advocacy of such features for future standards is probably more
topical in comp.std.c, but I see no real problem with bringing it up
here.

Discussion about how to use C effectively, so that we can enjoy the benefits
of pure functions despite the fact that the language provides no way to
enforce lack of side-effects, is also topical.
For instance you could have a convention that pure functions always take
single-letter parameters, non-pure functions always take at least one
parameter with more than one letter.

 

[Chris Croughton]

For instance you could have a convention that pure functions always take
single-letter parameters, non-pure functions always take at least one
parameter with more than one letter.

Or no parameters at all (a function which has no parameters can't be
'pure' unless it is trivial and returns a constant).

Chris C

 

[Anonymous 7843]

Or no parameters at all (a function which has no parameters can't be
'pure' unless it is trivial and returns a constant).

There are also "short term" pure functions like time() and ftell()
which normally cannot be treated as pure by the compiler, but which
are nonetheless good candidates for manually hoisting out of tight loops
in which nothing in the loop resets the date or writes to the file.

 

[Walter Roberson]

There are also "short term" pure functions like time() and ftell()
which normally cannot be treated as pure by the compiler, but which
are nonetheless good candidates for manually hoisting out of tight loops
in which nothing in the loop resets the date or writes to the file.

That's an interesting idea; I'm not sure that the examples are
the best ones, though.

time() deals in terms of seconds, not in terms of "dates"; any
loop that operates for long enough is going to tick over to a new
second. One could imagine an algorithm that sleep() until just before
an action was to be taken, and then went into a loop polling time()
until the crossover. (The algorithm should, of course, check that
the time() is returning a valid value, for the cases where there is
no real-time clock.)


ftell()... one should look at signals for this one. One cannot
do much within a pure C signal handler routine, but C does not
prohibit implementation extensions such as POSIX.1 . In POSIX.1,
two of the routines that are considered "signal safe" (allowed to
execute them inside a signal handler) are close() and write().
Both of those operate on file descriptors, not on FILE*, but
if I'm interpreting correctly, close() on the file descriptor
"underlying" a FILE* has an effect on the FILE*'s state.

The POSIX.1 1990 language about the connection between file descriptors
and FILE* is not the clearest, so I'm not certain of the exact POSIX.1
proper behaviour in the case of close() and write() on the
underlying descriptors... plausibly the FILE* level wouldn't properly
catch on until the next fseek() [or until sufficient data was
read to exhaust the in-memory buffer, thus calling upon the underlying
read() routine that would notice the end-of-file.] We'd need someone
well versed in POSIX.1 to detail this situation for us.

 

[Keith Thompson]

That's an interesting idea; I'm not sure that the examples are
the best ones, though.

time() deals in terms of seconds, not in terms of "dates"; any
loop that operates for long enough is going to tick over to a new
second. One could imagine an algorithm that sleep() until just before
an action was to be taken, and then went into a loop polling time()
until the crossover. (The algorithm should, of course, check that
the time() is returning a valid value, for the cases where there is
no real-time clock.)

time() deals in terms of time_t, an arithmetic type capable of
representing times. The standard doesn't specify the resolution of
time_t or of the time() function; 1 second is common, but not
required.

An aggresively optimizing compiler presumably can know what the
resolution is, but I'm still skeptical that optimizing away a call to
time() would be worth the effort.

 

[Lawrence Kirby]

There are also "short term" pure functions like time() and ftell()
which normally cannot be treated as pure by the compiler, but which
are nonetheless good candidates for manually hoisting out of tight loops
in which nothing in the loop resets the date or writes to the file.

However taking time() out of the loop can produce different results. It
isn't a matter of assuming that the results will be the same, it is
whether the potentially different results can still be considered correct
in context. They may even be preferable.

On some platforms a file position can be altered by something other than
the executing program.

Lawrence

 

[Anonymous 7843]

However taking time() out of the loop can produce different results. It
isn't a matter of assuming that the results will be the same, it is
whether the potentially different results can still be considered correct
in context. They may even be preferable.

I should have used different words: by "manually" I meant "as
performed by a human not by the compiler". "hoist" in this
context however is usually meant as an optimization performed
by the compiler, so I apologize for the confusion.

Obviously, if the compiler wanted to do such a thing it would have to
be quite careful about the conditions, or even be specifically
told (e.g. gcc -O9) that it's okay to make aggressive
assumptions about short-term functiony pure-ness.

On some platforms a file position can be altered by something other than
the executing program.

(ITYM file length, but point taken.)

So any program that uses time() or ftell() is already
non-deterministic. Extra out-of-dateness from my proposed
trick would only make the problem worse, but would not
make a deterministic program non-deterministic.