[Freeciv-Dev] Re: Map coordinate cleanups.

[Vasco Alexandre Da Silva Costa <vasc@xxxxxxxxxxxxxx>]

On Fri, 17 Aug 2001, Kevin Brown wrote:
> Vasco Alexandre Da Silva Costa <vasc@xxxxxxxxxxxxxx> wrote:

> > Function calls don't have a habbit of getting much faster.
> 
> I don't see how this would be the case, because it implies that the
> operation of pushing arguments and current PC onto the stack and
> jumping to the function location, then executing the function code,
> then returning, doesn't get faster as CPUs and memory get faster.

Its more than pushing arguments and PC onto the stack, you must save all
the registers you are using too and the machine status word. Ands jumps
are getting to be worse and worse. When you do many long jumps you are
trashing the code cache and function calls usually are long jumps.

This is the reason jumps are bad:
Regardless of what you may think main memory speed hasn't kept pace with
cpu speed in the last decades. The gap between CPU and memory speed keeps
increasing. There have been some sucessfull efforts in recent years in
memory bandwith but latency is still poor. And besides it still isn't
keeping pace with CPU speed. The CPU designers offset this with ever
increasing cache sizes. It helps but it isn't perfect.

> Frankly, I don't believe it.  Access to the registers gets faster over
> time.  Access to the caches get faster over time.  Access to main
> memory gets faster over time.  The CPU clocks get faster over time
> (which affects a lot of the other things).

Contrary to what you think access to the L1 caches doesn't improve
compared to CPU speed in fact, recent L1 caches take more than the 1
clock cycle they used to in order to get an access.

> There is NOTHING in a computer system that has remained the same speed
> over the past 5 years aside from mundane things like keyboard
> controllers.  EVERYTHING that counts here has gotten faster.

Sure. I didn't say that. What i say is that the rest of the systems keeps
drifting more and more regarding the CPU in terms of speed. You remember
the time when system buses used to be as fast as CPUs? Well now they
aren't, and I/O keeps getting slower. As fast as a CPU may be it is
limited by core memory and peripheral speed.

> So what possible reason do you have for believing that function calls
> haven't gotten faster over time???

They have gotten faster. But they don't get as fast as regular ops do. And
this will be noticeable more and more as time passes. Unless someone
invents an über-memory. But i doubt it.

> > I suggest you delve a bit more in this problem. 
> 
> Okay, you asked for it!  :-)
> 
> I can PROVE that function calls have gotten faster.  Take the
> following code:
> 
> #include <stdio.h>
> #include <stdlib.h>
> 
> void func(void)
> {
> }
> 
> int main (int argc, char *argv[]) {
>         int i, n;
> 
>         n = 1000000;
>         if (argc > 1) 
>                 n = atoi(argv[1]);
>         for (i = 0 ; i < n ; ++i) {
> #ifdef CALLFUNC
>                 func();
> #endif
>         }
> }

> Now, let's establish the baseline time for execution of the code
> without calling func():
> 
> [kevin@frobozz kevin]$ gcc -O -o /tmp/foo /tmp/foo.c
> [kevin@frobozz kevin]$ time /tmp/foo 500000000
> 5.03user 0.01system 0:05.03elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (55major+6minor)pagefaults 0swaps
> 
> This was on my PPro 200 box.  Copy foo over to my Celeron 466 box and
> run it:
> 
> [kevin@dimwit /tmp]$ scp -p frobozz:/tmp/foo .
> foo                       |          3 KB |   3.8 kB/s | ETA: 00:00:00 | 100%
> 
> [kevin@dimwit /tmp]$ time ./foo 500000000
> 2.72user 0.01system 0:02.77elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (67major+8minor)pagefaults 0swaps

> Now put in the function call:
> 
> [kevin@frobozz kevin]$ gcc -DCALLFUNC -O -o /tmp/foo /tmp/foo.c
> [kevin@frobozz kevin]$ time /tmp/foo 500000000
> 18.42user 0.01system 0:18.74elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (55major+6minor)pagefaults 0swaps
> 
> and run it on the Celeron 466:
> 
> [kevin@dimwit /tmp]$ scp -p frobozz:/tmp/foo .
> foo                       |          3 KB |   3.8 kB/s | ETA: 00:00:00 | 100%
> 
> [kevin@dimwit /tmp]$ time ./foo 500000000
> 9.81user 0.02system 0:10.10elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (67major+8minor)pagefaults 0swaps
> 
> 
> So for 500,000,000 iterations on the PPro 200, the function call
> itself takes 18.42 - 5.03 seconds, or 13.39 seconds.  On the Celeron,
> the function call itself takes 9.81 - 2.72 seconds, or 7.09 seconds.
> 
> The Celeron is twice as fast.  Looks to *me* like function calls are
> subject to Moore's Law...

Bah. That program fits in the L1 cache. Freeciv doesn't even fit in the L2
cache. That proves nothing. :)

> > Besides, compilers can't optimize functions as well as inlined code.
> 
> Is this true of inlined functions?  I have suspicions that it is.  I'm
> not sure how to devise a testcase for this...

Inlined functions aren't part of the C89 spec. Sure they are part of the
C99 spec, but how many 100% C99 compliant compilers do you know? (Hint:
gcc isn't even one of them). Sure most C compilers have inlined functions
in some form. But it isn't standard so they often use different keywords
for it and so on. And remember the inline keyword is a hint. The compiler
may ignore it.

> The real question, of course, is just how much of a difference does it
> really make?  It's worth putting something into a macro instead of a
> function if it gives you an order of magnitude speedup for a
> significant (30% or so) part of the execution of the program, but
> anything less than that isn't even worth the hassle unless the use of
> a macro instead of a function gives you other benefits (readability,
> ease of comprehension, flexibility, etc.).  And keep in mind that the
> macro has to be that much faster than an *inline* function, which
> means that the optimizer has to make that much of a difference.  I'll
> concede that this is possible, but I have trouble imagining that it
> would happen often enough to make use of macros the preferred method
> of improving performance.

A one line function doesn't have much a compiler can optimize. If the code
is inlined the compiler may do optimizations by using neighbouring code
values and so on to speed things up. And you have no function call
overhead. You could say this increases code size. I say that all the
context saving and restoring and function call probably have more
instruction than the function itself.

IMHO making one line functions that are used over and over again isn't a
good idea. Unless you really *must* use a function.

---
Vasco Alexandre da Silva Costa @ Instituto Superior Tecnico, Lisboa