Velocity Reviews > function call optimization question

function call optimization question

Szabolcs Nagy
Guest
Posts: n/a

 09-12-2007
in the code below i thought the function call in g() could be easily
optimized out so that g() becomes the same as h() (which becomes
{return 0;})

executing 'gcc -O3 -S' i found that gcc does not do this

now i'm wondering: is there something in the standard (eg c99) that
prevents this optimization (theoretically)

#include <stdio.h>
#include <stdlib.h>

static inline int c(int a, int b) {
return a == b;
}

static int f(int a, int b, int(*c)(int, int)) {
return c(a, b) - c(b, a);
}

int g(int a, int b) {
return f(a, b, c);
}

int h(int a, int b) {
return c(a, b) - c(b, a);
}

int main(int argc, char *argv[]) {
int a, b;

if (argc < 3)
return printf("usage: %s a b\n", argv[0]);
a = atoi(argv[1]);
b = atoi(argv[2]);
printf("f: %d\n", f(a, b, c));
printf("g: %d\n", g(a, b));
printf("h: %d\n", h(a, b));
return 0;
}

Army1987
Guest
Posts: n/a

 09-12-2007
On Wed, 12 Sep 2007 03:01:26 -0700, Szabolcs Nagy wrote:

> in the code below i thought the function call in g() could be easily
> optimized out so that g() becomes the same as h() (which becomes
> {return 0;})
>
> executing 'gcc -O3 -S' i found that gcc does not do this
>
> now i'm wondering: is there something in the standard (eg c99) that
> prevents this optimization (theoretically)

The standard only requires that files and volatile objects are
written/read in the right order. But I won't expect a program to
compute the 100008th prime number to generate the same machine
code as
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
return (fwrite("1299827\n", 1, 8, stdout) < * EXIT_FAILURE;
}

IOW, while you shouldn't do micro-optimizations yourself, you
shouldn't write silly code hoping that the compiler will make it
decent.
--
Army1987 (Replace "NOSPAM" with "email")
If you're sending e-mail from a Windows machine, turn off Microsoft's
stupid “Smart Quotes” feature. This is so you'll avoid sprinkling garbage
characters through your mail. -- Eric S. Raymond and Rick Moen

Michal Nazarewicz
Guest
Posts: n/a

 09-12-2007
Szabolcs Nagy <(E-Mail Removed)> writes:

> in the code below i thought the function call in g() could be easily
> optimized out so that g() becomes the same as h() (which becomes
> {return 0;})
>
> executing 'gcc -O3 -S' i found that gcc does not do this

Well... You can go complain to GCC developers if you like.

> now i'm wondering: is there something in the standard (eg c99) that
> prevents this optimization (theoretically)

No. Standard doesn't prevents optimisation.

--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86*tlen.pl>---<jid:mina86*chrome.pl>--ooO--(_)--Ooo--

Szabolcs Nagy
Guest
Posts: n/a

 09-12-2007

Michal Nazarewicz wrote:
>
> No. Standard doesn't prevents optimisation.
>

actually what i was thinking about is the situations like sorting int
arrays

static inline int intcmp(int *a, int *b) {
return *a < *b ? -1: *a > *b;
}

void intqsort(int *arr, size_t n) {
qsort(arr, n, sizeof(int), intcmp);
}

imho this is not a silly thing to optimize out, since many algorithms
can be done in a (type) generic way with a couple of function
arguments and most of these algorithms are performance critical (eg
when we cannot allow an additional function call for each int
comparison)

other possible examples:
int find_if(int *arr, size_t n, int (*pred)(int));
int hash_get(const hashtable_t *ht, const key_t *key, int (*hash)
(key_t *), int (*isempty)(item_t *), int (*isdeleted)(item_t *));
....

Richard Tobin
Guest
Posts: n/a

 09-12-2007
In article <(E-Mail Removed) .com>,
Szabolcs Nagy <(E-Mail Removed)> wrote:

>actually what i was thinking about is the situations like sorting int
>arrays
>
>static inline int intcmp(int *a, int *b) {
> return *a < *b ? -1: *a > *b;
>}
>
>void intqsort(int *arr, size_t n) {
> qsort(arr, n, sizeof(int), intcmp);

This is unlikely to be useful, because

(a) intcmp is an argument to qsort(), and will be different for different
calls;
(b) even if it wasn't an argument, to inline the calls to intcmp()
its source would have to be available when qsort was compiled,
and typically qsort() is in a pre-compiled library.

One possibility would be for qsort itself to be inline, with its definition

If you really need this efficiency, you could take one of the many free
implementations of qsort() and produce a specialised version yourself.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

Szabolcs Nagy
Guest
Posts: n/a

 09-12-2007

Richard Tobin wrote:
> This is unlikely to be useful, because
>
> (a) intcmp is an argument to qsort(), and will be different for different
> calls;
> (b) even if it wasn't an argument, to inline the calls to intcmp()
> its source would have to be available when qsort was compiled,
> and typically qsort() is in a pre-compiled library.

true
you are right

well i'm writing an algorithm lib for my own amusement and i thought
it would make things easy if i could write

static void sort_internal(int *arr, size_t len, int (*less)(int, int))
{..}
static inline intless(int a, int b) {return a < b;}

void sort_f(int *arr, int len, int (*less)(int, int)) {
return sort_internal(arr, len, less);
}

void sort(int *arr, int len) {
return sort_internal(arr, len, intless);
}

so i don't need to write down the algorithm 2 times for sort() and
sort_f().
also type generic code can be written in this way so i can make my own
c++ stl like thing.

Malcolm McLean
Guest
Posts: n/a

 09-12-2007

"Army1987" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
> On Wed, 12 Sep 2007 03:01:26 -0700, Szabolcs Nagy wrote:
>
> The standard only requires that files and volatile objects are
> written/read in the right order. But I won't expect a program to
> compute the 100008th prime number to generate the same machine
> code as
> #include <stdio.h>
> #include <stdlib.h>
> int main(void)
> {
> return (fwrite("1299827\n", 1, 8, stdout) < * EXIT_FAILURE;
> }
>

I'd expect a Fortran 77 compiler to do this.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm